4.1 of 5
www.google.com Mountain View, CA 5000+ Employees

# GoogleLinux Kernel Engineering Interview Question

I interviewed in Mountain View, CA and was asked:
"You have 25 horses, what is the minimum number of races you can find the top 3. In one race you can race 5 horses, and you don't have a timer."
 Tags: ,   See less 8

Part of a Linux Kernel Engineering Interview Review - one of 2,368 Google Interview Reviews

0
of 1
vote
I don't know, but Google it, you'll find the answer. Once you know it, it's obvious.
- Interview Candidate on Mar 11, 2009 Flag Response
0
of 2
12
- Anonymous on Apr 28, 2009 Flag Response
3
of 5
Probably 8.

First answer: at least 5 (you have to look at every horse).
Second answer: 11. You can race five horses, replace 4th and 5th place horse by two horses from pool of horses that haven't raced, and continue doing this until all horses have raced. Since there are 25 horses, you need 1 race for the first five horses and 10 to go through the remaining 20.
Round 1 (5 heats) : Race horses in heats of five. Eliminate all 4th and 5th place horses. (15 horses left)
Round 2 (1 heat): Race winning horses from every heat. Eliminate 2nd and third place horses that lost to horses in round 2 that came third or worse. (7 horses left).
Round 3 (1 heat): Pick any five horses. Race them. Eliminate bottom two and replace with remaining two horses. (5 horses left)
Round 4 (1 heat): Eliminate bottom two.

Note:
after round 2 it may be possible to use some interesting decision tree mechanism to determine the three fastest horses using fewer horses per heat but you still need two heats to do that.
This problem assumes horses don't get tired, no ties are possible and a horse's speed is deterministic race after race after race. Good assumptions for brain teasers, but not for real life.
- B on Apr 29, 2009 Flag Response
3
of 4
Actually, should be 7. Forgot that after round 2 you can eliminate one more horse leaving you with 6 horses, one of which (the winner of the second round), is the fastest horse of them all. One more race with the five horses not No.1 and you pick the top two.
- B on Apr 29, 2009 Flag Response
1
of 10
6. First round consists of 5 races of 5 horses. Pull aside the winner of each race in the first round for the final heat and eliminate the bottom 2.
- J on May 27, 2009 Flag Response
0
of 4
8.
Run 5 races of 5 horses. (5)
Put all the 3rd place horses in a race, winner is 3rd fastest. (6)
Put all the 2nd place horses in a race, winner is 2nd fastest. (7)
Put all the first place horses in a race, winner is fastest. (8)
The third place horse was beaten by one of the 2nd place horses. So third stays in third.
Same for the second place horse.
- chzwiz on Jul 29, 2009 Flag Response
1
of 3
chzwiz, r u sure u r not high?
B, what happened in round 2? why 8 horses suddenly get eliminated by 1 race? again, do u know what you are smoking?
- Anonymous on Aug 1, 2009 Flag Response
0
of 1
vote
oh, forget J,..... just speachless
- Anonymous on Aug 1, 2009 Flag Response
8
of 8
7. chzwiz, your answer is incorrect. One of the first or second place horses could be 2nd fastest and/or 3rd fastest. I drew a grid to visualize the problem. First, run five races to establish 5 groups of internally ranked horses, and you can of course immediately eliminate 4 & 5 of each race.

1 2 3 x x
1 2 3 x x
1 2 3 x x
1 2 3 x x

Then race 1st place horses, eliminate 4 & 5, and those they beat earlier. You can also eliminate the horses #3 beat, and the 3rd place horse from #2's first race.

1 ? ? X X
2 ? X X X
3 X X X X
X X X X X
X X X X X

You know #1 is fastest. Race the remaining horses (2, 3 and ?'s), and the top two are 2nd and 3rd. After reading the above answers, this is the same as B's revised answer, but I found it easier to explain/visualize with the grid.
- Brad on Aug 17, 2009 Flag Response
0
of 0
@brad ... but isnt dat v dont have timer to know d ranking ... or my assumption is wrong??

I thought v know only 1 result of every race .. i.e. top 1
- spawn on Feb 11, 2010 Flag Response
0
of 0
Spawn, it's true that you don't know timings, but you do know RANKINGS.
- Jerry on Oct 9, 2010 Flag Response
0
of 1
vote
I don't see errors in logic with each answer above. They may claim to discover the answer with fewer races, but they have too many assumptions or errors to be correct. To do this optimally and without any potential error, you must eliminate as many correctly placed horses as possible and eliminate the maximum number of non-win/place/show horses each round.

