华侨网,有态度的华人新闻网站!

帮助中心 广告联系

華僑時報 | 華僑網

热门关键词:  央行  发顺丰  蓝狐  詩詞  习近平
热门TAG标签:

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

来源:网络整理 作者:华侨时报 发布时间:2018-01-02
摘要:关于编程工作有很多很不错的面试谜题。新年之际,我把压箱底儿的一道好题,同时也是传说中谷歌招聘官最喜欢问

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

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

今天我们来好好八一八这道题,如果你今年恰好想去谷歌面试,可以抓紧多读几遍!我们只放有口碑的神助攻)

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

题目如下:

你在一座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方程式。

责任编辑:华侨时报