PPractick

The problem

A server cluster has n nodes labelled 1..n and directed links with transmission times. Node k broadcasts a signal. How long until every node has received it? Each node receives the signal at its shortest-path time from k, so the answer is the largest of those shortest times, or −1 if some node is unreachable. That's single-source shortest paths with non-negative weights: Dijkstra.

Example: times = [[2,1,1], [2,3,1], [3,4,1]], n = 4, k = 2 → 2.

Function signature

int networkDelayTime(const vector<array<int, 3>>& times, int n, int k);  // nodes 1..n; times {u, v, w}

Test cases

Input (times, n, k)	Output	Explanation
([[2,1,1],[2,3,1],[3,4,1]], 4, 2)	2	Node 4 is last, at time 2
([[1,2,1],[2,3,2],[1,3,4]], 3, 1)	3	1→2→3 beats the direct 4
([[1,2,1]], 2, 1)	1
([[1,2,1]], 2, 2)	-1	Node 1 can't be reached from 2
([], 1, 1)	0	Only the source

(Confirm: links are directed; times are non-negative; the signal starts at time 0.)

How interviewers phrase it

• "Send a signal from node k. Return the minimum time for all n nodes to receive it, or −1 if that's impossible" (LeetCode 743).

Clarifying questions to ask

1. Are links directed? (Yes.)
2. Can times be zero? (Yes, but not negative.)
3. Are nodes 1-indexed? (Yes.)

Follow-ups to expect

1. "Why the maximum of the distances?"
2. "Why Dijkstra?"
3. "Could Bellman–Ford work?"
4. "How do you detect unreachable nodes?"
5. "Complexity?"

Related questions

• Swim in Rising Water Medium
• Djisktra's Algorithm Hard
• Why priority Queue is used in Djisktra's Algorithm Hard
• Path with minimum effort Hard
• Number of ways to arrive at destination Hard
• Connected Components Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in