1 假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词呢？
内存足够：采用哈希表统计出每个关键词出现的次数，建立一个大小为10的小顶堆，将所有的搜索关键词按照出现的次数，加入到小顶堆，遍历完后，堆中的关键词就是top 10搜索关键词
内存不够，假如只有1G：将10亿条搜索关键词通过哈希算法分片到10个小文件中，针对每个小文件，利用散列表和堆，分别求出top 10，然后把每个文件的top10取出，进行排序，获取top10（如果内存特别小，需要分成很多个小文件，这些小文件的top10加起来内存放不下，就需要将每个小文件的top10排序，然后用堆归并小文件，最后去top10）
2 有一个存放着200亿个数字的文件，存放着32位整型，可能会有重复的数字，现在想从这堆数字中找到他们的中位数。注意，内存只有512M
如果内存足够，可以使用快排的思想在O（N）复杂度下找到第K大元素
如果内存不够
分桶法：分成200个桶，第一个桶代表1到1亿的区间，第二个桶代表1亿到2亿的区间，以此类推。。。遍历200亿数据，每遍历到一个数字，将数字写入桶内，并且桶计算加1。最终可以确定中位数在哪个桶中，如果这个桶中的数据不能完全加载到内存，继续分桶，如果可以加载到内存，使用快排思想在O（N）复杂度下找到第K大元素
二分法：假如我们假设中位数是100万，如果大于100万的数有50亿个，就说明了中位数在1到100万之间。相反，如果大于100万的数字有150亿个，也就说明了中位数大于100万。假如大于100万的数字有50亿个，那么我们可以再次假设中位数是50万，再次扫描文件，看看大于50万的数字有多少个，假如是70亿个，那么我们再次假设中位数是25万。按照上述方法，我们每次都用二分法，找到中位数，每次都扫描整个文件，最多需要扫描log(N)次文件。这种方法，对内存的依赖极小
3 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序
顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中，找一台内存在2G左右的机器，依次对用哈希表来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件。对这10个文件进行归并排序
4 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url
遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M
遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可
求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了
5 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数
采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存22MB（1亿bit大约11MB），还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完后，查看bitmap，把对应位是01的整数输出即可
6 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中
申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
网友评论