有10个⽂件，每个⽂件1G，每个⽂件的每⼀⾏存放的都是⽤⼾的query，每个⽂件的query都可能重复。要求你按照query的频度排序。
解析:
还是典型的TOPK算法，解决⽅案如下：
www.aboutyun.com/thread-24246-1-1.html 53/57
2019/4/24 spark相关的⾯试题跟答案，带着问题学习效果更佳哟。?）-⾯试区-about云开发
⽅案1：
顺序读取10个⽂件，按照hash(query)%10的结果将query写⼊到另外10个⽂件(记为)中。这样新⽣成的⽂件每个的⼤⼩⼤约也1G(假设hash函数是随机的)。
找⼀台内存在2G左右的机器，依次对⽤hash_map(query,query_count)来统计每个query出现的次数。利⽤快速/堆/归并排序按照出现次数进⾏排序。将排序好的query和对应的query_cout输
出到⽂件中。这样得到了10个排好序的⽂件(记为)。
对这10个⽂件进⾏归并排序(内排序与外排序相结合)。
⽅案2：
⼀般query的总量是有限的，只是重复的次数⽐较多⽽已，可能对于所有的query，⼀次性就可以加⼊到内存了。这样，我们就可以采⽤trie树/hash_map等直接来统计每个query出现的次
数，然后按出现次数做快速/堆/归并排序就可以了。
⽅案3：
与⽅案1类似，但在做完hash，分成多个⽂件后，可以交给多个⽂件来处理，采⽤分布式的架构来处理(⽐如MapReduce)，最后再进⾏合并。
解析:
三个代：年轻代（Young Generation）、年⽼代（Old Generation）和持久代（Permanent Generation）
在5亿个整数中找出不重复的整数，注，内存不⾜以容纳这5亿个整数。
解析:
⽅案1：采⽤2-Bitmap(每个数分配2bit，00表⽰不存在，01表⽰出现⼀次，10表⽰多次，11⽆意义)进⾏，共需内存2^32*2bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap
中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
⽅案2：也可采⽤与第1题类似的⽅法，进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中找出不重复的整数，并排序。然后再进⾏归并，注意去除重复的元素。
腾讯⾯试题：给40亿个不重复的unsignedint的整数，没排过序的，然后再给⼀个数，如何快速判断这个数是否在那40亿个数当中?
解析:
第⼀反应时快速排序+⼆分查找。以下是其它更好的⽅法：
⽅案1：oo，申请512M的内存，⼀个bit位代表⼀个unsignedint值。读⼊40亿个数，设置相应的bit位，读⼊要查询的数，查看相应bit位是否为1，为1表⽰存在，为0表⽰不存在。
⽅案2：这个问题在《编程珠玑》⾥有很好的描述，⼤家可以参考下⾯的思路
解析:
⽅案1：先做hash，然后求模映射为⼩⽂件，求出每个⼩⽂件中重复次数最多的⼀个，并记录重复次数。然后找出上⼀步求出的数据中重复次数最多的⼀个就是所求(具体参考前⾯的题)。
