说明

1024 * 1024 * 1024 = 1073741824，1G约为10亿字节. 大体思路都是先按照哈希拆成很多个小文件，然后分别处理每个小文件，最后合并每个小文件的处理结果得到最终结果。

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。

分析 首先计算一下每个文件的大小：50亿*64/10亿字节= 300G，每个文件约为300G

解法 我们可以先用hash的方法将大文件拆成很多个小文件，然后针对每个小文件做操作。 一个文件300G，我们把一个文件拆成1000份，然后针对每一份计算共同的URL，然后取集合就可以。

步骤一：分别遍历A，B文件，将每条url的哈希值%1000，得到1000个小文件，每个文件大小300MB。 步骤二：使用HashSet遍历A的小文件的url，然后遍历对应的B的小文件，同时判断这个url是否存在于HashSet，如果存在那就是共同的，否则跳过。小文件遍历结束之后将HashSet的结果加到一个结果文件中，然后清空HashSet，并遍历每一组小文件。 步骤三：返回对这1000个小文件遍历的结果的集合。

有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序

步骤一：首先对这十个文件中的每个query进行hash然后%10，得到另外十个文件，新的文件的query都在一个文件中。 步骤二：针对新十个文件中的每个文件都使用HashMap遍历，统计每个query出现的次数。并生成对应的结果文件，结果文件的key为query，value为出现的次数。并对结果文件进行归并排序，单个文件中的所有query按照value递减排序。 步骤三：针对十个结果文件的query，每次取十个文件中出现次数最多的query，将十个以排序的结果文件整理成一个最终返回的文件。

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词

分析 首先我们将1G的文件拆成很多个小文件，我要保证相同的词都在一个小文件中，并且每个小文件的大小小于1MB。因为我们后面需要遍历每个小文件。

解法 步骤一：遍历这个1G的文件，将每个词哈希然后对2048取余，得到2048个文件，每个文件大小约为0.5MB。如果其中有的文件超过了1MB的大小，我们再讲这个文件拆成若干个小于1MB的文件。 步骤二：依次遍历2048个文件，使用HashMap统计每个词出现的次数，key为词，value为出现的次数。遍历完一个小文件之后将HashMap的值放到一个大小为100的最小堆中，然后HashMap清空，重新遍历下一个小文件，直到所有文件都被遍历。 步骤三：返回最小堆。

海量日志数据，提取出某日访问百度次数最多的那个IP。

分析 IP地址有2的32次方也就是4G种取值情况，

解法 步骤一：遍历所有日志数据，将ip的哈希对2048取余，将日志数据分配到2048个小文件中。 步骤二：使用HashMap遍历小文件，统计这个小文件中每个ip的出现次数，遍历的过程中使用maxIp和maxTimes纪录出现次数最多的ip和出现的次数。maxIp和maxTimes贯穿所有遍历小文件的操作，重复这个操作2048次。 步骤三：返回maxIp

2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。

解释 Java中一个整数是4字节，2.5亿个整数那就是10亿字节，约为1GB。

位图法 整数范围为2的32次方，约为4亿，每个数分配两比特位，一个字节可以存储四个数，那么一亿个字节可以统计4亿个整数，10亿字节约为1GB，1亿字节约为100MB。 遍历所有整数，出现过一次的数，对应的位设置为01，出现过多次的数设置为10，00 和 11 无意义。遍历之后，统计所有位为01的数。

分治法 2.5亿个约为1GB，我们可以分成1024个文件来处理，每个文件大约就是1MB。 步骤一：遍历所有整数，将数字对1024取余后，放到对应的文件中。 步骤二：使用HashMap统计每个数字出现的次数，遍历HashMap，纪录出现次数为1的数字放到结果文件中。清除HashMap，并针对每个小文件都做这种操作。

海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

解释 我们需要考虑一个数据在每一台机器上都处于第11，不过总的来说处于TOP10的情况。为了解决这种情况，我们需要先将100台机器的数据进行重新Hash。

方法 步骤一：遍历所有的数据，获取数据哈希值并对100取余，将这个数据放到对应的机器上，进行完这个操作之后，相同的数据都在一个机器上了。 步骤二：将单台机器的数据按照数据的哈希值取余，分成很多个小文件，每个小文件先用HashMap计算每个数据出现的次数，当前小文件遍历结束之后，将HashMap的所有元素都放到一个机器维度的大小为10的小顶堆中，每个机器都重复上述操作。 步骤三：然后使用一台机器统计100台机器的所有TOP10.

怎么在海量数据中找出重复次数最多的一个

方法 步骤一：将海量数据通过哈希值和取余的操作拆分到很多个小文件，保证相同的数据都在一个小文件中。 步骤二：针对每个小文件，使用HashMap统计每个元素出现的次数，同时使用maxValue，maxTime，纪录出现次数最多的数据和对应的次数。maxValue 和 maxTime贯穿所有文件的遍历过程。 步骤三：返回maxValue。

1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

方法 步骤一：遍历所有字符串，将字符串的哈希值对1000取余，分配到1000个小文件中。 步骤二：使用HashMap遍历小文件，纪录每个字符串出现的次数。小文件遍历结束之后，遍历HashMap将出现次数为1的放到结果文件中。针对1000个小文件，重复这个操作。 步骤三：返回结果文件

一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。

方法 步骤一：遍历每一行，使用前缀树纪录每个字符出现的次数，遍历每个词的时候如果这个词出现的次数大于最小堆的堆顶元素，那就移除堆顶元素，并将当前词加入堆，并整理堆。 步骤二：返回最小堆。时间复杂度为O(n*le)+O(n*lg10)

寻找热门查询

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录， 这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多， 也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。 （1）请描述你解决这个问题的思路； （2）请给出主要的处理流程，算法，以及算法的复杂度。

思路 3百万个字符串，如果每个字符串都是最长的也就是255字节，大概7亿字节，也大约是0.7GB。 那么我们会使用一个HashMap统计所有纪录的出现次数，在统计的时候使用一个大小为10的最小堆统计TOP10，遍历的时候如果发现字符串的次数大于最小堆的堆顶且不存在最小堆中，那就移除堆顶，将当前元素加入堆顶，然后整理。时间复杂度是 O(N) + O(n*logk)

一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。 如何找到N^2个数的中数(median)？

方法一 步骤一：如果所有数都是整数，将整数按照值拆成N份，分别分配到对应的机器上。 步骤二：按照分配的值的范围，从低往高累加每个机器存储的值，如果累加当前机器的值超过了n的平方的一半，那么中位数就在这个机器上。 步骤三：问题缩小为获取机器上第n的平方-上一个机器的累加的数的最小的值。假设为k，我们就是获取这个机器第k小的值。可以先桶排序，然后再遍历搜索。还可以根据k大于机器的中位数还是小于机器的中位数，判断使用小顶堆还是大顶堆，遍历之后返回对应的值。

有1亿个浮点数，如果找出期中最大的10000个？

思路 Java用四个字节表示一个浮点数，1亿个浮点数就是四亿字节，约为0.4GB。

方法一 步骤一：将浮点数通过哈希并且对100取余，分配到100个小文件中。 步骤二：使用HashMap统计小文件中每个浮点数出现的次数，并使用大小为10000的大顶堆，统计出现次数对多的10000个。对100个小文件都做这样的操作 步骤三：合并上面得到的10000个大顶堆，得到一个大小为10000的大顶堆，最后返回这个大顶堆。