Amazon.com

www.amazon.com
Engaged Employer

Interview Question

Software Development Engineer Interview Seattle, WA

"Solve a maze", you have a 2D matrix with 1's as blocked

and 0's as path. Find a path from one corner to another, backtracking should be allowed.

1

Might be a little sloppy, but it works.

public static int solveMaze(int[][] maze, int i, int j, int oldi, int oldj) {
int solved = 0;
if((i+1) == maze.length && (j+1) == maze[i].length) {
return 1;
}

if((j-1) >= 0 && (j-1) != oldj && maze[i][j-1] == 0) {
solved = solveMaze(maze, i, j-1, i, j);
} if(solved != 1 && (i-1) >= 0 && (i-1) != oldi && maze[i-1][j] == 0) {
solved = solveMaze(maze, i-1, j, i, j);
} if(solved != 1 && (j+1) < maze[i].length && (j+1) != oldj && maze[i][j+1] == 0) {
solved = solveMaze(maze, i, j+1, i, j);
} if(solved != 1 && (i+1) < maze.length && (i+1) != oldi && maze[i+1][j] == 0) {
solved = solveMaze(maze, i+1, j, i, j);
}
return solved;
}

Curtis on Jan 27, 2012
0

Here is the maze.

1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 0 0 1
0 0 1 0 1 0 1 1 1 1 0 1
1 1 1 0 1 0 0 0 0 1 0 1
1 0 0 0 0 1 1 1 0 1 0 1
1 1 1 1 0 1 F 1 0 1 0 1
1 0 0 1 0 1 0 1 0 1 0 1
1 1 0 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 1 0 1
1 1 1 1 1 1 0 1 1 1 0 1
1 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1

public class MazePath {

char[][] maze = new char[12][12];

// Define the starting point and endpoint in a node.
Node startingPoint = new Node(1,1);
Node endPoint = new Node(10,10);

Map<Node,Node> hm = new HashMap<Node,Node>();

public void createArray() throws IOException{
// read maze from a file and create an array
FileInputStream in = new FileInputStream("c:/Personal/Maze.txt");
String strLine;
for(int j = 0; j<maze.length; j++)
{
}

System.out.println(maze[2][0]);
}

hm.put(startingPoint, startingPoint);

while(!queue.isEmpty()){
Node n = queue.poll();
if(n.equals(endPoint)){
printPathUsingParent(n);
break;
}
}

}

public void printPathUsingParent(Node destination){

Node current = destination;
while(current.parentNode!=null){
System.out.println(current.toString());
current = current.parentNode;
}

System.out.println(current.toString());
}

Node v1 =v;
int row = v1.row;
int column=v1.column;

//check if any point exist in the top side and add it in the Queue
if(v1.row!=0 ){
if(convertCharToInt(maze[row-1][column])==0 ){
Node top = new Node(row-1,column);

if(!hm.containsKey(top)){

}
}
}

// check point in the bottom and add it int he queue
if(v1.row!=maze.length){
if(convertCharToInt(maze[row+1][column])==0){
Node bottom = new Node(row+1,column);
if(!hm.containsKey(bottom)){
}
}
}

// check point in the right and add

if(v1.column!=maze[1].length){
if(convertCharToInt(maze[row][column+1])==0){
Node right = new Node(row,column+1);
if(!hm.containsKey(right)){
}
}
}

// check point in the left and add.
if(v1.column!=0){
if(convertCharToInt(maze[row][column-1])==0){
Node left = new Node(row,column-1);
if(!hm.containsKey(left)){

}
}
}

}

public int convertCharToInt(char c){
return Character.getNumericValue(c);
}

v.setParentNode(parentNode);
hm.put(v, v);

}

public static void main(String [] args) throws IOException
{
MazePath mp = new MazePath();
mp.createArray();
// mp.findPathDepthFirt();
}
}

Anand on Jan 31, 2012
0

My previous answer was an implementation and here brief description on the implementation.

* 1) Read a maze from file and convert into a int[][] array.
* 2) Declare starting point and end point
* 3) declare Queue and add startingPoint in that queue.
* 4) Deque the node from Queue and find all the possible path add it in the queue again.
* 5) Each Node contains a reference to their parent Node. Starting point doesn't contains any reference to the parent node.
* 6) While dequeing a node, if it matches with endpoint then traverse back to the starting point and that's the path of the maze.
* 7) To avoid duplicate traversing, create a visited=true flag or use HashMap.
*
* hm.put(startingPoint, startingPoint);
while(!queue.isEmpty()){
Node n = queue.poll();
if(n.equals(endPoint)){
printPathUsingParent(n);
break;
}
}
*/

Anonymous on Jan 31, 2012
1

Here is a concept that may works, starting from the beginning point, each step could lead to possibly three path, we can draw a tree which each node has three children (max), then find the longest path would do it, each dead end will determine if the current node has any child or not.

needajob on Feb 1, 2012
1

enter the maze into a graph data structure where adjacent 0's are connected to each other with an edge. Label the starting and ending points, and do a DFS from the starting location.

This would be an internal solution, as there would be no visual representation of it, but you could easily enough attach coordinates to each node to allow for a visual solution

PC on Feb 14, 2012
0

A* Algorithm

Wikipedia has a nice animated image to describe it

Anonymous on Jan 19, 2013