1、题目：每一个ip访问百度，其ip地址都会被记录到后台日志文件中，假设一天的访问日志有100G，求出一天中访问百度次数最多的ip地址，可以使用的内存大小是1G。
解题
1M `=10^6B 1G`=10^9B
首先解决大文件问题，也就是如何处理100G的一个大文件，这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件（file0,file1......file1023），注意这里的1024个文件并不是平均分的，也就是每个文件大小并不是（100G/1204）。当然我们考虑的时候可以假设文件是平均分的，那么每个文件大小为100M，这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。
考虑到ip地址是32为，那么总共有2^32=4G种可能出现的ip地址，每个ip地址出现的次数不确定，这个具体是由100G大文件决定的。对每个小文件进行处理，我们知道前面每个文件中的ip是通过hash(ip)%1024。这样相当于将2^32=4G种ip地址进行了分段，每个文件中可能出现的ip最大范围是4G/1024=4M。创建一个hashmap，读取小文件中的每个ip地址，判断hashmap中是否有这个ip，如果没有，这往haspmap中插入一个的键值对，即hashmap.put(ip,1)；如果haspmap中已经存在了这个ip，那么求出这个ip所对应的值count=haspmap.get(ip)，然后往修改这个ip所对应的value，使其数量增加1，即hashmap.set(ip,count+1)。
当我们求出每个文件中出现次数最大的ip地址以后，我们在比较这1024个文件中的那个ip出现次数最大
关于本题，注意两点：
Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是%1000算法，那么同一个IP在hash后，只可能落在同一个文件中，不可能被分散的。
那到底什么是hash映射呢？简单来说，就是为了便于计算机在有限的内存中处理big数据，从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小树存放在内存中，或大文件映射成多个小文件)，而这个映射散列方式便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发生了变化而已。
2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前一个日志文件中有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
解答：
1M `=10^6B 1G`=10^9B
1000万条记录，每条记录最大为255Byte，那么日志文件最大有2.5G左右，大于1G内存。但是题目中又提到这样的1000万条记录中有许多是重复的，出去重复的话只有300万条记录，存储这样的300万条记录需要0.75G左右的内存，小于1G内存。那么我们可以考虑将这些无重复的记录装入内存，这是我们需要一种数据结构，这种数据结构即能够存储查询串，又能存储查询串的出现次数，我们可以通过hashmap来保存。读取文件，创建一个hashmap，如果hashmap中存储了遍历到的query，则修改该query所对应的count值，使其+1；如果hashmap中没有这个query，那么往haspmap中插入。这样我们就创建好了一个包含所有query和次数的hashmap。
然后我们创建一个长度为10最小堆MinHeap（求最多的要用最小堆，求最小的要用最大堆），(这里需要假定这个小顶堆是大顶堆)。最小堆的堆顶元素最小，如果堆顶这个最小的元素都大于其他非堆元素了，那么堆中的其他元素必定大于其他非堆中元素。遍历hashmap，如果MinHeap未满，那么往MinHeap中插入这个键值对，如果MinHeap满了，则比较遍历到的元素的count值堆顶的count，如果遍历到元素的count大于堆顶count值，删除堆顶元素，插入当前遍历到的元素。遍历完整个hashmap以后，在MinHeap中存储的就是最热门10个查询串。
3、将query按照出现的频度排序（10个1G大小的文件）。有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。如何按照query的频度排序？求出Top10？
1）读取10个文件，按照hash(query)%10的结果将query写到对应的10个文件（file0,file1....file9）中，这样的10个文件不同于原先的10个文件。这样我们就有了10个大小约为1G的文件。任意一个query只会出现在某个文件中。
2）对于1）中获得的10个文件，分别进行如下操作
利用hash_map（query，query_count）来统计每个query出现的次数。
创建一个长度为10的堆来保存一个文件中出现次数最多的hash_map（query，query_count），最后将这10个键值对输出到result文件中。
3）通过2）获得的result文件保存着每个文件出现次数最多的10条记录，对其中的100条记录按照query_count进行排序，最后输出query_count最大的10条query。
来源：http://www.cnblogs.com/xwdreamer
4、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
1G`=10^6M
方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。
如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。
下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。这个时候就和上面的第三题很类似了，相同的Hashcode%1000放在一个文件中.
5、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
1. 遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M。
2. 遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
3. 求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。
方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。
Bloom filter日后会在本BLOG内详细阐述。
6、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可
方案2：
遍历文件求hash(num)%10000，分成1万个小文件，对每个小文件找出不充分的数
对于每个小文件,利用Hash key = num,value =次数，最后发现此时是1的就是只出现一次的整数
汇总1万个小文件的结果
如果分成1万个小文件，部分文件过大，也可以继续进行分成小文件
7、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
与上第6题类似，我的第一反应时快速排序+二分查找。以下是其它更好的方法：方案1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
dizengrong：方案2：这个问题在《编程珠玑》里有很好的描述，大家可以参考下面的思路，探讨一下：又因为2^32为40亿多，所以给定一个数可能在，也可能不在其中；这里我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1 并将这两类分别写入到两个文件中，其中一个文件中数的个数<=20亿，而另一个>=20亿（这相当于折半了）；与要查找的数的最高位比较并接着进入相应的文件再查找
再然后把这个文件为又分成两类: 1.次最高位为0 2.次最高位为1
并将这两类分别写入到两个文件中，其中一个文件中数的个数<=10亿，而另一个>=10亿（这相当于折半了）； 与要查找的数的次最高位比较并接着进入相应的文件再查找。 ....... 以此类推，就可以找到了,而且时间复杂度为O(logn)，方案2完。
上面讲的无法理解
我感觉这样应该也可以：
计算Hash（num）%10000,分成1万个小文件，求hash(target)%10000,找到所在的小文件区域，若与1万个文件的hash(num)%10000值不一样，说明不存在。
对于存在的时候，找到这个小文件，继续进行上面的操作，（%1000，或者更小，这里根据内存大小而定）
若果存在一个小文件的hash（num）%1000 == hash(target)%1000 ，只需要顺序的遍历判断是否存在这个数了。
附：这里，再简单介绍下，位图方法： 使用位图法判断整形数组是否存在重复 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。
位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
8、怎么在海量数据中找出重复次数最多的一个？
方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。
9、上千万或上亿数据（有重复），统计其中出现次数最多的N个数据。
方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。
10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。
附、100w个数中找出最大的100个数。
方案1：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
方案2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比100多的时候，采用传统排序算法排序，取前100个。复杂度为O(100w*100)。
方案3：采用局部淘汰法。选取前100个元素，并排序，记为序列L。然后一次扫描剩余的元素x，与排好序的100个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把x利用插入排序的思想，插入到序列L中。依次循环，知道扫描了所有的元素。复杂度为O(100w*100)。
来源:http://www.cnblogs.com/zuoyuan/p/4747635.html
网友评论