第4部分 解答题

第4部分

4.1 Hadoop解答题

4.1.1 MapReduce编程题

1. 当前日志采样格式为，请用你最熟悉的语言编写一个 mapreduce，并计算第四列每个元素出现的个数。

1. a,b,c,d

2. b,b,f,e

3. a,a,c,f

2. 给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？

解答：

方案 1：将大文件分成能够被内存加载的小文件。

可以估计每个文件安的大小为 50G×64=320G，远远大于内存限制的 4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

s 遍历文件 a，对每个 url 求取 ，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 ）中。

这样每个小文件的大约为 300M。

s 遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 各小文件（记为 ）。这样处理后，所有可能相同的 url 都在对应的小文件（ ）中，不对应的小文件不可能有相同的 url。然后我们只要求出 1000 对小文件中相同的 url 即可。

s 求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hash_set 中，如果是，那么就是共同的 url，存到文件里面就可以了。

方案 2：内存映射成 BIT 最小存储单元。

如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该 url 应该是共同的 url（注意会有一定的错误率）。

3. 有 10 个文件，每个文件 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求你按照query 的频度排序。

解答：

方案 1：

s 顺序读取 10 个文件，按照 hash(query)%10 的结果将 query 写入到另外 10 个文件（记为 ）中。这样新生成的文件每个的大小大约也 1G（假设 hash 函数是随机的）。

s 找一台内存在 2G 左右的机器，依次对 用 hash_map(query, query_count)来统计每个 query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_cout 输出到文件中。这样得到了 10 个排好序的文件（记为 ）。

s 对 这 10 个文件进行归并排序（内排序与外排序相结合）。

方案 2：

一般 query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的 query，一次性就可以加入到内存了。这样，我们就可以采用 trie 树/hash_map 等直接来统计每个 query 出现的次数，然后按出现

次数做快速/堆/归并排序就可以了。

方案 3：

与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处

理（比如 MapReduce），最后再进行合并。

//一般在大文件中找出出现频率高的，先把大文件映射成小文件，模 1000，在小文件中找到高频的

4. 有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。

解答：

方案 1：顺序读文件中，对于每个词 x，取 ，然后按照该值存到 5000 个小文件（记为 ）中。这样每个文件大概是 200k 左右。如果其中的有的文件超过了 1M 大小，还可以按照类似的方法继续往下分，知道分解得到的小文件的大小都不超过 1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用 trie 树/hash_map 等），并取出出现频率最大的 100 个词（可以用含 100 个结 点的最小堆），并把 100词及相应的频率存入文件，这样又得到了 5000 个文件。下一步就是把这 5000 个文件进行归并（类似与归并排序）的过程了。

方案2:

1. 将文件逐行读写到另一个文件中，并将每行单词全变成小写

2. 十六次循环执行，将每行单词按照a-z写到不同文件里

3. 最后相同的单词都写在了通一个文件里

4. 再将文件读写到各自另一个文件里，内容是“单词 个数”

5. 定义一个treemap，大小是100，依次插入大的，移除小的

6. 最后得出结果

5. 海量日志数据，提取出某日访问百度次数最多的那个 IP。

解答：

1. 先根据日期在日志文件中提取出ip，根据ip哈希进行分写N个文件。

2. 采用mapreduce的word cont

方案 1：首先是这一天，并且是访问百度的日志中的 IP 取出来，逐个写入到一个大文件中。注意到 IP是 32 位的，最多有 个 IP。同样可以采用映射的方法，比如模 1000，把整个大文件映射为 1000 个小文件，再找出每个小文中出现频率最大的 IP（可以采用 hash_map 进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这 1000 个最大的 IP 中，找出那个频率最大的 IP，即为所求。

6. 在 2.5 亿个整数中找出不重复的整数，内存不足以容纳这 2.5 亿个整数。

解答：

方案 1：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意义）进 行，共需内存 内存，还可以接受。然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是00 变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。

方案 2：也可采用上题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

方案3：

1. 将2.5亿个整数重写到一个文件里，内个整数占一行。

2. 进行对半排序重写到新的文件里，这样最后2.5亿个整数在文件里便是有序的了

3. 读取文本，将不重复的写到一个新的文件里即可。

7. 海量数据分布在 100 台电脑中，想个办法高校统计出这批数据的 TOP10。

解答：

方案 1：（方法不正确，取出来得不一定是top10）

s 在每台电脑上求出 TOP10，可以采用包含 10 个元素的堆完成（TOP10 小，用最大堆，TOP10 大，用最小堆）。比如求 TOP10 大，我们首先取前 10 个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元 素就是 TOP10 大。

