作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] Google Interview Question (2)
時間Wed Feb 13 16:21:14 2013
※ 引述《Leon (Achilles)》之銘言：
:
: 這題是考 怎麼找 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
: 推 RockLee:不好意思不是很懂L大的意思 Third round拿X跟2 unkonws比 02/13 15:52
: → RockLee:就可以知道5th嗎? 以下123與ABC的情形要如何區分呢? 02/13 15:52
: → RockLee:(game 1) 1 2 9 (game A) 1 2 7 02/13 15:52
: → RockLee:(game 2) 3 4 5 (game B) 3 4 6 02/13 15:52
: → RockLee:(game 3) 6 7 8 (game C) 5 8 9 02/13 15:53
就用你的例子講解.
After Game (1, 2, and 3), we know the median of the first round is
car with number 2, 4, 7.
Then in the second round, we compare car 2, 4, 7.
Assume the result is 4-2-7. car 4 is the fastest in second round.
In this case, we know car 2 is the median of the median.
Now it's clear that car 2 is slower than 1, and 4, 3
but faster than 9, and 7,8.
So in the third round we just need to compare car with number
2 and two unclear 5 and 6.
你懂了嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 142.136.127.112
1F：推 RockLee:其實我舉例的意思是數字小的就是比較快的 以game 123為例 02/13 16:36
2F：→ RockLee:Third round會拿4 6 9來比 但都不是5th 02/13 16:36
3F：→ Leon:you can draw a graph and it will become clear 02/13 16:56
4F：→ Leon:the third round will tell 4 is the 4th of the cars 02/13 16:57
5F：推 RockLee:But how to tell which car is the 5th after third round 02/13 17:10
7F：→ Leon:去讀 median of median 那一段 02/14 01:48
8F：推 RockLee:Median of Medians那段 看來主要是在講 Median of Medians 02/14 09:41
9F：→ RockLee:保證大於及小於某固定比例的cases 不過看完之後還是無法釐 02/14 09:41
10F：→ RockLee:清我原本的問題: L大完整的步驟到底是什麼? 02/14 09:41
11F：→ RockLee:就第一篇回文 9 cars 的描述 我原本以為只要 Round 3 拿 X 02/14 09:42
12F：→ RockLee:跟 2 unkonws 比完就可以知道哪輛車是 5th 不過就我舉的例 02/14 09:42
13F：→ RockLee:子 Game 123 來看並非如此 02/14 09:42
14F：→ RockLee:L大有空的話 可否好人做到底舉個 49 cars 的 worst case 02/14 09:42
15F：→ RockLee:說明如何保證在 16 步之內找到 25th car? 02/14 09:43