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

What role is this question designed for?

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

Find Shortest Paths to Target Nodes | Waymo Coding Question

Find Shortest Paths to Target Nodes

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a weighted directed graph representing distances between nodes. - There are `n` nodes labeled from `0` to `n - 1`. - `edges[i] = [u, v, w]` means there is a directed edge from node `u` to node `v` with positive distance `w`. - You are given a starting node `source`. - You are also given a list of target nodes `targets`. Return the shortest distance from `source` to each target node. If a target cannot be reached from `source`, return `-1` for that target. The result should preserve the order of `targets`. Example: ```text n = 5 edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 5], [3, 4, 3]] source = 0 targets = [1, 3, 4] ``` Output: ```text [3, 4, 7] ``` Explanation: - The shortest path from `0` to `1` is `0 -> 2 -> 1`, with distance `1 + 2 = 3`. - The shortest path from `0` to `3` is `0 -> 2 -> 1 -> 3`, with distance `1 + 2 + 1 = 4`. - The shortest path from `0` to `4` is `0 -> 2 -> 1 -> 3 -> 4`, with distance `1 + 2 + 1 + 3 = 7`. Constraints: - `1 <= n <= 10^5` - `0 <= edges.length <= 2 * 10^5` - `edges[i].length == 3` - `0 <= u, v < n` - `1 <= w <= 10^9` - `0 <= source < n` - `1 <= targets.length <= n` - All edge weights are positive.

Quick Answer: This question evaluates knowledge of graph algorithms and algorithmic problem-solving, specifically computing shortest paths in weighted directed graphs and handling unreachable targets.

You are given a weighted directed graph with `n` nodes labeled from `0` to `n - 1`. Each entry `edges[i] = [u, v, w]` represents a directed edge from node `u` to node `v` with positive weight `w`. Given a starting node `source` and a list of `targets`, return a list where each element is the shortest distance from `source` to the corresponding target node. If a target cannot be reached from `source`, return `-1` for that target. The order of the returned distances must match the order of `targets` exactly.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
edges[i].length == 3
0 <= u, v < n
1 <= w <= 10^9
0 <= source < n
1 <= len(targets) <= n
All edge weights are positive.

Examples

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

Expected Output: [3, 4, 7]

Explanation: The best routes are 0->2->1 with cost 3, 0->2->1->3 with cost 4, and 0->2->1->3->4 with cost 7.

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

Expected Output: [5, -1, 0]

Explanation: Node 2 is reachable with cost 5, node 3 is unreachable, and the distance from the source to itself is 0.

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

Expected Output: [0, -1, 0]

Explanation: With no edges, only the source node 1 is reachable. Duplicate targets should still appear in the output in the same positions.

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

Expected Output: [4, 6, 5, -1]

Explanation: The cheapest distances are to 1 via 0->2->1 (4), to 3 via 0->2->1->3 (6), to 4 via 0->2->4 (5), and node 5 is unreachable.

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

Expected Output: [2, 9]

Explanation: There are multiple edges from 0 to 1; the cheaper one with weight 2 should be used. The shortest path to 4 is 0->1->2->3->4 with total cost 9, which beats the direct edge of cost 10.

Hints

Because all edge weights are positive, a shortest-path algorithm based on a min-heap is a good fit.
You only need one run from `source`: compute distances to all reachable nodes, then read off the answers for each target in order.

Quick Overview

This question evaluates knowledge of graph algorithms and algorithmic problem-solving, specifically computing shortest paths in weighted directed graphs and handling unreachable targets.