s 求出每台电脑上的 TOP10 后，然后把这 100 台电脑上的 TOP10 组合起来，共 1000 个数据，再利用上面类似的方法求出 TOP10 就可以了。

8. 怎么在海量数据中找出重复次数最多的一个？

解答：

方案 1：（同上，方法错误）

先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

正确的方法，先排除

9. 上千万或上亿数据（有重复），统计其中出现次数最多的前 N 个数据。

解答：

10. 1000 万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

解答：

11. 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析。

解答：

方案 1：这题是考虑时间效率。用 trie 树统计每个词出现的次数，时间复杂度是 O(n*le)（le 表示单词的平准长 度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是 O(n*lg10)。所以总的时间复杂度，是 O(n*le)与 O(n*lg10)中较大的哪一个。

12. 一个文本文件，找出前 10 个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。

解答：

13. 100w 个数中找出最大的 100 个数。

解答：

14.

15. D

16. D

17. D

第5部分 处理海量数据问题之六把密匙

第5部分

5.1 密匙一、分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序

1、海量日志数据，提取出某日访问百度次数最多的那个IP。

既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：

1. 分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决

2. hash统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。

3. 堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。

具体而论，则是： “首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方 法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率 最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”--十道海量数据处理面试题与十个方法大总结。

注：Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是mod1000算法，那么相同的IP在hash后，只可能落在同一个文件中，不可能被分散的。

那到底什么是hash映射呢？我换个角度举个浅显直白的例子，如本文的URL是：http://blog.csdn.net/v_july_v/article/details/7382693，当我把这个URL发表在微博上，便被映射成了：http://t.cn/zOixljh，于此，我们发现URL本身的长度被缩短了，但这两个URL对应的文章的是同一篇即本文。OK，有兴趣的，还可以再了解下一致性hash算法，见此文第五部分：http://blog.csdn.net/v_july_v/article/details/6879101。

2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。

假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

由上面第1题，我们知道，数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢?比如这第2题，虽然有一千万个Query，但是由于重复度比较 高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在 这里，Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。So，

1. hash 统计：先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable，即 hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该 字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；

2. 堆排序：第二步、借助堆 这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍 历300万的Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N为1000万，N’为300万）。

别忘了这篇文章中所述的堆排序思路：“维 护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k），并调整堆（费时O（logk））后， 有k1>k2>...kmin（kmin设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若 x>kmin，则更新堆（用时logk），否则不更新堆。这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。此方法 得益于在堆中，查找等各项操作时间复杂度均为logk。”--第三章续、Top K算法问题的实现。

当然，你也可以采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

由上面那两个例题，分而治之 + hash统计 + 堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下面，再拿几道再多多验证下。请看此第3题：又是文件很大，又是内存受限，咋办?还能怎么办呢?无非还是：

1. 分 而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为 x0,x1,...x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到 的小文件的大小都不超过1M。

2. hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。

3. 堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

4、海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

此题与上面第3题类似，

1. 堆排序：在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大。

2. 求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

上述第4题的此解法，经读者反应有问题，如举个例子如比如求2个文件中的top2，照你这种算法，如果第一个文件里有

a 49次

b 50次

c 2次

d 1次

第二个文件里有

a 9次

b 1次

c 11次

d 10次

虽然第 一个文件里出来top2是b（50次）,a（49次）,第二个文件里出来top2是c（11次）,d（10次）,然后2个top2：b（50次）a（49 次）与c（11次）d（10次）归并，则算出所有的文件的top2是b(50 次),a(49 次),但实际上是a(58 次),b(51 次)。是否真是如此呢?若真如此，那作何解决呢？

正如老梦所述：

首先，先把所有的数据遍历一遍做一次hash(保证相同的数据条目划分到同一台电脑上进行运算)，然后根据hash结果重新分布到100台电脑中，接下来的算法按照之前的即可。

最后由于a可能出现在不同的电脑，各有一定的次数，再对每个相同条目进行求和（由于上一步骤中hash之后，也方便每台电脑只需要对自己分到的条目内进行求和，不涉及到别的电脑，规模缩小）。

5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

直接上：

1. hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。

2. hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。

3. 堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。对这10个文件进行归并排序（内排序与外排序相结合）。

除此之外，此题还有以下两个方法：

方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

方案3：与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

1. 分而治之/hash映射：遍历文件a，对每个url求取 ，然后根据所取得的值将url分别存储到1000个小文件（记为）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（ ）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

2. hash统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

OK，此第一种方法：分而治之/hash映射 + hash统计 + 堆/快速/归并排序，再看最后三道题，如下：

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)中较大的 哪一个。

接下来，咱们来看第二种方法，双层捅划分。

5.2 密匙二、双层桶划分

双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！

适用范围：第k大，中位数，不重复或重复的数字

