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.

- DS January 20, 2014 | Flag Reply
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;
}

- Nit January 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Guy January 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- DS January 20, 2014 | Flag
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

- Dave January 20, 2014 | Flag Reply
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.

- mo February 08, 2014 | Flag Reply
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.

- Anonymous February 17, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More