Adobe Interview Question Software Engineer / Developers
Team: Lifecycle
Country: India
7 Races
1. Make 5 batches of 5 each. Eliminating 10 members (2 from each group). Top 3 of every group remains.
2. Take 1 top from each of 5 batches and whosoever is winner, gives us fastest.
3. Take 2nd topper from batch from which fastest was found and run against 4 remaining from step 2. After this race top two will form 2nd and 3rd fastest.
8 races. 6 races to find the first place and after that for next i.e. Second we need one more and so on
First take 5 sets of 5 horses. Notice the position of each group horces. Now take top five horses say A1,B1,C1,D1,E1... now with one race we can know the top horse lets say its B1, Now choose B2 and have a race between A1,B2,C1,D1,E1..... now we need another race to know the second position. Similarily we can find the third one in 1 more race Sp total races are 6(to determine 1st place) + 1(to determine 2nd) + 1(to determine (3rd), So total of 8 races
first make groups of 5. Race them all. (5 races). Reject the bottom 2 of all groups.
Race all their winners. Eliminate the 1st (he is fastest) and the 4th horse and 5th (along with their groups). (6 races and 8 horses left ).
Now take the remaining two of the horses from which the fastest was found the top two of the second set and the top of the 3rd set.(this is 7h race and is the final answer.)
12 races:
Race 1 : 1 2 3 4 5
Race 2 : 6 7 8 9 10
Race 3: 11 12 13 14 15
Race 4: 16 17 18 19 20
Race 5: 21 22 23 24 25
Take top 3 of each set --- you will get 15 shortlisted horses
This will lead to another 3 races... (Now 8 races)
From 15 horses, Again take top 3 of each of 3 set -- you will get 9 shortlisted horses
this will lead to another 2 races.. (Now 10 races)
From 9 horses of 2 races .. take top 3 of each of 2 set .. you will get 6 horses..
From the 6 horses... one race is done with 4 horses(11th race) .. from the top 3 of the 11th race , 12 th race is done with remaining 2 horses... and top 3 will be found..
1. 5 Group of 5 horses, We eliminate 2*5 = 10 horses, 15 left
2. 3 Group of 5 horses, We eliminate 2*3 = 6 horses , 9 left
3. Race one group of 5 horses, 3 left, and total 4+3 == 7 left
4. Race one group of 5 horses to eliminate 2 horses and we are left with 5 horses
5. One more race and all 3 top mighty horses are known to you
So total minimum race required 5+ 3 + 1+ 1 + 1 = 11
Cheers
This is obviously incorrect. Suppose the five groups are A, B, C, D, E. After racing each of these groups you can find out the top horse in each group. So you know the horse ranked 1 in each group (A1, B1, C1, D1, E1) and you can race these to find out the fastest horse. But it is possible that the horse that came second in Group A (A2) is faster than the horse that came first in Group B (B1). Your method doesn't take that into account.
Or as ben pointed out, if the top 3 horses out of the 25 are in the same group, then your method won't work.
The essence of the problem i think here is that, after a race you can't store the timings. you just know the positions.
A1,A2,A3,A4,A5
B1,B2,B3,B4,B5
C1,C2,C3,C4,C5
D1,D2,D3,D4,D5
E1,E2,E3,E4,E5
Above 5 races
A1,B1,C1,D1,E1
1 Race
Now top 3 in the list as per my assumption or take any other also
D1, C1, E1
Qualified for next round
D1, C1, E1,
D2 C2
D3
D1 is the first best here
pick best two in the next race among D2,D3, C1,C2, E1
total races = 5+1+1 = 7
A1,A2,A3,A4,A5
- Anonymous July 05, 2012B1,B2,B3,B4,B5
C1,C2,C3,C4,C5
D1,D2,D3,D4,D5
E1,E2,E3,E4,E5
Above 5 races
A1,B1,C1,D1,E1
1 Race
Now top 3 in the list as per my assumption or take any other also
D1, C1, E1
Qualified for next round
D1, C1, E1,
D2 C2
D3
D1 is the first best here
pick best two in the next race among D2,D3, C1,C2, E1
total races = 5+1+1 = 7