The Time When the Network Becomes Idle

The Time When the Network Becomes Idle

What is this problem about?

Imagine a network of servers represented as an undirected graph. Server 0 is the master server, and all other servers are data servers. Each data server 'i' sends a message to server 0 at time 0 and continues to resend the message every patience[i] seconds until it receives an acknowledgment from server 0. A message takes a certain amount of time to travel across each edge. Once server 0 receives a message, it immediately sends an acknowledgment back. Your goal is to find the first second when the entire network becomes idle (no messages are traveling on any edges).

Why is this asked in interviews?

This the Time When the Network Becomes Idle interview question is used by companies like Atlassian to test a candidate's ability to model a complex communication system using graph algorithms. It requires finding the shortest path from each node to the master server (BFS) and then using that distance to calculate the total time the server remains active. It evaluates your ability to combine graph traversal with mathematical modeling of resending logic.

Algorithmic pattern used

This problem follows the Array, Breadth-First Search, Graph interview pattern.

1. Use BFS to find the shortest distance d[i] from server 0 to every other server i.
2. The total time for a message to go to server 0 and for the ACK to return is round_trip = 2 * d[i].
3. The server resends every patience[i] seconds as long as it hasn't received the ACK.
4. The last message is sent at time last_send = ((round_trip - 1) // patience[i]) * patience[i].
5. The last message returns to the server at last_send + round_trip.
6. The network becomes idle 1 second after the last message returns to its server.
7. The answer is max(last_send + round_trip) + 1 across all data servers.

Example explanation

Server 1 is 2 units away from Server 0. Round trip = 4. Patience = 3.

1. Time 0: Server 1 sends first message.
2. Time 3: Server 1 hasn't received ACK yet (ACK arrives at 4), so it sends another message.
3. Time 4: Server 1 receives ACK for the first message. It stops resending.
4. The last message was sent at time 3. It will take 4 seconds to return.
5. Last message returns at 3 + 4 = 7.
6. Server 1 becomes idle at time 7. Network idle at 7+1=8 (if this is the max).

Common mistakes candidates make

In "The Time When the Network Becomes Idle coding problem," a common mistake is incorrectly calculating the time of the last resend. Many candidates forget the round_trip - 1 logic, which accounts for the fact that a message arriving at the same time as a resend would prevent that resend. Another error is not using BFS to find the shortest paths, as the graph edges are unweighted.

Interview preparation tip

When dealing with network latency or message resending, always draw a timeline to visualize the events. Understanding the relationship between round-trip time and resending intervals is key to solving these types of problems. For graph traversal, remember that BFS is optimal for finding shortest paths in unweighted graphs.