網路城邦
上一篇 回創作列表 下一篇  字體:
谷歌口試題目 Google interview quesiton
2013/05/02 18:13:59瀏覽411|回應0|推薦3

聽說這是Google 的口試題目 :

有25隻馬, 每次競賽只可以跑最多5隻馬, 沒有馬表下, 最少要幾次才可以找出最快的5隻馬?

原文 : There are 25 horses. At a time only 5 horse can run in the single race. How many minimum races are required to find the top 5 fastest horses? Please explain your answer. (There is no timer.)


網路上有很多解法, 7次是最多的說法, 但我套入真實數字時都無法過關, 我自己的解法是 9次.

將25隻馬分成 5 個 group, 在 5 次競賽後找出各組第1,假設得到 a1, b1, c1, d1, e1

a1 a2 a3 a4 a5
b1 b2 b3 b4 b5
c1 c2 c3 c4 c5
d1 d2 d3 d4 d5
e1 e2 e3 e4 e5

所以第 6次是找出  a1, b1, c1, d1, e1 的前兩名 假設成績是 : 

a1> b1>c1>d1> e1, 則a1, b1 為 top 2, 將top2 擺一旁然後取最快的 a1的下兩階及次快 b1 的次排名來進行次輪競賽, e1 為 bottom 1, e1不再參加競賽

第 7次找出 a2, a3, b2, c1, d1 中前兩名為全部的第3, 4名,  假設成績是 :

c1>d1>b2>a2>a3, 則c1, d1為 top 2, 即第3, 4名, 將top2 擺一旁然後取最快的 c1的下兩階及次快 d1 的次排名來進行次輪競賽,a3 為 bottom 1, 不再參加競賽

第8次找出 a2, b2, c2, c3, d2 誰是第5, 6名, 假設成績是 :

b2>c2>a2>d2>c3, 則b2, c2為 top 2, 即第5, 6名,接下只要找出第 6 名就可以解出前5名 

第9次找出'去掉第1名的 a1', 在  b1, b2, c1, c2, d1中有一個是第6名, 假設成績是 :

b1>c1>d1>b2>c2 得 c2 為第 6 名. 故得最快的5隻馬為a1,b1,b2,c1,d1.


後記 : 覺得沒找到最好的解法, 等下週考完試再來想, 不然想到半夜居然睡不著.. 

( 知識學習考試升學 )
回應 推薦文章 列印 加入我的文摘
上一篇 回創作列表 下一篇

引用
引用網址:https://classic-blog.udn.com/article/trackback.jsp?uid=madeleinelee&aid=7570459