作者eetug (eetug)
看板Tech_Job
標題Re: [討論] Google面試問題
時間Sat Apr 12 17:46:22 2014
※ 引述《bleed1979 (十三)》之銘言:
: ※ [本文轉錄自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 標題: [討論] Google面試問題
: 時間: Sat Apr 12 02:07:46 2014
: 問題:
: 假設你有兩顆蛋,然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固,堅固到從一百層樓跌下都沒事,
: 有的可能很脆弱,一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的,
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是:你要摔幾次才能計算出來?
: (如果你低於高度摔下蛋,蛋就沒事,如果高於那個樓層,蛋就完蛋)
: 在這過程你可以摔破蛋。
: --- 以下是完全不經大腦思考的 rough 策略,有雷 ---
: http://ideone.com/B7E85H
: 策略是:
: 當我還有兩次機會時,我使用二分法。
: 當我只剩一次機會時,選擇已經安全的樓層 + 1。
我的策略
1.先以十樓為單位丟,
2.丟到會破的,再減9個樓層丟
最快時間
1樓破:2次,一次十樓,一次一樓
最慢時間
99樓
10次+9次=>19次
10次是10 20 30~100 。共 10 次才會破
9次是 91 92 到99樓 ,共 9次才會破
以上為面試 google的答案
如果是面試鴻海,我會叫供應商提測試報告
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.163.217
※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397295984.A.675.html
推 ur260:送ITS 04/12 18:08
推 kuoll:首篇的推文已經有最佳解是14次 怎麼很多人都沒看到的樣子 04/12 18:37
推 apley:按邏輯最佳解就是14次了, 去看看人家的方式吧 04/12 20:28
→ apley:況且你要以10為基準當你的最佳化方式, 也要能說明為何是10? 04/12 20:30
→ apley:難道1~9或11~50之類的不好嗎? 靠感覺是絕對行不通的 04/12 20:31