1 如何在两个大量的文件中找到相同的部分？
a和b两个文件，各自存放50亿个URL，每个URL占64B，内存限制为4G，请找出a，b两个文件共同的url。
2^10 10^9 a，b文件大小为320GB
分治+堆+哈希
- 将a，b大文件拆分为多个小文件。该过程利用相同的哈希规则让url映射存放到某个文件之中，这样能够保证a和b中相同的url映射到相同的文件之中。拆分的过程主要在磁盘中进行，内存中边读边拆，逐行写入到磁盘之中。
- 将a和b中相对应的文件依次比较，最后合并结果即可。
优化点
1 由于url经常出现公共前缀，可以优化url的存储方式
2 布隆过滤器。（仅仅可用于前置筛选掉一定不存在的数据，之后还得进一步用分治+哈希、位图法等精确方案）
布隆过滤器中是能够排除肯定不在文件的数据，但是有部分不在文件的数据可能判断不出来即误判率。
- 因此根据A文件的url数量，设置一个误判率较低的布隆过滤器，然后将A文件中所有的值存入。将B文件中的url逐个读取逐个比较，最后得到最终筛选出来的url。
- 解决误判率：将该小文件的url，和A中的原始数据进行比对，可以分治法每次读取一部分A的数据，最后删除误判的url得到最终结果。
2 如何从大量数据中找出高频词？TOPN
单个文件大小为1GB，每个词大小不超过16B，内存大小限制为1MB，返回频数最高的100个词。
分治+堆+哈希
- 和上面思路相同，先采用哈希的方法分成多个小文件，如果小文件中存在大小超过限制的，那么对该小文件进行二次哈希，选择不同的哈希方案。
- 统计每个小文件的局部词频，直接存储在该文件中即可，写入磁盘。
- 维护一个小顶堆，当当前频数小于100时，直接加入该堆，大于100时，大于当前堆顶时加入该堆，反之去掉。
3 在2.5亿个整数中找到不重复的整数？
1 哈希+分治成多个小文件，再用hashmap找出每个小文件中不重复的整数，最后合并结果。
2 位图法。当存在2.5亿个整数时，从前到后依次用每个位判断该值是否存在（00不存在，01存在一次，11存在多次）缺点在于浪费了很多空间，数据必须是整数，整数范围不能过大。
4 如何找到大量数据的中位数？
1 分桶。预估范围分桶，得到每个桶中的数据量个数，遍历计算得到中位数的桶。将该桶加载到内存中排序即可。
2 二分查找。选择一个值，将数据分成两部分。中位数一定在较大的一边中，之后递归可以找到中位数。缺点在于需要内存中能存储所有的数，很消耗内存。
综合
大部分采用分治+哈希。
另外如果内存够大，考虑位图，二分查找；
对数据进行前置处理，考虑布隆过滤器，前缀树；
找TOPK，用堆
参考链接：
| 1 [海量数据处理 | 阿秀的学习笔记](https://interviewguide.cn/notes/03-hunting_job/02-interview/07-01-massive_data.html) |
