NO IMAGE

面試中,為了考察應聘者的思維方式,面試官偶爾會出一些謎題(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網”