How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle

Video quality	The size	Download

Information How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle

Title	:	How To Solve The Hiding Cat Puzzle - Microsoft Interview Riddle
Lasting	:	13.37
Date of publication	:
Views	:	2,4 jt

Editorial note: I started working on this problem 1 month ago Completely independently Alex Bellos at The Guardian posted the 7 door version, using a cat behind a door ( wwwtheguardiancom/science/2017/jul/03/did-you-solve-it-are-you-smarter-than-a-cat) If you read that, sorry the puzzle is spoiled It's a coincidence we both used cats; I had already finished my video and post before he posted his puzzle But hopefully you'll like my video presentation and comprehensive solution of n doors
Comment from : MindYourDecisions

Plot twist:you don’t want a cat jumping on you
Comment from : Ivy

Schroedinger's solution: As long as you don't look, the cat is in the even and in the odd numbered boxes simultaneously
Comment from : radastir

imagine you, bright young man, solving this puzzle with ease just to spend 10 years writing error messages for windows system failures
Comment from : kazkas kito baisaus

Paradox, Conundrum, Logic, Interesting Math

This is a very good puzzle It tricked me by appearing to have no special asymmetry except at the endpoints The last thing I suspected was the possibility of dividing it into cases by odd and even
Comment from : Paradox, Conundrum, Logic, Interesting Math

After you find the cat you squish that cat
Comment from : Aaron Fonseca

With the 5 boxes you could find it by doing 2 ,2 , 4 , 4 , 3 , 2 and always find it
Comment from : Daniel Adorjan

lol why did I think boxes stay open
Comment from : I M

2,2,3,4,4 solves it in 5 moves?
Comment from : Wayne Cammidge

What if the boxes are on a circle ?
Comment from : Andre Antunes

Day 1 : 3brDay 2: 4brDay 3: 4brDay 4 : 4brDay 5 : 3brDay 6 : 2brbrDay 1 : 3brDay 2: 2brDay 3 : 2brDay 4 : 2brDay 5: 3brDay 6 : 2brbrEither was day 5 it has to be in day 3 brPlease correct if I am wrong
Comment from : Fahmeeda

The real question is that, until you open the right box, is the cat dead or alive (or both)?
Comment from : Blue Sun

This is just theoretical assumption in reality if their are n number of boxes you cant find out until cat sense smell of fish 🐠💀
Comment from : galib ki yaadein

These all seem to be suboptimal You have to keep track of probabilities for an optimal solution
Comment from : Mega Upstairs

2
Comment from : Geok Wiew Chua

I remember seeing this question in highschool, but it was with a mole and it's holes instead I didn't get how to solve it but my friend did and I wrote the code to solve it
Comment from : Arky

Alternate solution:brstep1: "pspspsp"brstep2: ???brstep3: profit
Comment from : Bence Patus

Reminds me of roaming legendaries in Pokemon
Comment from : CubeBizz

So basically we have solution for even numer starting box and when it fails it means that cat started in odd number and it's only information we need to solve it again using even starting box solution
Comment from : Gniewomir Ciołek

Is it possible to find an equation for this in 2-Dimensions? Instead of the boxes being in a line, they could be on a 2-D plane
Comment from : Mihai Mihalca

Cats always win the game or you need more training
Comment from : Tara Joyce

Precisely,think outside the box: Just open the sixth box, the great one i mean:" THE FOOD BOX!" And suddendly the cat appears Shroedinger never tried this He should have
Comment from : Daniel DEROUDILHES

Save your brain and just use cheese or sausages 🙂
Comment from : julietgn

I came up with a less efficient onebrBasically alternating between 4 and 2 each one twice in a row However occasionally pick the middlelike this or its reverse (instead of 4 first, 2 first):br4-4-2-2-4-4-3-2-2-3-4brbrI like how the efficient and true solution is similar to the thinking of solving even and odd rubiks cubes
Comment from : Read 譯Jordan 文達

You need to explain it better at the moment beginning, I thought that when I searched the box, it would not be available anymore for the cat to hide
Comment from : Diego Campos Vaz dos Santos

I solved slightly differently, I think mine is less effecient but still valid Does someone see a problem with it?brbrSweep down from 1 to 5, if you find him he started in an odd box, if you don't find him he is now in an odd box,brSweep down for a second time from 1 to 4 and you are guaranteed to find himbrbrGeneraliezs to when n is odd, when n is even preform the first sweep, he is now on an even number, pick 1, he is now on an odd, preform the second sweep and you find him!brbrThere is probably a way to cut down on the number of days it takes but this seems good enough for now
Comment from : Marks Music

