Re: [討論] Google面試問題

看板Soft_Job作者 (遊客)時間11年前 (2014/04/16 16:46), 編輯推噓6(6推 0噓 7→)
留言13則, 7人參與, 最新討論串10/19 (看更多)
※ 引述《brucetu (sec)》之銘言： : 既然知道兩個蛋相同 : 就再找98個相同的蛋 從1~100樓同時落下 : 再算算看有幾顆蛋 : 平行處理 : ※ 引述《howdiun (Howdiun)》之銘言： : : 把蛋交給別人， : : 叫他從一樓開始丟， : : 破掉再跟我回報樓層， : : 我會付他薪水， : : 為了怕她騙我， : : 我可以一次請兩個人（反正有2個蛋）， : : 我要摔幾次？ : : 0次 這個應該和camera af差不多的algorithm 第一顆蛋做coarse search,第二顆做fine search 所以假設第一顆一次跳x層樓，最差跳100／x次 第二顆要找x-1次 所以找100/x + x／2-1的最小值 x大約是10 也就是說第一顆蛋每10樓丟一次 最差情況是在99樓，丟10次 第二顆可2層丟一次，要丟4次 共14次 不知這答案可不可行 -- Sent from my Android -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.74.136.62 ※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397637976.A.C51.html
推
04/16 17:40, , 1F
這的確是最佳解～但是解釋的方式比較淺顯
04/16 17:40, 1F
推
04/16 18:56, , 2F
強...@@
04/16 18:56, 2F
推
04/16 19:05, , 3F
如果第二顆蛋破在第92層 ，怎麼知道該在91還92？
04/16 19:05, 3F
推
04/16 19:26, , 4F
92破 怎麼還會再92
04/16 19:26, 4F
推
04/16 19:38, , 5F
他意思是破在92, 你怎麼知道安全的極限是90還91?
04/16 19:38, 5F
推
04/16 21:07, , 6F
e.g 1號蛋在90樓丟沒破, 此時x=5, 90+x=95樓再丟一次1號
04/16 21:07, 6F
→
04/16 21:08, , 7F
蛋破掉後, 直接從91樓開始一樓一樓丟2號蛋, 當你在92樓
04/16 21:08, 7F
→
04/16 21:08, , 8F
丟2號蛋第一次破, 那麼91樓就是答案.
04/16 21:08, 8F
→
04/16 21:09, , 9F
x可以隨著coarse search次數逐漸增多而遞減
04/16 21:09, 9F
→
04/16 22:22, , 11F
樓上跟這篇講的不一樣吧 以樓上作法99層是丟12次
04/16 22:22, 11F
→
04/17 00:14, , 12F
@GoalBased，我是說破在 92，如何知道 91 會不會破？
04/17 00:14, 12F
→
04/17 00:17, , 13F
@chester06，您說明的和您貼的以及這篇講的都不一樣
04/17 00:17, 13F
‣ 更多 realboy1977 的文章
文章代碼(AID): #1JJaDOnH (Soft_Job)
討論串 (同標題文章)
完整討論串 (本文為第 10 之 19 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共19篇)
‣ 更多 realboy1977 的文章
文章代碼(AID): #1JJaDOnH (Soft_Job)