The Time When the Network Becomes Idle
Asked at Atlassian
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.
Asked At
| 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.
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
from 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 ans
Frequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.