Interview Question – Find top three horses

Interview Question – Find top three horses :

You are given five race tracks and twenty five horses.Find the minimum number of races you need to organize to find the fastest three horses. Here five race tracks means that only five horses can run at a time.

Solution

The trick to approach these type of probelm is to consider the corner cases, most of the times what seems obvious is not what is true.

Lets name the five tracks as

T1 , T2, T3 , T4 , T5

and we organize five races in the beginning Let us say that we have the horses named from A – Y.

Lets organize the below races on the respective tracks:

T1 – A , B , C , D , E – Race1
T2 – F , G , H , I , J – Race2
T3 – K , L , M , N , O – Race3
T4 – P , Q , R , S , T – Race4
T5 – U , V , W , X , Y – Race5

We can safely assumed that the horses
A , B , C , D , E are rank 1 , 2 , 3 , 4 , 5 on track T1 ,
F , G , H , I , J are rank 1 , 2 , 3 , 4 , 5 on track T2 ,
K , L , M , N , O are rank 1 , 2 , 3 , 4 , 5 on track T3 ,
P , Q , R , S , T are rank 1 , 2 , 3 , 4 , 5 on track T4 ,
U , V , W , X , Y are rank 1 , 2 , 3 , 4 , 5 on track T5 ,

A , F , K , P , U are the fastest horses on their respective tracks T1 , T2 , T3 , T4 , T5.

At this point of time we can be sure of just one thing, that the fastest horse among the twenty five horses is one among A , F , K , P , U. Hence we organize one more race on any of the track lets say T1 to find the fastest horse.

T1 – A , F , K , P , U – Race6

We can safely assume that A got rank 1, F got rank 2, K got rank 3 , P got rank 4 and U got rank 5. So the fastest horse among the twenty five horses is A.

At this point most of us make a mistake, we blindly say that F is second and K is third among the 25 horses, but the reality is that F is slower than A and K is slower than F. We do not know if F is also slower than B , C , D , E and also we do not know if K is slower than G , H , I , J .

So we need to choose horses among B , C , D , E , F , G , H , I , K to get the second and third horses. We have a condition to test

1) B and C migth be faster than F, so we need to test them with F, hence the next race must include B , C , F for sure
2) B and C might be slower than F, so in that case F is the second fastest horse and we need to choose the third horse from G and K.

Hence the next race will have the horses B , C , F , G and K – Race7 running, lets say that C got rank 1 and F got rank 2, then C is the second fastest and F is the third fastest horse in the 25 horses.

Answer

Hence the answer is 7 races

Stay connected and stay Subscribed

  • serverdevil

    Pretty simple and straightforward explanation. Like it.

  • dharam

    Thanks…
    glad that people liked it

  • Vijay

    Thanks for the question.

    How can you make sure either L, M, Q, R, V or W is second or third.

    • dharam

      Hi,

      Sorry, I am not able to understand your question. Well I never said that either of L, M, Q, R, V or W is second or third.

      • Vijay

        Hello Dharam,

        Yeah, The question might not be clear.

        Is only 7 races sufficient to find first 3 position in race ?

        • dharam

          Yes it is… If you need some more clarification. I would write one again.

      • Vijay

        From your explaination it is clear that:

        At the end of race 6, the fastest can be found out. That I agree.

        Now coming to my question:
        A,B,C take 15,14,13 unit respectively
        F,G,H take 12,11,10 unit respectively
        K,L,M take 9,8,7 unit respectively
        P,Q,R take 6,5,4 unit respectively
        U,V,W take 3,2,1 unit respectively

        At the end of race 1,2,3,4,5 winners would be C,H,M,R,W respectvely.

        At end of race 6 –> W is winner.

        Now, I have a question that, how can you guarntee that V and W are winning in 3 place..

        I dint exactly understood about the 2 and 3 place calculation by exactly one extra race. Can you please elaborate more on this.

        Thanks,
        Vijay K

  • dharam

    Ok, It’s really simple, lets not put time taken against each horse. What do we know from the article after 6th Race?

    A is the fastest

    B > C > D > E, also
    F > G > H > I > J and
    K > L > M > N > O and so on.

    We also know that F is slower than A hence, G, H, I and J are also slower than A. But we cannot say that F is slower than B as well, because we never contested F with B.

    Similarly, we know that K is slower than F, but we don’t know if K is also slower than G, H, I and J.

    Now, we just need two find out 3 fastest horses, and we already have the fastest that is A.

    To pick two more, we need to find them from B, C, D, E, F, G, H, I, J, K.
    Remember we need two more horses, what is the best case?
    B and C are faster than F – If this is the case, we got our two horses by choosing B and C.

    What is the worst case?
    B and C are slower than F, if this is the case then we got our second horse as F. and we need to find the third horse, which can be one of G, H, I, J, K,

    Hence, if we need to organize a race then who all should compete in the race?

    B and C definitely ( to find out if they are faster or slower than F), also F, G and K to find out if G is faster than K or not.

    Hence the seventh race will include B, C, F, G and K

    • Vijay

      Yes, Got it. Thanks for the clear explaination.

      • dharam

        You are most welcome… Happy to help.