Round 1:
(Races 1-5) You must start with 5 heats @ 5 horses apiece. The non-Win/Place/Show horses of each round have been eliminated, leaving 15 horses.
Round 2:
(Race 6) You then race the top finishing horses against one another, leaving you with your overall fastest horse. We now have the Win horse, leaving only Place and Show as unknowns. This also eliminates the bottom two horses, leaving 2 horses from this race. There are also only two more unknown horses.
Race 7) You may race the Place horses against one another. Only two survive this race, since we know that each of these horses can place 2nd at best. This leaves 2 horses from this race.
(Race 8) You may also race the show horses of each round. Since they each have been beaten by two other horses in Round 1, only the 1st place horse of this round survives as the potentially 3rd best horse. This will leave 1 horse in this race to battle for the 2 remaining spots.

Round 2 leaves 2 Horses (Race 6) + 2 Horses (Race 7) + 1 Horse (Race 8) = 5 Horses, for 2 unknown spots.

Round 3:
(Race 9) We can now have the final 5 horses race for the remaining two spots leaving us with the undisputed 2nd and 3rd places.

Here is a more complex scenario below in which the top 2 horses come from the same original race and the later races are full of lame horses. Many of the solutions above do not address those problems. Each # is a horse, named by it's inherent ranking. X signifies 'eliminated horse'

Race1 R2 R3 R4 R5
1-->R6 3-->R6 11-->R6 16-->R6 21-->R6
2-->R7 7-->R7 12-->R7 17-->R7 22-->R7
4-->R8 8-->R8 13-->R8 18-->R8 23-->R8
5X 9X 14X 19X 24X
6X 10X 15X 20X 25X

Round 2:
Race 6 (Winners) Race 7 (Places) Race 8
1 -->1st Place 2-->Race 9 4-->Race 9
3 -->Race 9 7-->Race 9 8X
11-->Race 9 12X 13X
16X 17X 18X
21X 22X 23X

Round 3:
Race 9
2P
3S
4X
7X
11X

First Place = 1 Horse -- Race 6 Winner
Second Place = 2 Horse -- Race 9 Winner
Third Place = 3 Horse -- Race 9 2nd place
- Josh E on Dec 30, 2010 Flag Response
0
of 0
To fix the formatting issues that appeared as spaces are eliminated above--

Race1________R2___________R3___________R4___________R5____

_1-->R6_______3-->R6_______11-->R6_______16-->R6_______21-->R6
_2-->R7_______7-->R7_______12-->R7_______17-->R7_______22-->R7
_4-->R8_______8-->R8_______13-->R8_______18-->R8_______23-->R8
_5X__________9X___________14X__________19X___________24X
_6X__________10X__________15X__________20X___________25X

Round 2:
Race 6 (Winners)__________Race 7 (Places)__________ Race 8

1 -->1st Place_____________2-->Race 9______________4-->Race 9
3 -->Race 9_______________7-->Race 9 _____________ 8X
11-->Race 9______________12X____________________13X
16X_____________________17X____________________18X
21X_____________________22X____________________23X

Round 3:
Race 9
2P
3S
4X
7X
11X

Less ascetically pleasing than the original, but it will suffice.
- Josh E on Dec 30, 2010 Flag Response
0
of 0
This problem can be reduced to (viewed as) multiway mergesort:
1) split the horses into groups of five as if we had five files to sort
2) do a multiway mergesort but instead of sorting all horses, stop as soon as you get the top 3

We need one race per group to sort them (5 races total). And 3 more races to get the top 3. We will need 8 races.

The interviewer might have been looking whether an applicant was able to spot this relation to algorithms or not.

But if this was a brain teaser instead, maybe the answer is less than 8.
- russell on Apr 2, 2011 Flag Response
5
of 5
The answer is definitely 7, here is a fantastic explanation:

http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/
- Maya on May 26, 2011 Flag Response
0
of 0
Randomly race the horses 5 times and keep a winner's bracket.

The 6th race will determine the fastest horse. This is trivial.

The 2nd and 3rd fastest could be in the winner's bracket or they could be the 2nd or even 3rd fastest in one of the losing brackets. Then we have to race 2nd and 3rd place from the winners bracket as well as from each original bracket, which had 5. This means we have 12 horses to try.

Randomly keep 2 horses out and race 5v5. Keep the top two horses from both. We have 6 horses now. Race 3v3 and keep the top two, leaving 4 horses. Then race these.

I count 11?
- Anonymous on Feb 7, 2013 Flag Response
0
of 0
Brute force divide and conquer solution = 18 races.

Just be aware of the brute force solution in case there's restriction where we can't use the memory to save the first 3 places.
- Leo on Dec 2, 2013 Flag Response