25 horses 5 tracks 5 fastest horses puzzle | Google Interview Question


25 horses, 5 race tracks. How many races you have to run to select top 5 horses.

Solution:

Step 1: First, we group the horses into groups of 5 and race each group in the race course. This gives us 5 races.



W11   W12   W13   W14   W15

W21   W22   W23   W24   W25

W31   W32   W33   W34   W35

W41   W42   W43   W44   W45

W51   W52   W53   W54   W55


Step 2:we race the 5 level 1 winners(w11,w21,w31,w41,w51) and assume winning order of this race is w11,w21,w31,w41,w51 (THIS IS 6TH RACE)

Step 3: BECAUSE WE NEED TOP 5 AND W51 HAS COME 5TH Position that is the reason we don't need to consider W52   W53   W54   W55 
now we have

W11   W12   W13   W14   W15

W21   W22   W23   W24   W25

W31   W32   W33   W34   W35

W41   W42   W43   W44   W45

W51

Step 4: because we need top 5 then dont need    W25   W34   W35   W43   W44   W45

now we have

W11   W12   W13   W14   W15

W21   W22   W23   W24   

W31   W32   W33  

W41   W42   

W51


Step 5:  top 1 is already achieved which is W11(winner of 6th race)
remaining are 
   X        W12   W13   W14   W15

W21   W22   W23   W24   

W31   W32   W33  

W41   W42   

W51

Step 6: candidates for 5th position:  W51 W42 W33 W24 W15. 1 RACE TO GET 5TH POSITION (this is 7th race)

remaining are

 X        W12   W13   W14   

W21   W22   W23   

W31   W32 

W41


Step 7:  candidates for 4th position: W41 W32 W23 W14. 1 race to get 4th position ((this is 8th race)

X        W12   W13   

W21   W22   

W31


Step 8: candidates for 2nd and 3rd position:  W12   W13   W21   W22   W31. 1 race to get 2nd and 3rd  position ((this is 9th race)


Hence answer is 9 races.





Comments

  1. UnknownOctober 25, 2017 at 12:37 PM

    I think step-6 is wrong. All horses remaining after step-5 can be candidate of 5th position.

    ReplyDelete
  2. UnknownNovember 8, 2017 at 12:38 PM

    Can't this be the order of race result. W11 > W12 > W21 > W13 > W22. If this can be the order, then I don't think proposed solution can find the correct result. Correct me if I am wrong. Thanks

    ReplyDelete
  3. UnknownJuly 3, 2019 at 3:52 AM

    this solution is entirely wrong after you eliminate lower right of the square(after 6th step). 4th and 5t can be one of W13 or W22 or W31 or W32 or W23 or W41 or W14

    ReplyDelete
  4. UnknownMay 17, 2020 at 11:50 PM

    Correct answer should be 10. You should find top 5 in order. Once you eliminate W11, the next step is to find the horse who ranks second. It's either W12 or W21. Because no horse can beat w21 except horses in group1. Put W12 in and race again: (W12, W21, W31, W41, W51). Eliminate the first and put the one next to the first in from the same group. Repeat the process until find the top 5.

    Answer is 10

    ReplyDelete
  5. jane hollyAugust 2, 2020 at 6:28 PM

    After a long time of searching for a recovery expert and platforms to help me recovering my funds, I finally meet a ethical hacker who helped me to recovery all i have lost to this broker site 24options worth $30 Thoushand USD, and I must say that he's a God sent, His help was quite outstanding from the handling of the case by the case manager to completion. I just want to say thank you onlineghosthacker247 for this rare opportunity to get my funds back when all hope seems lost due to the sea of scams out there. I totally recommed him and you can reach him on his email ( onlineghosthacker247 @ gmail . com) and thank me later .

    ReplyDelete

Post a Comment