Samsung Interview Question Interns
Country: India
Interview Type: In-Person
I think min-7 races needed
partition 25 horses into 5 buckets
Bkt1:{H1...H5}
Bkt2:{H6...H10}
Bkt3:{H11...H15}
Bkt4:{H16...H20}
Bkt5:{H20...H25}
run 5 races for 5 buckets
Winner of each race is W1...W5
run once race between W1..W5
Winner of this race is W2,W1,W3,W5,W4 (say in winning order 1,2,3,4,5)
Total races so far = 5+1
Eliminate last three (W3,W4,W5) and their buckets from race 6 and eliminate winner of race 6(W2) use winner's bucket and remaining 4 horses and run race between 4 and W1
Total races: 5+1+1=7
9 Races is the Correct Answer.
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Race 1 to 5: 5 Winners from the Top Group
Winners: X1 X6 X11 X16 X21
Top 5 Winner List: Empty
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Race 6: Finding the Best Horse from the top.
Participants: x1 x6 x11 x16 x21
Winner: x1
Top 5 Winner List: x1
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Elimination: We need to eliminate the horses to keep the race minimum.
we cant take top 3 among the rest since x5 could be faster than x21.
but we can remove the rest of horses after x21 in G5 since x21 finished the last in race-6.
we can keep eliminating horses all the way to winner group with this strategy.
After Elimination,
G1: x2 x3 x4 x5
G2: x6 x7 x8 x9 (1 horse removed)
G3: x11 x12 x13 (2 horses removed)
G4: x16 x17 (3 horses removed)
G5: x21 (4 horses removed)
Race 7: Finding the 2nd Best horse
Participants: x2 x6 x11 x16 x21
Winner: x2
Top 5 Winner List: x1 x2
Eliminate all horses in loser group since we only need 3 more horses to find and eliminate the rest of horses in
x16.
After Elimination,
G1: x3 x4 x5
G2: x6 x7 x8
G3: x11 x12
G4: x16
G5:
Race 8: Finding the 3rd best horse
Participants: x3 x6 x11 x16
Winner: x3
Top 5 Winner List: x1 x2 x3
G1: x4 x5
G2: x6 x7
G3: x11
G4:
G5:
Race 9: Finding the final 2 horses
Participants: x4 x5 x6 x7 x11
Winner: x4, x5
Top 5 Winner List: x1 x2 x3 x4 x5
9 Races is the Correct Answer.
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Race 1 to 5: 5 Winners from the Top Group
Winners: X1 X6 X11 X16 X21
Top 5 Winner List: Empty
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Race 6: Finding the Best Horse from the top.
Participants: x1 x6 x11 x16 x21
Winner: x1
Top 5 Winner List: x1
G1: x1 x2 x3 x4 x5
G2: x6 x7 x8 x9 x10
G3: x11 x12 x13 x14 x15
G4: x16 x17 x18 x19 x20
G5: x21 x22 x23 x24 x25
Elimination: We need to eliminate the horses to keep the race minimum.
we cant take top 3 among the rest since x5 could be faster than x21.
but we can remove the rest of horses after x21 in G5 since x21 finished the last in race-6.
we can keep eliminating horses all the way to winner group with this strategy.
After Elimination,
G1: x2 x3 x4 x5
G2: x6 x7 x8 x9 (1 horse removed)
G3: x11 x12 x13 (2 horses removed)
G4: x16 x17 (3 horses removed)
G5: x21 (4 horses removed)
Race 7: Finding the 2nd Best horse
Participants: x2 x6 x11 x16 x21
Winner: x2
Top 5 Winner List: x1 x2
Eliminate all horses in loser group since we only need 3 more horses to find and eliminate the rest of horses in
x16.
After Elimination,
G1: x3 x4 x5
G2: x6 x7 x8
G3: x11 x12
G4: x16
G5:
Race 8: Finding the 3rd best horse
Participants: x3 x6 x11 x16
Winner: x3
Top 5 Winner List: x1 x2 x3
G1: x4 x5
G2: x6 x7
G3: x11
G4:
G5:
Race 9: Finding the final 2 horses
Participants: x4 x5 x6 x7 x11
Winner: x4, x5
Top 5 Winner List: x1 x2 x3 x4 x5
All right its right this problem is solved with 8 races by considering the following approach.
Let us suppose that after the first 5 races we get the following results as:
H1 H2 H3 H4 H5
H6 H7 H8 H9 H10
H11 H12 H13 H14 H15
H16 H17 H18 H19 H20
H21 H22 H23 H24 H25
Now we again do the 6th race among the group leaders and get the following result as:
1st- H1, 2nd- H6, 3rd- H11, 4th- H16 and 5th- H21
After the 6th race we can safely eliminate the following horses as:
1. H22 H23 H24 H25 from the last group as among the top 5 their group leader will be considered first and also they cannot win from H4, H3 , H2 and H1 which will be considered first.
2. H18, H19 and H20 from the 4th group as the top 5 would be considered as
H1 H6 H11 H16 and H17. So clearly their group leader and H17 would be considered and these horses have no chance of coming up
3. H14 and H15 from the 3rd group as the top 5 would first be
H1 H6 H11 H12 and H13 as H12 and H13 could be faster than both H16 and H17 and also H21
4. H10 from 2nd group as first the top 5 would come up as:
H1 H6 H7 H8 H9.
5. And no one from 1st group as they all are eligible to beat the group leaders from the next group
So we are left with:
H1 H2 H3 H4 H5
H6 H7 H8 H9
H11 H12 H13
H16 H17
H21
Clearly as H1 came first in all of the races so this is one of the top 5 horses.
Now we do a 7th race among H3 H7 H12 H11 and H16 as:
1. To consider H7 is faster than those of third group members
2. Make a competition among 3rd and 4th group members
3. H21 is not considered as first the 3rd and 4th group members and leaders will compete.
4. H6 is not considered to consider the competition between its group member with the corresponding group leaders as we know H6 is already faster than H11 H16 and H21 from the 6th race we did
5. Similarly eliminate H12 and H13 and H8 H9 are eliminated
So let the results of the 7th race be the following:
1st- H3 2nd- H7 3rd- H11 4th- H12 and 5th- H16
We can safely eliminate the following horses
1. H21 definitely cannot come in the top 5
2. H17 definitely cannot come in the top 5
3. H16 cannot come as first these horses would be considered as
H1 H2 H3 H4 H5 H6 H7 H11 as H7 is both better than H11 and H16 because of the results of the 7th race
4. We can also eliminate H11 as this would not be faster than both H6 and H7 as from 6th and 7th race and also H3 is faster than it as due to 7th race.
So we are left with
H1 H2 H3 H4 H5
H6 H7
Now we know that
H3 is better than H7 so H2 is also better. But we dont know which is better among H3 and H6 and H2 and H6. Dont worry as no matter what H2 will be there among the top 5 horses. So we do an 8th race among
H3 H4 H5 H6 H7 and the top 3 horses along with H2 and H1 will come up in the top 5 horses and thus we are done..
horse1=h1,..........horse25=h25
h1,h2,h3,h4,h5====> race1///// best racer=A(consider)
h6,h7,h8,h9,h10====>race2///// best racer=B(consider)
h11,h12,h13,h14,h15====> race3///// best racer=C(consider)
h16,h17,h18,h19,h20====>race4///// best racer=D(consider)
h21,h22,h23,h24,h25====>race5///// best racer=E (consider)
BY COMPARING THHE TIME:
from race1= we get A(one of the racer from h1-h5 as the best)
from race2&rest of race1 = we get B
from race3&rest of race1&2 = we get C
from race4&rest of race1&2&3= we get D
from race5&rest of race1&2&3&4= we get E
Therefore,A,B,C,D,E(which is the best horses from the above 25 horses.i.e.,h1-h25:)
lets say these are the 25 horses :
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
We can do a race btw first row having atmost 5 horses and we'll know the winner.
Repeat for rest of the rows and we will know the top 5 horses. Ofcourse we will not know which ones is fastest but that is not needed according to question. So we will need minimum 5 races between 25 horses to know 5 fastest horses.
Well , I think only 5 races are required .After 5 races ,all horses would've run atleast once .Note the time required for each horse ,select the top 5 .Problem solved .
What is the logic in comparing the horses that became winners in each group of 5 ??What if the first group contained all the best 5 horses ? Only the top horse gets to run the next race nah ?!!
I know I can do it with 10 races using k-way MergeSort:
- First split the 25 horses in 5 groups of 5 horses each
- Then race the top horses of each group (there are five of them), the winner it's the best horse of the 25.
- Then replace the one top horse for the second of his group and repeat.
- After 5 races you get the top 5 horses
So, with 10 it's possible but maybe you can do it with less because here I got the top 5 completely ordered.
@amish.cusat Can you explain your logic how u can find in 8 races...i looking to do it in 8 races bcoz 9 races approach i know already
Here is the explanation:-
1 6 11 16 21
2 7 12 17 22
3 8 13 18 23
4 9 14 19 24
5 10 15 20 25
========5 races with winners 1 6 11 16 21========
Imp - discard horses 10, 14, 15, 18, 19 20, 22, 23 24, 25
Result groups would be as below:-
1 6 11 16 21
2 7 12 17
3 8 13
4 9
5
6th race among these winners with result say 1 6 11 16 21
7th race - 2 3 7 12 16(Idea is to take 16 as ref and discard grps that are slower completely or paritally - here discarding x* means I am gonna discard horse x and all the horses in same group below that horse x)
Test cases of 7th race:-
=======================
Case 1 - 16 comes 1st. That means we got top 4 horses as 1 6 11 & 16 so
8th race would be among 17 21 and runner of 7th race
Case 2 - 16 comes 2nd(over all min 4 horses are ahead of 16 and those are 1 6 11 & winner of 7th race. That means we can discard horses slower than 16)
12 comes first - discard 2*, 7*, 21*,17* - 8th race among 13&16
2 comes first - top 5 are 1 6 11 2 16(all other 3* 7* 12* are behind 16 in 7th race hence discard them and discard slower ones i.e.17 21)
7 comes first - discard 2*, 12*, 17*, 21* so the race would be among 7 8 9 11 16 for 3rd 4th and 5th post(top 3 in 8th race).
Case 3 - 16 comes 3rd(discard 16 17 21) the combination of top 2 in 7th race would be (2,3), (2,7), (2,12), (7,12)
1 6 11
2 7 12
3 8 13
4 9
5
(2,3) - discard 7*, 12* - 8th race would be among 4 5 6 11 to discard last 2
(2, 7) - discard 3* 12* - 8th race would be among 2 7 8 9 11 to eliminate last 3(1 is top and 6 can be 2nd or 3rd(still in top5))
(2, 12) - discard 3* 7*- 8th race would be among 2 6 11 12 13
(7, 12) - discard 2*
here 12 comes second(1 6 11 7 being faster than 12 now - discard 13) - 8th race would be among 7 8 9 11 12 to eliminate last 2
but if 12 comes first (1 6 11 12 being faster than 7 - check for 7 8 9 13 to get the last post.)
1 6 11 16 21
2 7 12 17 22
3 8 13 18 23
4 9 14 19 24
5 10 15 20 25
========5 races with winners 1 6 11 16 21========
Imp - discard horses 10, 14, 15, 18, 19 20, 22, 23 24, 25
Result groups would be as below:-
1 6 11 16 21
2 7 12 17
3 8 13
4 9
5
6th race among these winners with result say 1 6 11 16 21
7th race - 2 3 7 12 16(Idea is to take 16 as ref and discard grps that are slower completely or paritally - here discarding x* means I am gonna discard horse x and all the horses in same group below that horse x)
Test cases of 7th race:-
=======================
Case 1 - 16 comes 1st. That means we got top 4 horses as 1 6 11 & 16 so
8th race would be among 17 21 and runner of 7th race
Case 2 - 16 comes 2nd(over all min 4 horses are ahead of 16 and those are 1 6 11 & winner of 7th race. That means we can discard horses slower than 16)
12 comes first - discard 2*, 7*, 21*,17* - 8th race among 13&16
2 comes first - top 5 are 1 6 11 2 16(all other 3* 7* 12* are behind 16 in 7th race hence discard them and discard slower ones i.e.17 21)
7 comes first - discard 2*, 12*, 17*, 21* so the race would be among 7 8 9 11 16 for 3rd 4th and 5th post(top 3 in 8th race).
Case 3 - 16 comes 3rd(discard 16 17 21) the combination of top 2 in 7th race would be (2,3), (2,7), (2,12), (7,12)
1 6 11
2 7 12
3 8 13
4 9
5
(2,3) - discard 7*, 12* - 8th race would be among 4 5 6 11 to discard last 2
(2, 7) - discard 3* 12* - 8th race would be among 2 7 8 9 11 to eliminate last 3(1 is top and 6 can be 2nd or 3rd(still in top5))
(2, 12) - discard 3* 7*- 8th race would be among 2 6 11 12 13
(7, 12) - discard 2*
here 12 comes second(1 6 11 7 being faster than 12 now - discard 13) - 8th race would be among 7 8 9 11 12 to eliminate last 2
but if 12 comes first (1 6 11 12 being faster than 7 - check for 7 8 9 13 to get the last post.)
I believe 8 works. Let's call horses h1, h2, h3, .., h25.
First race between groups of 5 horses. WLOG assume that h5 is the winner of the first group (h1, ..h5) and h10 is the winner of second group (h6, ..h10) and h115 and h20 and h25 are winners as well. So far we had 5 races. In the 6th race, we have all the winners, i.e., h5, h10, h15, h20, and h25. Now WLOG assume that horses are in the order of h5, h10, h15, h20 and h25. Thus, h25 is the fastest between all. Now in the 7th race we have h5, h9 (second fastest of group h6,..h10), h10, h14 (second fastest of the group h11,..,h15), and h15. Top three horses in the 7th race are chosen. Similarly in the 8th race, we have h14, h15, h19, h20, h24.
7 Races required to find top 3 fastest horses.
1. First divide horses in group of 5. Let's say group name is G1,G2,G3,G4,G5.
2. Now 5 races required for each group. Lets say Horses are named as their ranking in a group. For instance fastest horse in G1 is named G1H1, second fastest in G1 is named G1H2 and so on. Do this naming scheme for all group. Till now you have done only 5 races.
3. 6th race will be among top horses of groups. Means G1H1, G2H1, G3H1, G4H1, G5H1. For instance result of the race is G3H1, G5H1, G2H1, G1H1, G4H1. Whoever wins this race will be fastest horse among 25 and it is G3H1. As G1H1 and G4H1 is not able to win 6th race, all the horses in G1 and G4 is not a candidate of top 3 horses. You can discard this two groups. As G3H1 comes first, G3H2 and G3H3 will be eligible for top 3 candidate. G5H1 comes second in 6th race, only G5H2 will be candidate for top 3. G2H1 comes third so no other horses from G2 will be eligible except G2H1.
4. So last race will be among G3H2, G3H3, G5H1, G5H2, G2H1. Top two horses from this race and G3H1 is top 3 horses among 25.
5 groups, run 5 races first --- 5
now, select first from each grp and run --- 1
now, select 2nd from group where winner belongs, and all others --1
now, select 2nd if winner belongs to other group...else 3rd from previous winner group ...always make rest of racer top within each group ...1
again same..1
lastly 9 will be races and top 5 will be horses
This is a very poorly worded question. When you run a race, do you know the timing of each horse ? or just the ranking. If you know the timing, then just divide into 5 groups, run your 5 races one per group and you have the timings of all 25 horses and hence can pick the top 5.
Now if you don't have timings and all you have is rankings as output of each race, then the solution is different.
Again, poorly worded question.
The answer is different depending on what is the output of a race: Is it
a) the timings of each horse OR
b) just a ranking
With a, you divide into 5 groups. Run 5 races, 1 per group and now you have the timings of all 25 horses and hence can pick the top 5.
If its b, then it is a little more involved
Plz read question again i asked top 5 not top 3...i know top 3 it can be done in 7 races...
Thanks buddy, you solved for top 5 but its not right solution
S1 S2 S3 S4 S5 25 24 23 22 21
S6 S7 S8 S9 S10 20 19 18 17 16
S11 S12 S13 S14 S15 15 14 13 12 11
S16 S17 S18 S19 S20 10 9 8 7 6
S21 S22 S23 S24 S25 5 4 3 2 1
if horses speed like this then if u eliminate bottom 2 from each group, u cannot find right top 5 horses, check your approach on this type data
all wrong answers ..
- mike June 03, 2014last racer from one group may be faster than first racer of another group