基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。

扩展：

问题实例：

10、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。

11、5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数 落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是 int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区 域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

5.3 密匙三：Bloom filter/Bitmap

Bloom filter

关于什么是Bloom filter，请参看此文：海量数据处理之Bloom Filter详解。

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：

对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明 显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进 就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何 根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下，m 至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，因为还要保证bit数组里至少一半为0，则m应该>=nlg(1 /E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。

举个例子我们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。

注意这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。

扩展：

Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

12、给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，如果按出错率0.01算需要的大概是650亿个 bit。现在可用的是340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。

同时，上文的第5题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？如果允许有 一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

Bitmap

至于什么是Bitmap，请看此文：http://blog.csdn.net/v_july_v/article/details/6685962。下面关于Bitmap的应用，直接上题，如下第9、10道：

13、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看 bitmap，把对应位是01的整数输出即可。

方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

14、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

方案1：frome oo，用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

5.4 密匙四、Trie树/数据库/倒排索引

Trie树

适用范围：数据量大，重复多，但是数据种类小可以放入内存

基本原理及要点：实现方式，节点孩子的表示方式

扩展：压缩实现。

问题实例：

1. 有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。

2. 1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

3. 寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。

4. 上面的第8题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。

更多有关Trie树的介绍，请参见此文：从Trie树（字典树）谈到后缀树。

数据库索引

适用范围：大数据量的增删改查

基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

关于数据库索引及其优化，更多可参见此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html。同时，关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章：http://www.codinglabs.org/html/theory-of-mysql-index.html。

倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询

基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

　以英文为例，下面是要被索引的文本：

T0 = "it is what it is"

T1 = "what is it"

T2 = "it is a banana"

我们就能得到下面的反向文件索引：

"a": {2}

"banana": {2}

"is": {0, 1, 2}

"it": {0, 1, 2}

"what": {0, 1}

　检索的条件"what","is"和"it"将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索 引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档， 很容易看到这个反向的关系。

扩展：

问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

关于倒排索引的应用，更多请参见：第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践，及第二十六章：基于给定的文档生成倒排索引的编码与实践。

5.5 密匙五、外排序

适用范围：大数据的排序，去重

基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树

扩展：

问题实例：

1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。

关于多路归并算法及外排序的具体应用场景，请参见此文：第十章、如何给10^7个数据量的磁盘文件排序。

5.6 密匙六、分布式处理之Mapreduce

适用范围：数据量大，但是数据种类小可以放入内存

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。

扩展：

问题实例：

1. The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:

2. 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

3. 一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？

更多具体阐述请参见：从Hadhoop框架与MapReduce模式中谈海量数据处理，及MapReduce技术的初步了解与学习。

的

18.

19. 的

第6部分 设计题

5.7 日志收集分析系统

1. 日志分布在各个业务系统中，我们需要对当天的日志进行实时汇总统计，同时又能离线查询历史的汇总数据（PV、UV、IP）

解答：

1、通过flume将不同系统的日志收集到kafka中

2、通过storm实时的处理PV、UV、IP

3、通过kafka的consumer将日志生产到hbase中。

4、通过离线的mapreduce或者hive，处理hbase中的数据

2. Hive语言实现word count

解答：

1.建表

2.分组（group by）统计wordcount

select word,count(1) from table1 group by word;

3. 实时数据统计会用到哪些技术，他们各自的应用场景及区别是什么?

解答：

flume：日志收集系统，主要用于系统日志的收集

kafka：消息队列，进行消息的缓存和系统的解耦

storm：实时计算框架，进行流式的计算。

4. 的

5. 的

6. 的

5.8 MapReduce

1. 有两个文本文件，文件中的数据按行存放，请编写MapReduce程序，找到两个文件中彼此不相同的行（写出思路即可）

解答：

写个mapreduce链 用依赖关系，一共三个mapreduce，第一个处理第一个文件，第二个处理第二个文件，第三个处理前两个的输出结果，第一个mapreduce将文件去重，第二个mapreduce也将文件去重，第三个做wordcount，wordcount为1的结果就是不同的

2. 共同朋友

1. A B CD E F

2. B A CD E

3. C A B E

4. D B E

5. E A BC D

6. F A

第一个字母表示本人，其他事他的朋友，找出有共同朋友的人，和共同的朋友是谁

解答：

思路：例如A，他的朋友是B\C\D\E\F\，那么BC的共同朋友就是A。所以将BC作为key，将A作为value，在map端输出即可！其他的朋友循环处理。

import java.io.IOException;

import java.util.Set;

import java.util.StringTokenizer;

import java.util.TreeSet;

import org.apache.hadoop.conf.Configuration;

import org.apache.hadoop.fs.Path;

import org.apache.hadoop.io.Text;

import org.apache.hadoop.mapreduce.Job;

10. import org.apache.hadoop.mapreduce.Mapper;

11. import org.apache.hadoop.mapreduce.Reducer;

12. import org.apache.hadoop.mapreduce.Mapper.Context;

13. import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;

14. import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;

15. import org.apache.hadoop.util.GenericOptionsParser;

public class FindFriend {

public static class ChangeMapper extends Mapper<Object, Text, Text,

Text>{

@Override

public void map(Object key, Text value, Context context) throws

IOException, InterruptedException {

StringTokenizer itr = new StringTokenizer(value.toString());

Text owner = new Text();

Set<String> set = new TreeSet<String>();

owner.set(itr.nextToken());

while (itr.hasMoreTokens()) {

set.add(itr.nextToken());

}

String[] friends = new String[set.size()];

friends = set.toArray(friends);

for(int i=0;i<friends.length;i++){

for(int j=i+1;j<friends.length;j++){

String outputkey = friends[i]+friends[j];

context.write(new Text(outputkey),owner);

}

}

}

}

public static class FindReducer extends Reducer<Text,Text,Text,Text>

{

public void reduce(Text key, Iterable<Text> values,

Context context) throws IOException,

InterruptedException {

String commonfriends ="";

for (Text val : values) {

if(commonfriends == ""){

commonfriends = val.toString();

}else{

commonfriends =

commonfriends+":"+val.toString();

}

}

context.write(key, new

Text(commonfriends));

}

}

public static void main(String[] args) throws IOException,

InterruptedException, ClassNotFoundException {

Configuration conf = new Configuration();

String[] otherArgs = new GenericOptionsParser(conf, args).getRemainingArgs();

if (otherArgs.length < 2) {

System.err.println("args error");

System.exit(2);

}

Job job = new Job(conf, "word count");

job.setJarByClass(FindFriend.class);

job.setMapperClass(ChangeMapper.class);

job.setCombinerClass(FindReducer.class);

job.setReducerClass(FindReducer.class);

job.setOutputKeyClass(Text.class);

job.setOutputValueClass(Text.class);

for (int i = 0; i < otherArgs.length - 1; ++i) {

FileInputFormat.addInputPath(job, new Path(otherArgs[i]));

}

FileOutputFormat.setOutputPath(job,

new Path(otherArgs[otherArgs.length - 1]));

System.exit(job.waitForCompletion(true) ? 0 : 1);

}

}

结果：

1. AB E:C:D

2. AC E:B

3. AD B:E

4. AE C:B:D

5. BC A:E

6. BD A:E

7. BE C:D:A

8. BF A

9. CD E:A:B

10. CE A:B

11. CF A

12. DE B:A

13. DF A

14. EF A

3. 的

4. 的

5. 的

6. 的

5.9 优化

1. 如果要存储海量的小文件（大小都是几百K-几M）请简述自己的设计方案

解答：

1.将小文件打成har文件存储

2.将小文件序列化到hdfs中

2.

3. 的

第7部分 涉及Java基础部分

1. ArrayList、Vector、LinkedList的区别及其优缺点？HashMap、HashTable的区别及优缺点？

解答：

ArrayList 和Vector是采用数组方式存储数据的,是根据索引来访问元素的，都可以根据需要自动扩展内部数据长度，以便增加和插入元素，都允许直接序号索引元素，但是插入数据要涉及到数组元素移动等内存操作，所以索引数据快插入数据慢，他们最大的区别就是synchronized同步的使用。

LinkedList使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作，最好选择LinkedList

HashMap、HashTable的区别及其优缺点：

HashTable 中的方法是同步的 HashMap的方法在缺省情况下是非同步的 因此在多线程环境下需要做额外的同步机制。

HashTable不允许有null值 key和value都不允许，而HashMap允许有null值 key和value都允许 因此HashMap 使用containKey（）来判断是否存在某个键。

HashTable 使用Enumeration ，而HashMap使用iterator。

Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类。

2. 的

3. 的

第8部分 十道海量数据处理面试题

第6部分

第7部分

第8部分

8.1 海量日志数据，提取出某日访问百度次数最多的那个 IP 。

此题，在我之前的一篇文章算法里头有所提到，当时给出的方案是：IP 的数目还是有限的，最多 2^32个，所以可以考虑使用 hash 将 ip 直接存入内存，然后进行统计。再详细介绍下此方案：首先是这一天，并且是访问百度的日志中的 IP 取出来，逐个写入到一个大文件中。注意到 IP 是 32 位的，最多有个 2^32 个 IP。同样可以采用映射的方法，比如模 1000，把整个大文件映射为 1000 个小文件，再找出每个小文中出现频率最大的 IP（可以采用 hash_map 进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这 1000 个最大的 IP 中，找出那个频率最大的 IP，即为所求。

8.2 2 、搜 索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255 字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是 1 千万，但如果除去重复后，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10 个查询串，要求使用的内存不能超过 1G。

典型的 Top K 算法，还是在这篇文章里头有所阐述。文中，给出的最终算法是：第一步、先对这批海量数据预处理，在 O（N）的时间内用 Hash 表完成排序；然后，第二步、借助堆这个数据结构，找出 TopK，时间复杂度为 N‗logK。即，借助堆结构，我们可以在 log 量级的时间内查找和调整/移动。因此，维护一个 K(该题目中是 10)大小的小根堆，然后遍历 300 万的 Query，分别和根元素进行对比所以，我们最终的时间复杂度是：O（N） + N'*O（logK），（N 为 1000 万，N‘为 300 万）。ok，更多，详情，请参考原文。或者：采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 10 个元素的最小推来对出现频率进行排序。

8.3 有一个 1G 过 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是

1M 。返回频数最高的 100 个词。方案：顺序读文件中，对于每个词 x，取 hash(x)%5000，然后按照该值存到 5000 个小文件（记为

www.aboutyun.com

x0,x1,...x4999）中。这样每个文件大概是 200k 左右。如果其中的有的文件超过了 1M 大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过 1M。 对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用 trie 树/hash_map等），并取出出现频率最大的 100 个词（可以用含 100 个结点的最小堆），并把 100 个词及相应的频率存入文件，这样又得到了 5000个文件。下一步就是把这 5000 个文件进行归并（类似与归并排序）的过程了。

8.4 4 有 10 个文件 件，每个文件 1G ，每个文件的每一行存放的都是用户的 query ，每个文件的 query照 都可能重复。

要求你按照 query 的频度排序。还是典型的 TOP K 算法，解决方案如下：

方案 1：顺序读取 10 个文件，按照 hash(query)%10 的结果将 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），最后再进行合并。

8.5 5、 给定 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）中，不对应的小文件不可能有相

www.aboutyun.com

同的 url。然后我们只要求出 1000 对小文件中相同的 url 即可。

求每对小文件中相同的 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 内详细阐述。

8.6 在 2.5 亿个整数中找出不重复的整数，注，内存不足以容纳这 2.5 亿个整数。

方案 1：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意

义）进行，共需内存内存，还可以接受。然后扫描这2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00

变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。

方案 2：也可采用与第 1 题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，

并排序。然后再进行归并，注意去除重复的元素。

8.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 完。

附：这里，再简单介绍下，位图方法： 使用位图法判断整形数组是否存在重复判断集合中存在重复

是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取

了。

位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，

然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到 5 就给新数组的第六个元素置 1，这样下

次再遇到 5 想置位时发现新数组的第六个元素已经是 1 了，这说明这次的数据肯定和以前的数据存在着重

复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的

情况为 2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

8.8 8 、怎么在海量数据中找出重复次数最多的一个？

方案 1：先做 hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。

然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

8.9 9 、上千万或上亿数据（有重复），统计其中出现次数最多的钱 N 个数据。

方案 1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用 hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前 N 个出现次数最多的数据了，可以用第 2 题提到的堆机制完成。

8.1010 、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前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)。

