Facebook Interview QuestionSoftware Engineer / Developers
- 0of 0 votes
Suppose you have a graph G(V,E).
You are supposed to find the shortest path from a vertex 's' to vertex 'e' for 'n' different cases.
In each case one of the edges 'Ei' (any one edge) of the graph will be blocked/deleted only for that case and we have to find the shortest path in the graph with that edge removed.
Guys finding the shortest path is easy. But how can I make the algo so fast that even if I remove one of the edges my algo should still be very fast. O(n log n) or faster.
Remember we are not deleting the edges permanently. We are just temporary removing one edge per case.
In each case only one edge is removed.
Suppose we blocked one edge E in one case. We have to find the shortest path for the graph.
In next case, we will reconnect the last edge and we will block/remove a new edge. And again for this new case we have to find the shortest path.
Another way of understanding the problem is suppose there are cities connected to each other.
And every day one of the roads gets blocked because of heavy rain. what is the shortest path every day from city s to e.
Also one more important thing to note that each road can be used only once.
But there could be more than 1 direct road from city a to city b.
FInd the shortest path distance from city s to e on a day when all direct roads from city f to city h are blocked. If there is no connecting path return -1
Country: United States
Interview Type: In-Person