Bloomberg L.P. Interview Question: You have 25 horses, and you w... | Glassdoor

Interview Question

Financial Software Developer Interview(Student Candidate) New York, NY

You have 25 horses, and you want to know which are the top

  3 fastest, but you don't have a stopwatch. You can race the horses, but the track is only big enough to fit 5 horses at a time. How do you find the first, second and third fastest horses using the least amount of races possible?
Tags:
logic, problem solving, analytical, difficult
Answer

Interview Answer

3 Answers

9

Split the horses into 5 groups and race each of the 5 groups (5 races). After that, you have the horse placements for each group. I laid it out like this:

A B C D E
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Five columns, one for each group of horses, lettered A-E. Each number represents a horse... say horse A1 is the one that came in first place from group A, C2 is the horse that placed 2nd in group C, and so on.

You can eliminate all 4's and 5's from the chart, since we know that there are at least 3 horses that are faster for each 4th and 5th place horse.

A B C D E
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

Now race all the 1's (race #6). This will give you the fastest horse from the initial 25. But what about 2nd and 3rd place?

Let's say A1 got 1st, B1 got 2nd, C1 got 3rd, D1 got 4th and E1 placed last in race #6. A1 is definitely the fastest horse, but B1 may or may not be. Horse A2 can still be faster than B1- we have never raced them together before.

Approach it this way: which horses can we eliminate? Find all horses that we know have at least 3 horses faster than them. We can eliminate D1 and E1, because we know that A1, B1, and C1 are all faster than them. We can also eliminate all other horses in columns D and E below them. We can't eliminate C1, but we can eliminate C2 and C3. We also eliminate B3, since B2, B1, and A1 were all proven to be faster.

A B C D E
1* 1 1
2 2
3

The only horses left to race are A2, A3, B1, B2, and C1. (Race #7). The 2nd and 3rd place finishers are then 2nd and 3rd fastest from the original 25.

Interview Candidate on Jan 30, 2010
1

thanks. very nice explanation

Anonymous on Feb 19, 2010
0

very nice~calm thinking! hope I can be so calm in an interview!

yifeng on Dec 7, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.