## Flipkart Interview Question for SDE-2s

Country: United States
Interview Type: In-Person

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

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.

invariant 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.

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

run Djikstra twice on all the nodes, once for uphill and then for downhill .... run it from source as well as destination
take minimum of sum of both values calculated above for each node and take minimum

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

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.

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

Exercise 3: http dot slash slash algo2 dot iti dot kit dot edu slash sanders slash courses slash algdat03 slash sol2 dot pdf

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Use Bellman-Ford.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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).

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

does it takes care of additional constraint too (regarding the uphill and downhill)?

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

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.)

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

Thanks for the clarification.

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.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.