Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x+1, y, sol) == true)
return true;
/* If x moving in x direction doesn't give solution then
Move down in y direction */
if (solveMazeUtil(maze, x, y+1, sol) == true)
return true;
/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
return false;
}
return false;
}
Use graph where vertices are in a matrix configuration.
Gen maze: pick a random out side vertex for the starting point, do a DFS to generate a path where the edge is picked at random, if the vertex is already discovered, pick another edge, if all edges have been discovered, DFS continues with another vertex, this way all vertices will be visited.
Solve: do a DFS until you get to the end, if dead end is reached, that part of the path is not part of the optimal path, DFS = shortest path
Maze falls under a graph G(V, E) problem which can be solved by Adjacency Matrix or Adjacency List. Adjacency Lists are preferred as most graphs are sparse by nature . As for traversing the graph, the important thing to note is that a DFS algorithm is typically solved using a Stack. The stack basically remembers all the visited nodes/vertex so that each node is visited only once.
I can see 2 options:
- DS January 20, 2014- a graph with each cell representing a node. This gives very easy way to setup walls (no connectivity between nodes), traps (some property of edges), etc. as well as base for solving the maze. As as side effect it doesn't restrict number of connections between cells, i.e. it could be hexagon based maze.
- a matrix with 4 bits representing ability to move in each direction. Same graph algorithms applied if the matrix is treated as connectivity matrix. The downside is that non-flat mazes (2D) could be harder to comprehend and cells must be uniform in shape, i.e. more bits that 4 maybe confusing and connection between cells of different shape could be hard to describe.