25 Horses 5 Tracks Problem (Solved) | ninjasquad

The *25 Horses 5 Tracks* Problem is a famous Google interview question that has been asked in many companies to evaluate candidateβs analytical ability and problem solving approach.

## Problem Statement

You have 25 horses

πππππ

πππππ

πππππ

πππππ

πππππ

and you need to identify the fastest 3 horses πππ out of those 25. Only 5 horses can run in each race at the same time as there are only 5 tracks.

**What is the minimum number of races required to identify the fastest 3 horses without using a stopwatch or timer?**

## Solution

This is an interesting puzzle. Letβs look at the limitations first.

- We donβt have a stopwatch or timer so we canβt record the finish time of each horse otherwise we could have find out the fastest 3 horses by 5 races of 5 horse in each race.
- Only 5 horses can run in each race otherwise we could have find out fastest 3 horses by just one race of 25 horses.

#### First 5 Races

So at this point we are certain that we need minimum 5 races first

```
25 horses / 5 horses per race = 5 races
```

Visualization is very important for such puzzles. Draw a matrix of horses for first 5 races.

*Where RxHy Where R is race, x is race number, H is horse, y is horse number*

(Race 1) | R1H5 | R1H4 | R1H3 | R1H2 | R1H1 |
---|---|---|---|---|---|

(Race 2) |
R2H5 |
R2H4 |
R2H3 |
R2H2 |
R2H1 |

(Race 3) |
R3H5 |
R3H4 |
R3H3 |
R3H2 |
R3H1 |

(Race 4) |
R4H5 |
R4H4 |
R4H3 |
R4H2 |
R4H1 |

(Race 5) |
R5H5 |
R5H4 |
R5H3 |
R5H2 |
R5H1 |

After first 5 races we will have a winner for each race. Result of first five races are as follows:-

(Race 1) | R1H5 | R1H4 | R1H3 | R1H2 | `R1H1` |
---|---|---|---|---|---|

(Race 2) |
R2H5 |
R2H4 |
R2H3 |
R2H2 |
`R2H1` |

(Race 3) |
R3H5 |
R3H4 |
R3H3 |
R3H2 |
`R3H1` |

(Race 4) |
R4H5 |
R4H4 |
R4H3 |
R4H2 |
`R4H1` |

(Race 5) |
R5H5 |
R5H4 |
R5H3 |
R5H2 |
`R5H1` |

Assume Results are as follows:- |
(Slowest) |
(Second Last) |
(Third Winner) |
(Second Winner) |
(Winner) |

*For simplicity letβs assume first horse of each race is winner i.e. *

`R1H1`

, `R2H1`

, `R3H1`

, `R4H4`

, `R5H5`

.#### 6th Race (The Race of winners of first 5 races)

Now we need 6th race of all the winners of first 5 races i.e. ** R1H1**,

**,**

`R2H1`

**,**

`R3H1`

**,**

`R4H4`

**. This race will reveal the fastest horse out of all 25 horses. Result of 6th race is as follows:-**

`R5H5`

(Race 6) | R5H1 | R4H1 | R3H1 | R2H1 | `R1H1` |
---|---|---|---|---|---|

Assume Results are as follows:- |
(Slowest) |
(Second Last) |
(Third Winner) |
(Second Winner) |
(Winner) |

*For simplicity letβs assume first horse of first race i.e. *

`R1H1`

is winner for 6th race.Now we know the fastest horse ** R1H1** out of all 25 horses but we donβt know the 2nd and 3rd fastest horse yet because 2nd and 3rd might be from 1st race since

**from Race 1 is the fastest horse**

`R1H1`

**OR**from the winners of all first five races.

#### 7th Race (The Race of Chosen Five)

To understand this we need to align all the horses as per their ranking in each race and eliminate the horses which are definitely cannot be 2nd and 3rd fastest

(Race 1) | `R1H3` |
`R1H2` |
`R1H1` |
||
---|---|---|---|---|---|

(Race 2) |
`R2H2` |
`R2H1` |
|||

(Race 3) |
`R3H1` |
||||

(Race 4) |
|||||

(Race 5) |
|||||

Assume Results are as follows:- |
(Slowest) |
(Second Last) |
(Third Winner) |
(Second Winner) |
(Winner) |

- Race 1: Since fastest horse
is from Race 1, second`R1H1`

and third`R1H2`

winner of Race 1 can be 2nd and 3rd faster so eliminate Second Last and Slowest. Also eliminate the fastest horse because that can not be 2nd or 3rd fastest. We already know that.`R1H3`

- Race 2: Second winner of 6th race
is from Race 2 so it can be 2nd fastest horse. If it is 2nd fastest then second winner`R2H1`

can be 3rd fastest. Eliminate rest.`R2H2`

- Race 3: Third winner of 6th race
is from Race 3 so it can ve 3rd fastest horse. Eliminate rest.`R3H1`

- Race 4: Fourth winner of 6th race is from from Race 4. Since we have to find 2nd and 3rd fastest horse. Eliminate all.
- Race 5: Fifth winner of 6th race is from from Race 5. Since we have to find 2nd and 3rd fastest horse. Eliminate all.

Now that weβve eliminated the all of the horses that canβt possibly be in the top three, what are we left with? The chosen 5 horses, letβs do the 7th race:-

The first and second winner of the 7th race will be the 2nd and 3rd fastest horse out of all 25 horses. So you need minimum **7 races** to identify fastest 3 horses.

**5 races (of all 25) + 6th race (winners of first 5 races) + 7th race (the chosen five) = 7 races**

## Conclusion

I have tried to explain the solution as easy as possible. Please let me know by writing in comment section if you still find it difficult to understand.

Source: Internet