How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle

Tech companies like Google have asked this question during interviews. 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.

My blog post for this video (extensive links for sources of this puzzle):

Alexander recreated the puzzle in Python

Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.

My Books

[MWSin]

Cats playing by logical and consistent rules... You've never owned a cat, have you?

[MrVirus]

Yeah there are three pretty simple solutions to this problem.

1) Get 4 more cats, so that no matter what box you open up, you will find a cat.
2) Lift the box to feel how heavy it is. Then move the heaviest box to the first in the line. The next day, open the second box. You will always find the cat in this way.
3) Get rid of 4 of the boxes so that your house isnt such a darn mess.

[deepghadiyali]

I will check wieght of all boxes and open the heaviest box 🙂

[joeqmix]

I don't know why, but I originally came away with the impression that Box 5 was also "adjacent" to Box 1. That would totally blow the odd/even thing.

[hendrilibrata]

Unknowingly to you, the cat got bored and left on day 4

[jonathanfowler]

The cat is in a superposition, existing in all of the boxes at the same time, until you open them. ;)

[JohnRandomness]

Practical answer: wait until he's hungry enough to come back out on his own.

[oatlord]

I can open 1 box? OK, I'll open a box of cat food. Perfect method for finding cat each day.

[FUGP]

Another one of those "interview questions" that has never actually been asked on an interview.

[richardyork]

This solution does give the fewest number of nights in order to be certain of catching the cat, but personally I would pick the boxes in the order 2, 2, 3, 4, 4, 3, 2. This guarantees finding the cat in 7 nights, but with a much higher probability of finding it within the first few nights.

Using the method in the video, assuming an equal probability of the cat being in each box on day 1: (bold indicates box chosen that day, number in brackets is percentage chance of finding the cat by that day)
Day 1: 20% *20%* 20% 20% 20% (20%)
Day 2: 00% 30% *10%* 30% 10% (30%)
Day 3: 15% 00% 30% *10%* 15% (40%)
Day 4: 00% *30%* 00% 30% 00% (70%)
Day 5: 00% 00% *15%* 00% 15% (85%)
Day 6: 00% 00% 00% *15%* 00% (100%)

Whereas using my method:
Day 1: 20% *20%* 20% 20% 20% (20%)
Day 2: 00% *30%* 10% 30% 10% (50%)
Day 3: 00% 05% *15%* 15% 15% (65%)
Day 4: 2.5% 00% 10% *15%* 7.5% (80%)
Day 5: 00% 7.5% 00% *12.5%* 00% (92.5%)
Day 6: 3.75% 00% *3.75%* 00% 00% (96.25%)
Day 7: 00% *3.75%* 00% 00% 00% (100%)

So as you can see, the method in the video only gives an advantage on day 6. Anybody find anything better?

[pentox]

Since it's a programmer interview question, indexing starts at 0.

[ejun]

I don't know if anyone else thought the same way, but for the even case, I literally thought of the strategy you use to checkmate someone with only a king and a rook. You basically chase them to a corner until they walk into you either by force or by mistake. In order for it to work, you need to make sure to sync up so you never walk into them, you want to make them walk into you. Sure, it's not the exact same problem, but it helped me come up with a solution.

[Nuoska]

The grid representation is ingenious. The cat always moves diagonally, and you have to use blue squares to draw a shape that blocks all possible paths.

[Dewald]

Three ways to find the cat.

1) Shake the cat treat box and see where the can comes from.

2) Sit in front of the boxes without making a sound and see what box moves when the cat moves inside it.

3) Set up a camera on the boxes before bed and see which box the cat in by review the recording the next morning.

[Commenter]

The way to solve this problem is by shaking all the boxes.

If you hear hissing coming from one of the boxes then that's the one to open.

[Firzj]

Applying to janitor position at Microsoft
Microsoft: solve this riddle 🗿🗿🗿

[CostaCostaCosta]

Day 1: Called the cat. He didn't show up but could feel him ignoring me like a jerk.
Day 2: Put catnip on box 3.
Day 3: Check box 3. Just catnip.
Day 4: Check box 3. Still just catnip.
Day 5: Check box 3. Catnip is gone. Feel cat's smug smirk.
Day 6: Jump on box 5. It was empty. Shame.
Day 7: Check box 2. Found some catnip leftovers.
Day 8: Check box 2 again and decide to smoke the catnip.
Day 9: Drench all the boxes with gasoline, set them on fire. No cat.
Night 9: Wake up in my room with the cat looming over my head holding a kitchen knife.
Day 8: Had a bad trip.
Day 9: Sell the boxes, buy dog food, adopt a puppy from a shelter called Nimoy.
Day 10: Nimoy is the best puppy in the world.
Day 11: Nimoy talks to me saying something about kibbles.
Day 8: Still tripping yarn balls.
Day 9: Wished I could remember that youtube video about this exact scenario.
Da

[matthiasrupp]

Day 1: put sand all over the place
Day 2: follow footprints

[collinbeal]

I got the limitations of where the cat has to move if in an odd box, but couldn't formulate the specific search pattern to exploit it because I got too caught up on trying to make the search consistent for any result rather than narrowing the search based on an assumption and using that to force the cat to fit the assumption. It requires you to put the cart before the horse, or the box before the cat in this instance, which is very unintuitive. Pretty clever

[KnakuanaRka]

I saw a near-identical puzzle on Ted-Ed (“Can you solve the seven planets riddle?”) before, so doing the same thing here is pretty trivial. First, think about the parity of the boxes.
Each night, the cat moves either from an odd box to an even one, or the other way around, so you can consider them separately.
First look at the case where it starts in an even box. On the first night, check box 2; if it isn’t there, it must have been in box 4, and moved to either 3 or 5. Since 3 leaves more possibilities open than 5, check 3. If it isn’t there, it must have been at 5, where it can only move to 4 to be discovered the next night.
Now what if it started in an odd box? If you did the three previous checks and didn’t discover it, it must have started in an odd box. Since you checked the boxes three times, it has moved three times, from odd to even to odd to even again; since you know it’s in an even box, you can just check 2-3-4 again, and are guaranteed to discover it.