Network delay time

Python data engineering interview problem. Difficulty: advanced. Pattern: Graphs. About 18 minutes. Part of the Pro drill bank.

Find the minimum travel time required for all nodes in a directed network to receive a broadcast signal. Treat this as a production helper: match the contracted return shape, including empty and duplicate inputs.

Implement network_delay_time(times: list[list[int]], n: int, k: int) -> int to calculate signal broadcast duration across a network. You are given a network of n nodes labeled from 1 to n. You are also given times, a list of directed edges where times[i] = [u, v, w] indicates that a signal takes w time units to travel from source node u to target node v. We send a signal from source node k. Return the minimum time it takes for all n nodes to receive the signal. If it is impossible for all n nodes to receive the signal, return -1.

Requirements

  • Edges are directed.
  • Return -1 if any node cannot be reached.

Constraints

  • 1 <= k <= n <= 100
  • 1 <= len(times) <= 6,000
  • times[i] = [u, v, w], where 1 <= u, v <= n and 0 <= w <= 100
  • All pairs (u, v) in times are unique.

Examples

Input: network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2) Output: 2 From node 2, signal reaches nodes 1 and 3 in 1 time unit, and node 4 through node 3 in 2 time units.

Topics: lakebench, python, dijkstra, shortest-path.

More Python interview questions · All interview problems · Learn data engineering

advanced

Network delay time

Interview-style drill: Find the minimum travel time required for all nodes in a directed network to receive a broadcast signal.

Implement `network_delay_time(times: list[list[int]], n: int, k: int) -> int` to calculate signal broadcast duration across a network. You are given a network of `n` nodes labeled from 1 to `n`. You are also given `times`, a list of directed edges where `times[i] = [u, v, w]` indicates that a signal takes `w` time units to travel from source node `u` to target node `v`. We send a signal from source node `k`. Return the minimum time it takes for all `n` nodes to receive the signal. If it is impossible for all `n` nodes to receive the signal, return `-1`.