There are 25 Horses – Find the Fastest Three

Stop me if you've heard this one… It's about some horses, some tracks, and figuring out which of the horses are the fastest… 😉

From what I understand, this is a common programming interview question (in other words, a question that an interviewer will ask a computer programmer who is applying for a job). Here's the full question along with the answer, and my explanation for it.

There are 25 horses and only five horses can race at a time. What's the minimum number of races you need to have in order to determine the fastest 3 horses? (There is no stopwatch or clock.)

Solution: 7

Explanation:
Begin by racing five sets of five horses.
A1 A2 A3 A4 A5 – race
B1 B2 B3 B4 B5 – race
C1 C2 C3 C4 C5 – race
D1 D2 D3 D4 D5 – race
E1 E2 E3 E4 E5 – race
——-
So, we have 5 races at this point.

Now, let's say the fastest of each of the above races was A1, B1, C1, D1, and E1.

So, take those and race them against each other. This makes 6 races.

In that race, let's say A1 finished first, then B1, then C1, then D1, and then E1.

So, we now know that A1 is the fastest horse.

So, that leaves two slots left to fill for the top 3 fastest horses. This is one of the most crucial things to focus on; there are ONLY TWO slots left.

We know from the 6th race that B1 and C1 are faster than D1 and E1. So, this eliminates both D1 and E1. (Remember: There are only *two slots* left.) We also know that D1 is faster than D2 through D5, as shown when they raced together. Likewise, E1 finished ahead of E2 through E5 in their race. So, all of the D horses and all of the E horses can be eliminated (if D1 and E1 aren't fast enough to be the second and third fastest horses, then horses that lost against them certainly aren't either).

This leaves the C's, B's, and the remainder of the A's. Again though, there are only two positions left. We know that B1 is faster than C1, and that C1 beat out C2 through C5. So, C2 through C5 can be eliminated. Because there are only two positions left, this also eliminates B3 through B5 (as B1 and B2 are faster). A4 and A5 can also be eliminated (as A2 and A3 are faster than them).

So, this leaves A2, A3, B1, B2, and C1, and those make up the 7th race.

The two top-placing horses of that race will be the second and third fastest horses, respectively, out of the 25 horses.

If you were searching for an explanation to this problem, please let us know if this helped!



 
Google Search