作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] Google Interview Question (2)
時間Wed Feb 13 15:24:45 2013
※ 引述《RockLee (Now of all times)》之銘言：
: 原始網址:
: 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次是最少的嗎?
18 次太誇張了吧.
這題是考 怎麼找 Median, 你可以用 Quick Sort 的變形去找.
你先考慮一下簡單的題目:
要是有 9 cars, and has a run way with 3 laps
How to do it?
First round: do a run with 3 cars, we need 3 games.
Second round: We pick the 'median' of the first round,
thus, we will have `median of the median'.
We call it X.
Now, we are sure 3 cars are faster than X, 3 cars are slower than X.
2 cars are unknown.
Third round will be X and 2 unkonws.
用這個 Median of Median 的原理, 你就能解那個 49 cars case.
我就留給你自己補完了.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.127.112
1F：推 RockLee:不好意思不是很懂L大的意思 Third round拿X跟2 unkonws比 02/13 15:52
2F：→ RockLee:就可以知道5th嗎? 以下123與ABC的情形要如何區分呢? 02/13 15:52
3F：→ RockLee:(game 1) 1 2 9 (game A) 1 2 7 02/13 15:52
4F：→ RockLee:(game 2) 3 4 5 (game B) 3 4 6 02/13 15:52
5F：→ RockLee:(game 3) 6 7 8 (game C) 5 8 9 02/13 15:53