Interview Question for Software Development Engineer at Microsoft:

My initial answer was just to race each horse against all others which is quite inefficient and can be improved a lot...

Conduct four races, and then race the four winners. Thats 5 races and you've got the fastest horse. Remove this winner horse from the pool, and remove the three horses that raced the losing horse of the fifth race. Now you have 12 horses left and 2nd, 3rd, and 4th place to fill. Repeat the same procedure and race the three winners, thats four more races and a total of nine. Remove the 2nd fastest horse (the winner of the ninth race) from the pool and remove the three horses that raced the loser of the ninth race. Now you have 8 horses left. Conduct 2 races, race the two winners to determine the 3rd fastest horse, thats three more races and a total of 12 races. To get the fourth place horse you just have to race the loser of the twelfth race with the three horses that raced the winner of the twelfth race and you've got your 4th place horse in 13 races. If anyone has thought of a quicker way please post.