Interview Question Software Engineers
Country: United States
Interview Type: Written Test
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
So your answer is pretty close, but your BFS does not guarantee shortest path (only a path). Instead of a simple BFS, use Dijkstra's algorithm with P as the source. Like you said, maintain the parents in a hashmap or array of some sort and then ascend through the parents starting with Q's parent to determine the shortest path.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
"Integer array with dimensions M and N" is a matrix so can be assimilated to a Graph (G).
- GT March 16, 20151. Use BFS, with P as entry vertex and stop when you find Q. During this phase, keep a track of the parents of each vertex. (may a HashMap<Vertex,Parent>)
2. Starting from Q, ascend all the parents until P adding one parent by one to a List.
Time complexity O(Vertices+Edges) + O(Depth of G).
Space complexity : O(Vertices) + O(Depth of G).