Bloomberg L.P. Interview Question: You have 25 horses and a race... | Glassdoor

Interview Question

Financial Software Developer Interview

You have 25 horses and a racetrack where you can only race

5 horses at a time. You can only get qualitative comparisons of horses (e.g. horse A is faster than horse B), not actual race times. How can you determine the three fastest horses with the fewest races?

0

let us assume we have horses with numbers 1,2,3,4....25 .I would start a race with 5 horses and then after the first race i would replace the 2 slow horses with the 6,7 numbered horse, and then go for another race and again replace the 2 slow horses with 8,9 and so on. So i would end up 11 races to find 3 fast horses among 25.

Narendher on Jan 15, 2014
0

Sorry for the previous answer it was the basic idea but after giving serious thinking and searching online i came up with this link.. hope it helps. http://wiki.answers.com/Q/There_are_5_racing_tracks_and_25_horses_At_a_time_you_can_conduct_race_for_5_horses_in_the_five_available_tracks_What_will_be_the_minimum_number_of_trials_needed_to_find_out_the_ultimate_winner_run

Narendher on Jan 16, 2014
8

I had an idea that would solve the problem in 7 races. First divide the 25 horses into 5 groups, race respectively to get their winners. Then, race the winners in the same game and rank. The winner of the 6th game is the fastest. 4th and 5th are disqualified (together with all horses within their original groups). Then, I choose the 2nd and 3rd position from the group where the grand winner belongs to, the 2nd and 3rd position of the 6th race and the 2nd position from the group where the 2nd position of the 6th race belongs to. These five horses have the last race and the top two are the 2nd and 3rd of all horses.

Dagger on Jan 16, 2014
1

I had an idea that would solve the problem in 7 races. First divide the 25 horses into 5 groups, race respectively to get their winners. Then, race the winners in the same game and rank. The winner of the 6th game is the fastest. 4th and 5th are disqualified (together with all horses within their original groups). Then, I choose the 2nd and 3rd position from the group where the grand winner belongs to, the 2nd and 3rd position of the 6th race and the 2nd position from the group where the 2nd position of the 6th race belongs to. These five horses have the last race and the top two are the 2nd and 3rd of all horses.

Dagger on Jan 16, 2014
1

No offense, but the above mentioned methods do not use the information that relative information (i.e., A is better than B) is given. Ignoring the information given is a wrong thing in an interview.

(Assuming you know the classic "Union & Find" datastructure used in Kruskal's algorithm):
Let there be 25 nodes each representing a horse.
Initially all nodes point to itself.
Based on the relative information, the pointers are modified such that B is made to point A (and A pointer still points to itself). After all the information is fed, you end up with possibly few distinct sets.
Race #1:
the race is conducted between the heads (the nodes pointing to themselves) of all the distinct sets. Discard the sets of the lost horses (horses that stood in 4th and fifth position)
Race#2:
Get the children of the Winning horse(there can be more than one). to fill 3 leftover positions (replace the winner of Race#1, losers of Race #1).
Race#3.
Similar to Race#2.

In this way if after forming the datastructure, if there are <= 5 distinct sets, the top 3 horses can be obtained in 3 races!

Anonymous on Jan 25, 2014
0

Dagger, this solution unfortunately is incorrect. Consider the case where all horses are ordered in descending speed i.e. horse i will always beat horse i+1. The output of your algorithm for this case would be the following:

Winner of race 0 between horses 0 to 4: 0
Winner of race 1 between horses 5 to 9: 5
Winner of race 2 between horses 10 to 14: 10
....
Winner of race i between horses i*n to i*(n+1)-1 : i*n

where n = maximum heat size = 5 (in this example).

In the final race, the order would be: 0 5 10 15 20, and your algorithm would incorrectly conclude that the 0th, 5th and 10th fastest horses were the 0th, 1st and 2nd fastest.

su on Oct 1, 2014
0

Dagger is right.

Inigo on Oct 9, 2014