作者：Marcin Moskala

編譯：ShanLIU、笪潔瓊、Harry

關(guān)于編程工作有很多很不錯(cuò)的面試謎題。新年之際，我把壓箱底兒的一道好題，同時(shí)也是傳說(shuō)中谷歌招聘官最喜歡問(wèn)的一道題找出來(lái)了！

今天我們來(lái)好好八一八這道題，如果你今年恰好想去谷歌面試，可以抓緊多讀幾遍！（絕對(duì)不會(huì)出現(xiàn)下圖的情況，我們只放有口碑的神助攻）

題目如下：

你在一座100層的高樓大廈里工作，拿到了兩個(gè)一模一樣的雞蛋。你得搞明白雞蛋最高可以從幾層樓扔出去還不摔壞。

請(qǐng)?zhí)岢鲆粋€(gè)算法，能找到投擲雞蛋卻保證不摔壞的最少次數(shù)～

我們可以先做些假設(shè)：

• 如果雞蛋從某一樓層跌落而不摔壞，那么當(dāng)它從更低樓層跌落也不會(huì)有破損。

• 一個(gè)在被投擲之后完好無(wú)損的蛋可以被再利用。

• 一顆雞蛋如果破損，則必會(huì)被丟棄。

• 跌落對(duì)于所有雞蛋都具有同等效應(yīng)。

• 如果一顆雞蛋從某一樓層跌落之后受損，那么當(dāng)它從更高樓層跌落后必定會(huì)摔壞。

• 如果一顆雞蛋從一次跌落中存活下來(lái)，那么它一定會(huì)從更短程的降落中存活。

大多數(shù)人會(huì)寫(xiě)出算法來(lái)解決這個(gè)謎題（我們同樣也是會(huì)用算法），然而實(shí)際上有更容易的辦法。

敲黑板說(shuō)重點(diǎn)啦！

最簡(jiǎn)單的方式來(lái)獲取最少樓層數(shù)就是將雞蛋從第一層扔出，然后第二層，然后依次往后疊加。這樣一來(lái)，當(dāng)雞蛋破碎那一刻我們就知道是這一層了。這是一個(gè)可靠的算法，但是在最差的情況下它需要的投擲次數(shù)是100次。

需要注意的最重要的一點(diǎn)是，假如你只有一顆雞蛋，這是唯一可靠的方法。所以在你打破第一顆雞蛋時(shí)就需要開(kāi)始運(yùn)用這個(gè)算法。

這樣，我們應(yīng)該把這100層劃分成更小數(shù)目的的區(qū)間，以盡可能有效地應(yīng)用這第一顆雞蛋。因此，一個(gè)憑直覺(jué)的而且頗受歡迎的方法是從1/第n層逐層檢查。

比方說(shuō)，從第一層到第三層。由此得出算法如下：

• 從33樓投擲出這顆雞蛋。如果它破損了，那么我們用第二顆雞蛋檢查第32層樓。

• 否則，我們從33+ (67 *1/3) =55層樓扔，如果雞蛋破損，我們?cè)賮?lái)用第二顆雞蛋檢查34層到55層。

• …

對(duì)于1/3最壞的情況是最大值是33層，這樣一來(lái)，我們可能可以找到一個(gè)完美的n，借助一些動(dòng)態(tài)編程手段，來(lái)優(yōu)化投擲次數(shù)。這是一個(gè)體現(xiàn)編程思維的有價(jià)值的解決方式，然而這不是最優(yōu)解。

為了理解完美解法，我們需要理解均衡狀態(tài)，用于計(jì)算出在最壞情境下所需的投擲次數(shù)。

這里，F(xiàn)(n) 是我們從開(kāi)始投擲雞蛋計(jì)算的下一層樓層。

假如我們引入以下的變量：

那么均衡點(diǎn)將會(huì)是如下：

最優(yōu)解是當(dāng)這個(gè)方程里的所有參數(shù)都相等。我們是如何取得的呢？從末尾開(kāi)始看，最后的D(n)將會(huì)變成1，因?yàn)槲覀冏罱K將會(huì)到達(dá)一個(gè)點(diǎn)，就是只有單一的一層樓用于投擲第一顆雞蛋。所以D(n-1)應(yīng)該等于2，因?yàn)樗啾扔诘谝活w雞蛋少了一次投擲。

