hadoop面试题,
1、查找linux下文件的重复行
sort | uniq -d
2、mysql外联结和内联结的区别
在SQL标准中规划的(Join)联结大致分为下面四种:1. 内联结:将两个表中存在联结关系的字段符合联结关系的那些记录形成记录集的联结。2. 外联结:分为外左联结和外右联结。左联结A、B表的意思就是将表A中的全部记录和表B中联结的字段与表A的联结字段符合联结条件的那些记录形成的记录集的联结,这里注意的是最后出来的记录集会包括表A的全部记录。右联结A、B表的结果和左联结B、A的结果是一样的,也就是说:Select A.name B.name From A Left Join B On A.id=B.id和Select A.name B.name From B Right Join A on B.id=A.id执行后的结果是一样的。
3、mysql explain的含义,作用
explain显示了mysql如何使用索引来处理select语句以及连接表。可以帮助选择更好的索引和写出更优化的查询语句。
4、文件内容的行以/t 为列分隔符,查找第三列为0的行。用awk实现
cat 1.txt | awk '$3==0'
5、海量数据随机抽样问题,要求从N个元素中随机的抽取k个元素,其中N无法确定。
【解决】解决方案就是蓄水库抽样(reservoid sampling)。主要思想就是保持一个集合(这个集合中的每个数字出现),作为蓄水池,依次遍历所有数据的时候以一定概率替换这个蓄水池中的数字。其伪代码如下:
[cpp] view plaincopy- Init : a reservoir with the size: k
- for i= k+1 to N
- M=random(1, i);
- if( M < k)
- SWAP the Mth value and ith value
- end for
下面来具体证明一下:每个水库中的元素出现概率都是相等的。
【证明】
(1)初始情况。出现在水库中的k个元素的出现概率都是一致的,都是1。这个很显然。
(2)第一步。第一步就是指,处理第k+1个元素的情况。分两种情况:元素全部都没有被替换;其中某个元素被第k+1个元素替换掉。我们先看情况2:第k+1个元素被选中的概率是k/(k+1)(根据公式k/i),所以这个新元素在水库中出现的概率就一定是k/(k+1)(不管它替换掉哪个元素,反正肯定它是以这个概率出现在水库中)。下面来看水库中剩余的元素出现的概率,也就是1-P(这个元素被替换掉的概率)。水库中任意一个元素被替换掉的概率是:(k/k+1)*(1/k)=1/(k+1),意即首先要第k+1个元素被选中,然后自己在集合的k个元素中被选中。那它出现的概率就是1-1/(k+1)=k/(k+1)。可以看出来,旧元素和新元素出现的概率是相等的。情况1:当元素全部都没有替换掉的时候,每个元素的出现概率肯定是一样的,这很显然。但具体是多少呢?就是1-P(第k+1个元素被选中)=1-k/(k+1)=1/(k+1)。(3)归纳法:重复上面的过程,只要证明第i步到第i+1步,所有元素出现的概率是相等的即可。
6、Mapreduce如何实现join
参考我之前的文章,hadoop学习--多表关联
7、写一个二分查找算法,用你熟悉的语言
#include <iostream>
using namespace std;
//二分查找
int binary_search(int* a, int len, int goal);
int main()
{
const int LEN = 10000;
int a[LEN];
for(int i = 0; i < LEN; i++)
a[i] = i - 5000;
int goal = 0;
int index = binary_search(a, LEN, goal);
if(index != -1)
cout<<goal<<"在数组中的下标为"<<binary_search(a, LEN, goal)<<endl;
else
cout<<"不存在"<<goal<<endl;
return 0;
}
int binary_search(int* a, int len, int goal)
{
int low = 0;
int high = len - 1;
while(low <= high)
{
int middle = (low + high)/2;
if(a[middle] == goal)
return middle;
//在左半边
else if(a[middle] > goal)
high = middle - 1;
//在右半边
else
low = middle + 1;
}
//没找到
return -1;
}
8、hadoop的数据倾斜为什么产生,如何解决
常见的数据倾斜有以下几类:
数据频率倾斜——某一个区域的数据量要远远大于其他区域。
数据大小倾斜——部分记录的大小远远大于平均值。
在map端和reduce端都有可能发生数据倾斜。在map端的数据倾斜会让多样化的数据集的处理效率更低。在reduce端的数据倾斜常常来源于MapReduce的默认分区器。
数据倾斜会导致map和reduce的任务执行时间大为延长,也会让需要缓存数据集的操作消耗更多的内存资源。
解决方案:
在这个方案中将讨论多个减轻reduce数据倾斜的性能损失的方法。
方法1:抽样和范围分区
Hadoop默认的分区器是基于map输出键的哈希值分区。这仅在数据分布比较均匀时比较好。在有数据倾斜时就很有问题。
使用分区器需要首先了解数据的特性。在第4章的TotalOrderPartitioner中,可以通过对原始数据进行抽样得到的结果集来预设分区边界值。TotalOrderPartitioner中的范围分区器可以通过预设的分区边界值进行分区。因此它也可以很好地用在矫正数据中的部分键的数据倾斜问题。
方法2:自定义分区
另一个抽样和范围分区的替代方案是基于输出键的背景知识进行自定义分区。例如,如果map输出键的单词来源于一本书。其中大部分必然是省略词(stopword)。那么就可以将自定义分区将这部分省略词发送给固定的一部分reduce实例。而将其他的都发送给剩余的reduce实例。
方法3:Combine
使用Combine可以大量地减小数据频率倾斜和数据大小倾斜。在可能的情况下,combine的目的就是聚合并精简数据。在技术48种介绍了combine。
方法4:Map端连接和半连接
如果连接的数据集太大而不能在map端的连接中使用。那么可以考虑第4章和第7章中介绍的超大数据集的连接优化方案。
方法5:数据大小倾斜的自定义策略
在map端或reduce端的数据大小倾斜都会对缓存造成较大的影响,乃至导致OutOfMemoryError异常。处理这种情况并不容易。可以参考以下方法。
设置mapred.linerecordreader.maxlength来限制RecordReader读取的最大长度。RecordReader在TextInputFormat和KeyValueTextInputFormat类中使用。默认长度没有上限。
通过org.apache.hadoop.contrib.utils.join设置缓存的数据集的记录数上限。在reduce中默认的缓存记录数上限是100条。
考虑使用有损数据结构压缩数据,如Bloom过滤器。
海量数据随机抽样问题(蓄水池问题)
9、用MapReduce实现K-means 算法
参考我之前的文章,hadoop学习--K-Means算法实现
10、用正则表达式查找邮箱地址
还有1个题目忘记了,有关正则表达式的。。。。