Facebook Interview Question: 25 racehorses, no stopwatch. ... | Glassdoor

Interview Question

Software Engineering Summer Intern Interview Palo Alto, CA

25 racehorses, no stopwatch. 5 tracks. Figure out the top

  three fastest horses in the fewest number of races.
technical, logic

Interview Answer

11 Answers


We can do it in seven races, we'll call them races A-F. For notation, we'll say that the Nth horse in race X is called X.N.

Races A-E: Divide the horses into 5 groups of 5 each such that each horse races only once.

We can eliminate the slowest 2 horses in each of the five races because there are definitely 3 horses faster in each case. As a result, we eliminate 5x2 = 10 horses: {A.4,A.5,B.4,B.5,C.4,C.5,D.4,D.5,E.4,E.5}

Race F: Race the fastest horses in each race A-E: {A.1, B.1, C.1, D.1, E.1}. To simplify notation, we'll label F.1 as horse A.1, F.2 as horse B.1, and so forth. That means the winner of this race is A.1, and it is the fastest horse of all. We don't have to race A.1 anymore.

We can eliminate D.1 and E.1 = 2 horses. Because they are not in the top 3.

As a result, we know that all remaining horses from D and E are eliminated. This is D.2,D.3,E.2,E.3 = 4 horses.

We know that A.1,B.1, and B.2 are all faster than B.3 (and similar for C.3) so they are not in the top 3.We can eliminate B.3 and C.3 = 2 horses.

Finally, we know that A.1 is faster than B.1, which is faster than C.1, and thus C.2, so we can remove C.2 = 1 horse.

Race G: We have removed 19 horses from competition and are sure that A.1 is the fastest horse of them all. This leaves just 5 horses: {A.2,A.3,B.1,B.2,C.1}. We race them and select the top 2 to join A.1 as the top 3 fastest horses.

Anonymous on Apr 4, 2010

just run them all on the one track :)
one race, and you get your 3 fastest horses in one go........or am I missing something!

kp on Aug 11, 2010

6 races.

Divide 25 horses into 5 groups. Each group races and the fastest is selected.

The winner of each of the 5 races all race together. Pick Top 1,2 and 3.

My only concern: Could the answer be this simple?

B on Nov 17, 2010

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.


5 top horses from each race of 5 races (25 / 5)
5 top contenders race; 1 wins--that's one top horse (5-1)
4 remaining top horses race, one wins; that's 2 top horses (4-1)
3 remaining top horses contend; winner is #3
That's 3 top horses from 8 races

Wendy Godfrey on Mar 4, 2011

Race#1 Race#2 Race#3 Race#4 Race#5
A1 B1 C1 D1 E1
A2 B2 C2 D2 E2
A3 B3 C3 D3 E3
A4 B4 C4 D4 E4
A5 B5 C5 D5 E5

A1 B1 C1 D1 E1
Let's Say ranking
1st 2nd 3rd 4th 5th

            D1 E1
            D2 E2
            D3 E3
A4 B4 C4 D4 E4
A5 B5 C5 D5 E5

Left with
    B1 C1
A2 B2 C2
A3 B3 C3

Eliminate C3 as there are more than three faster horses C2, C1, B1, A1
Eliminate C2 as there are three faster horses C1, B1, A1
Eliminate B3 as there are three faster horses B2, B1, A1

Left with 5 horses for Race#7
    B1 C1
A2 B2

So 7 races

Anonymous on Aug 5, 2011

7 races.
put 25 horses in 5 group. and we will have 5 sorted list of horses in each group.
put 1st place horse in each group, and we will have a sorted list X.
X_1 is the 1st place horse, and X_2 is 2nd place horse's candidate, X_3 is 3rd place's candidate.
2nd place horse in X_1's group is candidate for 2nd place, 3rd place one is candidate for 3rd place. and 2nd place horse in X_2's group is a candidate for 3rd place. that's 5 horses in total, 2 from X_1's group, 2 from X_2's group, X_3. race them, and 1st place is 2nd place, 2nd place is 3rd place horse.

Anonymous on Feb 5, 2012


Anonymous on Jan 27, 2016

the answer is one race as the question doesn't specify all the horses have to run in separate races.

Anonymous on Sep 22, 2016

0 Races. Ask the jockeys to rate the 10 fastest horses and take the average of the top 3. Nobody knows the horses that are fast better than the jockeys. Race results can vary from race to race but the jockeys truly know the fastest and besides because race results vary anyway you will not find the fastest horses with the least races you will find the fastest on that day. Either way your results will not be accurate without a larger dataset. The jockeys however already have a deeper dataset.

ShannonMcCoy on Aug 2, 2018

Better yet find the local bookie for the track and ask for the odds on the horses. Why solve a problem that has already be solved.

ShannonMcCoy on Aug 2, 2018

Add Answers or Comments

To comment on this, Sign In or Sign Up.