去谷歌面试，竟让扔鸡蛋？-技术圈

算法题是咱们程序猿面试逃不过绕不开的环节。相较于我们国内，外企的面试，更加看重算法，比如谷歌早年就有一道超级经典的算法：高楼扔鸡蛋。

当年可是难倒了一大片人，后来鸡蛋也经过变异，演化成蓝桥杯的摔手机，但解题思路是完全一致的。

题目分析

为什么这道题能成为经典呢？

我们先来看看题目描述：

你有2颗鸡蛋，需要以最少的尝试次数来判断在100层的高楼上，哪一层楼是鸡蛋的安全层。

换句话说，就是需要确定我们从哪一层楼扔鸡蛋下去，鸡蛋恰好不会摔碎。高于安全层鸡蛋都会碎，低于安全层都不会碎。比如鸡蛋在第1层没有摔碎，在第2层摔碎了，那么鸡蛋的安全层就是第1层。

这里有几个假设条件：

没有摔碎的鸡蛋可以重复使用；
每颗鸡蛋的坚硬程度都是相同的。

这道题乍一看挺简单的，但其实解答相对复杂，而且解法多种多样，要在面试时逻辑清楚地表达完整思路，不仅要求面试者的知识储备要广、反应能力要快，逻辑思维和语言表达能力也是必不可少的。

成为经典可谓当之无愧。

解法一：简单粗暴

我们先来个最省事儿的方法：假设我们只有一颗鸡蛋，显然只有从一楼开始扔，逐层试探，直到鸡蛋摔碎，安全层就是第N-1层。

但是缺点想必大家也看出来了，这是拼运气啊，最坏情况需要扔100次。

用一颗鸡蛋的方法虽然简单粗暴，但也是给两颗鸡蛋的情况缕清一些思路。

解法二：常规二分

有两颗鸡蛋，二分法想必是大多数同学脑海里浮现的第一个念头吧？

我们先从50楼扔一颗鸡蛋，如果没碎，就往上继续二分，到75楼继续扔······

这是比较顺利的情况，如果不顺利呢，比如我们从50楼扔鸡蛋，直接碎了，那就只有一颗鸡蛋了。

这时候我们就回到解法一了，只能从1楼开始遍历，又是拼运气的时候了，要是运气好，1楼鸡蛋就没了，那测试次数就是1+1=2次，但最坏情况就是1+49=50次。

这么多次，显然是不能通过google面试的。

解法三：均衡切割

虽然二分法不够优秀，但体现了切分范围的思想。

我们的基本思路是，将100层切分成两个维度，由两个鸡蛋分别控制一个维度。

一个维度是用第一颗鸡蛋分金定穴，另一个维度是用第二颗鸡蛋在前蛋的基础上进行遍历。

换言之，我们是将100层切分成若干个区块，由第一颗鸡蛋确定最高安全楼层所属的区块，再由第二颗鸡蛋逐层确定其具体的位置。

在1-100层楼之间，假设我们从上往下尝试，即从100层开始扔第一颗蛋，大概率是碎了，那第二颗蛋便又回到了解法一。

所以，我们应该从下往上进行划分、尝试，这样即使第一颗鸡蛋碎了，用第二颗蛋遍历的成本也比较低。

比如第一颗蛋每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从30层扔……一直扔到100层。

第二颗蛋就只用在第一颗蛋摔碎的层数和前一次的安全层之间的9层进行范围遍历。

也就是说，要是第一颗鸡蛋在第30层摔碎了，那就拿第二颗蛋从21层到29层逐层尝试。

这样的最好情况就是第一颗蛋在第10层碎掉，总的尝试次数为1+1=2次。

最坏的情况是在第100层碎掉，总尝试次数为10+9=19次。

解法四：微妙平衡

上面的方法，看似已经比较完美了。

但是我们再具像化一点，就能发现问题：第一颗鸡蛋能快速定位安全楼层低的情况，但如果安全楼层位置越高，耗时就会越久，而第二颗鸡蛋在每个区块内的消耗，都是一样的。

如果鸡蛋的最高安全层为18或者98，用解法三的思路的话，这两种情况的总尝试次数并不一样：

最高安全楼层为18时，第一颗鸡蛋试了2次就定位了区块；而最高安全楼层为98时，第一颗鸡蛋试了10次才定位了区块。

虽然第二颗鸡蛋在区块内部的逐层尝试次数是一样的，但98层对应的总尝试次数就多太多了。

原因就是区块完全均匀划分对大数不利。

明白了这个缺陷，也就知道了改进的基本思想：要对100找出一种二维区块划分，但不是均匀划分。

对于比较小的区块部分，其包含的楼层范围可以适当增加；越向大数部分走，其包含的楼层范围越来越小。从下往上，每一个区块内所含楼层递减。

