2039. The Time When the Network Becomes Idle
Asked at Atlassian
Difficulty
Medium
Time
O(n + m)
Space
O(n + m)
Pattern
Array
Companies
1
Problem
You are given a network of n servers numbered 0 to n-1, connected by undirected message channels in edges. Server 0 is the master. Every other server is a data server.
At the start of second 0, every data server sends one message to the master. A message travels along the shortest path and takes 1 second per edge. The master processes each message the moment it arrives and sends a reply straight back along the same path. So a data server at distance d from the master gets its reply at time 2*d.
While a data server waits, it may resend. Server i has a value patience[i]. Starting at second 1, at the beginning of each second, server i checks whether a reply has arrived. If not, and if patience[i] seconds have passed since its last send, it sends the message again. Once a reply arrives, that server stops sending forever. The network is idle at the first second when no message is in transit and none is arriving. Return that second, as an integer.
How messages and replies flow
Constraints
- ●
n == patience.length - ●
2 <= n <= 10^5 - ●
patience[0] == 0 - ●
1 <= patience[i] <= 10^5 for 1 <= i < n - ●
1 <= edges.length <= min(10^5, n * (n - 1) / 2) - ●
edges[i].length == 2 - ●
0 <= ui, vi < n - ●
ui != vi
Examples
edges = [[0,1],[1,2]], patience = [0,2,1]8edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]3Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Compute the shortest distance from each node to node 0 using BFS since all edges have equal weight.
For each server, calculate the round-trip time: 2 times the shortest distance.
Determine how many times the server resends its message before receiving the response.
The last send time plus the round-trip time gives when the server becomes idle.
The answer is the maximum idle time across all servers.
Optimal Approach
Run BFS from node 0 to find the shortest distance d for each server. For each server i, the message arrives back at time 2d[i]. If patience[i] is large enough that 2d[i] <= patience[i], the server does not resend, so it becomes idle at time 2d[i]. Otherwise, the server resends at intervals of patience[i], so the last resend occurs at floor((2d[i] - 1) / patience[i]) * patience[i], and the server becomes idle at that time plus 2*d[i]. The answer is the maximum idle time across all servers except node 0.
BFS distances, then last send time
What Trips People Up in Real Interviews
The master server (node 0) is already idle at time 0, so exclude it from the maximum calculation.
BFS from node 0 gives shortest distances since edge weights are uniform.
A server with patience p resends every p seconds until it gets a response at time 2*d.
The formula for last resend is ((2d - 1) // p) * p, then add 2d for the final round trip.
Double-check the edge case where patience is very large, meaning the server never resends.
Solution Code
O(n + m) timefrom collections import deque
class Solution:
def networkBecomesIdle(self, edges, patience):
n = len(patience)
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
dist = [-1] * n
dist[0] = 0
queue = deque([0])
while queue:
node = queue.popleft()
for nei in adj[node]:
if dist[nei] == -1:
dist[nei] = dist[node] + 1
queue.append(nei)
ans = 0
for i in range(1, n):
d = dist[i]
p = patience[i]
round_trip = 2 * d
if round_trip <= p:
idle = round_trip
else:
last_resend = ((round_trip - 1) // p) * p
idle = last_resend + round_trip
ans = max(ans, idle)
return ansFrequently Asked Questions
What is the The Time When the Network Becomes Idle problem?
Given an undirected graph representing a network of servers and edges representing communication channels, each server sends a message to the master server (node 0) at time 0. The message bounces back after reaching the master. A server becomes idle when it has sent and received its message and no further messages are in transit. Each server waits `patience[i]` seconds before resending if it has not received its response yet.
How do you solve The Time When the Network Becomes Idle?
The optimal approach runs in O(n + m) time and O(n + m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask The Time When the Network Becomes Idle?
The Time When the Network Becomes Idle is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on The Time When the Network Becomes Idle?
- The master server (node 0) is already idle at time 0, so exclude it from the maximum calculation.
- BFS from node 0 gives shortest distances since edge weights are uniform.
- A server with patience p resends every p seconds until it gets a response at time 2*d.
- The formula for last resend is ((2*d - 1) // p) * p, then add 2*d for the final round trip.
- Double-check the edge case where patience is very large, meaning the server never resends.