漫画:经典谷歌面试题扔鸡蛋 看看你会做吗?
消息来源:baojiabao.com 作者: 发布时间:2024-05-13
第二天
题目:扔鸡蛋问题
有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。
问:如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?
举个栗子,最笨的测试方法,是什么样的呢?把其中一个鸡蛋,从第1层开始往下扔。如果在第1层没碎,换到第2层扔;如果在第2层没碎,换到第3层扔.......如果第59层没碎,换到第60层扔;如果第60层碎了,说明不会摔碎的临界点是第59层。
在最坏情况下,这个方法需要扔100次。
方法一:二分法
采用类似于二分查找的方法,把鸡蛋从一半楼层(50层)往下扔。
如果第一枚鸡蛋,在50层碎了,第二枚鸡蛋,就从第1层开始扔,一层一层增长,一直扔到第49层。
如果第一枚鸡蛋在50层没碎了,则继续使用二分法,在剩余楼层的一半(75层)往下扔......
这个方法在最坏情况下,需要尝试50次。
方法二:平方根法
如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数,尽可能均衡呢?
很简单,做一个平方根运算,100的平方根是10。
因此,我们尝试每10层扔一次,第一次从10层扔,第二次从20层扔,第三次从30层......一直扔到100层。
这样的最好情况是在第10层碎掉,尝试次数为 1 + 9 = 10次。
最坏的情况是在第100层碎掉,尝试次数为 10 + 9 = 19次。
不过,这里有一个小小的优化点,我们可以从15层开始扔,接下来从25层、35层扔......一直到95层。
这样最坏情况是在第95层碎掉,尝试次数为 9 + 9 = 18次。
假设最优的尝试次数的x次,为什么第一次扔就要选择第x层呢?
这里的解释会有些烧脑,请小伙伴们坐稳扶好:
假设第一次扔在第x+1层:
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x层。
这样一来,我们总共尝试了x+1次,和假设尝试x次相悖。由此可见,第一次扔的楼层必须小于x+1层。
假设第一次扔在第x-1层:
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-2层。
这样一来,我们总共尝试了x-2+1 = x-1次,虽然没有超出假设次数,但似乎有些过于保守。
假设第一次扔在第x层:
如果第一个鸡蛋碎了,那么第二个鸡蛋只能从第1层开始一层一层扔,一直扔到第x-1层。
这样一来,我们总共尝试了x-1+1 = x次,刚刚好没有超出假设次数。
因此,要想尽量楼层跨度大一些,又要保证不超过假设的尝试次数x,那么第一次扔鸡蛋的最优选择就是第x层。
方法三:解方程法
x + (x-1) + (x-2) + ... + 1 = 100
这个方程式不难理解:
左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次,所以这个多项式共有x项。
右边是总的楼层数100。
下面我们来解这个方程:
x + (x-1) + (x-2) + ... + 1 = 100 转化为
(x+1)*x/2 = 100
最终x向上取整,得到 x = 14
因此,最优解在最坏情况的尝试次数是14次,第一次扔鸡蛋的楼层也是14层。
最后,让我们把第一个鸡蛋没碎的情况下,所尝试的楼层数完整列举出来:
14,27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
举个栗子验证下:
假如鸡蛋不会碎的临界点是65层,那么第一个鸡蛋扔出的楼层是14,27,50,60,69。这时候啪的一声碎了。
第二个鸡蛋继续,从61层开始,61,62,63,64,65,66,啪的一声碎了。
因此得到不会碎的临界点65层,总尝试次数是 6 + 6 = 12
相关文章
- 中兴受美国制裁事件 被罚了20亿美元过程事件始末 中兴被制裁后公司现状
2023-11-02 22:12:46
- B站怎么炸崩了哔哩哔哩服务器今日怎么又炸挂了?技术团队公开早先原因
2023-03-06 19:05:55
- 苹果iPhoneXS/XR手机电池容量续航最强?答案揭晓
2023-02-19 15:09:54
- 华为荣耀两款机型起内讧:荣耀Play官方价格同价同配该如何选?
2023-02-17 23:21:27
- google谷歌原生系统Pixel3 XL/4/5/6 pro手机价格:刘海屏设计顶配版曾卖6900元
2023-02-17 18:58:09
- 科大讯飞同传同声翻译软件造假 浮夸不能只罚酒三杯
2023-02-17 18:46:15
- 华为mate20pro系列手机首发上市日期价格,屏幕和电池参数配置对比
2023-02-17 18:42:49
- 小米MAX4手机上市日期首发价格 骁龙720打造大屏标准
2023-02-17 18:37:22
- 武汉弘芯遣散!结局是总投资1280亿项目烂尾 光刻机抵押换钱
2023-02-16 15:53:18
- 谷歌GoogleDrive网云盘下载改名“GoogleOne” 容量提升价格优惠
2023-02-16 13:34:45
- 巴斯夫将裁员6000人 众化工巨头裁员潮再度引发关注
2023-02-13 16:49:06
- 人手不足 韵达快递客服回应大量包裹派送异常没有收到
2023-02-07 15:25:20
- 资本微念与李子柒销声匿迹谁赢? 微念公司退出子柒文化股东
2023-02-02 09:24:38
- 三星GalaxyS8 S9 S10系统恢复出厂设置一直卡在正在检查更新怎么办
2023-01-24 10:10:02
- 华为Mate50 RS保时捷最新款顶级手机2022多少钱?1.2万元售价外观图片吊打iPhone14
2023-01-06 20:27:09
- 芯片常见的CPU芯片封装方式 QFP和QFN封装的区别?
2022-12-02 17:25:17
- 华为暂缓招聘停止社招了吗?官方回应来了
2022-11-19 11:53:50
- 热血江湖手游:长枪铁甲 刚猛热血 正派枪客全攻略技能介绍大全
2022-11-16 16:59:09
- 东京把玩了尼康微单相机Z7 尼康Z7现在卖多少钱?
2022-10-22 15:21:55
- 苹果iPhone手机灵动岛大热:安卓灵动岛App应用下载安装量超100万次
2022-10-03 22:13:45