在最高安全楼层比较低的情况下，第一颗鸡蛋尝试的次数少；在最高安全楼层比较高的情况下，则第二颗鸡蛋尝试的次数少。

就是用第二颗鸡蛋尝试次数的减少来弥补第一颗鸡蛋需要的尝试次数的递增，使两颗鸡蛋在不同维度上的尝试次数此消彼长，达到一种总体上的平衡。

每上一个区块，第一颗鸡蛋消耗的次数就+1，我们索性就假设每个区块包含的楼层数逐级递减1，以达到平衡。

那么每个区块包含的层数应该如何划分呢？

我们假设第一个区块有X层，那么第二个就是X-1，以此类推，我们就得到了一个方程式：

X+（X-1）+（X-2）+···+3+2+1≥100

可以看出来，这时候区块个数和第一个区块包含的层数其实是相等的。

现在我们回过头来，再仔细看看方程式，是不是有点熟悉，不就是等差数列求和么！

所以我们化简方程式：

X(X+1)/2≥100

这里X最小值我们向上取整，得到14。

有同学会问为什么一定到1呢，最后一个区块一定只有1层吗？

不是的，到1是表示在X个区块的情况下，最多能覆盖的层数。

比如我们这个例子，X是14，求出的楼层总数是105，也就是可以覆盖105层，题目要求的100层当然绰绰有余。

由此，第一个区块包含14层楼，即1到14层；

第二个区块包含13层楼，即15到27层；

第三个区块包含12层楼，即28到39层；

······

第一颗鸡蛋依次试第14、27、39、50、60、69、77、84、90、95、99、100层。只要期间任何一次鸡蛋碎了，就拿第二颗鸡蛋从上一次的安全层之后开始逐层尝试，直至第二颗鸡蛋也摔碎为止。

用这个方法，总次数一定不会超过14次。

因为最高安全楼层越高，第一颗鸡蛋的尝试次数也就越多，但第二颗鸡蛋的尝试次数随之越来越少，两者始终维持着一种微妙的平衡，最后总的尝试次数波动也不会太大。

微妙的平衡

写在最后

除了文中我们讨论的解法，这道题也还有其他解法可以选择，如果感兴趣大家可以自己研究研究，也欢迎来和牛牛讨论！

凭心而论，要是在毫无准备的情况下，牛牛面试遇到这道题，想到解法三已经是最优解了，能在这么短的时间内想到解法四的大神是凤毛麟角。

千里之行始于足下，我们一定要在平时多学、多看、多刷题，就算有些问题不能立刻明白，但随着知识和经验的积累，一定会有一个瞬间让我们茅塞顿开，灵光乍现。

有兴趣的同学可以火速加入我们的星球

3周零基础入门提供10节课程

全年12节趣味实战项目含源码，

每月奖励优秀的Top3同学送书

专业的答疑群，大厂的老师保姆式的教学

如果不满意，三天内随意退款！一年88，现在优惠16元

扫码加入，3周零基础入门

干货:爬取豆瓣短评，电影《后来的我们》 | 38年NBA最佳球员分析 | 从万众期待到口碑扑街！唐探3令人失望 | 笑看新倚天屠龙记 | 灯谜答题王｜用Python做个海量小姐姐素描图｜碟中谍这么火，我用机器学习做个迷你推荐系统电影

趣味:弹球游戏 | 九宫格 | 漂亮的花 | 两百行Python《天天酷跑》游戏!

AI: 会做诗的机器人 | 给图片上色 | 预测收入 | 碟中谍这么火，我用机器学习做个迷你推荐系统电影

小工具: Pdf转Word，轻松搞定表格和水印！ | 一键把html网页保存为pdf！| 再见PDF提取收费！ | 用90行代码打造最强PDF转换器，word、PPT、excel、markdown、html一键转换 | 制作一款钉钉低价机票提示器！｜60行代码做了一个语音壁纸切换器天天看小姐姐！｜

年度爆款文案

1).卧槽！Pdf转Word用Python轻松搞定！
2).学Python真香！我用100行代码做了个网站，帮人PS旅行图片，赚个鸡腿吃
3).首播过亿，火爆全网，我分析了《乘风破浪的姐姐》，发现了这些秘密
4).80行代码！用Python做一个哆来A梦分身
5).你必须掌握的20个python代码，短小精悍，用处无穷
6).30个Python奇淫技巧集
7).我总结的80页《菜鸟学Python精选干货.pdf》,都是干货
8).再见Python！我要学Go了！2500字深度分析！
9).发现一个舔狗福利！这个Python爬虫神器太爽了，自动下载妹子图片

点阅读原文，看200个Python案例!