• 淘宝校招鸡蛋篮子算法题标准答案
    时间:2012-09-25   作者:fourinone   出处:fourinone.iteye.com

    又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招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运行即可):
    <script>
    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<t+2&&n-t>=j){
                     arr[s]=n-t;
                     document.writeln(arr+"<br>");
                     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);
    </script>

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

    淘宝分布式并行计算框架fourinone(java实现)下载地址:http://www.skycn.com/soft/68321.html

    网友留言/评论

    我要留言/评论

    相关文章

    铁道部新客票系统设计(三):最近只是一时兴起,觉得无聊,正好要到买票的时候,写了这个一系列文章,首先是对自己这些年来的工作经验的总结,其次是把分布式事务性系统的设计思想进行分析和整理,最后也就是和想集大家的智慧,讨论系统的设计。我不是铁道部的工程师,我只是一家互联网金融类公司的屌丝工程师,级别不高,能力也一般,就是喜欢技术而已。
    铁道部新客票系统设计(二):在上一篇文章中《铁道部信客票系统设计(一)》里面,探讨了关于数据库层面的功能性需求以及非功能性的需求,在非功能性需求里面,一博主 提出了没有考虑到峰值的情况,这一点的确漏掉了,因为我们铁道部的特殊需求,在春运期间负载很大,平时可能一般,如果用考虑最大的情况,则回存在浪费的情况,如果考虑不足,就像网络订票一样,苦逼。就好比 铁道部春运的时候,发车量大,但是如果制造大量列车,平时就空闲了,也就很亏。机器的折旧很是块的。春运期间可以考虑紧急扩容来实现,所以从设计上可以保持这种扩展性。 扩容是一项工程,整体来说比较复杂。
    优秀的用户体验设计师应该做好的五件事:一大早又梦到了南开中学。一如既往的回到那里见了老朋友,然后一起去后街淘打口磁带和杂志。梦境中的情节没有让当时的自己感到哪怕一点点的时空穿越,只觉得一切都很真实而正常,反倒是醒来之后感到眼前这一切有些突兀,空白了几秒才想起自己正躺在哪里。
    陈一舟荐文:顶级优秀的产品经理如何从TOP 10%跻身TOP 1%:每个备受推崇的产品背后,是顶级优秀产品人的创新精神和执行力。今天,人人网CEO陈一舟回复了人人网一位员工同学的邮件——关于创新和专业学习,并推荐 Quora 上的一篇文章《顶级优秀的产品经理如何从TOP 10%跻身TOP 1%》。
    铁道部新客票系统设计(一):这几天正好看到一条新闻 铁道部:新客票系统2015年建成 ,正好最近想整理和总结一下这几年的工作中的收获,正好可以借这个机会,尝试设计一下铁路客票系统,把自己所学全部用到这个系统中去,顺便也希望各位猿们拍砖,一起探讨一下设计,技术吗,讨论讨论总是有点收获的,总比一个人在那里看书好。
    Tesseract-OCR3.01语言库训练步骤:这些天由于工作需要,需要对验证码进行识别,当然验证码识别是老问题了,这里介绍了google开源项目Tesseract-OCR3.01对于验证码的识别。对于这款开源项目,要想彻底搞清楚这款开源OCR软件的来龙去脉,还得看Google开源项目的说明:http://code.google.com/p/tesseract-ocr/wiki/TrainingTesseract3,这里就不罗嗦了。
    设计优秀的iPhone应用之五点建议:当用户在苹果应用商店里寻找新应用时,往往基于设计来考量是否购买。生活中,或许很多人告诫我们不要凭借封面去评判一本书;既然无法试用一款应用,那么截图成为我们评判一款应用质量好坏的重要依据。
    大数据量,海量数据 处理方法总结:大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google 腾讯 这样的一些涉及到海量数据的公司经常会问到。
    六年软件测试感悟:不知不觉已经从事软件测试六年了,2006毕业到进入外包公司外包给微软做软件测试, 到现在加入著名的外企。六年的时间过得真快。 长期的测试工作也让我对软件测试有了比较深入的认识。但是我至今还是一个底层的测试人员,我的看法都比较狭隘,如有错误还请批评改正。
    软件设计的一些感想:已经好久没有写博客了,不是因为没有学东西,而是因为学的东西不够系统,不够具体,没有整理起来(外加人懒),所以不想浪费笔墨。所以一直潜水。。但总会有感想的,在学习的过程中,时常会遇到一些令人惊喜的东西,令人拍案叫绝的东西,但学会之后觉得简单或者不值一提,于是没有当机立断写出一些洞见。事后用的时候倒觉得理所当然了。