我們接著會(huì)發(fā)現(xiàn)第一顆雞蛋最終應(yīng)該是從第99層樓投擲，之前是從99-2=97層，再往前則是97-3=94層，90, 85, 79, 72, 64, 55, 45, 34, 22，然后是第九層。這是一個(gè)最優(yōu)解！這樣一來(lái)，我們需要在最壞的情況下投擲14次（最小的差別在于13，但是我們還需要在第九層額外投一次）。

好啦，我們已經(jīng)有了解決方案，可以無(wú)需任何其他幫助來(lái)解開(kāi)它?，F(xiàn)在是時(shí)候驗(yàn)證它是否正確了！為此，我們可以寫(xiě)一個(gè)Kotlin方程式。

首先，我們來(lái)解釋一下對(duì)一些決策來(lái)說(shuō)，是如何計(jì)算投擲次數(shù)的。當(dāng)我們有2層或者更少的層數(shù)，那么我們需要按照剩余的樓層數(shù)來(lái)投擲盡量多的次數(shù)。否則我們應(yīng)該調(diào)用如下方呈現(xiàn)的均衡函數(shù)：

這里我們調(diào)用了bestMaxThrows 函數(shù)，這是一個(gè)假設(shè)函數(shù)，它會(huì)返回一個(gè)投擲次數(shù)的數(shù)值，假定接下來(lái)的一系列決策是完美的。

我們是這樣定義它的：

再一次的，我們剛剛授權(quán)給了bestNextStep 函數(shù)來(lái)計(jì)算“下一層的最優(yōu)解”。這個(gè)函數(shù)很好的為我們指明了下一步的方向，我們可以簡(jiǎn)單地定義它：當(dāng)只有二層或更少的樓層待檢驗(yàn)，那我們會(huì)從第一層扔出雞蛋，否則我們需要檢查所有備選項(xiàng)以找到最優(yōu)解。

下面是具體執(zhí)行步驟：

再一次的，我們剛剛授權(quán)給了bestNextStep 函數(shù)來(lái)計(jì)算“下一層的最優(yōu)解”。這個(gè)函數(shù)很好的為我們指明了下一步的方向，我們可以簡(jiǎn)單地定義它：當(dāng)只有二層或更少的樓層待檢驗(yàn)，那我們會(huì)從第一層扔出雞蛋，否則我們需要檢查所有備選項(xiàng)以找到最優(yōu)解。

下面是具體執(zhí)行步驟：

注意，這個(gè)函數(shù)使用了maxThrows 函數(shù)，所以涉及到了循環(huán)。這不是個(gè)問(wèn)題，因?yàn)楫?dāng)bestNextStep 調(diào)用到maxThrows時(shí)，它總是調(diào)用一個(gè)小于floorsLeft 的數(shù)（因?yàn)閚extFloor 總是大于0）。我們調(diào)用這個(gè)函數(shù)之前先加一些緩沖，用于加速這些運(yùn)算。

首先，我們看看它是否返回和之前計(jì)算相同的結(jié)果。

結(jié)果看著不錯(cuò)，我們?cè)倏纯聪旅鎺撞剑?/span>

結(jié)果：

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

正是我們計(jì)算的結(jié)果！贊！

現(xiàn)在我們有了一套可以解決很多相似問(wèn)題的不錯(cuò)的算法。比如說(shuō)，我們可以稍微修改一下來(lái)計(jì)算最隨機(jī)的情況下的投擲次數(shù)。我們也可以看看這一最小數(shù)值如何根據(jù)建筑高度不同而有所區(qū)別。

下圖回答了以上的問(wèn)題：

（該圖展示了最壞情景的最少投擲次數(shù)，縱軸是樓層數(shù)，橫軸是投擲次數(shù)，曲線代表最優(yōu)投擲次數(shù)。）

你現(xiàn)在對(duì)于谷歌的面試準(zhǔn)備更充分了，但更重要的是，你相比以前更具備算法思想。這個(gè)算法呈現(xiàn)了一個(gè)很好的，高效型的方法。還可應(yīng)用于解決我們每日工作中的許多問(wèn)題。

但愿你喜歡這篇“誠(chéng)意之作”。可以在下方狂點(diǎn)贊表示謝意！

祝大家新年快樂(lè)！大吉大利

原文鏈接：

https://medium./how-to-solve-the-google-recruiters-puzzle-about-throwing-eggs-from-a-building-de6e7ef1755d

回復(fù)“志愿者”加入我們