关于编程工作的面试题有很多不错的。新年之际，我在箱底发现了一个好问题，也是传说中的谷歌招聘人员最喜欢问的问题！今天我们就好好看看8月18日的问题。如果今年正好想去谷歌面试，可以多看几遍！（下图绝不会出现，我们只放口碑大神助攻。标题如下：你在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次，但在第9层需要额外掷一次）。检查一下，我们有无需任何额外帮助即可解锁它的解决方案。现在是时候验证它是否正确了！为此，我们可以编写一个Kotlin方程。首先，让我们解释一下如何计算某些决定的投掷次数。当我们有2层或更少的时候，那么我们需要根据剩下的层数尽可能多的扔。否则我们应该调用平衡函数，如下所示：这里我们调用bestMaxThrows函数，这是一个假设的函数，它返回一个抛出次数的值，假设下一系列决策是最好的。下面是我们如何定义它：同样，我们只是委托给bestNextStep函数来计算“下一级别的最佳解决方案”。这个函数为我们下一步提供了一个很好的方向，我们可以简单地定义它：当只有两层或更少要检查的时候，那么我们就从第一层扔鸡蛋，否则我们需要检查所有的Alternate选项来找到一个解决方案。下面是具体的执行步骤：同样，我们刚刚授权了bestNextStep函数来计算“下一层的最优解”。这个函数为我们下一步提供了一个很好的方向，我们可以简单地定义它：当只有两层或更少要检查的时候，那么我们就从第一层扔鸡蛋，否则我们需要检查所有的Alternate选项来找到一个解决方案。下面是具体的执行步骤：注意这个函数使用了maxThrows函数，所以涉及到一个循环。这不是问题，因为当bestNextStep被调用到maxThrows时，它总是使用小于floorsLeft的数字调用（因为nextFloor总是大于0）。我们在调用这个函数之前添加一些缓冲区来加速这些操作。首先，我们看它是否返回与之前计算相同的结果。结果看起来不错，我们看下面的步骤：结果：9,22,34,45,55,64,72,79,85,90,94,97,99,100，正是我们计算的结果！伟大的！扩展现在我们有一套很好的算法可以解决许多类似的问题。例如，我们可以稍微修改它以计算最随机情况下的抛掷次数。我们还可以看到这个最小值如何根据建筑物的高度而变化。下图回答了以上问题：（图中为最坏情况下的最少投掷次数，纵轴为楼层数，横轴为投掷次数，曲线代表投掷次数。）结论你现在正在为Fuller的Google面试做准备，但更重要的是，你比以前更有算法头脑。这个算法提供了一个很好的、有效的方法。它还可以应用于解决我们日常工作中的许多问题。
