文档章节

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

fourinone
 fourinone
发布于 2012/09/24 10:26
字数 838
阅读 248
收藏 2

又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招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
企鹅群:241116021
邮箱:Fourinone@yeah.net

© 著作权归作者所有

共有 人打赏支持
fourinone

fourinone

粉丝 273
博文 43
码字总数 49961
作品 1
杭州
私信 提问
加载中

评论(1)

朱坤朋
朱坤朋
这个,一旦找到这个Xm了,直接求解他的二进制表示,就代表取那些篮子了。不用在递归求解了吧
淘宝校招鸡蛋篮子算法题标准答案(javascript实现)

又到一年校招时,阿里集团虽然今年休养生息,缩紧招聘,但是现在继续开放校招,不过只招a类学生,也就是重点学校的最优学生(面试官认为),以往多半是研究生居多,本科生录用比率减少,但是编程逻辑思...

fourinone
2012/09/24
1K
6
九月十月百度,迅雷,华为,阿里巴巴最新校招笔试面试二十题(10.12)

九月十月百度,迅雷,华为,阿里巴巴,最新校招笔试面试二十题 题记 本博客自2010年10月11日开通以来,已经帮助了一大批人找到工作,特别是连续三年在每一年的9、10月份陪伴了至少三届毕业生...

mickelfeng
2013/10/12
0
0
前端相关整理

整理一下最近在网上收集的前端面试相关资料,包括预备知识、书籍、面试考点、面经等。前端方面资料其实太多太多,就光从知乎、前端乱炖、w3cplus 等网站就能找到很多,所以针对细节不发散,仅...

Seas0n_
2016/03/01
106
0
互联网公司最常见的面试算法题有哪些?

所谓知己知彼,百战不殆,今天就和大家聊聊互联网公司那些最常见的面试算法题。 清点面试算法题之前我们先要明确面试官考察的目的,比如有一道经典考题是“怎么用3升和5升的桶量出4升的水?”...

慕课网官方_运营中心
2018/07/20
0
0
90 道名企笔试和算法题 (含答题讨论)

(点击上方公众号,可快速关注) 节选自「算法爱好者」微信公号的精选算法题和名企笔试题。 问:如何获取题目列表? 答:① 长摁二维码关注「算法爱好者」,② 然后给它发送 名企笔试 或 算法...

Python开发者
2018/01/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

5、redis分布式锁

参考链接:https://www.cnblogs.com/linjiqin/p/8003838.html 一:介绍 实现分布式锁有三种方式:1、数据库乐观锁,2、基于redis,3、基于zookeeper。 redis服务端是单线程操作,完美地避免了...

刘付kin
23分钟前
3
0
OSChina 周日乱弹 —— 我重新说

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享矢野立美的单曲《LOVE Theme from TIGA <M-2>》: 《LOVE Theme from TIGA <M-2>》- 矢野立美 手机党少年们想听歌,请使劲儿戳...

小小编辑
今天
64
5
Java单例模式学习记录

在项目开发中经常能遇见的设计模式就是单例模式了,而实现的方式最常见的有两种:饿汉和饱汉(懒汉)。由于日常接触较多而研究的不够深入,导致面试的时候被询问到后有点没底,这里记录一下学习...

JerryLin123
昨天
10
0
VSCODE 无法调试

VSCODE 无法调试 可以运行 可能的原因: GCC 的参数忘了加 -g

shzwork
昨天
5
0
理解去中心化 稳定币 DAI

随着摩根大通推出JPM Coin 稳定币,可以预见稳定币将成为区块链落地的一大助推器。 坦白来讲,对于一个程序员的我来讲(不懂一点专业经济和金融),理解DAI的机制,真的有一点复杂。耐心看完...

Tiny熊
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部