(一)海量日记数据，提掏出某日拜访百度次数最多的那个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)%1024值，把海量IP日记分别存储到1024个小文件中。如许，每个小文件最多包含4MB个IP地址;
3. 对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址;
4. 可以获得1024个小文件中的出现次数最多的IP，再根据惯例的排序算法获得总体上出现次数最多的IP;

(二)搜刮引擎会经由过程日记文件把用户每次检索应用的所有检索串都记录下来，每个萌芽串的长度为1-255字节。

对每个小文件，统计每个文件中出现的词以及响应的频率(可以采取trie树/hash_map等)，并掏出出现频率最大年夜的100个词(可以用含100个结 点的最小堆)，并把100个词及响应的频率存入文件，如许又获得了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

假设今朝有一切切个记录(这些萌芽串的反复度比较高，固然总数是1切切，但如不雅除去反复后，不跨越3百万个。一个萌芽串的反复度越高，解释萌芽它的用户越多，也就是越热点。)，请你统计最热点的10个萌芽串，请求应用的内存不克不及跨越1G。

文中，给出的最终算法是：

第一步、先对这批海量数据预处理，在O(N)的时光内用Hash表完成统计;

第二步、借助堆这个数据构造，找出Top K，时光复杂度为N‘logK。

或者：采取trie树，关键字域存该萌芽串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

(三)有一个1G大年夜小的一个文件，琅绫擎每一行是一个词，词典大年夜小不跨越16字节，内存限制大年夜小是1M。返回频数最高的100个词。

筹划：次序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件(记为x0,x1,…x4999)中。如许每个文件大年夜概是200k阁下。

如不雅个中的有的文件跨越了1M大年夜小，还可以按照类似的办法持续往下分，直到分化获得的小文件的大年夜小都不跨越1M。

(四)有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)，最后再进行归并。

(五)给定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。

假设这40亿个数开端放在一个文件中。

求每对小文件中雷同的url时，可以把个一一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如不雅是，那么就是合营的url，存到文件琅绫擎就可以了。

筹划2：如不雅许可有必定的缺点率，可以应用Bloom filter，4G内存大年夜概可以表示340亿bit。将个一一个文件中的url应用Bloom filter映射为这340亿bit，然后挨个攫取别的一个文件的url，检查是否与Bloom filter，如不雅是，那么该url应当是合营的url(注领悟有必定的缺点率)。

(六)在2.5亿个整数中找出不反复的┞符数，注，内存不足以容纳这2.5亿个整数。

即，借助堆构造，我们可以在log量级的时光内查找和调剂/移动。是以，保护一个K(该标题中是10)大年夜小的小根堆，然后遍历300万的Query，分别 和根元素进行比较所以，我们最终的时光复杂度是：O(N)+ N’*O(logK)，(N为1000万，N’为300万)。ok，更多，详情，请参考原文。

筹划1：采取2-Bitmap(每个数分派2bit，00表示不存在，01表示出现一次，10表示多次，11无意义)进行，共需内存2^32 * 2 bit=1 GB内存，还可以接收。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如不雅是00变01，01变10，10保持不变。所描完过后，查看bitmap，把对应位是01的┞符数输出即可。

　　推荐阅读

　　Tier5 新标准？别闹了，亲

由此可见，并不是随便哪家机构推出一种新的标准就可以代替Tier的。这套认证体系本身的贸易化运作已经异常成熟>>>详细阅读

本文标题：10道Hadoop面试真题及解题思路

地址：http://www.17bianji.com/lsqh/37668.html

 1/2    1