妙解谷歌压箱底面试题：如何正确的从楼上抛鸡蛋

作者：Marcin Moskala

编译：ShanLIU、笪洁琼、Harry

关于编程工作有很多很不错的面试谜题。新年之际，我把压箱底儿的一道好题，同时也是传说中谷歌招聘官最喜欢问的一道题找出来了！

今天我们来好好八一八这道题，如果你今年恰好想去谷歌面试，可以抓紧多读几遍！（绝对不会出现下图的情况，我们只放有口碑的神助攻

题目如下：

你在一座100层的高楼大厦里工作，拿到了两个一模一样的鸡蛋。你得搞明白鸡蛋最高可以从几层楼扔出去还不摔坏。

请提出一个算法，能找到投掷鸡蛋却保证不摔坏的最少次数～

我们可以先做些假设：

• 如果鸡蛋从某一楼层跌落而不摔坏，那么当它从更低楼层跌落也不会有破损。
• 一个在被投掷之后完好无损的蛋可以被再利用。
• 一颗鸡蛋如果破损，则必会被丢弃。
• 跌落对于所有鸡蛋都具有同等效应。
• 如果一颗鸡蛋从某一楼层跌落之后受损，那么当它从更高楼层跌落后必定会摔坏。
• 如果一颗鸡蛋从一次跌落中存活下来，那么它一定会从更短程的降落中存活。

大多数人会写出算法来解决这个谜题（我们同样也是会用算法），然而实际上有更容易的办法。

敲黑板说重点啦！

最简单的回答

最简单的方式来获取最少楼层数就是将鸡蛋从第一层扔出，然后第二层，然后依次往后叠加。这样一来，当鸡蛋破碎那一刻我们就知道是这一层了。这是一个可靠的算法，但是在最差的情况下它需要的投掷次数是100次。

需要注意的最重要的一点是，假如你只有一颗鸡蛋，这是唯一可靠的方法。所以在你打破第一颗鸡蛋时就需要开始运用这个算法。

直觉性的答案

这样，我们应该把这100层划分成更小数目的的区间，以尽可能有效地应用这第一颗鸡蛋。因此，一个凭直觉的而且颇受欢迎的方法是从1/第n层逐层检查。

比方说，从第一层到第三层。由此得出算法如下：

• 从33楼投掷出这颗鸡蛋。如果它破损了，那么我们用第二颗鸡蛋检查第32层楼。
• 否则，我们从33+ (67 *1/3) =55层楼扔，如果鸡蛋破损，我们再来用第二颗鸡蛋检查34层到55层。
• …

对于1/3最坏的情况是最大值是33层，这样一来，我们可能可以找到一个完美的n，借助一些动态编程手段，来优化投掷次数。这是一个体现编程思维的有价值的解决方式，然而这不是最优解。

完美解决方案

为了理解完美解法，我们需要理解均衡状态，用于计算出在最坏情境下所需的投掷次数。

这里，F(n) 是我们从开始投掷鸡蛋计算的下一层楼层。

假如我们引入以下的变量：

那么均衡点将会是如下：

最优解是当这个方程里的所有参数都相等。我们是如何取得的呢？从末尾开始看，最后的D(n)将会变成1，因为我们最终将会到达一个点，就是只有单一的一层楼用于投掷第一颗鸡蛋。所以D(n-1)应该等于2，因为它相比于第一颗鸡蛋少了一次投掷。

我们接着会发现第一颗鸡蛋最终应该是从第99层楼投掷，之前是从99-2=97层，再往前则是97-3=94层，90, 85, 79, 72, 64, 55, 45, 34, 22，然后是第九层。这是一个最优解！这样一来，我们需要在最坏的情况下投掷14次（最小的差别在于13，但是我们还需要在第九层额外投一次）。

检查

好啦，我们已经有了解决方案，可以无需任何其他帮助来解开它。现在是时候验证它是否正确了！为此，我们可以写一个Kotlin方程式。

首先，我们来解释一下对一些决策来说，是如何计算投掷次数的。当我们有2层或者更少的层数，那么我们需要按照剩余的楼层数来投掷尽量多的次数。否则我们应该调用如下方呈现的均衡函数：

这里我们调用了bestMaxThrows 函数，这是一个假设函数，它会返回一个投掷次数的数值，假定接下来的一系列决策是完美的。

我们是这样定义它的：

再一次的，我们刚刚授权给了bestNextStep 函数来计算“下一层的最优解”。这个函数很好的为我们指明了下一步的方向，我们可以简单地定义它：当只有二层或更少的楼层待检验，那我们会从第一层扔出鸡蛋，否则我们需要检查所有备选项以找到最优解。

下面是具体执行步骤：

再一次的，我们刚刚授权给了bestNextStep 函数来计算“下一层的最优解”。这个函数很好的为我们指明了下一步的方向，我们可以简单地定义它：当只有二层或更少的楼层待检验，那我们会从第一层扔出鸡蛋，否则我们需要检查所有备选项以找到最优解。

下面是具体执行步骤：

注意，这个函数使用了maxThrows 函数，所以涉及到了循环。这不是个问题，因为当bestNextStep 调用到maxThrows时，它总是调用一个小于floorsLeft 的数（因为nextFloor 总是大于0）。我们调用这个函数之前先加一些缓冲，用于加速这些运算。

首先，我们看看它是否返回和之前计算相同的结果。

结果看着不错，我们再看看下面几步：

结果：

9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,

正是我们计算的结果！赞！

拓展

现在我们有了一套可以解决很多相似问题的不错的算法。比如说，我们可以稍微修改一下来计算最随机的情况下的投掷次数。我们也可以看看这一最小数值如何根据建筑高度不同而有所区别。

下图回答了以上的问题：

（该图展示了最坏情景的最少投掷次数，纵轴是楼层数，横轴是投掷次数，曲线代表最优投掷次数。）

结论

你现在对于谷歌的面试准备更充分了，但更重要的是，你相比以前更具备算法思想。这个算法呈现了一个很好的，高效型的方法。还可应用于解决我们每日工作中的许多问题。

你也许感兴趣的：

• 微软面试题：三角尺三个顶点各有一只蚂蚁，问它们不相遇的机率？
• Java面试官最爱问的volatile关键字
• 5道谷歌面试题：即使是天才也要怀疑自己能力了（附答案）
• 10个我最喜欢问程序员的面试问题
• 近5年133个Java面试问题列表
• 苹果最刁钻的33个面试题，有种就来挑战！
• 面试中的排序算法总结
• 有趣的面试题
• 不少程序员都会碰到的三个面试题
• 【外评】电脑从哪里获取时间？