淘宝校招鸡蛋篮子算法题标准答案

存储架构 2012-09-24

又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招a类学生,也就是重点学校的最优学生(面试官认为),以往多半是研究生居多,本科生录用比率减少,但是编程逻辑思维好的学生仍然是不多的,这是去年出的一道原创题和它的标准答案,做对的人非常少。

题目:把N个鸡蛋放到M个篮子里,每个篮子不能为空,要求满足:任意给出一个不超过N的数量,都能找到其中某几个篮子的鸡蛋和等于它。

请写一个程序,输入N,M,然后输出所有的鸡蛋放法。

题目解释:例如6个鸡蛋放3个篮子的一种可能为1,2,3,任意给出1<=x<=6的值,都可以找到1,2,3中的组合的和等于x.

该题目最早是我在网上看到一道600个鸡蛋放在10个篮子的放法,答案是给出了一个按2的乘积放的特例。我将其改编后用来招聘时考察工程师上机编程技能。

解题思路如下:

假设第一个篮子放一个鸡蛋:

那么1,X2中,X2可以放鸡蛋的范围是1<= X2<=2, 如果X2=3,便满足不了给出n=2的情况了

取X2=2

那么1,2,X3中,X3可以放鸡蛋的范围是2<= X3<=4

......

可以推出数学公式:在前m个篮子满足要求时,第m+1个篮子可以放置的鸡蛋数范围应该是: Xm<=Xm+1<=N+1

该范围同时也是搜索解的空间,比较好用递归实现,对于每找到一个符合范围的Xm,可以进一步深度遍历寻找下一个Xm+1, 由此便容易理解标准答案的实现了。

如果使用蛮力计算出所有组合,再逐一过滤筛选也可以实现,但是程序肯定要比上面繁琐,效率较低。

希望通过该题目能筛选到编程上有天赋的学生,特别是能独立完成构思和代码编写的,应该是很有潜力的。只是该类型的题目并不是特别适合笔试,很多学生写了大段代码逻辑难以判断是否能正确输出,笔试只适合考基础知识,进一步可安排其上机检查其程序技能。

参考答案(保存成html运行即可):

var n=20,m=5;

var total=0;

var arr = new Array(m);

function exerun(j,t,s){

for(var i=j;i<t+2;i++){

if(s==m-1){

if(n-t=j){

arr[s]=n-t;

document.writeln(arr+"
");

total++;

}

break;

}else if(t+i<n){

arr[s]=i;

exerun(i,t+i,s+1);

}else break;

}

}

exerun(1,0,0);

document.writeln("total:"+total);

思维延伸:对于太巨大的数字会超出单台机器的计算局限导致缓慢,对次,可考虑采用并行计算方式设计算法,分解到不同机器计算,再合并结果,留给读者去思考。

淘宝分布式并行计算框架fourinone(java实现)下载地址:

责编内容by:fourinone (源链)。感谢您的支持!

您可能感兴趣的

Algorithm for quickly obtaining a partial order on... I have a situation, as follows: I have n doubly-linked lists ...
H5与APP混合开发遇到的问题总结 首先,这是我第一次在这个平台上写文章,如果有不好的地方,还请各位指点哦,谢谢。【PS:本人小白一枚】 背景 在公司参与一个原生APP和h5混合开发的项目...
Problem with HTML Parser in IE I am trying to create a dialog box that will appear only if the browser selected...
Does not the HTML feature code appear on MacOs&... I am using html entities for previous and next page navigation on my web page...
Convert HTML into PDF on iOS Feb 14, 2018 by Aleksandar Vacić 2 minute read There are mu...