Google面試問題 - 面試

※ 引述《bleed1979 (十三)》之銘言：
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。

先假設蛋的硬度是uniform distribution

以100層來說，我們分成1~101級

1級表示1樓摔下來就破

100級表示100樓摔下來破

101級表示100樓摔下來也不破

所以我們有101個級距，uniform distributed

你可以挑戰這個假設，例如使用normal distribution

或是增加級數，例如200個級距，但101級後就只能確定屬於100層

但我們先討論最簡單的case

1. 在此假設下，我們從n樓丟下，蛋破的機率是 n/101

延伸此假設，在最高m樓的情況下，從n樓將蛋丟下

蛋破的機率是 n/(m+1)

2. 假設蛋在x樓破了，我們就被迫從1樓開始丟起

此時的期望值為 g(x) = (x*x + x - 2)/ 2x

我們先假設x是6 (從第6層丟下結果破了)

可能的情況有

1破 => 1次

2破 => 2次

3破 => 3次

4破 => 4次

5破 => 5次

5不破6破 => 5次

每種情況的機率是 1/6

(1+2+3+4+5+5)/6 = 20/6 = g(6)

3. 假設蛋在x樓丟下不破

等於是變成 x+1樓 ~ m樓的問題

問題可以轉化成 1樓 ~ m-x樓的問題

總共 m - x + 1 個級距 (包括m-x樓不破)

3. 綜合(1) (2) (3)

在最高m樓的情況下，將二顆蛋從n樓丟下次數的問題

可以看成是 蛋破的機率 * 一顆蛋在最高n樓丟下次數的問題

+ 蛋不破的機率 * 二顆蛋從n+1樓~m樓丟下次數的問題

f(n, m) = n/(m+1) * g(n) + (1-n/(m+1)) * f(m-n, k) + 1

(記得加一，已經丟一次了)

新變數k表示第二次從k樓丟下

f(n, 100) = n/(101) * g(n) + (1-n/101) * f(100-n, k) + 1

4. f'(m)表示f(n, m)值域的min (我們要求的)

f'(1) = 1

f'(2) = 5/3

照這樣一路求到f'(100)

--