作者:Bryant Lei
出处:/bryantlei
电话是中午差不多两点打来的,面试官问我现在合不合适进行面试,当时我从武汉理工面完爱立信没多久,正在睡觉,就说不大合适,能换个时间吗?他回答说那下午5点吧。于是这次电话面试的时间就定在下午5点了。
到了下午5点2分的时候,他打来电话,于是我认识中的第一个电话面试就正式开始了。
面试官:请先作一个自我介绍。
我:balabala。。
面试官:你的简历上写的一个项目是《基于Hadoop的电影推荐系统》,简单介绍下。
我:balabala。
面试官:你这个程序中只用了一个MapReduce吗?
我:不是,有很多个,balabala(模模糊糊的介绍了下其中的某一个MapReduce过程)。
面试官:我有一个1亿的文件,文件中的每一行都有一个整数,怎么利用MapReduce对其进行排序。
我:可以利用MapReduce过程中会对键自动排序的特点,把文件中每一行的数字当做键,这样的话就可以排好序了。
面试官:你这样做的话,因为只有一个reduce可以用,还是会耗费很多时间,你有什么解决办法?
我:(2、3分钟后)这个我就不大清楚了。
面试官:除了个性化推荐,你还学习过其他数据挖掘的算法吗?
我:学过一点,比如说分类和聚类的算法,我和你讲个KNN算法吧,balabala。
面试官:你接触SVM吗?
我:刚才没听清楚,您能把问题再重复一次吗。
面试官:你接触过SVM吗?
我:哦,你说的是支持向量机吧,我只知道数据挖掘有这个算法,但是还没有具体去学习。
面试官:给你出个题目,给你两个排好序的数组,都是n的长度,求中位数。
我:申请额外的O(n)的空间,遍历两个数组比较其大小,把小的那个数放到这个申请的空间中,这样就可以求的其中位数,其时间复杂度应该是O(nlogn)。
面试官:你确定时间复杂度是O(nlogn)吗?你给我解释下。
我:你让我想想。
面试官:(2、3分钟后)要遍历两个数组,你确定不是O(n*n)?
我:我说好像是O(n*n)诶,刚才说错了。(当时有点懵)
面试官:空间复杂度有点高,你能不能有其他办法降低这个空间复杂度?
我:我想想啊。
面试官:提示你下,这个是求中位数,不一定要知道数是怎么排列的。
我:(2、3分钟后)我说我一时也没有更好的办法诶。
面试官:我再给你出个题目,给你一个链表但你不知道它的头节点,只知道你需要删除的那个结点的指针,怎么删除这个指针指向的节点?
我:把下个结点的值复制到已知指针指向的结点处,删除下一个结点,这样就可以了。
面试官:你对设计模式有了解吗?
我:对常用的几种设计模式,比如单例模式、策略模式、观察者模式等,比较了解。
面试官:那你给我讲讲观察者模式吧。
我:balabala(讲了一通,但其实自己感觉讲的很模糊)。
(沉默了几分钟后)
我:我可以问您几个问题吗?
面试官:可以啊。
我:balabala。
面试管:balabala。
面试官:你还有什么问题吗?
我:没有了。
面试官:那这次面试就到这。
我:好的,谢谢您。
Result:面试未通过
这次电话面试的时间才25分钟,而且其中有几个关键问题并没有回答上来,一个是利用MapReduce对大文件进行排序时reduce的个数问题,另一个是求两个给定排好序的数组的中位数的更优解的问题,面试完我就想自己估计没戏啦。最让我印象深刻的是上午问到的问题(观察者模式),下午竟然又问到了,上午这个问题也回答的不是很清楚,本来是想着晚上补一补这方面的知识的,结果还是晚了一点。这个教训告诉我们不懂的东西一定要马上去恶补,否则后悔莫及。下面针对上述回答的不好的两个问题作更进一步的解决。
1.利用MapReduce对大文件进行排序时reduce的个数。
解答:其实这是一个使用hadoop进行大规模数据排序的问题。最直观的方法(也是我的回答)是把文件所有内容给map之后,map不做任何处理,直接暑输出给reduce,利用hadoop的自己的shuffle机制,对所有数据进行排序,之后有reduce直接输出。
然而这样的方法跟单机毫无差别,完全无法用到多机分布式计算的遍历,因此这种方法不是最优的,或者说是不行的。
利用hadoop分而治之的计算模型,可以参照快速排序的思想。在这里我们先简单回忆一下快速排序。快速排序基本步骤就是需要现在所有数据中选取一个作为支点。然后将大于这个支点的放在一边,小于这个支点的放在另一边。
设想如果我们有N个支点(这里可以称为标尺),就可以把所有的数据分成N+1个part,将这N+1个part丢给reduce,由hadoop自动排序,最后输出N+1个内部有序的文件,再把这N+1个文件首尾相连合并成一个文件,收工。
由此我们可以归纳出这样一个用hadoop对大量数据排序的步骤:
1)对待排序数据进行抽样;
2)对抽样数据进行排序,产生标尺;
3)Map对输入的每条数据计算其处于哪两个标尺之间;将数据发给对应区间ID的reduce
4)Reduce将获得数据直接输出。
这里使用对一组url进行排序来作为例子:
这里还有一点小问题要处理:如何将数据发给一个指定ID的reduce?hadoop提供了多种分区算法。这些算法根据map输出的数据的key来确定此数据应该发给哪个reduce(reduce的排序也依赖key)。因此,如果需要将数据发给某个reduce,只要在输出数据的同时,提供一个key(在上面这个例子中就是reduce的ID+url),数据就该去哪儿去哪儿了。
注意事项:
1)标尺的抽取应该尽可能的均匀,这与快速排序很多变种算法均是强调支点的选取是一致的。
2) HDFS是一种读写性能很不对称的文件系统。应该尽可能的利用其读性能很强的特点。减少对写文件和shuffle操作的依赖。举例来说,当需要根据数据的统计情况来决定对数据的处理的时候。将统计和数据处理分成两轮map-reduce比将统计信息合并和数据处理都放到一个reduce中要快速的多。
以上解答转载自/whkjlcw/article/details/25131045。
2.求两个等长的排好序的数组的中位数。
解答:这题有个关键的条件,那就是这两个数组长度相等
思路如下:
数组A:1, 3, 5, 7, 9
数组B:2, 4, 6, 8, 10
首先取二者的中位数,在O(1)时间复杂度内求出,那么数组A的midValue = 5,数组B的midValue = 6,则较小的元素midValue的左边所有元素,也就是midPosition个,和较大元素右边的所有元素,都要去掉,由于去掉的元素占所有元素的一半,所以复杂度为O(logn)。只需要移动begin和end的position即可。
第一轮:
数组A:1, 3,5, 7, 9
数组B:2, 4, 6, 8, 10
第二轮:
数组A:1, 3,5, 7, 9
数组B:2,4, 6, 8, 10
只剩下两个元素,由于这种情形下midValue始终是偏左的元素,因此循环无法退出,所以满足lhsBegin == lhsEnd - 1和 rhsBegin == rhsEnd - 1时,循环退出!
如果两个
上述情形是当数组中有两个及以上元素才成立,必须考虑两个数组只存在一个元素的情形,那么直接取较小的元素即可!
#include <iostream>using namespace std;int findMidValue(int *lhs, int *rhs, int size){if (lhs == NULL || rhs == NULL || size <= 0)return -1;int lhsBegin = 0;int rhsBegin = 0;int lhsEnd = size - 1;int rhsEnd = size - 1;int result;while ((lhsBegin < lhsEnd && rhsBegin < rhsEnd)){if ((lhsBegin == lhsEnd - 1 && rhsBegin == rhsEnd - 1))break;int lhsMid = (lhsBegin + lhsEnd) >> 1;int rhsMid = (rhsBegin + rhsEnd) >> 1;if (lhs[lhsMid] == rhs[rhsMid]){result = lhs[lhsMid];break;}else if (lhs[lhsMid] < rhs[rhsMid]){lhsBegin = lhsMid;rhsEnd = rhsMid;} else{lhsEnd = lhsMid;rhsBegin = rhsMid;}}if (lhsBegin == lhsEnd && rhsBegin == rhsEnd)result = min(lhs[lhsBegin], rhs[rhsBegin]);else if (lhsBegin == lhsEnd - 1 && rhsBegin == rhsEnd - 1){if (lhs[lhsBegin] < rhs[rhsBegin]){result = min(lhs[lhsEnd], rhs[rhsBegin]);}else{result = min(lhs[lhsBegin], rhs[rhsEnd]);}}return result;}void main(){int lhs[] = {1, 2, 3, 4};int rhs[] = {0, 2, 3, 4};const int size = sizeof lhs / sizeof *lhs;int result = findMidValue(lhs, rhs, size);cout << "mid value = " << result << endl;}
以上解答转载自:/alexingcool/article/details/7932441