海量数据处理面试题

百度三面考到了海量数据处理题，真的是血泪教训，在此记录一下。

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

可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。

顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。
找一台内存在2G左右的机器，依次用hash_map(query, query_count)来统计每个query出现的次数。
利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件。
对这10个文件进行归并排序（内排序与外排序相结合）。

遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,…,a999）中。这样每个小文件的大约为300M。
遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,…,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0 vs b0,a1 vs b1,…,a999 vs b999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1，并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（相当于折半）；与要查找的数的最高位比较并接着进入相应的文件再查找。

再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1，并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（相当于折半）；与要查找的数的次最高位比较并接着进入相应的文件再查找。以此类推，就可以找到了,而且时间复杂度为O(logn)。