第9部分 遗留

311、在线安装ssh的命令以及文件解压的命令？

312、把公钥都追加到授权文件的命令？该命令是否在root用户下执行？

313、HadoopHA集群中，各个服务的启动和关闭的顺序？

314、HDFS中的block块默认保存几份？默认大小多少？

315、NameNode中的meta数据是存放在NameNode自身，还是DataNode等其他节点？DatNOde节点自身是否有Meta数据存在？

316、下列那个程序通常与NameNode在一个节点启动？

317、下面那个程序负责HDFS数据存储？

318、 在HadoopHA集群中，简述Zookeeper的主要作用，以及启动和查看状态的命令？

319、HBase在进行模型设计时重点在什么地方？一张表中国定义多少个Column　Family最合适？为什么？

320、如何提高HBase客户端的读写性能？请举例说明。

321、基于HadoopHA集群进行MapReduce开发时，Configuration如何设置hbase.zookeeper,quorum属性的值？

322、 在hadoop开发过程中使用过哪些算法？其应用场景是什么？

323、MapReduce程序如何发布？如果MapReduce中涉及到了第三方的jar包，该如何处理？

324、在实际工作中使用过哪些集群的运维工具，请分别阐述其作用。

325、hadoop中combiner的作用?

326、IO的原理，IO模型有几种?

