Interview Question: The Mouse

I have a favorite interview question that I've been using over the last year.  It's time to get a new one, so I thought I'd share it with you all.  If you are not a Microsoft employee you might not be familiar with the interview process, but most technical positions involve a series of separate interviews where each interviewer will ask you to solve at least one problem relevant to your skill set. 

Of course, since I'm a developer, I ask people programming questions.  Finding an applicable solution to this problem should not be too difficult to most of you code slingers out there, but give it a try anyway since its fun.

The Setup

You are being asked to write the algorithm/software for a robotic mouse that needs to navigate a maze in order to find some cheese.  There are computing resources available, as wells as a modern programming language to develop your solution.   I'll describe the problem using C# but you may choose any common programming language.  The maze exists as a regular grid of squarish cells, potentially bordered on each side by a wall that prevents movement in that direction.  In one of these cells is the cheese, and in another is the mouse.  Neither location is known at the start of the search.

The interface you have by which to control the mouse is rather limited.   It has one function that moves the mouse in a cardinal direction, returning true/false depending on whether the move was successful or not, and another function that returns true if the cheese is actually in the mouse's current cell.

public interface IMouse {
   bool Move(Direction d);
   bool IsCheeseHere();

public enum Direction {

Things to note:   The mouse is intended to be a physical mouse that must be moved via this interface.  The software is required to move the mouse to the cheese and then halt.  You may ignore the physical uncertainties of actual movement and assume that each successful move moves the mouse into the center of the adjacent cell, and each unsuccessful moves leave the mouse in its position.  You may also assume the maze to be limited to some reasonable size, at most 100x100 cells, and it is actually possible for the  mouse to reach the cheese.

Have fun an send me your solutions via the 'Contact Me' feature.   I'll post the best solutions next week.   You may also ask me questions using the comments below.


Comments (23)

  1. Kris Gray says:

