Amazon Highbridge Capital Deshaw Inc Interview Question
Software Engineer / DevelopersLet's assign a speed to each horse:
a1= 99
a2= 4
a3= 3
a4= 2
a5= 1
b:
98
8
7
6
5
c:
97
12
11
10
9
d:
96
94
93
92
91
e:
95
90
89
88
87
This shows that horses in d2-3 and e2-3 could still come in second and third overall. Your proof is wrong
hi, friend!
"FOR II position,horse will be either b1 or a2" - looks like this is wrong, since we don't have timer and we don't know exact times at which horses arrived to finish.
So, all we know is that a1 arrived faster than {a2, a3, a4, b1}, but we don't know how faster/slower horses {a2, a3, a4, b1} were if compared to each other.
This means that for II position all 4 horses {a2, a3, a4, b1} are equally possible.
Its 7.
Filter the first out with 6 races.
The 7th race : 2nd, 3rd, 2 runners up of the best horses' group and 1 from the 2nd best horses group.
You'll get the best 3.
Looks like a wrong solution.
Your process is 1st have 5 races, get top from each and have a 6th race and find out the best.
Now you will be left with 2nd and 3rd position horses in those 6 races which will be 12.
Now it will take more than 1 race to find the remaining 2.
So your solution is wrong
He is specifically telling us which 5 will race in the 7th race. I think the solution is correct.
he is wrong. what if the best horses are in the first race?? arent you neglecting 2nd n 3rd best by only taking the first horse from the first set of five?
7 races.
1) divide 25 horses in 5 groups and you have 5 winners.
2) race these 5 winners and the winner of this race is the fastest horse, 2nd and 3rd horse (along with their respective groups) are candidate for remaining 2 positions while we can plainly reject remaining 10 horses belonging to horses who stood 4th n 5th in 6th race.
3) for final race we choose following horse
-> those who came 2nd and 3rd in 1st group
-> those who came 1st and 2nd in 2nd group
-> the one that came 2nd in 3rd group.
In the last part, why are you not considering those who 2nd and 3rd in 3rd, 4th, 5th and 6th(top 5)?
let me explain in detail.
race1: a1 a2 a3 a4 a5, winner: a1
race2: b1 b2 b3 b4 b5, winner: b1
race3: c1 c2 c3 c4 c5, winner: c1
race4: d1 d2 d3 d4 d5, winner: d1
race5: e1 e2 e3 e4 e5, winner: e1
race6: a1 b1 c1 d1 e1, winner: a1
lets arrange horses of 6th race in their final standing. lets say a1>b1>c1>d1>e1
a1 has beaten winners of all group winners so he is the fastest.
d1 and e1 could not make to top 3 so how can any other horse of their initial group make to top 3 (since we already know d1 and e1 were winners of their groups)? so we reject 2 groups d1 and e1. and b1 c1 are sent back to their respective groups because they have chances to be amongst top 3.
our job is to find ONLY 2nd and 3rd fastest because we already have a1 as the fastest horse. so who all can be the candidate for those 2 positions?
a2 and a3 (2nd and 3rd in 1st group, they are top two)
b1 and b2 (1st and 2nd of 2nd group, they are top two)
c1 (why only one from this? because even the winner of this group which was c1, had 2 horses above him in 6th race. so it cant come 1st or 2nd ever so this group is candidate for 3rd place only)
rest 2 groups were already rejected (i described above why)
race 7: a2 a3 b1 b2 c1.
I think we only need 7. Here is my explanation.
Run 5 races as everyone above explained. Pick up top 3 from each race. Suppose the sets of horses picked up is (a,b,c), (p,q,r), (m,n,o), (x,y,z) , (u,v,w). Now run a, p, m, x and u (i.e 1st horse from each set)in one race (6th race). Suppose the top 3 are a,p and m (the answer does not change even if any other 3 are top 3). Now since x and u are not in top 3, y, z, v and w will also not be in top 3. Now we are left with a, p, m, b, c, q, r, n, and o. since m is the 3rd among a, p and m, n and o cant be in top 3 so take them out. Now we are left with a, p, m, b, c, q, and r. Since a is the top horse in 6th race, it is going to be the top anyway. so take that one also out. Now we have p, m, b, c, q and r and we need to find out who can be 2nd and 3rd best horse. Since p is in 2nd position and r came 3rd in 2nd race, it can not be one of the top 3 horses. So that that out. Now we have p, m, b, c and q left. Make them run 7th race. Top 2 horses from this race will fill 2nd and 3rd position.
So we have a total of 7 races. Use pen and paper while going through my explanation. it will be easier.
7
divided into 5 groups, each 5 horses.
race 5 rounds.
pick top 3 of each group. 15 horse. 5 groups.
let top 1 of each group race.
throw the two slowest groups. <chose the first one.>
8 horses left.
throw the last one horse of the second fast group. 7 horse left
throw the last two horse of the third fast group. 5 horse left
race again, <pick top 2>
8 races
first do 5 races to find out top 3 in each group
now run the toppers to get overall topper
now from the group of the topper select second and run with the other toppers
if the second comes first then he is ovrall second
select the third from that group and run with other toppers whoever tops is the overall third
in case second doesnt win then select second from the group of the first and run wit other toppers and second among the first horse
winner is third
what if the 4th,5th horse of the first group is faster than the topper of all the other groups?How does that get accounted?
my solution works for your situation too. check it out.
The answer is 12.
first:: 5 5 5 5 5 --- total 5 races and 15 left
second:: 5 5 5 --- total 3 races and 9 left
third:: 5 4 --- total 2 races and 6 left
fourth:: 5 1 -- total 1 race and 4 left (observe that here we only need one race for 5 horses and 0 for 1 horse.)
fifth:: 4 ---total 1 race and 0 left
adding all the races = 5+ 3+ 2+ 1+ 1 = 12
The answer is 7.
Round 1: Take 5 horses at a time initially.(1 to 5 races)
Round 2: Then race the winning horse from each of the above 5 races.(6th race)
Round 3: Then race horse that finished 2nd and 3rd in the winners group in 6th race from round 1(i.e., one of the races 1 to 5) and race the horse that finished 2nd in 6th race with the horse that finished 2nd in his group in round 1 and finally the 5th horse will be the one that finished 3rd in round 2.
The answer is 12.
first:: 5 5 5 5 5 --- total 5 races and 15 left
second:: 5 5 5 --- total 3 races and 9 left
third:: 5 4 --- total 2 races and 6 left
fourth:: 5 1 -- total 1 race and 4 left (observe that here we only need one race for 5 horses and 0 for 1 horse.)
fifth:: 4 ---total 1 race and 0 left
adding all the races = 5+ 3+ 2+ 1+ 1 = 12
Can be done in only 4 races ....
Race [1]
Make 5 hourses run from one direction and another 5 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2] repeat this with another 10 hourses
Now we have 6 best hourses and 5 untested
Race [3] Make 4 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
ANS : 7
1st 2nd 3rd 4th 5th
group a: a1 a2 a3 a4 a5
group b: b1 b2 b3 b4 b5
group c: c1 c2 c3 c4 c5
group d: d1 d2 d3 d4 d5
group e: e1 e2 e3 e4 e5
race 6: a1 b1 c1 d1 e1 \\ first positions from all groups decides the first among all
race 7: a2 a3 b1 b2 c1 will decide the 2nd and third place
1.form 5 groups of 5 horses each.
2.make them race and get 5 topper
3.again race between these topper and get 1st topper
4.picks 2 from topper group,frist 2 from 2nd group and one from 3rd group and leave last 2 group
5. again race between these five and get first two topper finally we will get 3 topper among 25
total race is =5+1+1=7
1. Form 5 groups of 5 horses each.
2. make them race
3. pick top 3 from each group (since rest 2 are not amongst the top 3 of group they can not be in top 3 across all groups)
4. now you have 15 horses.
5. 3 races,
6. run winners of each group for 1st overall.
7. run 1st runnner up of each group for 2nd overall.
8. run 2nd runner up of each group for 3rd overall.
total races = 5+ 3+ 3 = 11
above solution does not include all the conditions:
for examples the best three horses are in different groups.
Group #: Position Number,...
Group1: 1*, 2, 3
Group2: 1*, 2, 3
Group3: 1*, 2, 3
Group4: 1, 2, 3
Group5: 1, 2, 3
Best Horses are denoted by *.
6. run winners of each group for 1st overall. [CORRECT]
7. run 1st runnner up of each group for 2nd overall. [INCORRECT]
8. run 2nd runner up of each group for 3rd overall. [INCORRECT]
Eight and Night step will not give you the second and the third best horses
1. Pick 5 horses and race them. Pick the top 3, get rid of slowest 2, 20 horses untested, 3 picked, 2 out
2-5. repeat step 1. 15 horses left, 10 out, 0 untested
Now you have 15 horces left. Group A all comes in 1, Group B all comes in 2, and Group C all comes in 3.
6. Now race Group A. Using numbers to show how fast they were on this race, the horces ranked A1, A2, A3, A4, and A5.
The fastest, A1, is the fastest horse in the group. Get rid of A4 and A5, and all the other horces in the B and C group that has already raced with it. You can also get rid of all the horces in group B and C of A3, and also the C group horce that raced with A2.
Now you only have the following horces to test. A2, A3, B1, C1, B2.
7. Let them race!
The answer is 7 races.
Race all 25 horses in groups of 5. Call the groups A, B, C, D and E. Call the winners from each of these races A1, B1, C1, D1, and E1. That's 5 races so far, and any horse who came in 4th or 5th in any race is out.
Now, race A1, B1, C1, D1, and E1 together. That's 6 races. Let's just assume that A1 wins, B1 is second, and C1 is third. That means:
(1) A1 is definitely the fastest horse overall.
(2) Any horse from group D or group E is out. (3) Any horse from group C, other than C1, is definitely out -- they lost to C1, who was third in the winners' race; thus for example, C2 is fourth fastest at best.
(4) B3 is out. He came in third to B1, thus he's at best 4th fastest overall.
Thus the only remaining horses vying for contention are A1, A2, A3, B1, B2, and C1. We know A1 is definitely the fastest. Thus race A2, A3, B1, B2, and C1 together. That's 7 races. The winner and second-place finisher of this race are the second and third-fastest overall.
Let's say i divide the horses in group like A,B,C,D,E and A[1]...E[1] are the first horses after Round 1.
In second round, we run A[1] to E[1] and let's say the result is 1st=A[1],2nd =B[1] 3rd=C[1].
So, A[1] is the fastest==>One horse found.
This is important, now we have to find the next two horses as we have to find 3 in total and we have already found 1.
These two can be A[2](second horse in A category after Round 1) & A[3](this means initial A group has all the fastest three horses)
There is a possibility that the second horse can also be B[1](second in Round 2) & third can be B[2](we dont need to consider B[3] here as that will mean we are considering B[1],B[2],B[3] where we have to find only the next two horses)So, we will take B[1] & B[2].
Because B[2] came second in Round 2, so the overall second must be anyone from B[1],B[2],A[2],A[3].We have to find one more place for overall third,so we will take C[1](third in Round 2)we do not need to consider C[2] here as we have already chosen top two & we just need the top third.
So, in the 3rd round(7th race) if we run A[2],A[3],B[1],B[2],C[1], the top two in this race along with A[1] wii give us the top three.
Vish,
Correct me if there was anything different in my understanding.
why are comparing with B[2] and A[3] in order to determine which horse is the second fastest. It will either be A[2] or B[1]. If B[2] could be the answer then that will be wrong as B[1] is faster than B[2] and B[1[ is the not the fastest but can be the second fastest.
after first round you take top 3 from each group A1-3, B1-3, C1-3, D1-3, E1-3....then you run 3 races with 15 hosrses remaining.....Now you take the top 3 horses out of the 3 races...You will be left will 9 horses.....you then run 2 races...One race iwth 4 horses and one race with 5....eliminate the botttom 2 horses in each race...you are now left with five horses....all you need to do is one more race and pick the top 3........Big Brown total of 11 races 5 +3 +2 +1 = 11
Level 1:
Group 1 : a1,a2,a3,a4,a5 - a1 is the winner. Similarly...say.. b1,c1,d1,e1 are winners.
Level 2 :
Race a1,b1,c1,d1,e1 ..say result is a1,b1,c1
Level 3:
we know a1 is the fastest. but we do not know if b1 is better than a2,a3..and similar reasining if c1 is better than b2.
So now race.. a2,a3,b1,b2,c1 ... fastest 2 are the 2nd and 3rd.
Total 7
Hello people..
7 is the correct answer..
For the man with the stop-watch: Why do as***les like u even bother 2 post???
Thesolver has given the correct explanation..
Answer would be 7. Explanation :
Make group of 5 horses and run 5 races.Suppose five groups are a,b,c,d,e and next alphabet is its individual rank in tis group(of 5 horses).for eg. d3 means horse in group d and has rank 3rd in his group. [ 5 RACES DONE ]
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
Now make a race of (a1,b1,c1,d1,e1).[RACE 6 DONE] suppose result is a1>b1>c1>d1>e1
which implies a1 must be FIRST.
b1 and c1 MAY BE(but not must be) 2nd and 3rd.
FOR II position,horse will be either b1 or a2
(we have to fine top 3 horse therefore we choose horses b1,a2,a3,c1 do racing among them [RACE 7 DONE].the only possibilities are :
c1 may be third
b1 may be second or third
a2 may be second or third
a3 may be third
The final result will give ANSWER. suppoose result is a2>a3>b1>c1
then answer is a1,a2,a3.
HENCE ANSWER is 7 RACES
case 1 ::
If u can use a stopwatch.
yeah 5 races is enough to decide the winner....
time the time taken by the horses..........
and the first 3 is selected out
case 2::
if u cannot use a stop watch..
6 races....
5 topper of each group is selected..and race between them..
the first three is the the best three horses.......
here is the answer,which can be easily understood[:)]
divide the horses into 5 groups..
now take 5 races 1 for each group.
now we have 5 toppers 1 from each group.number of races done=5.
now run 1 race,which will give three toppers.number of races done=6.
In 6th race,we find 4th and 5th horses also.now all horses of group of 4th horse are below that horse i.e. if they are made to compete again they can get positions from 5 onwards.hence these are rejected,because we want only first three horses.similarly all horses of group of 5th horse(in 6th race) can only compete for position no 6 onwards.hence these are also rejected.
now we consider the horse,which came first in 6th race.the horses who obtained 2nd and 3rd positions in group races can compete for 2nd and 3rd position respectively.hence these should be taken into account.similarly 1 horse(who was second in group race)from goup of horse,who obtained second position in 6th race can compete for third position,hence should be considered.
hence now we have in total 1 + 1 + 2 + 1=5 horses(first in 6th race will not be considered,since no horse can compete him) for the 7th race.
Now 7th race is done top 2 are second and third horses respectively.hence top 3 horses obtained in 7 races.
the answer is definitely 7, read here for detailed explanation:
programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/
That is exactly right. Folks here are not comparing hourses across the lanes and are assuming that the topper of 2nd race is better than the slowest of the first group. This assumption is WRONG.
The only way to do this is to carry forward the 3 hourses into the next race and take 2 new hourses from the batch of 20 and run the top 3 from first 5 horse race and so on...
when we make 25 horses and group them into 5 groups each of 5 horses, we make 5 independent races. Now from these results we cannot take the first toppers of each group to conduct the second race. This is logically wrong.
Consider the example
There could be cases where A2 is better than B1 or A3 is better than B1 etc. In this case we are ignoring A2 or A3 but selecting B1 just because B1 was first in B's group but A2 and A3 were not first in A's group.
That is exactly right. Folks here are not comparing hourses across the lanes and are assuming that the topper of 2nd race is better than the slowest of the first group. This assumption is WRONG.
The only way to do this is to carry forward the 3 hourses into the next race and take 2 new hourses from the batch of 20 and run the top 3 from first 5 horse race and so on...
I think it can be done in 6 races.
in each race 5 horses will participate and after 5 races all the 25 horses will run the race and we can get top 5 horses from each race.
Top 5 horses can run a race and decide the top 3
so we can get top 3 horses in 6 races.
correct me if i am missing anything.
7 RACES.
GRP A-B-C-D-E (5 HORSES EACH)= 5
A1-B1-C1-D1-E1(FASTEST HORSE FROM EACH GRP) = +1
SAY THEY FINISH AS C1-B1-A1-D1-E1
THE WINNER(C1) IS THE FASTEST HORSE (TAKE HIM OUT), THE 4TH AND 5TH HORSE(D1,E1) ARE NO GOOD, TAKE THEM OUT TOO.
NOW RACE B1-B2-B3-A1-A2 =+1
ORDER IS C1 + (WINNER AND RUNNER-UP OF THE 7TH RACE)
CORRECTION....
NOW RACE C2-C3-B1-B2-A1 =+1
ORDER IS C1 + (WINNER AND RUNNER-UP OF THE 7TH RACE)
A2 is slower than A1.
A1 is slower than B1.
Thus, if A2 is made to run he would end up after B1 and A1. In which case the fastest three racers would be C1 followed by B1 then A1. As a result, making A2 run in this race is redundant.
There is an implicit assumption that all horses are giving their best when they are being raced.
7 races.
5 groups = 5 race.
From each group, consider top 3 horses.
6th race : top 1 horse from each group (assume winner is 1st group horse)
7th race : top 2nd horse from 1st group & losers from 6th race (assume winner is 1st group horse)
8th race : top 3rd horse from 1st group & losers from 7th race (assume winner is 1st group horse)
I think it's 8
first 5 round to get each group a top 3,
additional 3 round to extract the top 3,
a situation is the top 3 are all in one group,
thus u will need 3 round to find the overall top 3
hay 25 horses are in 5 batch rt,it may all 3 horses may selected from 1st batch itself
1 batch race 5,5,5,5,5
prob - 3,3,3,3,3=>15
2nd batch race 5,5,5
prob 3,3,3=>9
3rd batch race 5,4
prob 3,3=>6
4th batch race 5,1=>
prob 3,1=>4
5th batch race 4
prob 3(selected)
5 race only
The answer is 12.
first:: 5 5 5 5 5 --- total 5 races and 15 left
second:: 5 5 5 --- total 3 races and 9 left
third:: 5 4 --- total 2 races and 6 left
fourth:: 5 1 -- total 1 race and 4 left (observe that here we only need one race for 5 horses and 0 for 1 horse.)
fifth:: 4 ---total 1 race and 0 left
adding all the races = 5+ 3+ 2+ 1+ 1 = 12
i think it should be 6 races...
each batch ie. 5 horses in a race..
so if 5 races happen and we can pick up all the bests of these 5 races.. so we have 5 best horses at the end.... so another race will choose the 1st, 2nd, 3rd horses ie. through the other race...
11 times.
1=>5,5,5,5,5=>3,3,3,3,3=15
2=>5,5,5=>3,3,3=9
3=>5=>3=7
4=>5=>3=5
5=>5=>3
Total 11
11 is not the optimal solution.
I think it is 8.
1=>5(A1-A5),5(B1-B5),5(C1-C5),5(D1-D5),5(E1-E5)=>3(A1-A3),..,3(E1-E3)=15
Now compare (A2, B2, C2, D2, E2). assuming the same order then you can say for sure B2 is not in the best 3 (A1, A2 and B1 are better).
So only 6 items will remain (A1..E1 , A2)
You will need two more tries to find them all
5+1+2 = 8
It would be 7,
first from each 5 filter top 3 out.
no of race=5
From the top 3 horses in each of the 5 groups,
select 1st horse from each group and conduct a race.
no of race=6
again select top 3 from them,
the 1st horse would be top 1
for the 2nd and 3rd horse
select other 2 horses from the top 1's team, the runner's up from 2nd team, and conduct a race with 2nd and 3rd horse
and select the top 2.
We are done.
i think it will be 8. In worst case 1st horse in same group.
1.Initial 5batch select top 3 mark them like batch1(1st, 2nd , 3rd), batch2(1st,2nd 3rd) so on = race count = 5
2.Race between each batch 1st horse, find 1st horse( example bactch2 1st horse win race) = race count ( 5+1)
3.Race between batch2 2nd horse and others batch 1st horse, find 2nd horse ( example bactch2 1st horse win race) = race count (5+1+1)
4.Race between batch2 3rd horse and other 4 batch 1st horse, find 3rd horse = race count (5+1+1+1)=8
6 Race is not write answer to find out the top 3 horse.
Case:first round B1:5 B2:5 B3:5 B4:5 B5:5 and find out the best from each batch.
But suppose any batch have best 2 or best 3 may be. We are selecting only the best not 2nd or 3rd best from the each batch , which may be the 2nd or 3rd best in all 25 horse ..
i think you got my point
6 Race is not right answer to find out the top 3 horse.
Case:first round B1:5 B2:5 B3:5 B4:5 B5:5 and find out the best from each batch.
But suppose any batch have best 2 or best 3 may be. We are selecting only the best not 2nd or 3rd best from the each batch , which may be the 2nd or 3rd best in all 25 horse ..
i think you got my point
I believe it is 7.
Round A: Five races between five horses.
Round B: One race between the number one horses from each group in Round A. The winner will be the overall fastest horse. The 2nd and 3rd place horses could potentially be the 2nd and 3rd overall.
Round C: A second place horse from Round A could only possibly be in the top three overall if it was in the same group as one of the top two from Round B. If it was in the same group in Round A as the Round B first place horse, it could possibly be either the second or third overall horse. If it was in the same group in Round A as the Round B second place horse, it could possibly be the third overall horse. By the same logic, a third place horse from Round A could only be in the top three overall if it was in the same group in Round A as the first place horse from Round B. Therefore, the final race will consist of the 2nd and 3rd place horses from Round B, the 2nd place horses from Round B's 1st and 2nd place horses' Round A group, and the 3rd place horse from Round B's 1st place horse's Round A group. The top two in this race will be the 2nd and 3rd fastest horses overall.
This is easy to see if you organize the data onto a table.
Race all the horses, 5x5, for a total of five races so far. Race all the firsts-place finishers - for a total of six races so far - and draw the chart below:
f1 f2 f3 f4 f5
s1 s2 s3 s4 s5
t1 t2 t3 t4 t5
In this chart, fn, sn, and tn stand for the horses that placed first, second, and third, respectively, in race n of the first five races, where n is arbitrarily assigned to reflect the place in which fn finished in the sixth race.
Now, since f4 can't be in the top 3, neither can s4 or t4; likewise for f5, s5, and t5, so let's eliminate them:
f1 f2 f3
s1 s2 s3
t1 t2 t3
And since s3 can't be in the top 3 - because then f3 would have to be in the top 3, too, but then there wouldn't be enough room in the top 3 to include f1 and f2, both of whom are faster than f3 - we can eliminate s3, as well as t3, from the chart. Similar logic applies to t2. So let's eliminate s3, t3, and t2.
f1 f2 f3
s1 s2
t1
Of course, no horse can be faster than f1, which means that there are only 5 contenders for second and third fastest: s1, t1, f2, s2, and f3. So let's race them, for a total of 7 races. The first and second place finishers in this 7th race will be second and third fastest horses, respectively.
Lets assume there are 5 divisions of 5. we can find division winners in 5 races.
now a race to determine top 3 among division winners. The best horse is the best overall but the 2nd and the 3rd may not be overall 2nd and 3rd.
the 2nd and 3rd from overall winner's division might be better than other division winners and could be overall 2nd and 3rd.
Moreover 2nd horse from the 2nd placed division leader could be better than 3rd placed division leader.
A race among 2nd and 3rd from winner's division + first runner up and 2nd horse from its division and 2nd runner up will clarify this.
This will take total of 5 + 1 + 1 = 7 races
Lets assume there are 5 divisions of 5. we can find division winners in 5 races.
now a race to determine top 3 among division winners. The best horse is the best overall but the 2nd and the 3rd may not be overall 2nd and 3rd.
the 2nd and 3rd from overall winner's division might be better than other division winners and could be overall 2nd and 3rd.
Moreover 2nd horse from the 2nd placed division leader could be better than 3rd placed division leader.
A race among 2nd and 3rd from winner's division + first runner up and 2nd horse from its division and 2nd runner up will clarify this.
This will take total of 5 + 1 + 1 = 7 races
6 races.
example:
race 1: a,b,c,d,e --> c wins
race 2: f,g,h,i,j --> g wins
race 3: k,l,m,n,o --> m wins
race 4: p,q,r,s,t --> r wins
race 5: u,v,w,x,y --> x wins
race 6: c,g,m,r,x --> 1st: x, 2nd: c, 3rd: g
done.
What if any one among the contenders of race 5 other than x ie u,v,w and y are still better than C?They can still claim 2nd or 3rd positions.what do u say?
Can be done in only 4 races ....
Race [1]
Make 5 hourses run from one direction and another 5 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2] repeat this with another 10 hourses
Now we have 6 best hourses and 5 untested
Race [3] Make 4 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
Read question again.
"5 gates to race".. it clearly specifies that for one race you can race only 5 horses. Each gate will have one horse and when gun is shot they start running.
Moreover, I dont think 5 horses from one direction and 5 from another is called a race. Have not seen one like that.
Even if this type of race is allowed, how can you mark middle of racetrack as the destination? A horse who completes the racetrack of half length in best time, may not complete entire racetrack in best time.
the correct answer is 7..here is the explanation
programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle
I think it's a simple thing of times! the first step it definitely
(1)race 5 groups of 5
take the 5 best times from these races! this takes into account that the 3 fastest horse maybe in the same group!
(2) Then race the these 5 in a playoff!
seeing I'm taking times into account you could argue take the 3 best times there!
Could someone explain to me how to convert lets say to find out if a horse ran 6 furlongs & won or didn't win but run 30r 4 lengths behind the winner. How fast could same horse run 1-mile and so on up to 1mile & 1 1/16 miles and so on. I would like to know if there is a conversion chart some where on the internet for answers to all my questions on how to convert different times from longer races & show what a horse would run if put into a shorter race and so on. like 7 furlongs now races 6 furlongs or more then a mole & now drops back into a sprint race how fast could these horses run ? ! PLEASE I REALLY NEED HELP WITH THIS FROM ANYONE. Thanks so much ! Charles e-mail charlessparks546@yahoo.com
The simplest logic is Think Like below:
You have 25 numbers(all in list of 5 numbers) and you want to top 3 max.
Sort all lists- 5 races
Now max element is among the top of each list. ( Think like you are sorting top 5 then)- 1 race
Now you can remove last two and top
You have 2 elements and take 2 from list from which top belongs to.
Race again and get top 2.
Total races=7
The answer is: 9 in worst case and 8 in best case.
Explanation:
To find 5 best horses we obviously need 5 races.
Then the 6th race is used to find the winner among those 5 best horses.
Let's say 6th race is done and {1a 2a 3a 4a 5a} - are the winners each in their respective group.
1a 2a 3a 4a 5a
1b 2b 3b 4b 5b
1c 2c 3c 4c 5c
1d 2d 3d 4d 5d
1e 2e 3e 4e 5e
Now we know for sure that 1a horse outperformed all horses and we take it as ranked #1 and exclude from consideration.
Further, we know for sure that horse 2a outperformed all horses EXCEPT of four ones: 1b 1c 1d 1e.
That is why we must test horse 2a against those {1b, 1c, 1d, 1e} horses in 7th race.
So, the 7th race is {2a, 1b, 1c, 1d, 1e}.
Here 2 variations are possible:
1) If horse 2a loses the 7th race, then we get ranked #2 horse as winner of race 7 (let's say it is 1b horse) and then we must test horse 2a against other losers for the 7th race.
This is the 8-th race: {2a, 1c, 1d, 1e}.
The winner of the 8-th race will be ranked #3 horse.
And we are done with 8 races in total.
2) But If horse 2a wins the 7th race, then we get 2a horse as ranked #2 horse.
Now we know for sure that 2a horse outperformed all horses EXCEPT of a1 and we take it as ranked #2 and exclude from consideration.
Further, we know for sure that horse 3a outperformed all horses EXCEPT of eight ones: {1b, 1c, 1d, 1e, 2b, 2c, 2d, 2e}.
That is why we must test horse 3a against all those 8 horses.
To do this we need 3 more races.
We can randomly shuffle given 9 horses and run 2 races
Race 7: {2e, 1b, 2d, 1e, 2b}
Race 8: {1c, 2c, 1d, 3a}
Race 9: {winner_of_race_7, winner_of_race_8}
Winner of race 9 will be ranked #3 horse.
And we are done with 9 races in total.
hey vish,
cant it happen that the fastest 3 horses in the 1st race(i.e where we raced 5 from 25 intially.) be the fastest among all???
where did you check this condition???
Correct answer is 9. After 5 races 10 horses are eliminated.
Group of first horses --> A[1], B[1], C[1], D[1], E[1]
Group of second horses --> A[2], B[2], C[2], D[2], E[2]
Group of third horses --> A[3], B[3], C[3], D[3], E[3]
One race (6th) between all firsts will give the top performer A[1] with 2 more horces eliminated (D[1], E[1]).
However, we still dont know top performaers in group of seconds. Race 7 will give us A[2], B[2]. Same way Race 8 will give us top performer in the group of thirds A[3]. So now choices for 2nd and 3rd positions are B[1], C[1], A[2], B[2], A[3]. Final race (Ninth race) will tell us which are the # 2 and #3. We have to do 7th and 8th race since A[2], B[2] and A[3] can also take 2nd 3rd spot as well.
ans is 8
imagine the times are
1 2 3 16 21
4 8 12 17 22
5 9 13 18 23
6 10 14 19 24
7 11 15 20 25
1 4 5 6 7 win first 5 races
do race between them to get 1st -> 6 races
do race for 2 4 5 6 7 to get 2nd -> 7 races
do 3 4 5 6 7 to get 3rd = 8
What? And this bunch of idiots is supposed to run the global economy?
5 race. Run 5 horses each race. There's something called a stopwatch - take the time of the horses. This is an absolute result. Running 3 top horses again is not fair because they will have been exhausted.
Answer would be 7. Explanation :
- Ambresh July 24, 2008Make group of 5 horses and run 5 races.Suppose five groups are a,b,c,d,e and next alphabet is its individual rank in tis group(of 5 horses).for eg. d3 means horse in group d and has rank 3rd in his group. [ 5 RACES DONE ]
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
Now make a race of (a1,b1,c1,d1,e1).[RACE 6 DONE] suppose result is a1>b1>c1>d1>e1
which implies a1 must be FIRST.
b1 and c1 MAY BE(but not must be) 2nd and 3rd.
FOR II position,horse will be either b1 or a2
(we have to fine top 3 horse therefore we choose horses b1,b2,a2,a3,c1 do racing among them [RACE 7 DONE].the only possibilities are :
c1 may be third
b1 may be second or third
b2 may be third
a2 may be second or third
a3 may be third
The final result will give ANSWER. suppoose result is a2>a3>b1>c1>b2
then answer is a1,a2,a3.
HENCE ANSWER is 7 RACES