Re: [討論] Google面試問題

[realboy1977 (遊客)]

※ 引述《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
推 SansWord:這的確是最佳解～但是解釋的方式比較淺顯
推 futureq:強...@@
推 changyuheng:如果第二顆蛋破在第92層 ，怎麼知道該在91還92？
推 GoalBased:92破 怎麼還會再92
推 apley:他意思是破在92, 你怎麼知道安全的極限是90還91?
推 chester06:e.g 1號蛋在90樓丟沒破, 此時x=5, 90+x=95樓再丟一次1號
→ chester06:蛋破掉後, 直接從91樓開始一樓一樓丟2號蛋, 當你在92樓
→ chester06:丟2號蛋第一次破, 那麼91樓就是答案.
→ chester06:x可以隨著coarse search次數逐漸增多而遞減
→ chester06:http://datagenetics.com/blog/july22012/index.html
→ alan3100:樓上跟這篇講的不一樣吧 以樓上作法99層是丟12次
→ changyuheng:@GoalBased，我是說破在 92，如何知道 91 會不會破？
→ changyuheng:@chester06，您說明的和您貼的以及這篇講的都不一樣