Go语言视频零基础入门到精通

admin

面试中，为了考察应聘者的思维方式，面试官偶尔会出一些谜题（Puzzles）。
比如，在谷歌，就有这样一道让人“闻风丧胆”的面试题：
You work in a 100 floor building and you get 2 identical eggs.
You need to figure out the highest floor an egg can be dropped without breaking.
The question is how many throws you need to make.
Find an algorithm that is minimizing number of throws in the worst-case scenario.

这道题的意思大致如下：
情景假设
你在一个100层高的大楼里
你有2个一模一样的鸡蛋
任务
弄清楚：鸡蛋最高可以从几层楼扔下去而不会被摔坏
弄清楚你需要扔几次
提出一个算法，找出在最坏情况下，扔出鸡蛋而不把鸡蛋摔坏的最少次数

好在近日，一位来自Gamekit的Senior Android Developer，在网上分享了他的解法。
对去Google工作感兴趣的小伙伴们，就赶紧来看看他是怎么说的吧：
首先，在解题之前，我们要做好几个简单的假设：
2个鸡蛋的脆弱程度是一样的。
如果鸡蛋从N楼扔下来没有碎，那么它从小于N楼扔下来，也不会碎
如果鸡蛋从N楼扔下来碎了，那么它从大于N楼扔下来，也一定会碎
一颗扔出去但没有碎的鸡蛋，可以继续被用于试验。
碎了的鸡蛋将无法再继续试验。
有了这些假设之后，我们就可以解题了。
其实解决这道问题的方法有很多，在此列举一些：
01 最简单解法
最简单的一个方法，就是将鸡蛋从第一层开始，逐层扔出，看它在哪一层会摔碎。
这个方法虽然可靠，但它可能需要进行很多次尝试。比如，在最差的情况下，它需要尝试的次数是100次。
需要注意的一点是，当你只有一颗鸡蛋时，这个算法是唯一可靠的方法。

所以一旦你打碎了第一颗鸡蛋，手里只剩下最后一颗的时候，你就要开始运用这个算法。
02 最直观解法
这个方法重点，是要利用好第一颗鸡蛋，最大效率地把100层高楼划分成N个更小数目的区间。
一个比较直观和流行的答案是，将鸡蛋从【要检查的楼层* 1/N】层开始扔下去，逐层检查。
例如，当N=3时，我们就将第一颗鸡蛋从100*1/3 ≈ 33层楼扔出：
►　如果它破损了，我们就接着用第二颗鸡蛋检验32层楼及以下。
►　如果它没破损，我们就继续将同一颗鸡蛋从33 + (67 * 1/3) = 55层楼扔出，如果它破了，我们就用第二颗鸡蛋，检验34层 - 55层
......
当N = 3时，最坏的情况是max(33, 24, …) = 33层。
按照这个思路，再通过动态编程（dynamic programming），我们就可以找到一个完美的N，来最优化鸡蛋的投掷次数了。
这个解法在面试中还是很有“价值”的，毕竟它能向面试官展现求职者的编程思维。
但它还不是最佳解法。
03 最优解
在理解最佳解法之前，我们需要理解以下这个equilibrium（均衡状态）：
这个均衡状态计算的是在最坏情境下，所需的扔鸡蛋次数。
这里，F(n)指的是楼层，是我们扔第一个鸡蛋后的下一层。
假如我们引入以下变量：

请点击此处输入图片描述
那么刚刚的equilibrium就变成这样：

请点击此处输入图片描述
当这个函数里的所有参数都相等时，就是我们的最优解。
那么我们如何做到呢？
从末尾开始看，最后的D(n)将会变成1，因为最终我们将会到达一个点 —— 就是只剩下一层楼可以扔第一颗鸡蛋。
因此，D(n-1)应该等于2。
我们接着会发现，第一颗鸡蛋最终应该是从第99层楼扔出，之前是从99-2=97层，再往前则是97-3=94层，90,85,79,72,64,55,45,34,22，然后是第9层。
这就是一个最优解！
这样一来，我们就得出了答案：
在最坏的情况下，我们需要的扔鸡蛋的最少次数，是14次（最小的差别在于13，但是我们还需要在第9层额外扔一次）。
04 检查
现在就到了检验我们的解法是否正确的时候了。
我们可以编写一个简单的Kotlin程序来检验答案。
首先，我们需要解释一下，如何在某些决策中，计算扔鸡蛋次数。
当有2层或更少的楼层时，我们需要按照剩余的楼层数，来决定扔鸡蛋的次数。
否则，我们应该调用以下均衡函数：

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

同样，我们把“计算下一层最优解”的任务，交给了bestNextStep 函数。
这个函数很好的为我们指明了下一步的方向，
我们可以这样简单地定义它：当只有二层或更少的楼层待检验时，我们会从第一层扔出鸡蛋。
否则，我们需要检查所有备选项，然后找到最优解。
下面是具体执行步骤：

需要注意的是，这个方程用了maxThrows函数，因此会涉及到recurrence （循环）。
但这并不成问题，因为当bestNextStep调用maxThrows时，它始终会使用比floorLeft更小的值调用它（因为nextFloor总是大于0）。
在我们使用它之前，我们需要添加一些缓冲，从而加速计算：

首先，我们可以检查它是否返回与我们计算结果相同的结果：

14 —— 这个结果看上去还不错，我们接着检查之后的几个步骤：

Result：
9, 22, 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99, 100,
跟我们计算的结果是一致的!

05 Bigger picture
以上分享的这个算法，其实还可以解决许多其他类似的问题。
比如，我们可以把原题的提问改改，改成计算最随机情况下的扔鸡蛋次数。我们还可以看看，当建筑物的高度有变化时，得出的结果是否也会跟着变化。
下图很好地回答了以上问题：

希望这些对正在求职的你们，有所帮助。
更多科技求职资讯，请关注"来Offer网"