327、Windows用什么样的模型，Linux用什么样的模型？

328、一台机器如何应对那么多的请求访问，高并发到底怎么实现，一个请求怎么产生的，

在服务端怎么处理的，最后怎么返回给用户的，整个的环节操作系统是怎么控制的？

329、hdfs的client端，复制到第三个副本时宕机，hdfs怎么恢复保证下次写第三副本?block块信息是先写dataNode还是先写nameNode?

330、快排现场写程序实现？

331、jvm的内存是怎么分配原理？

332、毒酒问题---1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。问最少需要多少只老鼠可在一周内找出毒酒？

333、用栈实现队列？

334、链表倒序实现？

335、多线程模型怎样（生产，消费者）？平时并发多线程都用哪些实现方式？

336、synchonized是同步悲观锁吗？互斥？怎么写同步提高效率？

337、4亿个数字，找出哪些重复的，要用最小的比较次数，写程序实现。

338、java是传值还是传址？

339、 java处理多线程，另一线程一直等待？

340、一个网络商城1天大概产生多少G的日志？

341、大概有多少条日志记录（在不清洗的情况下）？

342、日访问量大概有多少个？

343、注册数大概多少？

344、我们的日志是不是除了apache的访问日志是不是还有其他的日志？

345、假设我们有其他的日志是不是可以对这个日志有其他的业务分析？这些业务分析都有什么？

