作者RockLee (Now of all times)
看板Prob_Solve
標題[問題] Google Interview Question (2)
時間Tue Feb 12 09:11:13 2013
原始網址:
http://www.careercup.com/question?id=4280852
題目:
49 race cars and no two have the same speed.
Now give you 7 tracks with equal length to find the 25th fastest car.
At least how many races are needed.(no time recorder)
這個題目有兩種可能的解讀,
比較簡單的解讀是一開始幸運選中25th的車,
要進行多少次比賽證明它是25th?
這種解讀答案應該是8次.
因為扣掉選中的車還有48台車,
每次可拿選中的車跟其它6台比,
48/6=8.
我想第二種解讀應該比較符合Google的程度,
最少要比多少次可以保證找出25th的車?
目前我覺得正確的方法中最少的應該是以下網站描述的18次:
http://www.sureinterview.com/shwqst/1062001/154001
該方法的一種 worst case:
1 2 3 4 13 14 XX <- group 1
5 6 7 8 15 16 XX <- group 2
9 10 11 12 17 18 XX <- group 3
19 20 XX 34 35 36 37 <- group 4
XX 28 29 38 39 40 41 <- group 5
XX 30 31 42 43 44 45 <- group 6
XX 32 33 46 47 48 49 <- group 7
(XX: 21 ~ 27)
不知道是否有比18次更少的方法?
或者有辦法證明18次是最少的嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.88.12
1F：推 Favonia:這網站描述的顯然不是最佳，因為 Round One 第3步兩次足矣 02/13 04:58
2F：→ RockLee:不是應該三次嗎? Ex. (group 1[5~7], group 5[1~3]), 02/13 07:49
3F：→ RockLee:(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3]) 02/13 07:50
4F：推 pika0923:group 1[5~7] 先跟6比 再跟5或7其中之一比 兩次 02/13 08:49
5F：→ RockLee:了解 所以照網站描述的方法 Round Two 應該也只需要兩次 02/13 12:36
6F：→ RockLee:總共 16 次即可保證找出 25th 還有辦法更少嗎? 02/13 12:37