什么是大量数据处理？
海量数据处理就是基于海量数据上的存储、处理、操作。 什么是大容量，要么是因为数据量太大，无法在短时间内快速解决，要么是因为数据量太大而无法一次性加载内存。
要处理庞大的数据问题，只能是：
1 .分期治疗/混列图混列统计堆/快速/合并排序；
2 .双层桶划分
3.bloom过滤器/bitmap；
4 .树/数据库/倒排索引
5 .排名外
6 .分布式处理的Hadoop/Mapreduce。
1、从大量的日志数据中提取某一天访问百度次数最多的IP。
算法思想：分割统治的Hash
1.IP地址最多可取2^32=4G种值，无法完全载入内存进行处理； 2 .考虑采用“分区管理”，根据IP地址的混(IP ) 24的值，将大量的IP日志分别保存在1024个小文件中。 这样，每个小文件最多将包含4MB的IP地址。 3 .对于每个小文件，构建IP为key、出现次数为value的混列映射，得到1024个小文件中出现次数最多的IP，同时能够记录当前出现次数最多的IP地址，进而根据通常的排序算法
2 .搜索引擎在日志文件中记录用户每次搜索时使用的所有搜索字符串。 每个搜索字符串的长度为1-255字节。 假设现在有1千万张记录。 (这些查询列的重复程度很高，总数为1千万，但除去重复项，不超过3百万个。 查询字符串的重复程度越高，表示执行查询的用户越多，即越受欢迎。 请统计最受欢迎的10个查询串。 使用的内存不得超过1G。
典型的Top K算法
第一步，首先对这些大量数据进行预处理，在o(n )时间内用混列表完成统计
步骤2，利用堆这个数据结构，找到Top K，时间复杂度为N‘logK。
这意味着堆结构允许在日志订单的时间内搜索、调整和移动。 因此，我们的最终时间复杂度是，o(n ) (n ) (o ) (logk )，) n，因为我们保持k (在这个主题中是10 )大小的小根堆，遍历300万个查询，并分别与根元素进行比较
有3，1g大小的文件。 每行是一个单词，单词大小不超过16字节，内存限制大小为1M。 返回度数最高的100个单词。
情景：依次读取文件，每个单词x取hash(x ) P00，根据其值存储在5000个小文件(x0，x1， x4999 )中。 这样，每个文件约200k左右。
如果其中有超过1M的文件，也可以继续向下划分，直到用同样的方法分解得到的小文件大小小于或等于1M。
针对每个小文档，针对每个文档统计出现单词及其对应的频率(可以使用trie树/hash_map等)，取出出现频率最大的100个单词(可以使用包含100个节点的最小堆)，与100个单词相对下一步是合并(相似和合并排序)这5000个文件的过程。
4、庞大的数据分散在100台电脑中，寻找有效统计这些数据的TOP10的方法。
这个问题和上面的第三个问题类似。
堆叠顺序：在每台电脑上求TOP10，可以用包含10个要素的堆完成(TOP10小、最大堆、TOP10大、最小堆)。 例如，要求TOP10大，首先取前10个要素调整为最小堆。 如果发现，则扫描后续数据并将其与堆顶元素进行比较；如果大于堆顶元素，则将堆顶替换为该元素，然后将其调整为最小堆。 最后堆的要素是TOP10大。
求每台电脑的TOP10后，把这100台电脑的TOP10组合起来，求总计1000个数据，用以上方法求TOP10就可以了。 这里也请使用TOP-K算法。
有5、10个文件，每个文件为1G，每个文件每行保存的是用户的查询，每个文件的查询可能重复。 要求你按查询频率排序。
方案1 :
依次读取10个文件，根据hash(query )的结果将query写入其他10个文件。 这样新生成的每个文件的大小也约为1G (假设散列函数是随机的)。
找到内存2G左右的机器，用Hash_Map(Query，query_count )依次计数各query的出现次数。 使用快速/堆/合并排序按出现次数排序。 将已排序的query和对应的query_cout输出到文件。 这样得到了10个排序的文件(记载为)。
对这10个文件进行合并排序(内排序和外排序相结合)。
方案2 :
一般情况下，查询总量有限，但只是重复次数多。 对于所有查询，可能可以一次添加到内存中。 这样，用trie树/hash_map等直接计数各query出现的次数，按出现次数进行高速/堆/合并排序即可。
方案3 :
与方案1类似，但可以完成hash，将其分成多个文件，然后传递给多个文件进行处理，在分布式体系结构中进行处理(如MapReduce )，最后合并。
给6、a、b两个文件，分别保管50亿
个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件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，存到文件里面就可以了。
方案2：如果允许有一定的错误率，可以使用Bloomfilter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloomfilter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url(注意会有一定的错误率)。
7、怎么在海量数据中找出重复次数最多的一个？
方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求(具体参考前面的题)。
8、上千万或上亿数据(有重复)，统计其中出现次数最多的钱N个数据。
方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。
9、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。
10. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
方案1：这题用trie树比较合适，hash_map也行。
方案2：from xjbzju:，1000w的数据规模插入操作完全不现实，以前试过在stl下100w元素插入set中已经慢得不能忍受，觉得基于hash的实现不会比红黑树好太多，使用vector+sort+unique都要可行许多，建议还是先hash成小文件分开处理再综合。
11、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
采用2-Bitmap(每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义)进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。
12、5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
13、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？
与上第11题类似，我的第一反应时快速排序+二分查找。以下是其它更好的方法：
方案1：oo，申请512M的内存，一个bit位代表一个unsignedint值。读入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完。
14、题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。
Tire树
15、在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字6，则返回true；如果查找数字5，由于数组不含有该数字，则返回false。
本Young问题解法有二(如查找数字6)：
16、输入：一个最多含有n个不重复的正整数(也就是说可能含有少于n个不重复正整数)的文件，其中每个数都小于等于n，且n=10^7。
输出：得到按从小到大升序排列的包含所有输入的整数的列表。
条件：最多有大约1MB的内存空间可用，但磁盘空间足够。且要求运行时间在5分钟以下，10秒为最佳结果。
1、内存排序由于要求的可用内存为1MB，那么每次可以在内存中对250K的数据进行排序，然后将有序的数写入硬盘。
那么10M的数据需要循环40次，最终产生40个有序的文件。
2、归并排序
将每个文件最开始的数读入(由于有序，所以为该文件最小数)，存放在一个大小为40的first_data数组中；
选择first_data数组中最小的数min_data，及其对应的文件索引index；
将first_data数组中最小的数写入文件result，然后更新数组first_data(根据index读取该文件下一个数代替min_data)；
判断是否所有数据都读取完毕，否则返回2。