Re: [討論] Google面試問題

[cdmdrdtw (昌仔)]

※ 引述《Domos (沒事發發廢文)》之銘言：
: ※ 引述《bleed1979 (十三)》之銘言：
: : 作者: 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樓的問題
:    總共 m - x + 1 個級距 (包括m樓不破)
: 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+1, k) + 1
:    (記得加一，已經丟一次了)
:    新變數k表示第二次從k樓丟下
:    f(n, 100) = n/(101) * g(n) + (1-n/101) * f(101-n, k) + 1
: 4. f'(m)表示f(n, m)值域的min (我們要求的)
:    f'(1) = 1
:    f'(2) = 5/3
:    照這樣一路求到f'(100)



我的看法答案是:破掉的樓層/2 小數點有.5的話進位+1次
我的測試方法會是將第一顆蛋以雙數位樓層來丟
當丟到破掉時候已另一顆蛋回推一樓層丟確定前一樓層的但是破還是不會破
舉例:假設九樓破  2.4.6.8.1O十樓破的時候我就拿第二顆蛋在九樓丟
如果沒破就是十樓,如果破了就是九樓
現在假設九樓有破
這樣丟了六次就知道答案了:9/2=4.5進位+1=6
只要十樓有破就要回推一層樓驗證所以要有兩顆蛋
相對的是十樓破,只丟2.4.6.8.10樓拿第二顆蛋測試9樓是否會破
答案就是10/2+1次=6次
我的想法是比較保守因為是兩顆蛋
如果有三顆蛋的話可以以三的倍數去測試
答案是以蛋顆數決定

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.166.128
※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397270830.A.FF3.html
→ cdmdrdtw:題目蛋堅硬是無上限,所以沒有一定的數字我才有這種想發
→ fashion0604:既然無上限,1~100樓大家各拿一顆不同時間往下丟。
→ fashion0604:阿一次就知道了阿
→ wrt:人家有100樓 你只有10樓  應該會被淘汰
→ cdmdrdtw:他只是舉立雞蛋的硬度可能很硬或很脆弱
→ cdmdrdtw:沒有說雞蛋一定是一樓或一百樓會破掉吧!!
→ cdmdrdtw:回2F我的無上限說硬度!!但他說雞蛋只有兩顆
→ dider:三層一級距dominate 兩層一級距, 三層 vs 四層則不一定
→ dider:2科但也可以做三層一級距 四層一級距 仔細想一下吧