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

[Leon (Achilles)]

※ 引述《RockLee (Now of all times)》之銘言：
: ※ 引述《Leon (Achilles)》之銘言：
: : 你每次用 median of median, 幹掉某個比例的 element,
: : 很快就找到了.
: : 你參照一下
: : http://stackoverflow.com/questions/4075289/race-car-puzzle
: : 看
: : answered Mar 9 '11 at 22:59
: : Tom Sirgedas
: : 的答案, 我沒有去 trace 每一步, 但大致上應該是對的.
: 我明白 median of medians 可以每次幹掉某個比例的 elements
: 但重點是所謂的 "很快就找到了" 到底有多快呢?
: Tom Sirgedas 說他的解法需要 17 次
: 而我之前貼的網站的解法經 F 大及 P 大點出可以改進的地方後
: 看來只需要 16 次 所以目前看來最佳解是 16 次

小弟 (或是大哥?) 我不太喜歡幫人 trace code,
不過你這個簡直是得太明顯了

: 那個網站的解法基本上也是在幹掉某個比例的 elements
: 以下是將該網站的解法修正後16次的版本
: 如果有錯誤或還可以改進的地方再麻煩指出了:
: Step A (Find the rank of the median of medians):
: (7 races) Divide the cars into 7 groups and get the order within each group.
: (1 race)  Take the 7 medians and get the order. Find the median of medians
:           (denote as o). In following example, it is 34.

下面這一步, upper-right and lower-left 共有 18 elements,
你怎麼用 2 races 就和 pivort 比出來?


: (2 races) Find the rank of the median of medians. Take 6 elements from
:           lower-left corner and upper-right corner and race against the o.
:           After 2 rounds, we know the rank of this median of medians within
:           in the whole set.
:           The best case is that o is the global median (25th fastest).
:           The worst case is that o is the 16th or 34th fastest.



: Example:
: 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)
: Step B (We want to find the rank of other medians in a binary search fashion):



: (2 races) Pick the median less than 34, which is 12.
:           Race it against the lower-left and upper-right corner cars.
:           After 2 races, we know its rank is 12.
:           Now, the gap between those two medians are at most 21,
:           as shown in this example.
: Rearrange the 21 cars (>12 and <34) as follows:
: 13  14  XX  <- group 1
: 15  16  XX  <- group 2
: 17  18  XX  <- group 3
: 19  20  XX  <- group 4
: XX  28  29  <- group 5
: XX  30  31  <- group 6
: XX  32  33  <- group 7
: Step C
: (1 race) Find the median of medians again, which is 20.
: (1 race) Find its rank.
:          After this step, we know the car in previous step is ranked 20.
: (1 race) Similar to step A, check the rank of another median, 28.
: (1 race) Sort all cars between 21 ~ 27. The 25th fastest car is found.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 142.136.127.112
推 RockLee:其實這正是F大及P大點出可以改進的地方 以所舉的case為例
→ RockLee:第一次先拿 34 跟 14 16 18 28 30 32 比 就知道第二次拿
→ RockLee:34 跟 XX XX XX (upper-right) 29 31 33 比即可
→ Leon:我看不懂你寫甚麼
推 RockLee:意思是雖然 upper-right and lower-left 共有 18 elements
→ RockLee:但其實 pivort 只需和其中 12 elements 比即可知道 rank
→ Leon:write a articule and I will take a look after dinner
→ RockLee:方法是先和 medians of upper-right and lower-left 比
→ RockLee:例如 34 跟 14 比過之後就知道不需要跟 13 比了
→ RockLee:不好意思推完才發現L大希望我回文
→ Leon:你的方法應該不對, 你寫篇 detail 的作法
推 RockLee:不好意思 L大可以指出哪個部分有誤或不夠detail嗎?
推 yoco315:我也想看 Leon 大大的詳解 XD