筹划2：也可采取与第1题类似的办法，进行划分小文件的办法。然后在小文件中找出不反复的┞符数，并排序。然后再进行归并，留意去除反复的元素。
(七)给40亿个不反复的unsigned int的┞符数，没排过序的，然后再给一个数，若何快速断定这个数是否在那40亿个数傍边?
与上第6题类似，我的第一反竽暌功时快速排序+二分查找。以下是其它更好的办法：
筹划1：oo，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置响应的bit位，读入要萌芽的数，查看响应bit位是否为1，为1表示存在，为0表示不存在。
Bloom filter日后会在本BLOG内具体阐述。
筹划2：这个问题在《编程珠玑》里有很好的描述，大年夜家可以参考下面的思路，商量一下：
遍历文件b，采取和a雷同的方法将url分别存储到1000小文件(记为b0,b1,…,b999)。如许处理后，所有可能雷同的url都在对应的小 文件(a0vsb0,a1vsb1,…,a999vsb999)中，纰谬应的小文件弗成能有雷同的url。然后我们只请求出1000对小文件中雷同的url即可。
又因为2^32为40亿多，所以给定一个数可能在，也可能不在个中;
这里我们把40亿个数中的每一个用32位的二进制来表示
然后将这40亿个数分成两类:
- 最高位为0
- 最高位为1
并将这两类分别写入到两个文件中，个一一个文件中数的个数<=20亿，而另一个>=20亿(这相当于折半了);
与要查找的数的最高位比较并接着进入响应的文件再查找
再然后把这个文件为又分成两类:
- 次最高位为0
- 次最高位为1
并将这两类分别写入到两个文件中，个一一个文件中数的个数<=10亿，而另一个>=10亿(这相当于折半了);
与要查找的数的次最高位比较并接着进入响应的文件再查找。
…….
以词攀类推，就可以找到了,并且时光复杂度为O(logn)，筹划2完。
附：这里，再简单介绍下，位图办法：
应用位图法断定整形数组是否存在反复
断定集合中存在反复是常见编程义务之一，当集合中数据量比较大年夜时我们平日欲望少进行几回扫描，这时双重轮回法就弗采取了。
位图法比较合适于这种情况，它的做法是按照集合中最大年夜元素max创建一个长度为max+1的新数组，然后再次扫描原数组，碰到几就给新数组的第几地位上1，如碰到5就给新数组的第六个元素置1，如许下次再碰到5想置位时发明新数组的第六个元素已经是1了，这解释此次的数据肯定和以前的数据存在着反复。这种给新数组初始化时置零厥后置一的做法类似于位图的处理办法故称位图法。它的运算次数最坏的情况为2N。如不雅已知数组的最大年夜值即能事先给新数组定长的话效 率还能进步一倍。
(八)怎么在海量数据中找庄反复次数最多的一个?
筹划1：先做hash，然后求模映射为小文件，求出每个小文件中反复次数最多的一个，并记录反复次数。然后找出上一步求出的数据中反复次数最多的一个就是所求(具体参考前面的题)。
(九)上切切或上亿数据(有反复)，统计个中出现次数最多的钱N个数据。
典范的Top K算法，照样在这篇文┞仿里头有所阐述，详情请拜见：十一、大年夜头到尾彻调剂析Hash表算法。
筹划1：上切切或上亿的数据，如今的机械的内存应当能存下。所以推敲采取hash_map/搜刮二叉树/红黑树等来进行筒计ノ数。然后就是掏出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。
附赠：100w个数中找出最大年夜的100个数。
(十)一个文本文件，大年夜约有一万行，每行一个词，请求统计出个中最频繁出现的前10个词，请给出思惟，给出时光复杂度分析。
筹划1：这题是推敲时光效力。用trie树统计每个词出现的次数，时光复杂度是O(n*le)(le表示单词典平准长度)。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时光复杂度是O(n*lg10)。所以总的时光复杂度，是O(n*le)与O(n*lg10)中较大年夜的哪一个。
筹划1：在前面的题中，我们已经提到了，用一个含100个元素的最小堆完成。复杂度为O(100w*lg100)。
筹划2：采取快速排序的思惟，每次瓜分之后只推敲比轴大年夜的一部分，知道比轴大年夜的一部分在比100多的时刻，采取传统排序算法排序，取前100个。复杂度为O(100w*100)。
筹划3：采取局部镌汰法。拔取前100个元素，并排序，记为序列L。然后一次扫描残剩的元素x，与排好序的100个元素中最小的元素比，如不雅比这个最小的 要大年夜，那么把这个最小的元素删除，并把x应用插入排序的思惟，插入到序列L中。依次轮回，知道扫描了所有的元素。复杂度为O(100w*100)。
【编辑推荐】
- 克服安排挑衅，让Hadoop和云成为最佳拍档
- 分布式数据库和Hadoop都不敷好，于是我们设计分布式SQL计算体系
- 基于Hadoop大年夜数据分析应用处景与拭魅战
- 关于Hadoop你须要知道的一些事项
- 干货 | 98道常见Hadoop面试题及谜调剂析（一）
推荐阅读
由此可见，并不是随便哪家机构推出一种新的标准就可以代替Tier的。这套认证体系本身的贸易化运作已经异常成熟>>>详细阅读
本文标题：10道Hadoop面试真题及解题思路
地址：http://www.17bianji.com/lsqh/37668.html
1/2 1
网友点评
精彩导读
科技快报
品牌展示