文档介绍：数据分析面试常见问题
1、海量日志数据，提取出某日访问百度次数最多的那个
IP。
首先是这一天，并且是访问百度的日志中的
IP 取出来，逐个写入到一个大文件中。注
算法，解决方案如下：
方案
1 ：
顺序读取
10 个文件，按照
hash(query) 的结果将
query
写入到另外
10 个文件（记为）中。
这样新生成的文件每个的大小大约也
1G（假设
hash 函数是随机的） 。
找一台内存在 2G 左右的机器， 依次对用 hash_map(query, query_count) 出现的次数。利用快速 / 堆 / 归并排序按照出现次数进行排序。将排序好的输出到文件中。这样得到了 10 个排好序的文件（记为） 。 query_cout
来统计每个 query
query 和对应的
对这 10 个文件进行归并排序（内排序与外排序相结合） 。
方案 2：
一般 query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的 query，一
次性就可以加入到内存了。 这样，我们就可以采用 trie 树 /hash_map 等直接来统计每个 query
出现的次数，然后按出现次数做快速 / 堆 / 归并排序就可以了。
方案 3：
与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分
布式的架构来处理（比如 MapReduce），最后再进行合并。
5、 给定 a、 b 两个文件，各存放 50 亿个 url ，每个 url 各占 64 字节，内存限制是 4G，
让你找出 a、 b 文件共同的 url？
方案 1：可以估计每个文件安的大小为 5G× 64=320G，远远大于内存限制的 4G。所以
不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件 a，对每个 url 求取 hash(url)00 ，然后根据所取得的值将 url 分别存储到 1000
个小文件（记为 a0,a1, ,a999）中。这样每个小文件的大约为 300M 。
遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 小文件（记为 b0,b1, ,b999）。
这样处理后，所有可能相同的 url 都在对应的小文件（ a0vsb0,a1vsb1, ,a999vsb999）中，不
对应的小文件不可能有相同的 url。然后我们只要求出 1000 对小文件中相同的 url 即可。
求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。然后
遍历另一个小文件的每个 url ，看其是否在刚才构建的 hash_set 中，如果是，那么就是共同
的 url ，存到文件里面就可以了。
方案 2：如果允许有一定的错误率，可以使用 Bloom filter ，4G 内存大概可以表示 340
亿 bi