How much time do you have for this problem?
Comment from : TechnoFeeling

My solution for 5 boxes: brbr3, 2, 2, 3, 3, 4, 4, 4, 2brbrFor 4 boxes:brbr2, 2, 3, 3, 2brbrBasically trying to corner the cat to the most left or right, picking the same box twice next to the corner boxes makes it possible to deduce the location of the cat
Comment from : Itachi Uchiha

just listen for the cat bro, It's ez
Comment from : Thug gaming bro

Did anyone try pspspsps?
Comment from : Stephanie Revers

can this be done in one step less by choosing 2-2-3-4-4
Comment from : Brent Patrick

2,2,3,4,5,n-1 (half of your solution)
Comment from : Rudolph Tjaden

The arrows pointing in both directions are misleading, making me think the cat can move from 1 to 5 and from 5 to 1 as well
Comment from : Roxterat

I'd like this one better if the behavior at the endpoints was more explicit and it made clear we're concerned w/ adversarial worst case vs random average case 1 attempting to move left could plausibly either loop to n (modular), remain in place (attempted to move but failed to; position clamped), or move right b/c only legal move is forced Not immediately obvious the cat is avoiding being caught vs taking a random walk If the cat is taking a random walk and the boxes don't loop, I think your best average case is just guess the middle box repeatedly
Comment from : FireStormOOO

443322 - corner it!
Comment from : Lyle Cohen

234234
Comment from : Sp T

I took it too seriously and found out 1 2 2 3 3 2 3 4 4 3 3 2 2 works on 5 boxes aswell
Comment from : Syrlic11

About 5 seconds in, I realized this was litterally just Ted Eds planets puzzle xDbrbrSearch 33 22 33 44
Comment from : Fritzafella

This kind of thing causes a lot of stress for your cat
Comment from : Rich Williams

222432 wonder if its a special numberbredit: Dont search its g*y
Comment from : Braskcov Roldinin

While it's claimed that this question is asked in interviews at tech companies, I wonder if this (level of) question is also asked ones applying for management jobs
Comment from : Dirk P

isn't the cat in either box 2 or 4 on day 2?brbrso why go through the hassle of day 3 and 4 to get back to day 2 situation?
Comment from : Tab 5e

You’re making an awful lot of work out of this I can think of two solutions that don’t involve math One solution is pick up each box The heaviest one has the cat in it, so I open that one Another solution is to open a different box each day and leave it open Eventually, I’ll be able to see the cat, so I choose that box
Comment from : Daniel White

Why cant we go number wise check 1 on first day 2 on second and so on
Comment from : Aaditya Shukla

on day 1, cat can be in box1
Comment from : Russell Mok

could you find the cat by checking boxes 2, 2, 3, 3, 4, 4? I think that should work no matter where the cat is
Comment from : Aidin

Cat starts at boxes 5 or 1 and you'll never catch it that way 😂br1: 2-1, 3-2,4-3, etcbr4: 2-5, 3-4, 4-3/5, etc 😅
Comment from : Salariel Daemon

For the 5 box version, I came up with a 7 day strategy
Comment from : Clark Fennimore

If a company wants me to think like that, I don’t want to work there
Comment from : Grizzy B

Even tho random technically doesn't guarantee catching it, probably of failure is actually zero, what leads to the question, is better to try random (on average) vs following this, it would require calculating the expected value of both algorithms
Comment from : Gabriel Barrantes

why not 2, 2, 3, 3, 4, 4?
Comment from : Joseph Trutch

3,3,2,3,5 surely saves a move?
Comment from : Adam Omari

Shake each box and see which one meows
Comment from : SleepyShep

I think you could also do this, by checking each box starting from 1 twice, right? also, the fastest way is to remove the box each time you checked it:)
Comment from : Yura Skrynnykov

I didn’t think about it like odd and even numbers I approached it like cornering the cat My solution is to open the boxes like so: 2-2-3-4 That will guarantee finding the cat at the 4th try at the latest I didn’t do any calculations or so, so it might be wrong, but it feels right
Comment from : RedBeardRichard

Micrösofts cat
Comment from : Kamron Gregson

No, your algorithm doesn´t cover all possibilities If the cat starts 3 boxes from you on the first day and you use the described pattern, the cat can escape indefinitely
Comment from : Sonja

"Suppose the cat is in an even numbered box", posits the obvious non cat owner :)
Comment from : Snik Snoodle

I would just interview over and over until I guessed right the first try
Comment from : Daniel Robbins

Cats prefer small boxes brPick the box that is a just bit to small for the cat, and it will be there
Comment from : Michael Mortensen

