GT
BAN USER
Comments (4)
Reputation 15
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
2
of 2 vote
"Integer array with dimensions M and N" is a matrix so can be assimilated to a Graph (G).
1. 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).
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Correct me if I am wrong, I think the running time is not O(n*(log(n)), but it's O(m*(log(n)) where m is all your TimeSlots and n all the TimeSlots of your friends.
- GT March 17, 2015But it's just a detail.