Interview Question
Software EngineersCountry: United States
Interview Type: Written Test
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.
"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).