Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
Result
[0,0]->[1,0]->[1,1]->[1,2]->[1,3]->[2,3]->[3,3]->[3,2]->[4,2]->[5,2]->[5,3]->[5,4]->[5,5]
This is a clear implementation of the problem.. self explanatory and beautifully written. Thank you!!
Nice solution. It is very important to write the problem on pen and paper before thinking in mind :-)
This is quite very big question to be asked in an interview.
Anyways, I'm giving you a rough idea. We need to keep one thing in mind while generating the maze, there must be a path in and out of the maze! so that it could be solved.
We represent a maze as a double dimension of integer values:
int maze[rows][cols];
We use only four bits of an integer in this 2D array. Each four bits represents the boundary presence at cel [i,j].
For example:
if maze[0][0] = 2; (i.e. 0010) it means west boundary of the cell is blocked, and east, west, south boundaries are open. (bit from left to right are in order east-north-west-south)
and if maze[0][0] = 3 (ie. 0011) it means west and south are blocked
Now, while generating the maze we need to enforce a condition that, if a wall in a cell is open then its opposite wall should also be open in order to have a valid path.
We can do it using:
enum DIR {
E(1<<0),N(1<<1),W(1<<2),S(1<<3)
int bit;
private DIR(int bit)
{
this.bit = bit;
}
int getBit(){
return this.bit;
}
};
DIR opposite(DIR d) {
if(d == DIR.E) return DIR.W;
if(d == DIR.N) return DIR.S;
if(d == DIR.S) return DIR.N;
if(d == DIR.W) return DIR.E;
}
Code for generating the maze:
int [][]getMaze(int rows, cols){
DIR dirs[4] = {DIR.N, DIR.E, DIR.W, DIR.S};
Collections.shuffle(Arrays.asList(dirs));
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
Collections.shuffle(Arrays.asList(dirs));
for(DIR d: dirs){
maze[i][j] |= d.getBit();
maze[i][j] |= opposite(d).getBit();
}
}
}
}
This should do the job.
The second part of the question is easy. Use a simple DFS with backtracking.
You actually don't need to worry about a data structure for the walls if you model the cells as vertexes and lack-of-walls as edges. Start from the starting cell, and then do a random walk to the ending cell, connecting adjacent cells with edges (which are essentially non-walls). Mark the cells that are already visited so that you don't have any cycles in your path. Then flesh out the tree by picking random vertexes on your tree and random walk a random length, again avoiding cells that have been already visited. Obviously, enforce the geometric constraint that you can only connect two cells that are horizontally or vertically adjacent. Stop once all cells have been visited (a simple count will suffice).
When it comes time to actually draw walls, look for adjacent cells, and if they don't have an edge between them, draw the wall.
But the underlying data structure is a tree. With the edges of the tree being explicit ways that you can get between two cells without crossing a wall and/or teleporting, it becomes very straightforward to solve the maze with a DFS.
A maze is just a set of Vertices (Intersection points) linked by weighted Edges (length of the corridor between two points) Find the exit of the maze is then a Dijsktra algorithm form your location to the exit Vertex.
Pros : less memory usage than a matrix, and your data structure is not linked to it's visual representation (You could create a maze with diagonal corridors for instance)
Solution in C that finds the first suitable path:
#include <stdio.h>
#include <stdlib.h>
typedef struct Pos
{
int x;
int y;
} Pos;
int allowed(int* maze, int width, int height, Pos* pos, Pos* path, int len)
{
if ( pos->x >= 0 && pos->y >= 0 &&
pos->x < width && pos->y < height
&& ! maze[pos->y * width + pos->x] )
{
int i = 0;
for ( ; i < len; ++i )
{
// Don't return on the same explored path.
if ( !memcmp(pos, &path[i], sizeof(Pos)) )
return 0;
}
return 1;
}
return 0;
}
int find(int* maze, int width, int height,
const Pos* start, const Pos* end,
Pos* path, int* pathIndex)
{
// End condition.
if ( start->x == end->x && start->y == end->y )
{
memcpy(&path[*pathIndex], start, sizeof(Pos));
(*pathIndex)++;
return 1;
}
memcpy(&path[*pathIndex], start, sizeof(Pos));
(*pathIndex)++;
int success = 0;
Pos newPos = { start->x, start->y - 1 };
if ( !success && allowed(maze, width, height, &newPos, path, *pathIndex) )
success = find(maze, width, height, &newPos, end, path, pathIndex);
newPos.x = start->x + 1;
newPos.y = start->y;
if ( !success && allowed(maze, width, height, &newPos, path, *pathIndex) )
success = find(maze, width, height, &newPos, end, path, pathIndex);
newPos.x = start->x;
newPos.y = start->y + 1;
if ( !success && allowed(maze, width, height, &newPos, path, *pathIndex) )
success = find(maze, width, height, &newPos, end, path, pathIndex);
newPos.x = start->x - 1;
newPos.y = start->y;
if ( !success && allowed(maze, width, height, &newPos, path, *pathIndex) )
success = find(maze, width, height, &newPos, end, path, pathIndex);
if ( ! success )
--*pathIndex;
return success;
}
void print(const Pos* path, int len)
{
int i = 0;
while ( i < len )
{
printf("(%d, %d) ", path[i].x, path[i].y);
++i;
}
printf("\n");
}
int main()
{
int maze[9] = { 0, 0, 0, 0, 1, 1, 0, 0, 0 };
Pos start = { 0, 0 };
Pos end = { 2, 2 };
Pos path[100];
int len = 0;
find(maze, 3, 3, &start, &end, path, &len);
print(path, len);
}
- skywalker42345678 March 05, 2013import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Stack; public class Maze { public static void main(String[] args) { //Use 2D array int[][] maze = new int[6][6]; maze[0] = new int[] { 1, 1, 0, 0, 0, 0 }; maze[1] = new int[] { 0, 1, 0, 0, 0, 0 }; maze[2] = new int[] { 0, 1, 0, 1, 1, 1 }; maze[3] = new int[] { 1, 1, 1, 1, 0, 1 }; maze[4] = new int[] { 0, 1, 0, 0, 0, 1 }; maze[5] = new int[] { 0, 1, 0, 0, 0, 1 }; //This is the start of exit point of maze Point start = new Point(0,0); Point exit = new Point(5,5); //DFS approach Stack<Point> s = new Stack<Point>(); s.push(start); Map<Point,Status> visited = new HashMap<Point,Status>(); visited.put(start, Status.VISITING); while(!s.isEmpty()){ Point currentP = s.peek(); boolean isAllVisited = true; for (Point p : getAdjacent(currentP.x, currentP.y)){ //It should be y and x, see above array if (visited.get(p)==null && maze[p.y][p.x]==1){ visited.put(p, Status.VISITING); isAllVisited = false ; s.push(p); if ( p.equals(exit)){ printPath(s); } break; } } if (isAllVisited){ visited.put(currentP, Status.VISITED); s.pop(); } } } private static void printPath(Stack<Point> s){ while (!s.isEmpty()){ System.out.print("->"); Point p = s.remove(0); System.out.format("[%d,%d]",p.x,p.y); } } private static List<Point> getAdjacent(int x, int y){ List<Point> result = new ArrayList<Point>(); //above point; if (y-1>=0) { result.add(new Point(x, y-1)); }; //right point; if (x+1<=5) { result.add(new Point(x+1, y)); }; //below point; if (y+1<=5) { result.add(new Point(x, y+1)); }; //left point; if (x-1>=0) { result.add(new Point(x-1, y)); }; return result; } private static class Point { int x, y; public Point(int x,int y) { this.x = x; this.y = y; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + x; result = prime * result + y; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Point other = (Point) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } } private static enum Status { UNVISITED, VISITING, VISITED }; }