1
$\begingroup$

Here is problem in Sprinklr Interview Experience | Set 5 (On campus – FTE for Product Engineer).

You are given a graph of $n$ nodes with $m$ bidirectional edges. Each edge has some value associated with it. Vertex $1$ is source vertex. You have $K$ wildcards. In the path from vertex $1$ to vertex $i$ ($2 \leq i \leq n$), you can use at most $K$ wildcards while traversing. When you use a wildcard on an edge, you can pass that edge in summing the cost of path (i.e., value of that edge will be $0$ if you use a wildcard on an edge). Note: You can use at most $K$ wildcards from vertex $1$ to vertex $2$. Now you can again use at most $K$ wildcards from vertex $1$ to vertex $3$ and so on to vertex $n$. In other words, you can use at most $K$ wildcards in each path from source to destination. You have to find minimum distances from node $1$ to all other nodes in graph.

Constraints: $1 \leq n, m \leq 500000, 1 \leq K \leq 15$

Expected Approach: DP with shortest path algorithms on graph.

What I am doing is that, we can choose $k$ edges from $m$ edges in $\binom{m}{k}$ ways. And for each case find shortest path, but that will be too much time complexity.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – phan801 Feb 10 at 9:31
  • $\begingroup$ I tried this,choose edges k from m,which is m choose k. Remove them and find shortest path for each case.that is too much time complexity. $\endgroup$ – Manoharsinh Rana Feb 10 at 9:47
  • $\begingroup$ geeksforgeeks.org/… $\endgroup$ – Manoharsinh Rana Feb 10 at 10:06
3
$\begingroup$

Take $K+1$ copies of your graph. For each edge $(x,y)$ and for each $i \in \{1,\ldots,K\}$, connect the $i$'th copy of $x$ to the $(i+1)$'th copy of $y$ with a zero weight edge. Also connect the $i$'th and $(i+1)$'th copies of each vertex with a zero weight edge. Now calculate the minimum distance between vertex 1 on the first copy to all vertices in the last copy.

I'll let you figure out why this works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.