## Groupon Interview Question for SDE1s

• 0

Country: India

Comment hidden because of low score. Click to expand.
5
of 5 vote

Find the shortest path between any two nodes. Let them be A and B.
Now to get second shortest path between the same nodes, remove any one edge that is involved in the shortest path between the same nodes and calculate the shortest path. Do the above process for each of the node involved in shortest path and keep track of the minimum second shortest path found.

Comment hidden because of low score. Click to expand.
0
of 0 vote

For your solution time complexity is O(k(|E|+VlogV)), here V number of vertices, E number of edges in graph, K number of edges in shortest path. Can we reduce it?

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the shortest path algorithm is to be used as blackbox, I think aasshishh has the right solution.
But if we can modify the shortest path algorithm so that instead of tracking only the min path to any node, we track all paths length to a certain node, we can easily return all the shortest paths in order.

Comment hidden because of low score. Click to expand.
0
of 0 vote

As suggested above, apply the given algo and get the shortest path between A,B.
Now, in place of removing all edges one by one, why not, remove the shortest edge, and get the new path. That should be /can be the second shortest. I mean major shortest path algo are greedy ones, so this should suffice.
In case where post this we aren't able to find a path itself, then remove the next shortest edge and so forth until we get the path.

Comment hidden because of low score. Click to expand.
0

``No doubt, it is efficient to replace first shortest edge in the path, then next shortest edge, ..and so on. In the worst case, this solution ends up in the same solution like replacing each edge at a time to find the second shortest algorithm``

Comment hidden because of low score. Click to expand.
0
of 0 vote

To find the second shortest path between A and B, traverse through the nodes, use the available shortest function f, calculate sum = f(A,i) + f(i,B).

find the largest sum satisifying sum != f(A,B).

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.