Interview Question for Linux Kernel Engineering at Google:

I don't know, but Google it, you'll find the answer. Once you know it, it's obvious.

12

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.
Third answer: 8.
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.

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.

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.

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

oh, forget J,..... just speachless

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 ... 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, it's true that you don't know timings, but you do know RANKINGS.

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

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.

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.