开发面试题

hashmap 小顶堆

1、有一个1G大小的一个文件，里面每一行是一个英文单词，词的大小不超过16字节，内存限制是1M。请设计一个算法思路，返回频数最高的100个词。

解题思路：
1、遍历文件，对遍历到的每一个词，执行Hash操作：hash(x)%2000，将结果为i的词存放到文件ai中，通过这个分解步骤，可以是每个子文件的大小约为400KB左右，如果这个操作后的文件大小超过1MB，那么可以使用同样的方法把文件继续进行分解下去，直到文件的大小小于1MB为止。

2、统计出每个文件中出现频率最高的100个词。最简单的就是使用字典来实现，具体方法为：遍历文件中的所有词，对于遍历到的词，如果字典中不存在，则把这个词存入到字典中（键为这个词，值为1），如果这个词已经在字典中，那么把这个词对应的值加一。遍历后可以非常容易的找到出现频率最高的100个词。

3、上一步找出了每个文件中出现频率最高的100个词，这步可以通过维护一个小顶堆来找出所有词中出现频率最高的100个词。遍历第一个文件，把第一个文件中的出现频率最高的100个词构成一个小顶堆。（如果第一个文件中词的数目小于100，那么可以继续遍历第二个文件，直到构建好有100个节点的小顶堆为止）。继续遍历，如果遍历到的词的出现次数大于堆顶上词的出现次数，那么可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。当遍历完所有的文件后，这个小顶堆中的词就是出现频率最高的100个词。当然这一步也可以采用类似归并排序的方法把所有文件中出现次数最高的100个词进行排序，最终找出出现次数最高的100个词。

作者：CircleYua
来源：CSDN
原文：https://blog.csdn.net/kingyuan666/article/details/84502198
版权声明：本文为博主原创文章，转载请附上博文链接！

参考 TopK的常见解法
https://www.jianshu.com/p/0955ee38af65