大数据算法

1. TOP K 算法

有10个⽂件，每个⽂件1G，每个⽂件的每⼀⾏存放的都是⽤户的 query，每个⽂件的 query 都可能重复。要求你按照 query 的频度排序。

方法1：
顺序读取10个⽂件，按照 hash(query)%10 的结果将 query 写⼊到另外 10 个⽂件（记为）中。这样新⽣成的⽂件每个的⼤⼩⼤约也 1G（假设 hash 函数是随机的）。找⼀台内存在 2G 左右的机器，依次对⽤hash_map(query, query_count)来统计每个 query 出现的次数。利⽤快速/堆/归并排序按照出现次数进⾏排序。将排序好的 query 和对应的 query_cout 输出到⽂件中。这样得到了 10 个排好序的⽂件（记为）。对这 10 个⽂件进⾏归并排序（内排序与外排序相结合）。
方法2：
与⽅案 1 类似，但在做完 hash，分成多个⽂件后，可以交给多个⽂件来处理，采⽤分布式的架构来处理（⽐如 MapReduce），最后再进⾏合并。

2. 不重复的数据

在 2.5 亿个整数中找出不重复的整数，注，内存不⾜以容纳这 2.5 亿个整数。
解答：
1）⽅案 1：采⽤ 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现⼀次，10 表示多次，11 ⽆意义）进⾏，共需内存 2^32 * 2bit=1 GB 内存，还可以接受。然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。
2）⽅案 2：也可采⽤与第 1 题类似的⽅法，进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中找出不重复的整数，并排序。然后再进⾏归并，注意去除重复的元素。

3. 判断数据是否存在

给 40 亿个不重复的 unsigned int 的整数，没排过序的，然后再给⼀个数，如何快速判断这个数是否在那 40 亿个数当中？
1）⽅案 1：oo，申请 512M 的内存，⼀个 bit 位代表⼀个 unsigned int 值。读⼊ 40 亿个数，设置相应的 bit 位，读⼊要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在。

4. 重复最多的数据

有⼀千万条短信，有重复，以⽂本⽂件的形式保存，⼀⾏⼀条，有重复。请⽤5分钟时间，找出重复出现最多的前 10 条。
解答：
1）分析： 常规⽅法是先排序，在遍历⼀次，找出重复最多的前 10 条。但是排序的算法复杂度最低为 nlgn。
2）可以设计⼀个 hash_table, hash_map<string, int>，依次读取⼀千万条短信，加载到 hash_table 表 中，并且统计重复的次数，与此同时维护⼀张最多 10 条的短信表。 这样遍历⼀次就能找出最多的前 10 条，算法复 杂度为 O(n)。