面试现场：海量数据中的TOPK问题

• 1、只用2GB内存在20亿个整数中找到出现次数最多的数
  • 思路
• 2、40亿个非负整数中找到没出现的数
  • 思路
    • 进阶问题
• 3、找到100亿个URL中重复的URL以及搜索词汇的topK问题
  • 思路
    • 补充题目
• 4、40亿个非负整数中找到出现两次的数和所有数的中位数
  • 思路
    • 补充题目

1、只用2GB内存在20亿个整数中找到出现次数最多的数

初级进阶： 40亿个整数
高级进阶： 80亿个整数

思路

想要在很多整数中找到出现次数最多的数，通常的做法是使用哈希表对出现的每一个数做词频统计。

哈希表的key需要占用4B，value也是4B。

本题共有20亿个数，用32位的整数就可以表示其出现的次数，而不会产生溢出，但哈希表的一条记录(key, value)需要占用8B，当哈希表记录数为2亿个时需要至少1.6GB的内存。极端情况下20亿个数都不同，这样内存可能会不够用。

解决办法是把包含20亿个数的大文件用足够好的哈希函数分成21个小文件，根据哈希函数的性质，相同的数一定会在同一个文件中，我们这个时候就可以统计每个文件中出现次数最多的数，然后再从这些数中再次选出最多的数。

把一个大的集合通过哈希函数分配到多台机器中或者分配到多个文件里，这种技巧是处理大数据面试题时最常用的技巧之一。具体分配到多少台机器、分配到多少文件，要根据具体的限制来确定，比如本题确定分成21个文件就是根据内存限制2GB的条件来确定的。

2、40亿个非负整数中找到没出现的数

思路

32位无符号整数的范围是0~4294967295，哈希表存一个32位整数需要4B，如果用哈希表来保存出现过的数，40亿个数都不同的情况下需要40亿×4B=160亿字节（16GB）的空间是不符合要求的。

我们可以使用bit map的方式来表示数出现的情况。
申请一个长度为4294967295的bit类型的数组bitArr，占用空间500MB，bitArr上的每个位置只可以表示0或1状态。
接下来遍历这40亿个无符号数，把bitArr相应位置的值设置为1。之后再依次遍历bitArr，哪个位置上的值没被设置为1，相应位置代表的数就不在40亿个数中。例如，发现bitArr[8001]=0，那么8001就是没出现过的数。遍历bitArr之后，所有没出现的数就都找出来了。

进阶问题

可以把0~4294967295这个范围平均分成64个区间，每个区间有67108864个数，第i区间为67108864×i ~ 67108864×(i+1)-1。
因为一共只有40亿个数，如果统计落在每一个区间上的数有多少，至少有一个区间上的计数少于67108864，表示这个区间至少有一个没出现过的数。

具体过程
第一次遍历：

1. 先申请长度为64的整型数组countArr[0..63]，countArr[i]用来统计区间i上的数有多少；
   countArr的大小（64×4B）是非常小的。
2. 遍历40亿个数,根据当前数是多少来决定哪一个区间上的计数增加；
   例如当前数是3422552090，342252090/67108864=51，所以countArr[51]++。
3. 遍历完40亿个数之后再遍历countArr，至少会找到一个区间的值（countArr[i]）小于67108864。

假设找到第37区间上的计数小于67108864，进行第二次遍历：

1. 申请长度为67108864的bit map（占用大约8MB的空间），记为 bitArr[0..67108863]；
2. 再遍历一次40亿个数，此时只关注落在第37区间上的数num（num/67108864=37），其他区间的数全部忽略。
3. 做第37区间上的数的bitArr映射，将 bitArr[num-67108864*37]的值设置为1。
4. 遍历完40亿个数之后，在bitArr上第i个位置的值没设置成1,那么67108864×37+i这个数就是一个没出现过的数。

总结

1. 根据10MB的内存限制，确定统计区间的大小，也是第二次遍历时bitArr的大小；
2. 利用区间计数的方式，找到那个计数不足的区间（这个区间上肯定有没出现的数）；
3. 对这个区间上的数做bit map映射，再遍历bit map，找到一个没出现的数即可。

3、找到100亿个URL中重复的URL以及搜索词汇的topK问题

思路

使用解决大数据问题的一种常规方法：
把大文件通过哈希函数分配到机器或者拆成小文件。一直进行这种划分，直到划分的结果满足资源限制的要求。

哈希函数的性质决定了同一条URL不可能分给不同的机器：

• 分配到机器：将100亿字节的大文件通过哈希函数分配到100台机器上，然后每一台机器分别统计分给自己的URL中是否有重复的URL。
• 拆成小文件：在单机上将大文件通过哈希函数拆成1000个小文件，对每一个小文件再利用哈希表遍历找出重复的URL。

总结：很多大数据问题都离不开分流，要么是哈希函数把大文件的内容分配给不同的机器，要么是哈希函数把大文件拆成小文件，然后处理每一个小数量的集合。

补充题目

1. 最开始还是用哈希分流的思路来处理，把包含百亿数据量的词汇文件分流到不同的机器上；
2. 如果对每一台机器来说分到的数据量依然很大，可以再用哈希函数把每台机器的分流文件拆成更小的文件处理；
3. 处理每一个小文件的时候，哈希表统计每种词及其词频后再遍历。在遍历的过程中使用大小为100的小根堆来选出每一个小文件的top100，再将小根堆里的词按照词频排序，就得到了每个小文件的排序后top100；
4. 然后把各个小文件排序后的top100进行外排序或者继续利用小根堆，选出每台机器上的top100；
5. 不同机器之间的top100再进行外排序或者继续利用小根堆，最终求出整个百亿数据量中的top100。

对于topK的问题，除哈希函数分流和用哈希表做词频统计之外，还经常用堆结构和外排序的手段进行处理。

4、40亿个非负整数中找到出现两次的数和所有数的中位数

思路

可以用bit map的方式来表示数出现的情况：

• 申请一个长度为4294967295×2的bit类型的数组bitArr，1B占用8个bit，所以bitArr数组占用1GB空间；
• 遍历这40亿个无符号数，用2个位置表示一个数出现的词频;
  • 如果初次遇到num就把bitArr[num*2 + 1]和bitArr[num * 2]设置为01；
  • 第2次遇到num就把就把bitArr[num*2 + 1]和bitArr[num * 2]设置为10；
  • 第3次遇到num就把就把bitArr[num*2 + 1]和bitArr[num * 2]设置为11；
  • 再遇到num，发现此时bitArr[num*2 + 1]和bitArr[num * 2]已经设置为11，就不再做任何设置。
• 再依次遍历bitArr，如果发现bitArr[i2+1]和bitArr[i2]设置为10，那么i就是出现了两次的数。

补充题目

长度为2MB的无符号整型数组占用的空间为8MB，所以将区间的数量定为4294967295/2M，向上取整为2148个区间，第i区间为2M * i ~ 2M * (i+1) - 1。

用分区间的方式处理：

1. 申请一个长度为2148的无符号整型数组arr[0..2147]，arr[i]表示第i区间有多少个数，arr必然小于10MB；
2. 遍历40亿个数，进行arr[num/2M]++操作；
3. 累加每个区间的出现次数，找到40亿个数的中位数(也就是第20亿个数)到底落在第K个区间上；
4. 接着申请一个长度为2MB的无符号整型数组counter[0..2M-1]（占用空间8MB）；
5. 然后再遍历40亿个数，此时只关心在第K区间的数，记为numi。进行countarr[numi-K*2M]++对第K区间的数做频率统计；
6. 最后只在第K区间上找到第0.002亿个数，即40亿个数的中位数。