Re: [問題] Google Interview Question (2)
看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/02/13 15:24)推噓1(1推 0噓 4→)留言5則, 1人參與討論串2/9 (看更多)
※ 引述《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
推
02/13 15:52, , 1F
02/13 15:52, 1F
→
02/13 15:52, , 2F
02/13 15:52, 2F
→
02/13 15:52, , 3F
02/13 15:52, 3F
→
02/13 15:52, , 4F
02/13 15:52, 4F
→
02/13 15:53, , 5F
02/13 15:53, 5F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
