## Samsung Interview Question for Interns

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

last racer from one group may be faster than first racer of another group

Comment hidden because of low score. Click to expand.
-2

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

Comment hidden because of low score. Click to expand.
-2

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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..

Comment hidden because of low score. Click to expand.
0

I can,t get it how you are discarding the horses. Can you further explain it?

Comment hidden because of low score. Click to expand.
0
of 0 vote

10 races

Comment hidden because of low score. Click to expand.
0
of 0 vote
for me it take 11 races . 1)5 race 1st race :h1,h2,h3,h4,h5 winner: h1 , 2nd position: h2, 3rd position :h3, 4th position: h4, 5rd position :h5 2nd race: h6,h7,h8,h9,h10 winner: h6 , 2nd position: h7, 3rd position :h8, 4th position: h9, 5rd position :h10 3rd race: h11,h12,h13,h14,h15 winner: h11 , 2nd position: h12, 3rd position :h13, 4th position: h14, 5rd position :h15 4th race: h16,h17,h18,h19,h110 winner: h16 , 2nd position: h17, 3rd position :h18, 4th position: h19, 5rd position :h20 5th race :h21,h22,h23,h24,h25 winner: h21 , 2nd position: h22, 3rd position :h23, 4th position: h24, 5rd position :h25 6th race between winner of all the 5 groups :h1,h6,h11,h16,h21 winner: h1 , 2nd position: h6, 3rd position :h11, 4th position: h16, 5rd position :h21 remaining Horse after 6th race h1,h2,h3,h4,h5 h6,h7,h8,h9 (h10 eliminated) h11,h12,h13 (h14,h15 eliminated) h16,h17 (h18,h19,h20 eliminated) h21 (h22,h23,h24,h25 eliminated) 7th race between: h21,h16,h17,h12,h13 in 7th race we can find top two house, winner :h21, 2nd position :h16 remaining (h17,h12,h13 eliminating ) remaining horse: g1:h1,h2,h3,h4,h5 g2:h6,h7,h8,h9 remaining 3 horse :h11,h16,h21 8th race between :h11,h16,h21(3rd position 6the race),h9 (last second position in g2),h5(last position in g1)->{{{ h5,h9,h11,h16,h21 }}} selecting top 3 horse for this group {{{ h11,h21,h16}}} 9th race between :top 3 in 8th race (h11,h21,h16) and h4 (last second position in g1),h7 (last third position in g2)->{{{ h11,h21,h16,h7,h4 }}} selecting top 3 horse for this group {{{ h11,h21,h16}}} after 9th race remaining horses h1,h2,h3,h6,h11,h16,h21 h1 is conform in top position remaining horse {{{h2,h3,h6,h16,h21,h11} 10 race between :top horse 3 in 9th race and h3 and h6 11 race between top 4 horse and h2 top 5 horse is h1,top four in 11th race are the top 5 horses
Comment hidden because of low score. Click to expand.
0
of 0 vote

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:)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

7 is answer for top 3 hourses

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?!!

Comment hidden because of low score. Click to expand.
-1
of 3 vote

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.

Comment hidden because of low score. Click to expand.
0

improve your solution...i able to solve it in 9 races worst case but i looking better than this.....9 is my answer....

Comment hidden because of low score. Click to expand.
-1
of 3 vote

8 races

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
2

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
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.)

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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
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.)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``Only 5 races all the toppers are placed as best racers.....simple``

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

9

Comment hidden because of low score. Click to expand.
0

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 or 3rd from winner group keeping other top ...1
again same..

lastly 9 will be races and top 5 will be horses

Comment hidden because of low score. Click to expand.
-2
of 2 vote

satveer ji ..i solved horse problem
9

Comment hidden because of low score. Click to expand.
-2
of 2 vote

plz explain how 9 count solution is achieved

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

not necessary that eahc group top racer is among top 5...try it more...

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

Plz read question again i asked top 5 not top 3...i know top 3 it can be done in 7 races...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What if s16 is faster than s2...how can you eliminate it.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.