Just put the boxes in water When the meowing and clawing stops, you’ve found the cat!
Comment from : Patrick

Day 1 - box 1brDay 2 - box 1brDay 3 - box 2brDay 4 - box 3brDay 5 - box 4brDay 6 - box 5brbrDone and easier
Comment from : Caio Ricardo Alves Pereira de Moraes

@329 can anyone explain why the cat couldnt move from box 2 to box 1??
Comment from : MrPanz3r

I don't know if anyone wrote this, and I assume that I may be looking at this wrong, but I think you overcomplicated the solution:brDay 1 :brYou open box 3 (if the cat is in box 3 you win) If not he either is in box 1,2,4 or 5brDay 2 :brIf on the first day the cat was in box 1 or 5 - Open box 2 or 4 respectively and you find the catbrIf on the first day the cat was in box 2 or 4 - Open 3 again He either moved to box 3 and you find him or he moved to 1 or 5brDay 3:brIf you didn't find him yet he is for sure in box 2 or 4, depending on the box that moved on day 2 (box 1 or 5 respectively)brbrSame logic applies with 4 boxes
Comment from : umacenaqqparaencher

This was a tricky one My solution for n boxes is slightly different, but I believe it still works I solved it by realizing that the cat is stuck in a sort of pattern of two states, between even and odd boxes You can start by chasing the cat to the end of the row in which case it will have to turn around Yes, you might miss it on the first go around, but you will catch it on the second one All you have to do is make sure you take an odd number of steps before restarting, so now you are 'in sync' with the cat's 2 step cadence So for even instances of n, you just have to repeat n-1 for one more day For 6 boxes it would be 2,3,4,5,5,2,3,4,5,5
Comment from : Milano

I think my strategy to find the cat is to *kick each box until i hear it meow*…
Comment from : Bakr Babli

This sound like bullshtt you can literally make it sound another way toobrIt just depends how you problem solve
Comment from : Happopolous

After getting the puzzle, before seeing the solution:brMy first thought is 6: 2, 3, 4, 2, 3, 4brThe first three can catch any cat starting in 2 or 4, the last three any starting in 1, 3 or 5brFor n boxes, this generalises; we can catch any even box cat in slightly less than 2n checksbrHowever, this can probably be optimised further; I just don't see howbrEDIT: Oh no, apparently that is optimal Easier than I thought I didn't worry about the details for the n case, I suspected it would be 2(n-2) but didn't want to think about it :-P
Comment from : Pepijn dM

I did it a bit longer in 11 moves but I got there
Comment from : Electric Ninja

Just don't feed it for a day, the cat will find you
Comment from : Mort OOPz

I won on the first day the location of the Cat would be in box 2 or 4 and 2 is the best option
Comment from : xaero76

I had 4,4,4,3,3,2,2 so not as efficient as the answer, especially as it scales
Comment from : Pyornkrachzark

Could someone by any chance give me a hint why 2,2,3,3,4,4 would be incorrect?
Comment from : Green Exclusive

I would chase the cat, check 1, 2, 3 n brSimple and easy
Comment from : MrJamesman5000

just go into the room and crack a cat food can That's like the "quantum computing" solution
Comment from : Thug Lincoln

oh my god wrong is this a troll video?brif you said this to me in an interview you would be disqualified/fired brbrif you work at microsoft already and came up with this, no wonder they have constant outages and release features like vtubers for corporate teams meetings and you think electron is the greatest tool of all time brbryou’re dealing with a living creature a cat cats don’t have rules they have general guideline trends your question demonstrates a complete lack of understanding of reality or empathy just to start brbrthis is like when microsoft keeps releasing features that’s just an entire new row of a toolbar for every program but half the buttons just link to outlook and you can’t remove it because somehow it’s a core dependency of windows brbrboxes in a line on a spherical plane (earth) are all adjacent there’s just a slightly bigger gap between box 5 and 1 so you can’t “pick the middle one” or “tap it in the end” This shows you lack a fundamental key understanding of 3D space, reality, and communication bryour array of boxes could also be the size of continents on earth just follow the stampeding or setup cameras brbror simply remove (make inaccessible) all but one box or leave milk to lure the cat out which solves the original problem of finding the cat brbror exploit the box cat rule to invent teleportation if the cat must always be in a box and there are no boxes, you will have summoned a box from the ether I doubt the original problem is truly a problem anymore brbrI know what the question was supposed to be but man was there absolutely no code review on this before slapping a r/showerthought spin on in and force pushing it to prod
Comment from : LeetHaxington

“At the start of day 4 the cat is in an even numbered box” this is correct but you literally showed day 2 being the same -_-
Comment from : average human (xichen)