346、问：你们的服务器有多少台？

347、问：你们服务器的内存多大？

348、问：你们的服务器怎么分布的？（这里说地理位置分布，最好也从机架方面也谈谈）

349、问：你平常在公司都干些什么（一些建议）

350、hbase怎么预分区？

351、hbase怎么给web前台提供接口来访问（HTABLE可以提供对HTABLE的访问，但是怎么查询同一条记录的多个版本数据）？

352、.htable API有没有线程安全问题，在程序中是单例还是多例？

353、我们的hbase大概在公司业务中（主要是网上商城）大概都几个表，几个表簇，大概都存什么样的数据？

354、hbase的并发问题？

Storm问题：

355、metaq消息队列 zookeeper集群 storm集群（包括zeromq,jzmq,和storm本身）就可以完成对商城推荐系统功能吗？还有没有其他的中间件？

356、storm怎么完成对单词的计数？（个人看完storm一直都认为他是流处理，好像没有积攒数据的能力，都是处理完之后直接分发给下一个组件）

357、storm其他的一些面试经常问的问题？

二十三、面试题（18道）：

358、你们的集群规模？

开发集群：10台（8台可用）8核cpu

359、你们的数据是用什么导入到数据库的？导入到什么数据库？

处理之前的导入：通过hadoop命令导入到hdfs文件系统

处理完成之后的导出：利用hive处理完成之后的数据，通过sqoop导出到mysql数据库中，以供报表层使用。

360、你们业务数据量多大？有多少行数据？(面试了三家，都问这个问题)

开发时使用的是部分数据，不是全量数据，有将近一亿行（8、9千万，具体不详，一般开发中也没人会特别关心这个问题）

361、你们处理数据是直接读数据库的数据还是读文本数据？

将日志数据导入到hdfs之后进行处理

362、你们写hive的hql语句，大概有多少条？

不清楚，我自己写的时候也没有做过统计

363、你们提交的job任务大概有多少个？这些job执行完大概用多少时间？(面试了三家，都问这个问题)

没统计过，加上测试的，会与很多

364、hive跟hbase的区别是？

365、你在项目中主要的工作任务是？

利用hive分析数据

366、你在项目中遇到了哪些难题，是怎么解决的？

某些任务执行时间过长，且失败率过高，检查日志后发现没有执行完就失败，原因出在hadoop的job的timeout过短（相对于集群的能力来说），设置长一点即可

367、你自己写过udf函数么？写了哪些？

这个我没有写过

368、你的项目提交到job的时候数据量有多大？(面试了三家，都问这个问题)

不清楚是要问什么

369、reduce后输出的数据量有多大？

370、一个网络商城1天大概产生多少G的日志？ 4tb

371、大概有多少条日志记录（在不清洗的情况下）？ 7-8百万条

372、日访问量大概有多少个？百万

373、注册数大概多少？不清楚几十万吧

374、我们的日志是不是除了apache的访问日志是不是还有其他的日志？关注信息

375、假设我们有其他的日志是不是可以对这个日志有其他的业务分析？这些业务分析都有什么？

二十四、面试题(1道)：

376、有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。

请用5分钟时间，找出重复出现最多的前10条。

分析：

常规方法是先排序，在遍历一次，找出重复最多的前10条。但是排序的算法复杂度最低为nlgn。

