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

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

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

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

※ 引述《Leon (Achilles)》之銘言： : : 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. OK, here is my reply. Sorry for the delay, I have been busy on something. The reason I can't understand your statement in the last few lines of Step A is: You claim you can use 2 races to get the 'order' of median of median. (I don't like the word 'rank'). Based on your previous artiule, it's .. 推 Favonia:這網站描述的顯然不是最佳，因為 Round One 第3步兩次足矣 02/13 04:58 → RockLee:不是應該三次嗎? Ex. (group 1[5~7], group 5[1~3]), 02/13 07:49 → RockLee:(group2[5~7], group6[1~3]), (group3[5~7], group7[1~3]) 02/13 07:50 推 pika0923:group 1[5~7] 先跟6比再跟5或7其中之一比兩次 02/13 08:49 → RockLee:了解所以照網站描述的方法 Round Two 應該也只需要兩次 02/13 12:36 → RockLee:總共 16 次即可保證找出 25th 還有辦法更少嗎? 02/13 12:37 The original statement from pika0923 is not going to work. ( However, he propose a good method in the later article. ) Now I use the notation in pika0923's articule, It's very clear and good written. We should give him some credit. First we separate the cars into 7 groups, and sort them. Then we have Group A, B, .. etc, with their order inside the same group. We run an additional sorting on median of each group, get the 'median' of median, assume it's D4. It's possible to get the 'order' of the D4 faster. The relations between D4 and upper-left and lower-right are known. We need to figure out upper-right and lower-left. The trick is, you compare D4 with the 'median' of the rest. Say, A[6], B[6], C[6] and E[2], F[2], G[2]. With one comparsion, you not only get the relation between D[4] and the element and also the one connected to it in the same group. For example, if C[6] < D[4] ( faster ), we also know C[5] < C[6] < D[4]. Thus, no reason to compare C[5] anymore. The same arguement holds the other way around. Basically, in your description : : (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. It's not trivial at all. You need to compare it with 'median' of the rest to get this step. I suggests you to read the article by pika0923. His example is very easy to read and seems to be right. I am also interested in the "Decision Tree" notation. Do you want to say more about this? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 142.136.127.172