How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Microsoft during technical interviews.

Compute shortest path in cyclic graph | Microsoft Coding Question

Compute shortest path in cyclic graph

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## Problem: Shortest Path in a Graph With Cycles You are given a directed weighted graph that may contain cycles. - There are `n` nodes labeled `0..n-1`. - You are given an edge list `edges`, where each edge is `(u, v, w)` meaning there is a directed edge from `u` to `v` with non-negative weight `w`. - You are also given a source node `s` and a target node `t`. ### Task Return the length of the shortest path from `s` to `t`. If `t` is not reachable from `s`, return `-1`. ### Input/Output - **Input:** `n`, `edges`, `s`, `t` - **Output:** shortest distance from `s` to `t` or `-1` ### Constraints (assume for interview) - `1 <= n <= 2 * 10^5` - `0 <= |edges| <= 3 * 10^5` - `0 <= w <= 10^9` - Graph can contain self-loops and cycles ### Example - `n = 5` - `edges = [(0,1,2),(1,2,3),(2,1,1),(2,3,4),(0,4,10)]` - `s = 0, t = 3` Shortest path: `0 -> 1 -> 2 -> 3` with total weight `2 + 3 + 4 = 9`. So output is `9`.

Quick Answer: This question evaluates understanding of graph algorithms and shortest-path computation in weighted directed graphs, including handling cycles, non-negative edge weights, self-loops, and related edge-case reasoning.

You are given a directed weighted graph with `n` nodes labeled from `0` to `n-1`. The graph may contain cycles, self-loops, and multiple edges between the same pair of nodes. Each edge is represented as `(u, v, w)`, meaning there is a directed edge from node `u` to node `v` with non-negative weight `w`. Return the length of the shortest path from source node `s` to target node `t`. If `t` cannot be reached from `s`, return `-1`. Because edge weights are non-negative, an efficient solution is expected for large inputs.

Constraints

1 <= n <= 2 * 10^5
0 <= len(edges) <= 3 * 10^5
0 <= u, v < n
0 <= w <= 10^9
The graph is directed and may contain cycles, self-loops, and duplicate edges

Examples

Input: (5, [(0, 1, 2), (1, 2, 3), (2, 1, 1), (2, 3, 4), (0, 4, 10)], 0, 3)

Expected Output: 9

Explanation: The shortest path is 0 -> 1 -> 2 -> 3 with total cost 2 + 3 + 4 = 9.

Input: (3, [(0, 1, 5)], 0, 2)

Expected Output: -1

Explanation: Node 2 is not reachable from node 0.

Input: (4, [(0, 1, 2), (1, 2, 2)], 2, 2)

Expected Output: 0

Explanation: The source and target are the same node, so the shortest distance is 0.

Input: (4, [(0, 0, 7), (0, 1, 0), (1, 2, 0), (2, 1, 1), (2, 3, 5)], 0, 3)

Expected Output: 5

Explanation: The best path is 0 -> 1 -> 2 -> 3 with total weight 0 + 0 + 5 = 5. The self-loop and cycle do not improve the answer.

Input: (3, [(0, 1, 10), (0, 1, 3), (1, 2, 4), (0, 2, 20)], 0, 2)

Expected Output: 7

Explanation: There are multiple edges from 0 to 1. Using the cheaper one gives path 0 -> 1 -> 2 with cost 3 + 4 = 7.

Hints

Since all edge weights are non-negative, think about using Dijkstra's algorithm with a min-heap.
Store the best known distance to each node, and ignore heap entries that are worse than the current recorded distance.

Quick Overview

This question evaluates understanding of graph algorithms and shortest-path computation in weighted directed graphs, including handling cycles, non-negative edge weights, self-loops, and related edge-case reasoning.