Bloomberg LP Interview Question Financial Software Developers
///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. ///
shouldn't it be the 1st and 2nd of this race are the 2nd and 3rd of 25 >??
How can you eliminate C2? It can be faster than B2 as we never had a race between them. Can you please explain?
You can easily do it in 7 races.
step1: 5 races one each for 5 different horses. (5)
pick the top from each Q. (so 5 queues)
step2: eliminate the 4th and 5th horse and the succesors in their queue ( you are left with 15 horses. only 3 queues). Also you can eliminate the 4th and 5th horse from each of the remaining 3 queues. Also the second and third from 3rd queue and the third from the 2nd Q.
further the one that stood first is obviously the best. Move him out for further considerations.
you are left with only 5 horses.
step3: one more race required.
Ans shall be 6. Please comment if i am missing something .
I got 7 as the answer as well. Are you sure it's 6?
Here are my steps:
1) 5 races because 1 for each pool of 5
2) 1 race for all the winners in step 1
3) now you know the "superwinner" (guy who placed first in steps 1 and 2), so race the 2nd/3rd place horses in step 2 vs the 2-4th place horses from the superwinner's group
total is 7 races.
What did I miss?
It works even then. I mean the explaination and answer takes care of all possible combinations. Try urself on a piece of paper, i am sure you will not have problems
The answer is into maintain relations ships i.e rule out every horse that has at least 3 horses faster than him
Check it as ... Divide horses into 5 groups and race them
A 1 2 3 4 5
B 1 2 3 4 5
C 1 2 3 4 5
D 1 2 3 4 5
E 1 2 3 4 5
Now race all groups, you will get winners from all groups, and the following relationship would hold
A 1> 2> 3> 4> 5
B 1> 2> 3> 4> 5
C 1> 2> 3> 4> 5
D 1> 2> 3> 4> 5
E 1> 2> 3> 4> 5
please read 4>5 as 4th horse is faster than 5th
Now get horses from every group who stood first and race them
Lets suppose we have the following out put
A1 > B1 > C1 > D1 > E1
Now we can
Eliminate E1 we know that there are 4 horses faster than him
Eliminate E2, E3, E4, E5 as all of them are slower than E1
Eliminate D1 we know that there are 3 horses faster than him
Eliminate D2, D3, D4, D5 as all of them are slower than D1
Eliminate A1, he is the fastest
Eliminate B3 as B1, B2 and A1 are faster than him
Eliminate C3 as C2, C1, B1, and A1 are faster than him
Eliminate D3 as D1, D2, C1, B1, and A1 are faster than him
Eliminate E3 as E1, E2, D1, C1, B1, and A1 are faster than him
Eliminate C2 as A1, B1, and C1 are faster than him
Eliminate D2 as A1, B1,D1 and C1 are faster than him
Eliminate E2 as A1, B1,C1,D1 and E1 are faster than him
Now u r left with 4 horses, race them to find out the 2nd and 3rd position
so total number of races is 7
I think right answer is 11 races minimum.
race#1 : 3/5
race#2 : take 3 winning horses from prev race and add 2 new
.
.
race#11:
--You cannot split horses in 5 different groups because top 3 horses could be in the same group.
--To make sure you get top 3/25, top 3 of "n" race should go to "n+1" race.
Nicely explained Jaggs,
- initrd February 20, 2010just to put little more clarity…
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.