题目来自百度二面。
已知某个文件内包含大量电话号码，每个号码为8位数字，如何统计不同号码的个数？内存限制100M
这类题目其实是求解数据重复的问题。对于这类问题，可以使用位图法处理
8位电话号码可以表示的范围为00000000～99999999。如果用 bit表示一个号码，那么总共需要1亿个bit，总共需要大约10MB的内存。
申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。
假如有一个1G大小的文件，文件里每一行是一个词，每个词的大小不超过16byte，要求返回出现频率最高的100个词。内存大小限制是10M
由于内存限制，我们无法直接将大文件的所有词一次性读到内存中。
可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于10M，进而直接将单个小文件读取到内存中进行处理。
给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，找出 a、b 两个文件共同的 URL。内存限制是 4G。
每个 URL 占 64B，那么 50 亿个 URL占用的空间大小约为 320GB。
5,000,000,000 * 64B ≈ 320GB
由于内存大小只有 4G，因此，不可能一次性把所有 URL 加载到内存中处理。
可以采用分治策略，也就是把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。
给定100亿个无符号的乱序的整数序列，如何求出这100亿个数的中位数（中位数指的是排序后最中间那个数），内存只有512M。
中位数问题可以看做一个统计问题，而不是排序问题，无符号整数大小为4B，则能表示的数的范围为为0 ~ 2^32 - 1（40亿），如果没有限制内存大小，则可以用一个2^32（4GB）大小的数组（也叫做桶）来保存100亿个数中每个无符号数出现的次数。遍历这100亿个数，当元素值等于桶元素索引时，桶元素的值加1。当统计完100亿个数以后，则从索引为0的值开始累加桶的元素值，当累加值等于50亿时，这个值对应的索引为中位数。时间复杂度为O(n)。
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询床的长度不超过 255 字节。
假设目前有 1000w 个记录（这些查询串的重复度比较高，虽然总数是 1000w，但如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。（一个查询串的重复度越高，说明查询它的用户越多，也就越热门。）
每个查询串最长为 255B，1000w 个串需要占用 约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中处理。
有 1w 个数组，每个数组有 500 个元素，并且有序排列。如何在这 10000*500 个数中找出前 500 的数？
题目中每个数组是排好序的，可以使用归并的方法。
先将第1个和第2个归并，得到500个数据。然后再将结果和第3个数组归并，得到500个数据，以此类推，直到最后找出前500个的数。
对于这种topk问题，更常用的方法是使用堆排序。
有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。
如果 query 的重复度比较大，可以考虑一次性把所有 query 读入内存中处理；如果 query 的重复率不高，那么可用内存不足以容纳所有的 query，这时候就需要采用分治法或其他的方法来解决。
如果 query 重复率高，说明不同 query 总数比较小，可以考虑把所有的 query 都加载到内存中的 HashMap 中。接着就可以按照 query 出现的次数进行排序。
今天想跟大家聊一些常见的 topK 问题。
对于海量数据到处理经常会涉及到 topK 问题。在设计数据结构和算法的时候，主要需要考虑的应该是当前算法（包括数据结构）跟给定情境（比如数据量级、数据类型）的适配程度，和当前问题最核心的瓶颈（如降低时间复杂度，还是降低空间复杂度）是什么。
首先，我们来举几个常见的 topK 问题的例子：
题目来自百度二面。
已知某个文件内包含大量电话号码，每个号码为8位数字，如何统计不同号码的个数？内存限制100M
这类题目其实是求解数据重复的问题。对于这类问题，可以使用位图法处理
8位电话号码可以表示的范围为00000000～99999999。如果用 bit表示一个号码，那么总共需要1亿个bit，总共需要大约10MB的内存。
申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit对应的电话号码在文件中不存在。
假如有一个1G大小的文件，文件里每一行是一个词，每个词的大小不超过16byte，要求返回出现频率最高的100个词。内存大小限制是10M
由于内存限制，我们无法直接将大文件的所有词一次性读到内存中。
可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于10M，进而直接将单个小文件读取到内存中进行处理。