Re: [討論] Google面試問題
1 + 2 + ... + N > 100
其實不是簡單的一題 .. 我第一次被問30分鐘內沒解出來
金融業蠻常問這題的~
※ 引述《cdmdrdtw (昌仔)》之銘言：
: ※ 引述《Domos (沒事發發廢文)》之銘言：
: : 先假設蛋的硬度是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), 來自: 207.38.237.98
※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397272267.A.658.html
※ 編輯: tiwei (207.38.237.98), 04/12/2014 11:11:24
推
04/12 12:01, , 1F
04/12 12:01, 1F
→
04/12 14:27, , 2F
04/12 14:27, 2F
推
04/12 15:19, , 3F
04/12 15:19, 3F
推
04/12 16:59, , 4F
04/12 16:59, 4F
→
04/12 17:10, , 5F
04/12 17:10, 5F
推
04/12 18:58, , 6F
04/12 18:58, 6F
討論串 (同標題文章)