Flipkart Interview Question SDE-2s
Country: United States
Interview Type: In-Person
Let G = (V;E) be the graph that we construct given the road segments and their intersections.
We have costs on the edges that represent the length of the corresponding road segment. We
also have a value on every node that represents the elevation of that node. Let s be the node
representing the house, call it source, and let t be the node representing the university, call it
sink.
The idea is that we perform two separate shortest path computations. One from the source to
the rest of the nodes following only uphill edges, i.e, edges whose di erence of elevations of the
target node minus the source node is positive. One more, from the sink to the rest of the nodes
following uphill edges. On every node we store these two shortest path distances and we choose
the path that corresponds to the node that has the minimum sum of this values.
The next 4 steps describe more precisely the above procedure. Let for each node, the shortest
path distance from the source using only uphill edges be denoted as sp from s(v). Moreover,
let sp to t(v) denote the shortest path distance from node v to the sink t, for every v 2 V .
1. For all nodes v 2 V set sp from s(v) = 1 and sp to t(v) = 1.
2. Let G1 = (V;E1) be the graph induced by G if we remove all downhill edges. Run
SSSP algorithm on G1 using as source the node s. For every node in V set sp from s(v)
accordingly.
3. Let G2 = (V;E2) be the graph induced by G if we remove all uphill edges. Run SSSP
algorithm on G2 using as source the node t. For every node in V set sp to t(v) accordingly.
4. Find minv2V fsp from s(v) + sp to t(v)g. Choose the corresponding uphill and downhill
paths in order to get the desired s-t path.
USe Bellman-Ford. We can compute (by running Dijkstra or Bellman-Ford), the distance between v_1 and v_2 when using only one kind of roads (just remove the other kind of edges from the graph). Let it be C(v_1,v_2). This is constant. Let D(u,v) be the distance in our case. We have by Bellman iteration
D(u,v)= min {(c_{u,k} + C(k,v)), (c_{uk}+D(k,v))}.
Just iterate through it with appropriate boundary conditions (as in the case of Bellman-Ford).
I think what he meant is let's say we have two paths from 1 to 4:-
i) 1---u---2---d----3---u---4
ii) 1--u---6---u----7---u---9---10---u---4
1---u---2 means the path from 1 to 2 is uphill.
Then as per the problem shortest path we have to return is (ii). (i) is not a valid path as we are changing the path direction more than once ( once from uphill to downhill,then downhill to uphill & then again downhill to uphill.)
maintain the following attributes for each of the node u, d denoting number of uphill and downhill edges involved in shortest path to the node. initialize them to zero.
- anon123 May 01, 2014invariant to be maintained : at any given point in time, both u and d cannot be >1 simultaneously.
when considering an edge to be added to the SPT, check whether updating u and d values for the destinaion edge would violate the above invariant. an edge can be added only when the invariant is maintained.