⼤数据分析师常见的⾯试题解答
1、海量⽇志数据，提取出某⽇访问百度次数最多的那个IP。
⾸先是这⼀天，并且是访问百度的⽇志中的IP取出来，逐个写⼊到⼀个⼤⽂件中。注意到IP是32位的，最多有个2^32个IP。同样可以采⽤映射的⽅法，⽐如模1000，把整个⼤⽂件映射为1000个⼩⽂件，再出每个⼩⽂中出现频率最⼤的IP(可以采⽤hash_map进⾏频率统计，然后再出频率最⼤的⼏个)及相应的频率。然后再在这1000个最⼤的IP中，出那个频率最⼤的IP，即为所求。
或者如下阐述：
算法思想：分⽽治之+Hash
1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理;
2.可以考虑采⽤“分⽽治之”的思想，按照IP地址的Hash(IP)24值，把海量IP⽇志分别存储到1024个⼩⽂件中。这样，每个⼩⽂件最多包含
4MB个IP地址;
3.对于每⼀个⼩⽂件，可以构建⼀个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个⼩⽂件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP;
2、搜索引擎会通过⽇志⽂件把⽤户每次检索使⽤的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设⽬前有⼀千万个记录(这些查询串的重复度⽐较⾼，虽然总数是1千万，但如果除去重复后，不超过3百万个。⼀个查询串的重复度越⾼，说明查询它的⽤户越多，也就是越热门。)，请你统计最热门的10个查询串，要求使⽤的内存不能超过1G。
典型的Top K算法，给出的最终算法是：
第⼀步、先对这批海量数据预处理，在O(N)的时间内⽤Hash表完成统计(之前写成了排序，特此订正。July、2011.04.27);
第⼆步、借助堆这个数据结构，出Top K，时间复杂度为N‘logK。
即，借助堆结构，我们可以在log量级的时间内查和调整/移动。因此，维护⼀个K(该题⽬中是10)⼤⼩的⼩根堆，然后遍历300万的Query，分别和根元素进⾏对⽐所以，我们最终的时间复杂度是：O(N)+ N’*O(logK)，(N为1000万，N’为300万)。
或者：采⽤trie树，关键字域存该查询串出现的次数，没有出现为0。最后⽤10个元素的最⼩推来对出现频率进⾏排序。
3、有⼀个1G⼤⼩的⼀个⽂件，⾥⾯每⼀⾏是⼀个词，词的⼤⼩不超过16字节，内存限制⼤⼩是1M。返回频数最⾼的100个词。
⽅案：顺序读⽂件中，对于每个词x，取hash(x)P00，然后按照该值存到5000个⼩⽂件(记为x0,x1,…x4999)中。这样每个⽂件⼤概是200k左右。
如果其中的有的⽂件超过了1M⼤⼩，还可以按照类似的⽅法继续往下分，直到分解得到的⼩⽂件的⼤⼩都不超过1M。
对每个⼩⽂件，统计每个⽂件中出现的词以及相应的频率(可以采⽤trie树/hash_map等)，并取出出现频率最⼤的100个词(可以⽤含100个结点的最⼩堆)，并把100个词及相应的频率存⼊⽂件，这样⼜得到了5000个⽂件。下⼀步就是把这5000个⽂件进⾏归并(类似与归并排序)的过程了。
4、有10个⽂件，每个⽂件1G，每个⽂件的每⼀⾏存放的都是⽤户的query，每个⽂件的query都可能重复。要求你按照query的频度排序。
还是典型的TOP K算法，解决⽅案如下：
⽅案1：
顺序读取10个⽂件，按照hash(query)的结果将query写⼊到另外10个⽂件(记为)中。这样新⽣成的⽂件每个的⼤⼩⼤约也1G(假设hash函数是随机的)。
⼀台内存在2G左右的机器，依次对⽤hash_map(query,query_count)来统计每个query出现的次数。利⽤快速/堆/归并排序按照出现次数进⾏排序。将排序好的query和对应的query_cout输出到⽂件中。这样得到了10个排好序的⽂件。
对这10个⽂件进⾏归并排序(内排序与外排序相结合)。
⽅案2：
⼀般query的总量是有限的，只是重复的次数⽐较多⽽已，可能对于所有的query，⼀次性就可以加⼊到内存了。这样，我们就可以采⽤trie
树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
⽅案3：
与⽅案1类似，但在做完hash，分成多个⽂件后，可以交给多个⽂件来处理，采⽤分布式的架构来处理(⽐如MapReduce)，最后再进⾏合并。
5、给定a、b两个⽂件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你出a、b⽂件共同的url?
⽅案1：可以估计每个⽂件安的⼤⼩为5G×64=320G，远远⼤于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分⽽治之的⽅法。
遍历⽂件a，对每个url求取hash(url)00，然后根据所取得的值将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：如果允许有⼀定的错误率，可以使⽤Bloom filter，4G内存⼤概可以表⽰340亿bit。将其中⼀个⽂件中的url使⽤Bloom filter映射为这340亿bit，然后挨个读取另外⼀个⽂件的url，检查是否与Bloomfilter，如果是，那么该url应该是共同的url(注意会有⼀定的错误率)。
6、在2.5亿个整数中出不重复的整数，注，内存不⾜以容纳这2.5亿个整数。
⽅案1：采⽤2-Bitmap(每个数分配2bit，00表⽰不存在，01表⽰出现⼀次，10表⽰多次，11⽆意义)进⾏，共需内存2^32 * 2 bit=1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位
是01的整数输出即可。
⽅案2：也可采⽤与第1题类似的⽅法，进⾏划分⼩⽂件的⽅法。然后在⼩⽂件中出不重复的整数，并排序。然后再进⾏归并，注意去除重复的元素。
7、腾讯⾯试题：给40亿个不重复的unsigned
int的整数，没排过序的，然后再给⼀个数，如何快速判断这个数是否在那40亿个数当中?
与上第6题类似，我的第⼀反应时快速排序+⼆分查。以下是其它更好的⽅法：
⽅案1：oo，申请512M的内存，⼀个bit位代表⼀个unsigned int值。读⼊40亿个数，设置相应的bit位，读⼊要查询的数，查看相应bit位是否为1，为1表⽰存在，为0表⽰不存在。
⽅案2：这个问题⼤家可以参考下⾯的思路，探讨⼀下：
⼜因为2^32为40亿多，所以给定⼀个数可能在，也可能不在其中;
这⾥我们把40亿个数中的每⼀个⽤32位的⼆进制来表⽰
假设这40亿个数开始放在⼀个⽂件中。
然后将这40亿个数分成两类:
1.最⾼位为0
2.最⾼位为1
并将这两类分别写⼊到两个⽂件中，其中⼀个⽂件中数的个数<=20亿，⽽另⼀个>=20亿(这相当于折半了);
与要查的数的最⾼位⽐较并接着进⼊相应的⽂件再查
再然后把这个⽂件为⼜分成两类:
1.次最⾼位为0
2.次最⾼位为1
并将这两类分别写⼊到两个⽂件中，其中⼀个⽂件中数的个数<=10亿，⽽另⼀个>=10亿(这相当于折半了);
与要查的数的次最⾼位⽐较并接着进⼊相应的⽂件再查。
…….
以此类推，就可以到了,⽽且时间复杂度为O(logn)，⽅案2完。
附：这⾥，再简单介绍下，位图⽅法：
使⽤位图法判断整形数组是否存在重复
判断集合中存在重复是常见编程任务之⼀，当集合中数据量⽐较⼤时我们通常希望少进⾏⼏次扫描，这时双重循环法就不可取了。
位图法⽐较适合于这种情况，它的做法是按照集合中最⼤元素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)。
最后祝福所有遇到瓶颈的⼤数据程序员们突破⾃⼰，祝福⼤家在往后的⼯作与⾯试中⼀感谢您的观看，如有不⾜之处，欢迎批评指正。最后祝福所有遇到瓶颈的⼤数据程序员们突破⾃⼰，祝福⼤家在
往后的⼯作与⾯试中⼀感谢您的观看，如有不⾜之处，欢迎批评指正。
切顺利。