PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者 (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
推
02/13 16:36, , 1F
其實我舉例的意思是數字小的就是比較快的 以game 123為例
02/13 16:36, 1F
→
02/13 16:36, , 2F
Third round會拿4 6 9來比 但都不是5th
02/13 16:36, 2F
→
02/13 16:56, , 3F
you can draw a graph and it will become clear
02/13 16:56, 3F
→
02/13 16:57, , 4F
the third round will tell 4 is the 4th of the cars
02/13 16:57, 4F
推
02/13 17:10, , 5F
But how to tell which car is the 5th after third round
02/13 17:10, 5F
→
02/14 01:48, , 6F
02/14 01:48, 6F
→
02/14 01:48, , 7F
去讀 median of median 那一段
02/14 01:48, 7F
推
02/14 09:41, , 8F
Median of Medians那段 看來主要是在講 Median of Medians
02/14 09:41, 8F
→
02/14 09:41, , 9F
保證大於及小於某固定比例的cases 不過看完之後還是無法釐
02/14 09:41, 9F
→
02/14 09:41, , 10F
清我原本的問題: L大完整的步驟到底是什麼?
02/14 09:41, 10F
→
02/14 09:42, , 11F
就第一篇回文 9 cars 的描述 我原本以為只要 Round 3 拿 X
02/14 09:42, 11F
→
02/14 09:42, , 12F
跟 2 unkonws 比完就可以知道哪輛車是 5th 不過就我舉的例
02/14 09:42, 12F
→
02/14 09:42, , 13F
子 Game 123 來看並非如此
02/14 09:42, 13F
→
02/14 09:42, , 14F
L大有空的話 可否好人做到底舉個 49 cars 的 worst case
02/14 09:42, 14F
→
02/14 09:43, , 15F
說明如何保證在 16 步之內找到 25th car?
02/14 09:43, 15F
‣ 更多 Leon 的文章
文章代碼(AID): #1H6qpyUx (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 3 之 9 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共9篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 Leon 的文章
文章代碼(AID): #1H6qpyUx (Prob_Solve)