Amazon Interview Question Software Engineer / Developers
What's the logic for you to exclude a5-a9, b4-b9 and .... from step 6? Can you illustrate if your solution will come out with a1, a2, a3, a4, a5 and a6, if these six are indeed the six fastest horses?
when a1-- a6 are the best 6 horses., in step 4 a2,a3,a4 will come as 1st , 2nd and 3rd. so, now you have decided first four ones. now you need to select 5th and 6th ones.Assume 4th is from set 'b' and 5th is from set 'c'. then we can take 2 horses from set 'b' i.e., 4th one from the previous race and the next one in the set. and from set 'c 'you take only the 5th one from previous set as that will be the 6th from the entire 81. and take e1,e2, f1. now conduct race for them. you will get 5th and 6th in entire race of 81.
After you decide a1, a2, a3 and a4 are the top four, a5-a9 are still valid candidates for fifth and sixth. You collect no information (if a5 is faster or slower than any remaining horses from set b, c, d, e, f,)to prevent them from participating further selection.
I am having doubts over your step 6... we can't simply ignore 'a' set...
After step 5, we have 13 horses left (2 from the last race, 3 from set E and F(E1,E2,F1) and 2 each from the remaining groups which didn't get chance to participate yet)
Now from the last race, last 4 has to be discarded as they can't come at 5th and 6th position. Now this is important. All the horses which were not selected to race in last race and belongs to the group where these last 4 belongs needs to be removed.
And if you watch closely, you will select atleast two groups(4 horses), which will not participate in next race. Hence we are left with at-max 9(13 -4) horses for the last race.
So total number of races are 12.
Only 6 races can fetch the result
Can be done in only 4 races ....
Race [1]
Make 9 hourses run from one direction and another 9 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, 3,4] repeat this with another 18 hourses
Now we have 12 best hourses and 9 untested
Race [5] Make 9 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
The trick of this problem is that it highly likely to mislead most people to try different arrangements while the simple and straight way is to calculate how fast you could reduce candidate pool.
For this particular problem, 75 ( = 81-6 ) horses have to be eliminated at pace of 3 ( = 9 - 6). So it's 25. That's the formula above about.
Break them to 9 groups. So 9 races would cover 81 horses. So if we race the top 9 again we can get the top 6 horses among them. But since its for Amazon.. I would say thats not the correct answer. Because there may be better horses in other group. Is there any other answer with anyone??
Definitely the wrong answer, since all 6 could be in one of the original groups. It can be done in no more than 7 races, but probably less.
If the 6 fartest happened to be in one group, your solution ends up with one of the six top horse selected.
The precondition for your solution is to employ 9 modern timers at finishing line. I don'k think that is the case.
No, the answer is 11.
10 races are needed to select the horse for the first position
and last one race among the top 9 horses from the previous 10 races (a2, b1, a3, b2, c1, a4, b3, c2, d1) to select the remaining position.
1st set 9 races 81/9 = 9 fastest in each group
2nd set 1 race between 9 fastest ---> gives 1 fastest horse
3rd set 1 race between 2-6 from the winner of 2nd race and bottom 4 of 2nd race.
4th set 1 race between top 5 from 3rd race and 2-5 in 2nd race ---> get top 5 horses.
total 9 +3 =12 races and 6 fastest horses.
The answer is 13.
1: Group horses into 9 groups. Race each group to get the order within the group. (9 races)
2: Remove the slowest 3 groups and the first place winner. Race the fastest from each remaining group. You now have the fastest horse, and will need to look for the second fastest. (You can add any 3 next fastest horses from any remaining groups and it could cut best case performance if first and second place winners come from the same group, but will not affect worst case performance) (6 groups racing, 10 total races, found fastest horse)
3: Remove slowest group and the last race winning horse. Race fastest horse from each of 5 remaining groups and the next fastest horse from any remaining groups to fill out the 9 horse limit. (5 groups racing, 11 total races, found 2nd fastest)
4: Repeat step 3. But remember, with 4 groups and 9 racers, there will be at least 2 horses racing from each group. So there will be at least 2 winners. (4 groups racing, 12 total races, found third and fourth fastest)
5: Repeat step 4. Two groups racing best 2 from each group, this only needs to be a 4 horse race. (2 groups racing, 13 total races, found fifth and sixth fastest)
The answer is 9... the question never said don't use the stopwatch. Just race 9 horses in 9 batches....pick the top fastest based on their times.
The answer is 15.
first form 9 groups and run them ( 9 races ) , then each winner of the group forms another group and runs (+1 race, total 10). keep track of the winner, what was his original group. take out the second winner from that group and run with remaining 8 winners, next again do the same thing.
so for the first winner 10 races and then the remaining 5 winners 5 races = total 15 races.
Let me explain how the ans is 25.
The logic is that u have to always take the fastest 6 horses in every race because u dont know if the 6 fastest in n1 race are faster than or slower than the 6 fastest in n2 race. so if we start from 81 horses then 9 races are possible out of which 54 horses will be selected (i.e 6 form each) again.. 6 races are possible and 36 horses will be selected .. then if we continue like this atlast we will end up with 25 horses and the 6 fastest horses.. :p
no, u can get them within 12 without any doubt. you need to understand the logic that i have mentioned.
Many people ignore the fundamental logic that each race can elimenate at most 3 horses, and work hard trying to find a solution with less than 25 races through complicated logic.
If you have stop watch then you can easily find the top 6 in just 9 races. but if you don't have stopwatch and can only determine the winner of a race not the runner ups(i.e. 2nd, 3rd,4th) then I think minimum races required are 20.
Let me explain, as other people have already suggested make groups of 9 each. Let them be a ,b,....,i. Now run each group. let the winner be called TOP9, which are a1,b1,....,i1. So we will have 9 races. Now for ultimate top horse. race these a1,b1,..., i1 horses. Till now TOTAL RACES = 10 and we have to find 5 more horses. Let say winner horse is C1.
Now organize another race among C group( If you think that remaining 8 horses in C group can't have race and you need 9 horses then take 1 horse from any group)
From this C Group you will get another winner, include this winner in TOP9 group and race them again. Total race will = 12 and 4 more horses need to find. Keep doing so and you will get your top 6 horses.
So MIN. TOTAL RACES = 20
How come it will be 12. you have to have 9 races to find top horse in each group. you are left with 3 more races and you have to find 6 best horses.
Without having the specific time of completion for each horse I don't think 1 can make it 12 races.
It doesn't matter what you think. The first 9 races leave 54 candidates. The 10th race leaves 21 candidates, with the best horse known. The 11th race leaves at most 13 candidates, with the best 4 horses known; the 12th race among the remaining 9 establishes 5th and 6th place. The key to solving it is the fact that, if a horse can at best come in nth place, then any horse it has beaten can at best come in n+1th place.
1. 9 races x 9 horses each => 9 groups with 6 winners in each group = 9 races/54 horses left.
2. race the winners of each of 9 groups => 6 winners (including the TOP horse (the top winner and a winner of its own group) that does not need to race again). All 5 horses in the group, who's leader finished in the 6th place have lost by default (at least 6 horses are better than they are). The same applies to 4 bottom horses in the group, whos leased finished 5th, etc... As a result, 10 races, with 21 horses left.
Can you take it from here? ;)
I understood till 10 races with 21 horses left. Could you please explain me how to select fastest 6 horses among 21 only with 2 races. I tried a lot. But I couldnt.
Ok. We have 21 horses after 10 races:
A1 B1 C1 D1 E1 F1
A2 B2 C2 D2 E2
A3 B3 C3 D3
A4 B4 C4
A5 B5
A6
A1 is the fastest horse and does not need to race again.
The 2nd fastest is either A2 or B1
The 3rd fastest is either A3, B2, C1 plus a loser among A2 and A3
The 4th fastest is either A4, B3, C2, D1 plus 2nd and 3rd place losers.
Makes sense so far?
In race 11 we will race these 9 horses to determine 2nd, 3rd and 4th fastest horses. After the race we will eliminate 4 slowest horses and all the horses standing behind them in their groups.
In race 12 we will race horses 4th and 5th horses from race 11 with the rest ones to determine 5th and 6th fastest overall.
its 15.
9 races of 9 groups brings best 9 horses. Now have a race between top 9 horses u get the fastest horse. till now 10 races are finished.
now suppose from from the fastest horse is from group 5 so 2nd fastest from group 5 can now participate for the 2nd best position.
in the same way take the 8 loosers of the previous race as they are the best in their group + 1 horse from the winner group which ranks just after the winner.
this gives you 9+6=15 races
Answer is 13, here is the explanation.
first, lets group them with 9 horses, we now have 9 groups.Each group will have one race(9 races).
Among the winners of each group, we will have another race (+1 race).
So what we have now?
Winner of 10th race is the fastest horse among 81 horses.
Since we have to find out first 6 fastest horses, we will eliminate all except,
(where A1 is the fastest horse in the 10th race, and F1 is the slowest horse in the 10th race A1> B1>C1>D1>E1>F1 in 10th race)
and A1>A2>A3>A4>A5>A6 in the first race, same for other groups
A1 B1 C1 D1 E1 F1
A2 B2 C2 D2 E2
A3 B3 C3 D3
A4 B4 C4
A5 B5
A6
why?
because, all other horses cannot be among the first 6 fastest horses(think :)).
Now, A1 is already fastest.
2nd fastest must be either A2 or B1
3rd fastest must be either A3, B2 OR C1
4th fastest must be either A4, B3, C2, D1
we will conduct another race(11 th race) among them.
Winner, first runners up, and 2nd runners up are 2nd, 3rd and 4th fastest among 81.
Note that, still 2nd position must be held by either A2 or B1.3rd position by A3, B2, OR C1. And 4th position by A4, B3, C2, OR D1.
5th fastest must be either A5,B4,C3,D2 OR E1 = have a race(12th race) and winner is 5th fastest. NOTE THAT WE CANNOT DETERMINE 6TH FASTEST HERE. FOR THIS, WE MUST CONDUCT ANOTHER RACE.
6th fastest must be either A6,B5,C4,D3,E2,F1 = have the last race(13th race)
tetura,
I am able to follow your explanation. But how are you telling that only 5th fastest will be either A5,B4,C3,D2 OR E1?
Why can't 6th fastest also be one among A5,B4,C3,D2 OR E1?
tatura I think you don't need 13th race. By 11th race you can determine 2,3,4 places by choosing set of horses which contains 2,3,4(you can do it so I don't detail it :)) so first 3 places would be our 2,3,4 places and then by the 12th race you can determine 5th and 6th places. So totaly by the 12 races 6 best hources can be choosed.
I am sorry 5 and 6 places cannot be determined by 1 race, you are right 13 races needs :)
No, 12 is the right answer. The 11th race is among the 9 possible candidates for 2nd, 3rd, and 4th place; that race not only establishes those places, but also eliminates at least 8 horses from the running (at least 2 candidates for 4th place lose, taking with them 2 5th and 6th place candidates, and a 2nd and 3rd place candidate also loses). 21-8-4 = 9 for the 12th and last race that establishes 5th and 6th place.
@ tetura, while conducting the 11th race, you will select the best 6 and that should be the remaining candidates for the remaining 5 positions.. so no need for 12th and 13th run.. Because for the 11th run itself you are selecting only the top best horses...
tetura,
After the race 11th, you can discard 4 horses (6-9) + all the horses positioned behind them. The next race (12) will determine the rest of the 6 horses.
tetura,
after race 11, Can we eliminate the rest of the horses except top 3 from race 11 and consider only A5,B4,C3,D2,E1 for race 12? since we are picking the best horses here unlike previous 10 races where we tried to eliminate worst horses and keep best 6, will this work?
No. After race 11, we know for sure 2nd,3rd and 4th best horses. Horses 4 and 5 can potentially be 5th and 6th fastest horses. So, you can only eliminate 4 slowest horses from race 11 and all other horses standing behind them in their groups. So, if, for instance, horse A4 is not among 5 best horses in race 11, there is no need to race A5 and A6 in the next race, etc.
27 races
Step No of races selected for next step rejected
1 81/9 = 9 9*6 = 54 81-54 = 27
2 54/9 = 6 6*6 = 36 54-36 = 18
3 36/9 = 4 4*6 = 24 36-24 = 12
4 24/9 = 3 3*6 = 18 24-18 = 6
5 18/9 = 2 2*6 = 12 18-12 = 6
6 9h & 3h = 2 6+3 = 9 12-9 = 3
7 9/9 = 1 1*6 = 6(fastest) 9-6 = 3
Total 27 races
Almost correct - just skip incomplete races:
Step No of races selected for next step rejected
1 81/9 = 9 9*6 = 54 81-54 = 27
2 54/9 = 6 6*6 = 36 54-36 = 18
3 36/9 = 4 4*6 = 24 36-24 = 12
4 24/9(+6h)= 2 2*6 = 12 + 6h 24-18 = 6
5 18/9 = 2 2*6 = 12 18-12 = 6
6 12/9(+3h)= 1 1*6 = 6 + 3h 12-9 = 3
7 9/9 = 1 1*6 = 6(fastest) 9-6 = 3
6 horses - 25 races
On step 4 - 6 horses skipped
On step 6 - 3 skipped
Who said that? Read my explanation above and challenge me with a scenario where I can't make it 12.
"If you mean 12 - it's a wrong answer" -- It's been *shown* to be the right answer. I hope those who continue to say that 12 isn't the right answer even after it has been shown to be, never ever ever get hired as programmers or for any other intellectual work anywhere.
Following statements given by tetura in above solution are not correct :
2nd fastest must be either A2 or B1
3rd fastest must be either A3, B2 OR C1
4th fastest must be either A4, B3, C2, D1
Correct statements are :
2nd fastest must be either A2 or B1
3rd fastest must be either A2, B1, A3, B2 OR C1 (one of the case A1 > B1 > A2). similarly,
4th fastest must be either A2, B1, A3, B2, C1, A4, B3, C2, D1
Yes, Anonymous, but the correct way to think of it is
A2, B1 get at best 2nd place,
A3, B2, C1 get at best 3rd place,
A4, B3, C2, D1 get at best 4th place,
A5, B4, C3, D2, E1 get at best 5th place
A6, B5, C4, D3, E2, F1 get at best 6th place
From this and some clear thinking, one can see how to do it in 12 races.
I think this works:
After first 10 races as stated in tetura's method above:
A1 B1 C1 D1 E1 F1
A2 B2 C2 D2 E2
A3 B3 C3 D3
A4 B4 C4
A5 B5
A6
Now race (A6,B5,C4,D3,E2,F1,A5,B4,C3) and pick best 2 horses which may be 5th and 6th best horses=> (temp1,temp2)
then race (temp1,temp2,D2,E1,A4,B3,C2,D1,A3) and pick best 4 horses which may be 3rd,4th,5th and 6th best horses => (tempw,tempx,tempy,tempz)
finally race (tempw,tempx,tempy,tempz,B2,C1,A2,B1) and pick best 5 horses which are 2nd,3rd,4th,5th,6th best horses => (tempk,templ,tempm,tempn,tempo).
so that ans will be (A1,tempk,templ,tempm,tempn,tempo) in the sorted order of their performance.
Wrong answer. 11th race must be among A2, B1 (candidates for 2nd place or worse place), A3, B2, C1 (candidates for 3rd or worse place), and A4, B3, C2, D1 (candidates for 4th or worse place). The 3 top winners are the 2nd-4th best horses. The bottom 4 horses are eliminated (because there are at least 6 horses ahead of them, the other 5 plus 1st place) -- *and any horse they previously beat*. The worst case is that A2, A3, A4, and B3 lose, eliminating 8 horses total. 21-8-4 = 9, for the final race.
i think it should be 11..
Through the first 9 races, we choose the best horse of each race.. so we would have got 9 horses.. Through the 10 th race, we can list the horses by the best times.. so we have got 6 best horses... but there might be some tie ups with some horses.. so it is better to make another race for safety.. and choose the 6 best horses by their average times of the 10th and 11th races...
so the answer should be 11..
Hi from my point of view we can identify with in 15 races or in less for 15 i will give you explanation but for less than that we have to follow some permutation
1.1st fastest horse we can identify with in 10 races that every one know
ex: suppose we have a to i series
In 10 race we have position like that a1 first b1 second c1 d1 e1 f1 last rest of all are eliminated because g h i series fastest horse not qualify for top 6
now suppose f1 is in position 6 so it can fight only for last position e1 is fifth so in that group they can fight for position 5th and 6th, d1 is forth so their group can fight for position 4th 5th and 6th same for c1 B1 and A1 group
if we can follow this pocedure we can easily find out the minimum no. of races
so fm my side answer is 15 or less than that....
The best case is 11: the first 10 race determine the 1st place (say 1st is A and potential 2nd is B) and sort the horses inside each group. The 11 race sorts B with the rest 8 in A's group. If B is slower than at least 4 horses in A's group, then the rest 5 fastest horses are determined.
What's the worst case? My answer is 25.
10 races determine the 1st place. 1 race for 2nd, 2 races for 3nd, 3 races for 4nd... (10+1+2+3+4+5=25)
27 races
Step No of races selected for next step rejected
1 81/9 = 9 9*6 = 54 81-54 = 27
2 54/9 = 6 6*6 = 36 54-36 = 18
3 36/9 = 4 4*6 = 24 36-24 = 12
4 24/9 = 3 3*6 = 18 24-18 = 6
5 18/9 = 2 2*6 = 12 18-12 = 6
6 9h & 3h = 2 6+3 = 9 12-9 = 3
7 9/9 = 1 1*6 = 6(fastest) 9-6 = 3
Total 27 races
let me explain:
- putta.sreenivas May 10, 2011step1:divide 81 into 9 groups
group1:a1,a2,a3,......a9
group2:b1,b2,........b9
......................
......................
group9:i1,i2,i3,......i9
step 2:now conduct race for each group. you will get best in each group. so totally 9 races conducted.
step3:let the best ones be a1,b1,c1,d1,e1,f1,g1,h1,i1.
now conduct a race for all of them. i.e., 10th race. take the 6 good ones among them.
let the best ones be a1,b1,c1,d1,e1,f1. now no need to consider 'g' , 'h', 'i series 'as the best ones among those series even can't make a place in top 6.
step 4:
so, 1st best is a1.
now we will see what are the possibilities for remaining positions.
2nd : a2,b1
3rd : a2,a3,b1,b2,c1
4th : a2,a3,a4,b1,b2,b3,c1,c2,d1
5th : a2,a3,a4,a5,b1,b2,b3,b4,c1,c2,c3,d1,d2,e1
6th : a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,c1,c2,c3,c4,d1,d2,d3,e1,e2,f1
step 4:
now we will try to find out second best, third best, fourth best.
liable candidates for these postions are
2nd : a2,b1
3rd : a2,a3,b1,b2,c1
4th : a2,a3,a4,b1,b2,b3,c1,c2,d1.
take common things by eliminating repeated ones
a2,a3,a4,b1,b2,b3,c1,c2,d1.totally 9 are there. conduct a race for these 9. you will get 2nd, 3rd, 4th ones.
step 6:
from the set 5th one came, there is possibility that sixth one can be in the set. from that 2 horses we will take.from the set 6th one came, we will take only the sixth one. so, totally we are taking 3 horses. we will take e1,e2,f1 as they are liable for 5th and 6th position. now totally 6 horses we made for next race.from which the 7th, 8th, 9th came . we can eliminate those sets.at minimum we can eliminate one set from consideration. i.e., 'a' set because it is only the set from which three horses participated.so, from the remaining three sets we can select three horse. so totally 9 horses. conduct 12th race among them to determine the 5th and 6th best..