Google面試問題 - 面試
By Hamiltion
at 2014-04-13T12:08
at 2014-04-13T12:08
Table of Contents
個人認為正解是「最多七次」
因為一次可以刪掉最多50%的二分法,最多到第七次就能測出了
大家可以畫二分法的樹狀圖,第七層就答案出來了
第一次:丟50樓
第二次:有破丟25樓,沒破去75樓丟
依此類推.....
(接下來bbs我不會畫樹狀圖,所以只列出每次都破的情況)
第三次:有破丟13樓
第四次:有破丟7樓
第五次:有破丟4樓
第六次:有破丟2樓
第七次:視上面結果,再去1或3樓丟,答案出來!
以上面結果為例,可能的歷史進程就是
progress(50,25,13,7,4,2,1)=>得證1樓就會破
progress(50,25,13,7,4,2,3)=>得證到3樓才會破,2樓safe
還有另外62種可能的結果
因樹狀圖共有七階,有2的(7-1)次方,總共64種可能的歷史進程,但最多只要測7次
另顆蛋是完全相同的,所以沒必要再測一次,只是益智題的障眼法。
※ 引述《bleed1979 (十三)》之銘言:
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題:
: 假設你有兩顆蛋,然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固,堅固到從一百層樓跌下都沒事,
: 有的可能很脆弱,一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的,
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是:你要摔幾次才能計算出來?
: (如果你低於高度摔下蛋,蛋就沒事,如果高於那個樓層,蛋就完蛋)
: 在這過程你可以摔破蛋。
: --- 以下是完全不經大腦思考的 rough 策略,有雷 ---
: http://ideone.com/B7E85H
--
因為一次可以刪掉最多50%的二分法,最多到第七次就能測出了
大家可以畫二分法的樹狀圖,第七層就答案出來了
第一次:丟50樓
第二次:有破丟25樓,沒破去75樓丟
依此類推.....
(接下來bbs我不會畫樹狀圖,所以只列出每次都破的情況)
第三次:有破丟13樓
第四次:有破丟7樓
第五次:有破丟4樓
第六次:有破丟2樓
第七次:視上面結果,再去1或3樓丟,答案出來!
以上面結果為例,可能的歷史進程就是
progress(50,25,13,7,4,2,1)=>得證1樓就會破
progress(50,25,13,7,4,2,3)=>得證到3樓才會破,2樓safe
還有另外62種可能的結果
因樹狀圖共有七階,有2的(7-1)次方,總共64種可能的歷史進程,但最多只要測7次
另顆蛋是完全相同的,所以沒必要再測一次,只是益智題的障眼法。
※ 引述《bleed1979 (十三)》之銘言:
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題:
: 假設你有兩顆蛋,然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固,堅固到從一百層樓跌下都沒事,
: 有的可能很脆弱,一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的,
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是:你要摔幾次才能計算出來?
: (如果你低於高度摔下蛋,蛋就沒事,如果高於那個樓層,蛋就完蛋)
: 在這過程你可以摔破蛋。
: --- 以下是完全不經大腦思考的 rough 策略,有雷 ---
: http://ideone.com/B7E85H
--
Tags:
面試
All Comments
By Gary
at 2014-04-16T00:14
at 2014-04-16T00:14
By Eden
at 2014-04-20T23:40
at 2014-04-20T23:40
By Quanna
at 2014-04-21T23:47
at 2014-04-21T23:47
By Leila
at 2014-04-24T13:11
at 2014-04-24T13:11
By Bennie
at 2014-04-27T04:38
at 2014-04-27T04:38
By Agatha
at 2014-04-29T10:20
at 2014-04-29T10:20
By Irma
at 2014-05-02T13:17
at 2014-05-02T13:17
By Damian
at 2014-05-05T04:39
at 2014-05-05T04:39
By Jake
at 2014-05-09T00:45
at 2014-05-09T00:45
By Enid
at 2014-05-13T00:38
at 2014-05-13T00:38
By Cara
at 2014-05-14T07:26
at 2014-05-14T07:26
By Agatha
at 2014-05-15T07:47
at 2014-05-15T07:47
By Irma
at 2014-05-16T02:08
at 2014-05-16T02:08
By Joe
at 2014-05-20T23:01
at 2014-05-20T23:01
By Charlotte
at 2014-05-23T19:54
at 2014-05-23T19:54
By Dorothy
at 2014-05-25T19:24
at 2014-05-25T19:24
By Zanna
at 2014-05-26T16:43
at 2014-05-26T16:43
By Eden
at 2014-05-27T23:50
at 2014-05-27T23:50
By Skylar DavisLinda
at 2014-05-31T20:10
at 2014-05-31T20:10
By Jacob
at 2014-06-04T14:32
at 2014-06-04T14:32
By Oscar
at 2014-06-05T16:13
at 2014-06-05T16:13
By Erin
at 2014-06-10T13:53
at 2014-06-10T13:53
By Ingrid
at 2014-06-13T13:16
at 2014-06-13T13:16
Related Posts
offer請益
By Queena
at 2014-04-13T07:03
at 2014-04-13T07:03
一個面試時的益智問題
By Necoo
at 2014-04-13T06:02
at 2014-04-13T06:02
一個面試時的益智問題
By Quanna
at 2014-04-13T02:31
at 2014-04-13T02:31
一個面試時的益智問題
By Bennie
at 2014-04-13T01:42
at 2014-04-13T01:42
轉職好難...
By Hardy
at 2014-04-13T01:08
at 2014-04-13T01:08