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 { North, East, South, West}
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.
Matt
Comments
- Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
What's the "best" solution?
Fastest to find the cheese?
Shortest code?
Most elegant?
Mouse that acts most like a ballet dancer? :) - Anonymous
February 03, 2005
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. :-) - Anonymous
February 03, 2005
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. - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 03, 2005
Is it possible for cells to be completely unreachable? ie bounded on all sides by a wall? - Anonymous
February 03, 2005
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. - Anonymous
February 03, 2005
The comment has been removed - Anonymous
February 04, 2005
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. - Anonymous
February 04, 2005
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. - Anonymous
February 04, 2005
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? - Anonymous
February 04, 2005
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. - Anonymous
February 04, 2005
Eddie,
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. - Anonymous
February 04, 2005
Matt,
- 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? - Anonymous
February 04, 2005
Vlad, it is entirely possible that cells may exist with no walls at all, or even large unbounded regions of cells. - Anonymous
February 04, 2005
- 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?
- Anonymous
February 07, 2005
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? - Anonymous
February 07, 2005
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. - Anonymous
March 02, 2005
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.