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

25 horses, 5 race tracks. How many races you have to run to select top 3 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) ans assume winning order of this race is w11,w21,w31,w41,w51

Step 3: BECAUSE WE NEED TOP 3 AND W41 HAS COME 4TH Position that is the reason we don't need to consider W41   W42   W43   W44   W45 and also W51   W52   W53   W54   W55
now we have


W11   W12   W13   W14   W15

W21   W22   W23   W24   W25

W31   W32   W33   W34   W35


Step 4: because we need top 3 then dont need W14   W15   W24   W25   W34   W35

now we have

W11   W12   W13   

W21   W22   W23   

W31   W32   W33


Step 5: because in 6th race W31 has come on 3rd position that is the reason we do not need to consider W32,W33 and also we will not consider W23
now we have

W11   W12   W13   

W21   W22  

W31

Step 6:  top 1 is already achieved which is W11(winner of 6th race)
remaining are 

 W12   W13   

W21   W22  

W31

Step 7: now race W12 w13 w21 w22 w31 to get 2nd and 3rd winner

Hence answer is 7 races.