Interview Question

Interview

one question is to find a path in a maze

Tags:
technical, algorithm
Answer

Interview Answer

1 Answer

0

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<Vertex> stack = new Stack<Vertex>(); g[0].Visited = true; stack.Push(g[0]); while(stack.Count >0) { Vertex v = stack.Pop(); if(v.Data==val) { return v; } foreach(Vertex n in v.Neighbours) { n.Visited = true; stack.Push(n); } } return null; }

Tiger on Feb 9, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.