Fw: [討論] Google面試問題

[bleed1979 (十三)]

※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]

作者: bleed1979 (十三) 看板: Soft_Job
標題: [討論] Google面試問題
時間: Sat Apr 12 02:07:46 2014

問題：

假設你有兩顆蛋，然後有一棟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

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: bleed1979 (220.135.203.156), 04/12/2014 02:15:12
→ milk09012003:直接把兩顆蛋互相相撞不就好了?
→ milk09012003:然後沒破的那個直接從100樓丟下
推 steed:一次啊，就拿去一百樓丟 反正會破就是會破
→ YunJonWei:兩顆蛋，一顆 驗證可承受強度。摔一下就可分析。
→ YunJonWei:再根據承受強度用數學算出在幾樓摔不會破。
→ YunJonWei:最後進行最後一顆蛋的測試驗證。
推 YunJonWei:這是在考你是工程師，還是科學家喔。
推 i386:有兩顆蛋,最多也只能摔兩次不是嗎????
→ i386:抱歉..看錯題意...
推 hobart277:1以[14 27 39 50 60 69 77 84 90 95]順序摔 應該比較快
→ hobart277:                                 ^99
→ NeedGem:會寧可選擇一層一層往上慢慢丟的安全打法的呢 Orz
→ brucelinda:我會把蛋吃掉…
推 XMAno:令人蛋疼……
推 YahooTaiwan:把蛋砸向面試官，說是來應徵工程師的，要砸蛋自己去砸
推 hsienhui:1以[10 20 30 40 50 60 70 80 90]最多是100要19次
→ hsienhui:hobart的比較對
推 smartnick:我覺得3樓是正解耶  直接拿去100F一次往下砸
→ smartnick:會破就是會破  不會破就是不會破 @@
推 archiang:min(100/N+N)
推 polarization:直接問客戶至少要幾樓不會破,直接丟NG或PASS
→ Domos:50樓3次怎麼丟的?
推 dontsmoking:怎麼覺得答案是機率問題？除非那兩顆事先標明誰硬誰軟
推 steed:完全看錯問題...XD 難怪我不會進google
→ YunJonWei:都說兩顆蛋完全相同了，這根本是Hint。
→ YunJonWei:兩顆相同時，一顆拿來做強度驗證破了就算了，
→ YunJonWei:一顆拿來做實驗驗證。這樣最準確了。
→ vidoci:蛋蛋的幸福怎搞到這邊來了
→ ksxo:反正你是在101 立刻做實驗 這種行動力應該可以錄取
推 bandwidth:http://datagenetics.com/blog/july22012/index.html
推 kaoru886:如果我一開始拿去100樓摔，結果蛋沒破，怎辦?
→ kaoru886:畢竟題目也沒有說蛋的最大耐摔高度是多少啊
推 hsctp:純推hobart277
→ hsctp:不但有最佳解，也有最佳策略
→ nctugoodman:這太容易, 改成三顆蛋
推 weisenter:不要浪費雞蛋!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
推 globekjller:我的蛋~~~~~