类型一 海量数据，出现次数最多or前K
分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
IP有32位，共有232232个IP。
1）采用hash的方式，ip%m，将大文件分成m个小文件。
2）对每个小文件，用hash表统计ip出现的次数。找出这个小文件出现次数最多的ip
3）在这m个ip中，比较得到出现次数最多的ip。
如果是top k的话，就维护一个长度为k的最小堆。
2、统计最热门的10个查询串，要求使用的内存不能超过1G。
假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。每个查询串的长度为1-255字节。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。
300万*255=7.65x10^8<1GB
1）用hash表统计查询串出现的频率
2）维护长度为k的最小堆
3、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
10文件顺序读取，然后hash，分散到10个文件里面去。再hash表统计词频，排序。最后归并。
4、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
5G*64=320G
1）a,b分别用hash分成m个小文件
2）在a对应第i个文件,用hash表标记url是否出现，遍历在b对应的第i个文件查看url在hash表中是否存在，若存在则为共同url
3)合并m个文件中找到的共同url
5、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析
这个字典树暂时还没弄懂原理，稍后再研究。
1、2.5亿个整数中找出不重复的整数的个数
32位整数共有232232个，每个数用1bit标记是否出现，共需要232bit=4G/8=512M232bit=4G/8=512M
申请512M的内存，每一bit，0表示未出现，1表示已出现。
计数器count初始化为0。
遍历数据文件，对每一个数，查看对应标志位，如果为0，则count+1，并标记为1；
2、2.5亿个整数中找出不重复的整数
2-Bitmap，每个数用2个bit来标记，00未出现，01出现1次，10出现多次，11无意义。需要1G内存。
遍历数据文件，对每个数查看标志位，为00则改为01，为01则改为10
最后，查看bitmap输出标志位01的数。
这里对大数据技术感兴趣或者想学习大数据的朋友，我整理了一套大数据的学习视频免费分享给大家，从入门到实战都有，大家可以加我的微信：Lxiao_28获取，还可以入微信群交流！（备注领取资料，真实有效）。
3、5亿个int找它们的中位数
思路是先分治，再用双堆法：
首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
双堆法的思路：
序列中的元素，前一半存储在一个最大堆中，后一半存储在一个最小堆中。控制MaxHeap与MinHeap的大小差不能超过1。
网友评论