I've always been a big believer in technical interviews that really test a candidate's knowledge. I don't believe you can get a good understanding of someone's technical abilities any other way.
Recently I had just such an interview where I was asked a fantastic technical question. Actually, it wasn't an interview as such, but a test. I went in, sat a written test and went home. I didn't even have the chance to speak to anyone until I had proven my technical ability on their test.
Personally I think that's a little harsh, but I guess it's effective. Why waste time interviewing someone unless you're sure they have the skills to do the job?
In fact, I've been in that situation before. I was interviewing a candidate who had a fantastic CV, but 10 minutes into the interview he'd already said enough stupid things to convince my colleague and I that he was clueless. But despite that, we still had to continue with the interview knowing full well that it was a complete waste of everyone's time.
Anyway, back to the interview question...
The task was to write a program (on paper) to solve a maze. Given a representation of a maze, the program simply had to return a boolean value indicating whether the maze could be solved.
Consider the following diagram. The starting point of the maze is the top left-hand corner and the goal is to travel through the maze, square by square, to the bottom right-hand corner. You can only move to squares that contain a 1, and you can only move up, down, left and right (diagonal is not allowed).
| 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
The highlighted path in the maze above is the valid path through the maze.
Note that a maze would typically have a number of dead ends making it more difficult to solve, and could potentially have more than one valid path to the finish. A more typical maze is shown below.
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
From the program's point of view, the maze was represented as an array of integers, as well as the width and height of the maze. For example:
int[] maze = { 1, 0, 0, 1, 1, 0, 1, 1, 1 };
int width = 3;
int height = 3;
Represents the following maze:
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
Assuming a basic x, y coordinate system with (0, 0) being the top-left hand corner and (2, 2) being the bottom right-hand corner, finding the value at a given position in the maze can be determined as follows:
int value = maze[(y*width)+x];
So that's it! You have a pen and paper, and one hour - go write a program that accepts those parameters and determines whether the maze is solvable.
Believe me, with only a pen and paper this is HARD!
NOTE: If you want to have a go at this yourself then I suggest you stop reading now and come back when you're done.
Here's the solution I came up with. I've cleaned things up a little, but the program is essentially the same as the one I frantically scrawled on paper in my interview. My solution had to be written in Java.
First of all, here's the basic algorithm I came up with.
"Starting at position (0,0) in the maze, find all adjacent squares containing a 1 that have not already been moved to. For each of these square, attempt to recursively solve the maze from that position."
My first class was a simple utility class to represent a coordinate within the maze. Nothing too exciting here:
public class Coordinate {
private int x;
private int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public boolean equals(Object other) {
if (!(other instanceof Coordinate)) {
return false;
}
Coordinate c = (Coordinate) other;
return (c.x == this.x && c.y == this.y);
}
}
Next up was the class to actually solve the maze. The comments pretty much explain everything.
public class Solver {
// the details of the maze
private int[] maze;
private int width;
private int height;
// a list of visited coordinates
private List<Coordinate> visited = new ArrayList<Coordinate>();
/**
* Create a new maze solver.
*
* @param maze the maze to be solved.
* @param width the width of the maze.
* @param height the height of the maze.
*/
public Solver(int[] maze, int width, int height) {
// is the maze valid?
if (maze.length != (width * height)) {
throw new IllegalArgumentException("Illegal maze arguments.");
}
this.maze = maze;
this.width = width;
this.height = height;
}
/**
* Determine whether the maze can be solved.
*
* @return a boolean indicating whether the maze can be solved.
*/
public boolean canSolve() {
// start solving recursively from the start position
return canSolve(new Coordinate(0, 0));
}
/**
* Given a position, determine whether the maze can be solved from there.
*
* @param position the current position in the maze.
* @return a boolean indicating whether the maze can be solved.
*/
private boolean canSolve(Coordinate position) {
visited.add(position);
// have we reached the end of the maze?
if ((position.getX() == width-1) && (position.getY() == height-1)) {
return true;
}
// recurse for each adjacent coordinate
List<Coordinate> adjacent = getAdjacent(position);
for (Coordinate coordinate : adjacent) {
if(canSolve(coordinate)) {
return true;
}
}
// if we make it to here then the maze is unsolvable :(
return false;
}
/**
* Get a list of all adjacent coordinates in the maze that can be moved to
* from the given coordinate. An adjacent coordinate can only be moved to
* if it contains a '1' and if it is above, below, left or right of the
* given coordinate and hasn't yet been visited yet.
*
* @param position the position in the maze.
* @return a list of adjacent coordinates that can be moved to.
*/
private List<Coordinate> getAdjacent(Coordinate position) {
List<Coordinate> adjacent = new ArrayList<Coordinate>();
int x = position.getX();
int y = position.getY();
// create a list of potential adjacent coordinates
Coordinate[] potentialCoordinates = {
new Coordinate(x-1, y), // left
new Coordinate(x+1, y), // right
new Coordinate(x, y-1), // above
new Coordinate(x, y+1) // below
};
// only return unvisited adjacent coordinates containing a '1'
for (int i = 0; i < potentialCoordinates.length; i++) {
Coordinate c = potentialCoordinates[i];
if (!visited.contains(c) && getValueAt(c) == 1) {
adjacent.add(c);
}
}
return adjacent;
}
/**
* Get the value at the given coordinate in the maze.
*
* @param c the cordinate to get the value at.
* @return the value at the given position, or -1 if the position is invalid.
*/
private int getValueAt(Coordinate c) {
int x = c.getX();
int y = c.getY();
// only return the value from the maze if the given position is valid
if (x >= 0 && y >= 0 && x < width && y < height) {
return maze[(y*width)+x];
} else {
return -1;
}
}
}
And that's it really. Calling it is pretty straight forward.
int[] maze = {
1, 0, 0, 0, 0,
1, 0, 1, 1, 1,
1, 0, 1, 0, 1,
1, 0, 1, 0, 1,
1, 1, 1, 0, 1
};
Solver solver = new Solver(maze, 5, 5);
System.out.println(solver.canSolve());
I'm sure there's a much more elegant way to solve this using some fancy matrix mathematics, but I was pretty happy with this solution. The complete source code is available here
Send me an email if you have a better solution.