(1)海量日志数据，提取某日访问百度次数最多的IP。首先是这天，把访问百度的日志里的IP拿出来，一个一个写到一个大文件里。注意IP是32位的，最多有2^32个IP。也可以使用映射的方式，比如取模1000，将整个大文件映射成1000个小文件，然后找出每个小文件中出现频率最高的IP（可以使用hash_map进行频率统计，然后找出最频繁的IP))和相应的频率。然后在最大的1000个IP中，找出频率最高的那个IP，就是你要的。算法思路：分治法+HashIP地址最大有2^32=4G个值，所以不能完全加载到内存中处理；可以考虑使用“分而治之”的思想，根据IP地址的Hash(IP)%1024值，将海量IP日志分别存储成1024个小文件。这样每个小文件最多包含4MB的IP地址；对于每个小文件，可以构造一个以IP为键，出现次数为值的Hashmap，同时记录出现次数最多的IP地址。1024个小文件可以得到文件中出现次数最多的IP，然后按照常规排序算法得到整体出现次数最多的IP；(2)搜索引擎会通过日志文件记录用户每次搜索使用的所有搜索字符串，每次查询字符串的长度为1-255字节。假设当前有1000万条记录（这些查询字符串重复度比较高，虽然总数是1000万条，但是如果去掉重复，也不会超过300万条）。一个查询字符串的重复度越高，意思是查询它用户越多，越流行。）请统计最流行的10个查询字符串，所需内存不能超过1G。典型的TopK算法在本文中仍然进行说明。详见：十一．从头到尾彻底分析哈希表算法。本文最终给出的算法是：第一步对这批海量数据进行预处理，利用Hash表在O(N)时间内完成统计；第二步是利用堆的数据结构找到TopK，时间复杂度为N'logK。即，在堆结构的帮助下，我们可以在对数尺度时间中寻找和调整/移动。因此，维护一个K的小根堆（本题为10），然后遍历300万个Query，分别与根元素进行比较。因此，我们最终的时间复杂度为：O(N)+N'*O(logK)，（N为1000万，N'为300万）。ok，更多细节请参考原文。或者：使用trie树，keyword字段存储查询字符串出现的次数，没有出现则为0。最后用最少推10个元素对出现频率进行排序。(3)有一个1G大小的文件，每行一个字，一个字的大小不超过16字节，内存限制为1M。返回100个最常用的单词。解决方法：顺序读取文件，对每个单词x，取hash(x)%5000，然后将值存储在5000个小文件中（记为x0,x1,...x4999）。这样一来，每个文件大概200k左右。如果部分文件超过1M大小，可以按照类似的方法继续拆分，直到分解后的小文件大小不超过1M。对每个小文件，统计每个文件出现的词和对应的频率（可以用trietree/hash_map等），取出频率最高的100个词（可以用100个节点的最小堆),并将100个单词和对应的频率放入文件中，这样又得到了5000个文件。接下来就是合并这5000个文件的过程（类似于合并排序）。(4)有10个文件，每个文件1G，每个文件的每一行存储用户的查询，每个文件的查询可能会重复。您需要按查询频率排序。还是典型的TOPK算法，解决方法如下。方案一：依次读取10个文件，根据hash(query)%10的结果，将query写入另外10个文件（记为）。这样，每个新生成的文件大小约为1G（假设hash函数是随机的）。找一台内存2G左右的机器，用hash_map(query,query_count)统计每个query出现的次数。使用快速/堆/合并排序按出现次数排序。将排序后的query和对应的query_cout输出到文件中。这样就得到了10个排序后的文件（记为）。合并排序这10个文件（内部排序和外部排序的组合）。方案二：一般查询总量是有限的，但是重复次数比较多。可以一次将所有查询添加到内存中。这样我们就可以使用trietree/hash_map直接统计每个query的出现次数，然后根据出现次数进行fast/heap/merge排序。方案三：和方案一类似，但是做完hash分多个文件后，可以交给多个文件处理，使用分布式架构（如MapReduce）进行处理，最后合并。(5)给定两个文件a和b，每个文件存储50亿个url，每个url占用64字节，内存限制为4G，让你找出文件a和b的共同url？解法一：可以估算出每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中进行处理。考虑采取分而治之的方法。遍历文件a，对每个url计算hash(url)%1000，然后根据得到的值将url存储在1000个小文件中（标记为a0,a1,...,a999）。这样一来，每个小文件大概300M左右。遍历文件b，将url存储在1000个小文件中（记为b0,b1,...,b999），方法同a。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。那么我们只需要在1000对小文件中找到相同的url即可。当在每一对小文件中找到相同的url时，可以将其中一个小文件的url存储在hash_set中。然后再遍历另外一个小文件的每一个url，看看是不是在刚才建的hash_set里面，如果是，那么就是一个普通的url，存到文件里就行了。方案二：如果允许一定的错误率，可以使用Bloomfilter，4G内存可以表示大约340亿比特。使用Bloomfilter将其中一个文件中的url映射到这340亿位，然后将另一个文件的url一个一个读取，检查是否匹配Bloomfilter。如果是这样，该url应该是一个普通的url（注意会有一些错误率）。Bloomfilter以后会在本BLOG中详细阐述。(6)找出2.5亿个整数中不重复的整数。请注意，内存不足以容纳这2.5亿个整数。方案一：使用2-Bitmap（给每个数字分配2位，00表示不存在，01表示出现一次，10表示多次，11无意义），总共需要的内存为2^32*2bit=1GB内存，可以接受。然后扫描这2.5亿个整数，查看Bitmap中对应的位。如果00变成01，01变成10，10不变。描述完后，查看位图，输出对应位为01的整数。解法二：也可以用类似第一题的方法来划分小文件。然后找出小文件中的不重复整数，排序。然后合并，注意去除重复元素。(7)给定40亿个未排序的非重复unsignedint整数，再给一个数，如何快速判断这个数是否在40亿个数中？和上面第六题类似，我的第一反应是快速排序+二分查找。以下是其他比较好的方法：方案一：oo，申请512M内存，一位代表一个unsignedint值。读入40亿个数，设置对应位，读入要查询的数，查看对应位是否为1，为1表示存在，为0表示不存在.解法二：这个问题在《编程珠玑》中描述的很好，大家可以参考下面的思路来讨论：而且因为2^32大于40亿，给定的数可能在也可能不在；这里我们用32位二进制表示这40亿个数字中的每一个，假设这40亿个数字最初放在一个文件中。然后将这40亿个数分成两类：最高位为0和最高位为1，将这两种分别写到两个文件中。一个文件的数字个数<=20亿，而另一个>=20亿（这相当于减半）；与要查找的号码的最高位比较然后进入对应的文件进行查找然后将这个文件分为两类：次高位为0，次高位为1，将这两种分别写到两个文件中，一个文件的数字个数<=10亿，另一个>=10亿（这相当于一半）；将要查找的号码的第二高位进行比较，然后输入对应的文件重新查找。.......以此类推，可以找到，时间复杂度为O(logn)，解法2结束。附：这里简单介绍一下位图法：利用位图法判断整型数组是否存在重复。判断集合中的重复项是常见的编程任务之一。当集合中的数据量比较大时，我们通常希望少做几次。扫描，此时双循环方式不可取。位图方式更适合这种情况。它的方法是根据集合中最大的元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到时将1放在新数组的位置，如果遇到5，把新数组的第六个元素设置为1，这样下次遇到5想设置的时候，会发现新数组的第六个元素已经是1了，也就是说这次的数据一定是与复制数据之前相同。这种用零初始化一个新数组，然后设置为一的方法类似于位图处理方法，所以称为位图法。其操作次数的最坏情况是2N。如果知道数组的最大值，就可以预先确定新数组的长度，效率可以提高一倍。(8)如何在海量数据中找出重复次数最多的？方案一：先做hash，然后求取模映射成小文件，在每个小文件中找到重复次数最多的，记录重复次数。然后在上一步得到的数据中找出重复次数最多的就是你要找的那个（详见上一题）。(9)千万或亿条数据（有重复），统计出现次数最多的N条数据。方案一：当前机器的内存应该可以存储几千万或者几亿的数据。所以可以考虑使用hash_map/searchbinarytree/red-blacktree等来统计次数。然后就是取出出现次数最多的前N条数据，可以用问题2中提到的堆机制来完成。(10)一个文本文件大约有10000行，每行一个单词，要求计算出现频率最高的前10个词。请给出你的想法和时间复杂度分析。选项一：这道题是考虑时间效率。使用trie树统计每个单词出现的次数，时间复杂度为O(n*le)（le表示单词的平均长度）。然后找出出现次数最多的前10个词，可以用堆来实现。上一题提到，时间复杂度是O(n*lg10)。所以总的时间复杂度取O(n*le)和O(n*lg10)之间的较大者。奖励：找出100,000个数字中最大的100个数字。解法一：在上一题中，我们已经提到用一个包含100个元素的最小堆来完成。复杂度为O(100w*lg100)。方案二：采用快速排序的思路。每次划分后，只考虑比轴大的部分。当已知比轴大的部分超过100个时，采用传统的排序算法进行排序，取前100个。复杂度为O(100w*100)。方案三：采用部分淘汰法。选取前100个元素排序，记录为序列L。然后将剩余元素x扫描一次，与100个排序元素中最小的元素进行比较。如果大于最小元素，则删除最小元素，利用L中插入排序的思想将x插入到序列中。依次循环，直到扫描完所有元素。复杂度为O(100w*100)。
