[Microsoft] Find Top 3 Racing Horses from 25 Horses on 5 Tracks !!

Background

This is the most interesting puzzle I've seen till date and It was asked in campus interview of NIT Kurukshetra by Microsoft India Development Center. Luckily my friend could solve it and get into Microsoft.

Problem Definition

There are 5 Racing Tracks in a Ranch and you are given 25 horses. You have to find 3 fastest horses (considering there is no tie between any two horses) by conducting minimum number of races.

Solution:

This problem has interesting solution because to reach to the conclusion of this problem you only have to solve it to few steps and then analyzing the data from those steps you can easily come to conclusion. Let us discuss how to do so.

Divide 25 horses in five groups (A, B, C, D, E) with 5 Horses each. Now conduct the races of 5 Groups.

Number of Races Till Now: 5

After this you can arrange the top three horses from all the groups in following order

A - A1 A2 A3
B - B1 B2 B3
C - C1 C2 C3
D - D1 D2 D3
E - E1 E2 E3

Let us conduct a race among all the winners of a group i.e. A1, B1, C1, D1, E1

Number of Races Till Now: 6

Now sort the groups (A-E) from second table such that winner's group is placed first. For explanation let us assume that C1 is winner of 6th race with E1 as second winner and B1 as third, A1 fourth and D1 fifth.

Arrange the horses like this

C - C1 C2 C3
E - E1 E2 E3
B - B1 B2 B3
A - A1 A2 A3
D - D1 D2 D3

Now let us analyze these results to find three fastest horses.

1. Without doubt C1 is the fastest (Right? It has won from C2, C3 as well as A1, B1, D1, E1)
2. Second Fastest is Either E1 or C2 (Because all other are slower than these two. Agreed?)
3. Third Fastest will be among C2, C3, E1, E2, B1 (Why not E3?? It has two winners from it- E1, E2 so it can be at the max fourth.)

So we need to conduct a final race amond - C2, C3, E1, E2, B1 to determine second and third winner.

Number of Races Till Now (And Finally): 7 is the answer!!

For more such problems simply visit http://CodeBoat.blogspot.com
If you have any query/question or feedback. Feel free to send them over to codeboat@gmail.com