海量数据面试题

1. 两个大文件找共同的url

给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

方案1

预估每个文件的大小为5G $\times$ 64 =320G，远大于内存限制，可以采取分治的办法。

1. 遍历文件$a$，对每个$url$取$hash(url)%1000$，根据取得的值将url分别存储到1000个小文件中。这样每个肖文杰大约为300M。
2. 遍历文本$b$​，采取和$a$相同的文件方式将url分别存储到1000个小文件。这样所有可能相同的url都在对应的小文件中，不对应的小文件不可能有相同的url。然后只需要求出1000对小文件中相同的url即可。
3. 求每对小文件相同的url时，可以把其中一个小文件的url存储到hash_set中，然后遍历另一个小文件中的url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件中即可。

方案2

布隆过滤器

2. 多个大文件的query排序

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

方案1

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

方案2

可以使用布隆过滤器

3. 大文件中的内容求频率

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

方案1:

1. 顺序读取文件，对每个词$x$，取$hash(x)%5000$取余，然后按照该值存到5000个小文件中。这样每个文件大约是200k，如果其中有的文件超过了1M，按照这种方法继续去分。
2. 对每个小文件，统计每个文件中出现的词以及相应的频率，并取出出现频率最大的100个词，并把100词及相应评率存入文件，这样又得到了5000个文件。
3. 下一步对5000个文件进行归并。