Re: [討論] Google面試問題:－2016大台北美食推薦懶人包【食記】台北車站 | 微風美食廣場-夢卡朵/咖哩飯【台北餐廳】人氣拉麵～花月嵐拉麵台北車站台北平價餐廳美食總整理

Blogtrottr

批踢踢實業坊 Tech_Job 板

Apr 12th 2014, 20:24, by Munro

作者Munro ( )

看板Tech_Job

標題Re: [討論] Google面試問題

時間Sat Apr 12 20:24:18 2014

最佳策略是先用一顆蛋用二分法 e.g., 50F 沒破 -> 可能區間(51 - 100) ; 破 -> 可能區間(1 - 49) 用同樣方法縮小可能區間直到第一顆蛋破掉接下來第二顆蛋就只能從當時知道的可能區間最低樓層一樓一樓增加才能確保當蛋破掉的時候可以確定答案 best case 可以在log2 100 次左右用一顆蛋就得到答案 worse case (50F 第一顆蛋就破掉) 就是1+49次 ※ 引述《eetug (eetug)》之銘言： : ※ 引述《bleed1979 (十三)》之銘言： : : 作者: 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), 來自: 123.240.208.86 ※ 文章網址: http://www.ptt.cc/bbs/Tech_Job/M.1397305461.A.B88.html

噓 bitcx:你被fire了 04/12 20:24

→ Munro:enlighten me 04/12 20:27

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.

You are receiving this email because you subscribed to this feed at blogtrottr.com.

If you no longer wish to receive these emails, you can unsubscribe from this feed, or manage all your subscriptions