We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Time When the Network Becomes Idle

Number: 2151

Difficulty: Medium

Paid? No

Companies: Deutsche Bank

Problem Description

Given a network of n servers (labeled 0 to n-1) where server 0 is the master and all others are data servers. Each data server sends an initial message to the master at time 0. The messages travel optimally via bidirectional channels defined in the edges array. After time 0, at the beginning of every second, if a server has not received a reply to its latest message, it resends the message every patience[i] seconds. A reply is generated instantly upon arrival at the master and travels back along the same shortest path. Determine the earliest second when no messages are in transit in the network.

Key Insights

  • Use Breadth-First Search (BFS) starting from server 0 to calculate the shortest distance (in seconds) from the master to every data server.
  • The round-trip time for a data server i is 2 * (shortest distance).
  • Each data server sends messages at multiples of its patience until the reply arrives. The last message sent before the reply is determined by the largest multiple of patience[i] that is strictly less than the round-trip time.
  • The final reply for server i arrives at time = (last sent time) + (round-trip time). The answer is the maximum such time from all data servers plus 1.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of servers and m is the number of edges (for BFS traversal).
Space Complexity: O(n + m), due to the adjacency list and distance array.

Solution

We first build an adjacency list from the input edges and perform a BFS from the master server (server 0) to compute the shortest distances to all other servers. For each data server, the round-trip time is twice its distance from server 0.
If the round-trip time is less than or equal to the server’s patience value, no resends occur after the first message. Otherwise, determine the time when the last message was sent using:   lastSentTime = ((roundTrip - 1) // patience[i]) * patience[i]
Then, the final reply arrives at lastSentTime + roundTrip. The network becomes idle at one second after the latest arrival time among all data servers.

Code Solutions

from collections import deque

def networkBecomesIdle(edges, patience):
    # Number of servers
    n = len(patience)
    
    # Build adjacency list for graph representation
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    
    # BFS from the master server (server 0) to compute shortest distances
    dist = [-1] * n
    dist[0] = 0
    queue = deque([0])
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[current] + 1
                queue.append(neighbor)
    
    # Compute the time when the last reply arrives for each data server
    ans = 0
    for i in range(1, n):
        roundTrip = 2 * dist[i]
        if roundTrip <= patience[i]:
            lastSentTime = 0
        else:
            # Compute the last time the message was sent before receiving the reply
            lastSentTime = ((roundTrip - 1) // patience[i]) * patience[i]
        finalArrivalTime = lastSentTime + roundTrip
        ans = max(ans, finalArrivalTime)
    
    # Return idle time, which is one second after the last message arrives
    return ans + 1

# Example usage:
print(networkBecomesIdle([[0,1],[1,2]], [0,2,1]))  # Expected output: 8
← Back to All Questions