作者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