Solving A Classic Google Interview Logic Puzzle

There are 25 mechanical horses and a single racetrack. Each horse completes the track in a pre-programmed time, and the horses all have different finishing times, unknown to you. You can race 5 horses at a time. After a race is over, you get a printout with the order the horses finished, but not the finishing times of the horses. What is the minimum number of races you need to identify the fastest 3 horses?

I was suggested this puzzle via email by Terry Stickels. This is also a popular interview question at tech companies like Google. See a list of all sources in my blog post for this video:

Send me suggestions by email (address in video). I consider all ideas though can't always reply!

Why are there comments before the video is published? Get early access and support the channel on Patreon

If you buy from the links below I may receive a commission for sales. This has no effect on the price for you.

Show your support! Get a mug, a t-shirt, and more at Teespring, the official site for Mind Your Decisions merchandise:

My Books
Mind Your Decisions: Five Book Compilation
A collection of 5 books:
"The Joy of Game Theory" rated 4.1/5 stars on 44 reviews
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 3.5/5 stars on 4 reviews
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.4/5 stars on 13 reviews
"The Best Mental Math Tricks" rated 4.7/5 stars on 8 reviews
"Multiply Numbers By Drawing Lines" rated 4.3/5 stars on 6 reviews

Mind Your Puzzles: Collection Of Volumes 1 To 3
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.4/5 stars on 13 reviews
"Math Puzzles Volume 2" rated 4.5/5 stars on 6 reviews
"Math Puzzles Volume 3" rated 4.1/5 stars on 7 reviews

Connect with me

2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.

[TwistedOff]

Pick any 3 horses and destroy the remaining 22 horses. These three horses will be the fastest.

[arthuredens]

If I race 5 horses at a time there's no way I can beat any of them, horses are fast

[BradColemanisHere]

Yeah this was great. I was having a hard time until I saw you group them in to a, b, c, d, e based off of the rank of their race. I was getting stuck on the three fastest horses being in the same race initially but the re-grouping did the trick. The visual really helps.

[Orewastaken]

When you showed step three I was confused at first, then after a few seconds my brain understood and it BLEW my mind, what a great video

[asterisque]

I got 6, then realised i hadn't considered that the second fastest might be faster than another group's winner. Nice one

[keymasta]

Last season in F1 we ​​had 20 drivers and it took 17 races to identify the fastest 3 drivers

[undefined]

I know I will never work at these kinds of places, but to see the thought processes in these puzzles is awesome. Training yourself to look at the same real world problem in different perspectives to solve real world engineering/ self reliance problems are invaluable. Great video

[momamilosevic]

Google: Which 3 of those 25 horses are fastest?

Meanwhile on bing: Leave only 3 alive

[fostena]

You race 5 horses, sell the slowest one, and buy a watch.
The rest is trivial

[frorkbrunk]

I got the setup exactly the same up until the 6th round, but at the seventh round I couldn't quite get the final 2 horses. I thought c2 could be faster than a2 and b2 and got confused how I'd identify the 2nd and 3rd fastest horses with such complexity. What I missed is that c2 could infact be faster than a2 and b2, but it's irrelevant as in that case there is still a1, b1 and c1 faster.

Looking at it from the other side and eliminating all the horses that can not possibly qualify for top 3 is by far the easiest and smartest solution. I didn't come up with that.

[ang]

I got stumbled at "5 races give five " Fastest" Horses from each group, and the fastest among them is the first overall. But how exactly do I proceed with the 2nd and 3rd? " And I am happy about your explanation

[lluisg.]

In a Google's interview the better answer should always be: Google It!

[Oakenlix]

I realized pretty quickly that 6 races isn't enough, at which point I decided it's to complex and might require like 20 races or something.
Glad to see such an elegant solution, thank you!

[jamesrunco]

I think the key thing to think about is that A1 is automatically in so you are now looking for the fastest combination to fill 2 spots. So if there are only 2 spots then you know that anyone in group D or E is out because there just aren't enough slots for them. Everyone in D group is slower than D1 and D1 is slower than C1. So the LONGEST possible path is A1 to C1 (because B1 will always be faster than C1. This is also why C2 is out of contention, which threw me for a second). The shortest possible path is A1 to A3. A1 is automatically in. You just need to test the viable permutations of the fastest 3 horses. So their are 4 possible outcomes that include only the 3 fastest horses. They are:

A1, A2, A3
A1, A2, B1
A1, B1, C1
A1, B1, B2

So if you ignore the A1s since you automatically know they are automatically the fastest of the fast, you get the horses you need to test against each other being A2, A3, B1, C1, and B2. That's 5 horses which works out perfectly for a 7th race!

[csandford]

Interesting puzzle. I didn’t initially find the explanation very helpful, except it made me question my initial answer until I could work out the solution. Good stuff.

[puzzLEGO]

for people getting 6 races, we’re trying to find a method which guarantees the top 3 horses will be found. after the first 5 races, there are 15 horses which could still potentially be top 3 overall, and after the 6th race, there are still 5 in contention, including some of those 15 who didn’t win their initial race.

[ypob]

I am not getting smarter, i am just upgrading my memory over puzzles for when i do a job interview in like, four or five years

[mrbigheart]

This is damn good, man!
Until I saw the visual elimination and the surprise at the end (that we don't need to race again the fastest horse) I couldn't wrap my head around it.
Thank so much!!!

[Fabulous_Facade]

Love your method. I somehow got 12 by ruling out the horses that were not the fastest.

[jenniferkeeponfighting]

I think it also depends on who is keeping track and actually watching the races. Alice or Bob would be able to figure it out. Charlie is either selling popcorn or shoveling the stalls.