CareerCup

Solution:

Divide 25 into 5 groups of 5 people each. From each race, choose top 3.
A1 A2 A3, B1 B2 B3, C1 C2 C3, D1 D2 D3, E1 E2 E3.

Conduct a race between A1 B1 C1 D1 E1 (just for choosing the topmost performer). Without loss of generality, lets assume that A1 is overall winner. Now we have a task of choosing 2nd and 3rd position. We can also assume that A1 > B1 > C1 > D1 > E1 (in terms of position, i.e A1 is better than B1 and so on)

Remaining candidates are: A2 A3, B1 B2 B3, C1 C2 C3, D1 D2 D3, E1 E2 E3.
Now we need to decide for 2nd and 3rd position.
Since E1 came last in the race above, E1, E2 and E3 can be eliminated (since they can never become 2nd and 3rd).
Similary D1, D2 and D3 can be eliminated.
However C1 cannot be removed, but C2 and C3 can be straightway eliminated.
B3 can be eliminated but not B1 and B2.
This is because now we have following elements:
A2 A3 B1 B2 C1. Even if both A2 and A3 are smaller than all Bi, then the result will be B1 followed by someone from B2 and C1.

Just think about eliminating candidates which can never be at 2nd or 3rd position and u will be left with above 5 (A2 A3 B1 B2 C1).

Answer: 5 + 1 + 1 = 7 races.

7times
first 5 races,we get:
a1 b1 c1 d1 e1
a2 b2 c2 d2 e2
a3 b3 c3 d3 e3
ai is better than ai+1,bi is better than bi+1,mark:ai>ai+1
the 6th race:we compare a1,b1,c1,d1,e1,get first 3,suppose a1>b1>c1>d1>e1
then we can get rid of di,ei,c2,c3,b3,because b3<b2<b1<a1,c3<c2<c1<b1<a1,di<c1<b1<a1.....
now only a1,a2,a3,b1,b2,c1,and a1 is the best
the 7th race:a2,a3,b1,b2,c1

1. Divide all 25 racers into 5 groups, each containg 5 persons and make them race (5 races up to now).
2. From these 5 groups, merge into a list of 3 top performers by picking the first topper
in each group - very much like merging sorted arrays in the merge sort algorithm.

So, there are only 5 races required to identify the top 3 performers

BTW, the original problem seems to be like below:
There are 25 horses. At most, 5 horses can race together at a time. You must
determine the fastest, second fastest, and third fastest horses.
Find the minimum number of races in which this can be done.

6

Can u plz explain how answer is 6

5 is the answer.
perform 5 races and get first 5 people. we already know the timing of each winner
based on timing we can decide first 3, there is no need for 6th race.

I think the answer is 8... First divide the 25 people into 5 teams(say A, B, C, D and E). Conduct race for each team and get the top 3 in each race. Then do the 6th race with winners of each race. The winner of this race is the topper. If the winner is from C team. Then do a race with the remaining 4 in the 6th race and the 2nd place holder in C team. Now the winner will be overall 2nd. Now replace this guy with the next winner in his team. We will now get the 3rd person.

6 is the right answer.

Have 5 race, note down the time for each person, sort it and choose top 3.

7 races.

First split in 5 each. 5 races.

6th race, race the winners.

Now if the winner are w1,w2,w3,w4,w5 with w(i) > w(i+1).

So w1 is the best.

Now pick the second and third of the initial race in which w1 was winner.
Pick w2 and the runner up in the initial race which w2 had won.
and w3.

Race them again: seventh race. The winner and runner up of this race give the second best and third best overall.

Answer is 9 races.

Its a question from the book "algorithms for interviews". In that question, there has been an additional constraint that if a performer beats another performer in some race, he will beat him in any other race too.
Does the amazon question talk about any such constraint?

6 would be the answer.
5 races for each sub group of 5 persons

Then winner of 5 races will race between each other which required 1 more race and the top 3 will be selected accordingly.

here devide 25 into 5 group
supose in group A contain 5 member(A1,A2,A3,A3,A4,A5) choose the best one from them.
similary in group B contain 5 member (B1,B2,B3,B4,B5) choose the best one from them and so on.....(here 5 race required)
now in each group we find the best one .now 5 are the best one for each group,from these 5 chose the best 3(here 1 race required)
now 5+1=6 (Ans)

Perform 5 races and get first 5 people , then perform 6th race among the 5 people who won the previous race and pick first 3. Is this really an amazon question. It seems too simple.

Answeris 11 races. In first race out of 5 we get top 3 and add 2 more to conduct second race.Continue this process then we got the top three performers.

Have 5 race, note down the time for each person, sort it and choose top 3.