可以设计一个hash_table,hash_map<string, int>，依次读取一千万条短信，加载到hash_table表中，并且统计重复的次数，与此同时维护一张最多10条的短信表。

这样遍历一次就能找出最多的前10条，算法复杂度为O(n)。

二十五、面试题（5道）：

377、job的运行流程(提交一个job的流程)？

378、Hadoop生态圈中各种框架的运用场景？

379、hive中的压缩格式RCFile、TextFile、SequenceFile各有什么区别？

以上3种格式一样大的文件哪个占用空间大小.还有Hadoop中的一个HA压缩。

380、假如：Flume收集到的数据很多个小文件,我需要写MR处理时将这些文件合并

(是在MR中进行优化,不让一个小文件一个MapReduce)

他们公司主要做的是中国电信的流量计费为主,专门写MR。

383、解释“hadoop”和“hadoop生态系统”两个概念。

384、说明Hadoop 2.0的基本构成。

385、相比于HDFS1.0, HDFS 2.0最主要的改进在哪几方面？

386、试使用“步骤1，步骤2，步骤3…..”说明YARN中运行应用程序的基本流程。

387、“MapReduce 2.0”与“YARN”是否等同，尝试解释说明。

388、MapReduce 2.0中，MRAppMaster主要作用是什么，MRAppMaster如何实现任务容错的？

389、为什么会产生yarn,它解决了什么问题，有什么优势？

397、Hadoop体系结构（HDFS与MapReduce的体系结构）、Hadoop相比传统数据存储方式（比如mysql）的优势？

398、Hadoop集群的搭建步骤、Hadoop集群搭建过程中碰到了哪些常见问题（比如datanode没有起来）、Hadoop集群管理（如何动态增加和卸载节点、safe mode是什么、常用的命令kill等）？

399、HDFS的namenode与secondarynamenode的工作原理（重点是日志拉取和合并过程）、hadoop 1.x的HDFS的HA方案（namenode挂掉的情况如何处理、datanode挂掉的情况如何处理）？

400、HDFS的常用shell命令有哪些？分别对应哪些Client Java API？：显示文件列表、创建目录、文件上传与下载、文件内容查看、删除文件

401、HDFS的文件上传与下载底层工作原理（或HDFS部分源码分析）：FileSystem的create()和open()方法源码分析？

402、MapReduce计算模型、MapReduce基础知识点（MapReduce新旧API的使用、在linux命令行运行MapReduce程序、自定义Hadoop数据类型）？

403、MapReduce执行流程：“天龙八步”，计数器、自定义分区、自定义排序、自定义分组、如何对value进行排序：次排序+自定义分组、归约？

404、MapReduce的shuffle工作原理、MapReduce工作原理（MapReduce源码、InputStream源码、waitForCompletion()源码）、jobtracker如何创建map任务和reduce任务是面试的重点。

405、MapReduce进阶知识：Hadoop的几种文件格式、常见输入输出格式化类、多输入多输出机制、MapReduce的常见算法（各种join原理和优缺点、次排序和总排序）？

406、MapReduce性能优化（shuffle调优、压缩算法、更换调度器、设置InputSplit大小减少map任务数量、map和reduce的slot如何设置、数据倾斜原理和如何解决）？

407、HBase的体系结构和搭建步骤、shell命令与Java API、HBase作为MapReduce的输入输出源、高级JavaAPI、工作原理（重点是combine和split原理）、行键设计原则、性能优化？

408、Hive的工作原理、两种元数据存放方式、几种表之间的区别、数据导入的几种方式、几种文件格式、UDF函数、性能调优（重点是join的时候如何放置大小表）？

409、Zookeeper、Flume、Pig、Sqoop的基本概念和使用方式，ZooKeeper被问到过其如何维护高可用（如果某个节点挂掉了它的处理机制）？

410、Hadoop2：体系结构、HDFS HA、YARN？

411、关系型数据库和非关系型数据库的区别？

提示：

关系型数据库通过外键关联来建立表与表之间的关系，非关系型数据库通常指数据以对象的形式存储在数据库中，而对象之间的关系通过每个对象自身的属性来决定。

对数据库高并发读写、高可扩展性和高可用性的需求，对海量数据的高效率存储和访问的需求，存储的结构不一样，非关系数据库是列式存储，在存储结构上更加自由。

412、hive的两张表关联，使用mapreduce是怎么写的？

提示：打标记笛卡尔乘积

413、hive相对于Oracle来说有那些优点？

提示：

hive是数据仓库，oracle是数据库，hive能够存储海量数据，hive还有更重要的作用就是数据分析，最主要的是免费。

414、现在我们要对Oracle和HBase中的某些表进行更新，你是怎么操作？

提示：

disable '表名'