    IMouse xMouse = new Mousey(); <BR>Direction previousDirection; <BR>bool bMoved; <BR><BR>while(!xMouse.IsCheeseHere()) { <BR><BR>for(int c=0;c&lt;4, c++) { <BR>bMoved = false; <BR>if((Direction)c == previousDirection) <BR>continue; //— Lets not go back the way we came just yet. <BR><BR>if(xMouse.Move((Direction)c)) { <BR>previousDirection = (Direction)c; <BR>bMoved = true; <BR>break; //— Stop moving over the 4 directions. <BR>} <BR>} <BR><BR>if(bMoved == false) <BR>xMouse.Move(previousDirection); <BR><BR>if(previousDirection == Direction.North) <BR>previousDirection = Direction.South; <BR><BR>if(previousDirection == Direction.South) <BR>previousDirection = Direction.North; <BR><BR>//— Flip Flow East and West same way, to prevent the mouse from going back from where he just came and getting stuck again. <BR><BR><BR>} //— Go back to the while and see if the cheese is found. <BR><BR>if(xMouse.IsCheeseHere())//— Merely a formality. <BR>{ <BR>Response.Write("We know we found the cheese"); <BR>} <BR><BR>/* <BR>I’d like to spend more time on it, but I should probably get back to work. <BR><BR>*/ <BR>

  2. BradC says:

    What’s the "best" solution?

    Fastest to find the cheese?

    Shortest code?

    Most elegant?

    Mouse that acts most like a ballet dancer? 🙂

  3. Matt Warren says:

    Good Question. First of all, the solution has to be guaranteed to succeed, given that the mouse and cheese are not in two topographically different areas to begin with. (I should alter the description to rule that out.)

    After that, its pretty much up to me. So most elegant or most efficient. Maybe I’ll have multiple categories of best, if I get a lot of replies.

    If you’ve actually got a ballet dancer solution, I’d love to see it. 🙂

  4. IMHO, BradC is headed in the right direction.

    Sure, these "toy" problems are fun and interesting, and can be useful to help sort the wheat from the chaff. But hopefully by the time someone is talking to you, it’s already been determined that they are a competent programmer.

    If you’re just looking for a programmer, then your test is appropriate to find the "best" programmer.

    However, a developer will ask the questions BradC started with – and more. (Everybody may use different words for "programmer" and "developer", but you catch my drift…)

    For example, there may already be a MazeSolver object/library "out there", heck, it might be even burried in some corner of .NET 2.0. The most bug-free code is that which is never written.

  5. Matt Warren says:

    Fortunately, that’s not the way it works here either. Finding a correct solution to the problem is not the end goal. In an interview I assume you can do that. What is more important to me as an interviewer is what I learn about you as you attempt to solve it. Like, do you communicate well. Do you test your assumptions? Do you have any assumptions? Do you believe in your solution? Can you apply what you’ve just learned to a follow up question/scenario? Do you identify the full problem before plunging into the deep end? Are you able to back out of a dead end? Do you recognize when you are at a dead end?

    Still, the problems are fun to think about, and that’s why I’ve posted it here. I’m not interviewing any of you, and none of you a constrained to standing at my whiteboard sweating bullets.

  6. RichB says:

    Is it possible for cells to be completely unreachable? ie bounded on all sides by a wall?

  7. Matt Warren says:

    Rich, it may be possible, but the region the mouse is in is also the same region the cheese is in. There is a path between the two.

  8. RichB says:

    Your description of walls is a little implicit. If a wall exists moving east from cell a to cell b, is there also a wall moving west from cell b to cell a? ie are walls communtative? Put another way – are one-way walls allowed?

  9. Matt Warren says:

    No one-way walls are allowed. It’s supposed to be a real physical maze and you are writing the algorithm for an actual robotic mouse.

  10. Vlad Ivanov says:

    Your task has a problem in it: without an ability to drop a beakon at the start position – depending on a configuration of the maze – you have a definite chance to walk in a circle indefinetely.

  11. Eddie Garmon says:

    I wrote code for an actual robot mouse we built in one of my senior EE classes in college (in assembler). Man this question brings back memories… maybe i’ll look at a c# rewrite. but first some questions:

    1 – Can the mouse physically "see" all four walls around me without having to try and walk in that direction? We had multiple IR LEDs and sensors to determine possible next steps before going there, as well as to keep us in the middle of the square. This helps cut down on the number of exploratory backtracks before actually making the move that you want.

    2 – How much memory is available in the computing resources? is the mouse dumb with only 512bytes of memory, or are they an evil genious with 1GB memory? This affects the memory structure that he mouse uses to remember the current state of the maze and paths traveled.

    3 – Will the walls of the maze ever move on us while we are in there?

  12. Matt Warren says:

    Vlad, you are correct. All these interview question programming problems have ‘problems’ embedded in them. There lies the fun. Your task is to find a solution.

  13. Matt Warren says:


    1) The mouse is blind. It only knows about a wall when it runs into it.

    2) Consider the machine resources unbound. Though, ludicrous use of machine resources won’t lead you to an elegant solution.

    3) The walls will never move.

  14. Vlad Ivanov says:


    – Does a cell *always* have at least one wall? Or can cheese be located in a middle of a large room composed of number of cells without walls?

    – Is it a rectangular-shaped maze?

  15. Matt Warren says:

    Vlad, it is entirely possible that cells may exist with no walls at all, or even large unbounded regions of cells.

  16. 1) What’s the mouses motivation?

    2) What kind of cheese is in the maze?

    3) Will the cheese go bad over time?

    4) What is the life of the battery in the robotic mouse?

    5) Is the mouse and maze on Mars?

    6) What would a robotic mouse want with cheese?

  17. Since this isn’t an actual interview, is the goal here to produce the most technically elegant solution to the problem as stated, or are you still looking for solutions that address issues outside the scope of the question as stated? To pick one arbitrary example, would you lose points for failing to include unit tests?

    Essentially I guess I’m asking whether this is a "pure programming ingenuity" challenge or a "well-rounded programmer for real world situations" one?

  18. Matt Warren says:

    Stuart, I’m just looking for a correct algorithm. If you want to submit other things that’s okay too. Some people have also submitted implementations of IMouse and a harness that runs their solution against it.

  19. rolfliu says:

    use a stack to solve this problem.

    Each time the mouse tries to move, it has to know and remember the direction, one of the four choices. If it can move, push the previous location and next possilble direction. So, when there is a problem at some stage and no further move can be made, it will return to the previous location and try other directions. In that case, it pop up the stack.

    the mouse can try all the ways out and will definitely find the cheese and eat it.

Skip to main content