[討論] Google面試問題

[bleed1979 (十三)]

問題：

假設你有兩顆蛋，然後有一棟100層樓高的大樓。

而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，

有的可能很脆弱，一樓就可以摔破。

現在你只知道這這兩顆蛋是完全相同的，

你想要知道蛋最高從哪一層樓摔下來不會摔破。

問題是：你要摔幾次才能計算出來？

（如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）

在這過程你可以摔破蛋。


--- 以下是完全不經大腦思考的 rough 策略，有雷 ---




http://ideone.com/B7E85H

策略是：

當我還有兩次機會時，我使用二分法。

當我只剩一次機會時，選擇已經安全的樓層 + 1。　

附上此策略的解答 樓層 => 次數

1=>3
2=>4
3=>5
4=>6
5=>7
6=>8
7=>9
8=>10
9=>11
10=>12
11=>13
12=>14
13=>15
14=>16
15=>17
16=>18
17=>19
18=>20
19=>21
20=>22
21=>23
22=>24
23=>25
24=>26
25=>27
26=>28
27=>29
28=>30
29=>31
30=>32
31=>33
32=>34
33=>35
34=>36
35=>37
36=>38
37=>39
38=>40
39=>41
40=>42
41=>43
42=>44
43=>45
44=>46
45=>47
46=>48
47=>49
48=>50
49=>50
50=>3
51=>4
52=>5
53=>6
54=>7
55=>8
56=>9
57=>10
58=>11
59=>12
60=>13
61=>14
62=>15
63=>16
64=>17
65=>18
66=>19
67=>20
68=>21
69=>22
70=>23
71=>24
72=>25
73=>26
74=>26
75=>4
76=>5
77=>6
78=>7
79=>8
80=>9
81=>10
82=>11
83=>12
84=>13
85=>14
86=>15
87=>15
88=>5
89=>6
90=>7
91=>8
92=>9
93=>9
94=>6
95=>7
96=>7
97=>7
98=>7
99=>7
100=>7



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.135.203.156
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397239669.A.7EE.html
推 PasserDin:有點像資料結構中  討論排順序的感覺@@
→ lovdkkkk:2 顆時十層試一次, 一顆時每次加一層, 最多不超過 19 次
→ lovdkkkk:以上是想了二分鐘的想法
推 sealer:最多14次?
→ sealer:第一次從14層丟，沒破就+13，沒破再+12...依此遞減
→ sealer:中間如果一顆破了剩下那顆每次加一層
推 lovdkkkk:推樓上, (我猜)重點是最佳化 worst case, best case 沒差
推 GX90160SS:sealer答案目前看來最好
推 SheLoBDenI:直接從50樓丟，破了再從25，沒破從75。這樣呢？
推 SheLoBDenI:我蠢了...
推 duck10704:為什麼是從14層開始丟壓  @@
→ y3k:我有個笨問題 不是說只有兩顆蛋嗎....
→ y3k:當我沒問 看錯了XDDD
推 YahooTaiwan:to y3k: 蛋砸了不一定會破阿
→ YahooTaiwan:慢了一步 當我沒回答
→ y3k:XD樓上
→ inker610566:uva好像有這題的推廣版 http://ppt.cc/TIjz
→ y3k:我的作法會同sealer 不過我第二顆是+2上去 因為你不用留蛋XD
→ y3k:恩....?好像也不對 那sealer大的解應該是最好了吧@@
推 kkkmode:那可以討論好解答再去google面試嗎XD
→ Lordaeron:第一顆從50樓丟下,破了, 就從1測到49,頂多50次
→ Lordaeron:若沒破,則再從75再測,破了就在51~74之間,沒破就在
→ Lordaeron:76~100之間, 再對半測,如此類推, 所以, 最多50次
→ Lordaeron:最少就是100層才破的, 共6 次
推 jej:這不就統計的負二項 懂點統計去面試google會不會變得很容易?
→ x000032001:那如果1F摔一次沒破 摔一萬次破了呢
推 aby0d6q5n:不確定是不是我題目理解錯誤... 我一次摔會摔N,N+1樓
→ aby0d6q5n:之後就是binary search?
→ michaelz:這是好多年的老題了
推 usoko:推sealer
推 chatnoir:其實我一直很好奇這類的問題要怎麼去練,念數學?資結?
推 bobju:這類問題若要[練]的話 找本題庫拼命[練]就對了 會有效果
→ bobju:但若要入門的話 還是得修些離散數學 演算法之類的課程 至少
→ bobju:知道資訊科學方面的知識是如何用數學以及符號來表達
推 amozartea:Binary search?
推 heerowei0802:sealer法不完全,一旦破了沒必要1層1測,每次+2測即可
推 heerowei0802:仔細想想沒法每次+2丟...sorry~
推 orange7986:推sealer大