Re: [問題] Google Interview Question (2)

看板Prob_Solve作者Leon (Achilles)時間11年前 (2013/02/13 16:21)推噓3(3推 0噓 12→)

留言15則, 2人參與討論串3/9 (看更多)

※ 引述《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

推

RockLee

02/13 16:36, , 1^F

02/13 16:36, 1^F

→

RockLee

02/13 16:36, , 2^F

02/13 16:36, 2^F

→

Leon

02/13 16:56, , 3^F

02/13 16:56, 3^F