關于編程工作有很多很不錯的面試謎題。新年之際，我把壓箱底兒的一道好題，同時也是傳說中谷歌招聘官最喜歡問的一道題找出來了!

今天我們來好好八一八這道題，如果你今年恰好想去谷歌面試，可以抓緊多讀幾遍!(絕對不會出現下圖的情況，我們只放有口碑的神助攻

題目如下：

你在一座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,

正是我們計算的結果!贊!

拓展

現在我們有了一套可以解決很多相似問題的不錯的算法。比如說，我們可以稍微修改一下來計算最隨機的情況下的投擲次數。我們也可以看看這一最小數值如何根據建筑高度不同而有所區別。

下圖回答了以上的問題：

(該圖展示了最壞情景的最少投擲次數，縱軸是樓層數，橫軸是投擲次數，曲線代表***投擲次數。)

結論

你現在對于谷歌的面試準備更充分了，但更重要的是，你相比以前更具備算法思想。這個算法呈現了一個很好的，高效型的方法。還可應用于解決我們每日工作中的許多問題。