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

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

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/02/14 10:18)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串4/9 (看更多)

※ 引述《Leon (Achilles)》之銘言： : : 推 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 : 我留你的例子和下面寫的東西. 你需要去加強分析的概念, 以及 Quick sort Pivot 的使用. 如果你用上面 Game (1,2,3) 的例子, 以及照你的定義號碼代表車子真正的速度那麼, median of median 這一步是拿 cars 2,4,7 來比. 此時 median of median 是 4. 把這個當作 Pivort, 可以保證 2 < 4, and 1 < 2 from step 1. and 3 < 4 from step 1. 所以我得到 (1,2,3) 比 car 4 快, 以及 (5,7,8) 比 4 慢. 但 (6, 9) 此時是 unknown. 這個題目 scale 比較小, 所以下一步會是比 (4,6,9) 然後我就可以知道, (1,2,3) 比 4 快, (6), (9), (5), (7,8) 比 4 慢. 用這個 Pivort, 我找到了前四個 element (順序不明), 此時要找第五個, 會在 6,9,5 之間產生. 你每次用 median of median, 幹掉某個比例的 element, 很快就找到了. 你參照一下 http://stackoverflow.com/questions/4075289/race-car-puzzle 看 answered Mar 9 '11 at 22:59 Tom Sirgedas 的答案, 我沒有去 trace 每一步, 但大致上應該是對的. : -- : ※ 發信站: 批踢踢實業坊(ptt.cc) : ◆ From: 142.136.127.112 : 推 RockLee:其實我舉例的意思是數字小的就是比較快的以game 123為例 02/13 16:36 : → RockLee:Third round會拿4 6 9來比但都不是5th 02/13 16:36 : → Leon:you can draw a graph and it will become clear 02/13 16:56 : → Leon:the third round will tell 4 is the 4th of the cars 02/13 16:57 : 推 RockLee:But how to tell which car is the 5th after third round 02/13 17:10 : → Leon:http://en.wikipedia.org/wiki/Selection_algorithm 02/14 01:48 : → Leon:去讀 median of median 那一段 02/14 01:48 : 推 RockLee:Median of Medians那段看來主要是在講 Median of Medians 02/14 09:41 : → RockLee:保證大於及小於某固定比例的cases 不過看完之後還是無法釐 02/14 09:41 : → RockLee:清我原本的問題: L大完整的步驟到底是什麼? 02/14 09:41 : → RockLee:就第一篇回文 9 cars 的描述我原本以為只要 Round 3 拿 X 02/14 09:42 : → RockLee:跟 2 unkonws 比完就可以知道哪輛車是 5th 不過就我舉的例 02/14 09:42 : → RockLee:子 Game 123 來看並非如此 02/14 09:42 : → RockLee:L大有空的話可否好人做到底舉個 49 cars 的 worst case 02/14 09:42 : → RockLee:說明如何保證在 16 步之內找到 25th car? 02/14 09:43 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 142.136.127.112 ※ 編輯: Leon 來自: 142.136.127.112 (02/14 10:22)