1.海量日志数据，提取出现次数最多的一条(IP)
注意,这里说的是 IP,那么IP 是有大小范围的,是 32 位的
首先把海量数据放在一个文件中,接下来对已每个 IP 都进行mod(1000),那么这样的话就会产生 1000 个小文件,将海量数据进行了分散,针对这 1000 个文件中的每个小文件,使用 hashMap 进行统计,其中将 IP 作为 key,该条 IP 出现的次数作为 value。这样统计出每个小文件中出现最多的 IP,这样就取到了 1000 个 IP,然后从这 1000 个 IP 中找到出现次数最大的一个。
2.海量字符串(基于搜索热度),提取出现搜索词最多的十条记录
注意,这些海量搜索词中很多是重复的,所以字符串的种类其实并不多,可能只有原来的一半的样子,这时我们使用一个 hashMap 来保存每个字符串的引用和出现次数,内存是可以放的下的,所求是出现次数最多的,然后使用堆排序中的大根堆,找到最大的 10 个。
3.一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词
这个题目就没有前一个题目那么幸运了,也许没有很多重复的单词，我们无法将全部内容都读取到内存中,所以需要分成小文件;
1G 大小，每个单词 16 字节，那么一共有 1G/16byte = 2^26个单词
顺序读取该大文件，对于每个词 x，取 hash(x)%5000，然后按照该值存到 5000 个小文件（记为 x0,x1,…x4999）中(平均每个文件大约 20w 个单词)。这样每个文件大概是 200k 左右(如果单词比较随机的话)。
对于每个文件,使用 HashMap 统计每个文件中出现的词以及相应的频率,然后取出每个文件中出现频率最高的 100 个词(用最大堆排好序),这样就得到了 5000*100 个词,放到一个数组中,进行归并排序即可;
4.有 10 个文件，每个文件 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。
顺序读取 10 个文件，按照 hash(query)%10 的结果将 query 写入到另外 10 个文件（记为）中。这样新生成的文件每个的大小大约也 1G（假设 hash 函数是随机的）。
分好这 10 个文件之后,就需要进行着 10 个文件,进行快速/堆/归并排序按照出现次数进行排序,然后这 10 个文件时排好序的,在对这 10 个文件进行归并排序;
找一台内存在 2G 左右的机器，依次对用 hashMap(query,queryCount)来统计每个 query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 queryCout 输出到文件中。这样得到了 10 个排好序的文件。
5.给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？
遍历文件 a，对每个 url 求取 hash(url)%1000，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 a0,a1,…,a999）中。这样每个小文件的大约为 300M。
遍历文件 b，对每个 url 求取 hash(url)%1000，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 b0,b1,…,b999）中。这样每个小文件的大约为 300M。
那么接下来针对每一个 ax VS bx 文件（这时可以保证每个如果是相同的 url，都在相同的 ax 或 bx 中）,可以把其中一个小文件的 url 存储到 hashSet 中。然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hashSet 中，如果是，那么就是共同的 url，存到文件里面就可以了。
6.在 2.5 亿个整数中找出不重复的整数的个数
既然是整数,那么整数最多也就是 2^32 个,定义一个 2bit 的标志,00 没有出现过,01,出现一次;10,出现多次;11,无意义;那么整个 2^322bit 是完全可以在内存中放得下的
接下来遍历一次 2.5 亿个数,然后映射到 2bit 中,然后再遍历一次 2^322bit 的内存空间,只找 01 标志位的;
7.给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？
同 6 一样,将这 40 亿个数映射到一个 1bit 的内存中,如果是 0 则没出现过,如果是 1 则出现过;
方案 2:将这 40 亿个数按照每一位的 0 或 1 来分开：
2^32 为 40 亿多，所以给定一个数可能在，也可能不在其中；这里我们把 40 亿个数中的每一个用 32 位的二进制来表示假设这 40 亿个数开始放在一个文件中。
然后将这 40 亿个数分成两类:
1.最高位为 0
2.最高位为 1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20 亿，而另一个>=20 亿（这相当于折半了）；
与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类:
1.次最高位为 0
2.次最高位为 1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10 亿，而另一个>=10 亿（这相当于折半了）；
与要查找的数的次最高位比较并接着进入相应的文件再查找。
…….
以此类推，就可以找到了,而且时间复杂度为 O(logn)。
8.海量数据中找出重复次数最多的一个
先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。
9.海量数据中找出重复次数最多的 N 个
首先还是用 hash 进行分类,假设分成 1k 个组,对这 1k 个组中,分别进行堆排序,找出前 N 个,现在就有 1K*N 个数据,那么接下来就是对这 1K 个组进行归并或者堆排序。
10.一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析。
方案 1：这题是考虑时间效率。用trie 树统计每个词出现的次数，时间复杂度是O(n*le)（le 表示单词的平均长度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与 O(n*lg10)中较大的哪一个。
方案 2：先将这 1w 个单词进行 hash（eg：mod 10），分成 1000 个组，每组创建最大堆，维持 10 个元素，然后在对着 1000 个组中的 top10 进行归并，找到前 10 个即停止。
11.100w 个数中找出最大的 100 个数。
在前面的题中，我们已经提到了，用一个含 100 个元素的最大堆完成。复杂度为O(100w*lg100)。或者先分组（组内用堆排序），然后归并，找到前 100 即停止。