alter '表明', NAME => '列名', VERSIONS=>3

enable '表名'

415、HBase接收数据，如果短时间导入数量过多的话就会被锁，该怎么办？ 集群数16台 ，高可用性的环境。

参考：

通过调用HTable.setAutoFlush(false)方法可以将HTable写客户端的自动flush关闭，这样可以批量写入数据到HBase，而不是有一条put就执行一次更新，只有当put填满客户端写缓存时，才实际向HBase服务端发起写请求。默认情况下auto flush是开启的。

416、说说你们做的hadoop项目流程？

417、你们公司的服务器架构是怎么样的（分别说下web跟hadoop）？

418、假如有1000W用户同时访问同一个页面，怎么处理？

提示：优化代码、静态化页面、增加缓存机制、数据库集群、库表散列。。。

419、怎样将mysql的数据导入到hbase中？不能使用sqoop，速度太慢了

提示：

A、一种可以加快批量写入速度的方法是通过预先创建一些空的regions，这样当数据写入HBase时，会按照region分区情况，在集群内做数据的负载均衡。

B、hbase里面有这样一个hfileoutputformat类，他的实现可以将数据转换成hfile格式，通过new 一个这个类，进行相关配置,这样会在hdfs下面产生一个文件，这个时候利用hbase提供的jruby的loadtable.rb脚本就可以进行批量导入。

420、在hadoop组中你主要负责那部分？

提示：负责编写mapreduce程序，各个部分都要参加

421、怎么知道hbase表里哪些做索引？哪些没做索引？

提示：

有且仅有一个：rowkey，所以hbase的快速查找建立在rowkey的基础的，而不能像一般的关系型数据库那样建立多个索引来达到多条件查找的效果。

422、hdfs的原理以及各个模块的职责

423、mapreduce的工作原理

424、map方法是如何调用reduce方法的

425、fsimage和edit的区别？

提示：fsimage：是存储元数据的镜像文件，而edit只是保存的操作日志。

426、hadoop1和hadoop2的区别？

提示：

（1） hdfs的namenode和mapreduce的jobtracker都是单点。

（2） namenode所在的服务器的内存不够用时，那么集群就不能工作了。

（3）mapreduce集群的资源利用率比较低。

单NN的架构使得HDFS在集群扩展性和性能上都有潜在的问题，在集群规模变大后，NN成为了性能的瓶颈。Hadoop 2.0里的HDFS Federation就是为了解决这两个问题而开发的。扩大NN容量，共享DN数据，且方便客户端访问。

427、hdfs中的block默认报错几份？

提示：3份

428、哪个程序通常与nn在一个节点启动？并做分析

提示：jobtrack，将两者放在一起，减少网络访问，IO访问的时间，提高了效率。

429、列举几个配置文件优化？

430、写出你对zookeeper的理解

提示：大部分分布式应用需要一个主控、协调器或控制器来管理物理分布的子进程（如资源、任务分配等）。目前，大部分应用需要开发私有的协调程序，缺乏一个通用的机制协调程序的反复编写浪费，且难以形成通用、伸缩性好的协调器。

ZooKeeper：提供通用的分布式锁服务，用以协调分布式应用。

431、datanode首次加入cluster的时候，如果log报告不兼容文件版本，那需要namenode执行格式化操作，这样处理的原因是？

提示：

这样处理是不合理的，因为那么namenode格式化操作，是对文件系统进行格式化，namenode格式化时清空dfs/name下空两个目录下的所有文件，之后，会在目录dfs.name.dir下创建文件。

文本不兼容，有可能时namenode 与 datanode 的 数据里的namespaceID、clusterID不一致，找到两个ID位置，修改为一样即可解决。

432、谈谈数据倾斜，如何发生的，并给出优化方案。

原因：

（1）key分布不均匀

（2）业务数据本身的特性

（3）建表时考虑不周

（4）某些SQL语句本身就有数据倾斜

map处理数据量的差异取决于上一个stage的reduce输出，所以如何将数据均匀的分配到各个reduce中，就是解决数据倾斜的根本所在。

优化：参数调节；

433、介绍一下HBase过滤器

434、mapreduce基本执行过程

435、谈谈hadoop1和hadoop2的区别

436、谈谈HBase集群安装注意事项？

提示：

需要注意的地方是 ZooKeeper的配置。这与 hbase-env.sh 文件相关，文件中HBASE_MANAGES_ZK 环境变量用来设置是使用hbase默认自带的 Zookeeper还是使用独立的ZooKeeper。HBASE_MANAGES_ZK=false时使用独立的，为true时使用默认自带的。

某个节点的HRegionServer启动失败，这是由于这3个节点的系统时间不一致相差超过集群的检查时间30s。da