Amazon Interview Question: one question is to find a pat... | Glassdoor

Interview Question

Software Development Engineer Intern Interview

one question is to find a path in a maze

technical, algorithm

Interview Answer

1 Answer


This is a graph algorithm. Having seen other intern questions, this one looks unfairly difficult for intern level.

To find the path, model each intersection as a vertex in an undirected graph. Every line between two intersections would then represent and edge. To prevent against traversing the same path again, mark every vertex (i.e. intersection) as visited as you go. The algo will be depth-first search or breadth-first search. DFS is given below.

Vertex Find(Graph g, int val)
   Stack stack = new Stack();

   g[0].Visited = true;

  while(stack.Count >0)

Vertex v = stack.Pop();

return v;


foreach(Vertex n in v.Neighbours)

n.Visited = true;



return null;

Tiger on Feb 9, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.