## Google Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

I can see 2 options:

- 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/* 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;
}``````

Comment hidden because of low score. Click to expand.
0

But we didn't use any data structure in this case.

Comment hidden because of low score. Click to expand.
0

The question was to design the maze, not to solve it...

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

All we need to do is to structure the maize as an adjacency list and do a simple BFS starting from the source. BFS will always return the shortest path from source to destination, in case of "unweighted" graphs.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.