Solving A Classic Google Interview Logic Puzzle

7 million views! Thank you! Here's a Microsoft interview puzzle I think you will enjoy. A cat is hiding in one of five boxes that are lined up in a row. The boxes are numbered 1 to 5. Each night the cat hides in an adjacent box, exactly one number away. Each morning you can open a single box to try to find the cat. Can you win this game of hide and seek? What is your strategy to find the cat? What if there are n boxes? Watch the video for the solution! https://www.youtube.com/watch?v=yZyx9gHhRXM

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

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

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.

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!

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

Sell all but 3 of the horses…. Those 3 will be the “fastest” horses you have. 😎

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

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.

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

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

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

Mechanical horses make so much more sense, in the beginning I was thinking of actual horses where you'd have to consider how many races each individual horse ran to make it fair in comparison

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

Google: Which 3 of those 25 horses are fastest? Meanwhile on bing: Leave only 3 alive

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

The answer is 0. Kill 24 horses and the one left is the fastest as the others can't run.

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.

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!

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