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

Count Zero Request Servers

Number: 2833

Difficulty: Medium

Paid? No

Companies: DP world, Zomato, Flexport

Problem Description

Given n servers and a list of logs where each log is of the form [server_id, time], determine for each query time the number of servers that did not receive any requests during the time interval [query - x, query] (inclusive).

Key Insights

  • The problem asks us to count servers with zero requests within a moving time window for each query.
  • Sorting both the logs (by request time) and the queries (by query time) allows for efficient processing.
  • By using a sliding window technique with two pointers over the sorted logs, we can add logs that fall within the window and remove those that fall outside.
  • A frequency array (or hash table) is maintained to track the number of requests per server in the current window.
  • The difference between the total number of servers and the count of active servers (ones with at least one request) gives the answer for each query.

Space and Time Complexity

Time Complexity: O(L log L + Q log Q + L + Q)
Space Complexity: O(n + L + Q), where L is the number of logs and Q is the number of queries.

Solution

We start by sorting the logs based on their request time and pairing each query with its original index before sorting the queries by their time value. Using a sliding window and two pointers (left and right), we adjust the current window to cover the range [query - x, query]. As we move the pointers, we update a frequency counter for server requests. When a server’s count goes from 0 to 1, we mark it as active; when the count drops back to 0, we mark it as inactive. For each query, the result is calculated by subtracting the number of active servers from the total server count n.

Code Solutions

def countZeroRequestServers(n, logs, x, queries):
    # Sort logs by time (second element)
    logs.sort(key=lambda entry: entry[1])
    # Pair each query with its original index and sort by time value
    sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
    
    # Frequency array for server counts (using 1-indexing)
    server_counts = [0] * (n + 1)
    active_servers = 0
    results = [0] * len(queries)
    left = 0
    right = 0
    L = len(logs)
    
    # Process each query in sorted order
    for q, idx in sorted_queries:
        start_time = q - x
        # Add logs with time <= q (include into window)
        while right < L and logs[right][1] <= q:
            server_id = logs[right][0]
            server_counts[server_id] += 1
            if server_counts[server_id] == 1:
                active_servers += 1
            right += 1
        # Remove logs with time < start_time (slide window)
        while left < L and logs[left][1] < start_time:
            server_id = logs[left][0]
            server_counts[server_id] -= 1
            if server_counts[server_id] == 0:
                active_servers -= 1
            left += 1
        # Number of servers with zero requests is total servers minus active ones
        results[idx] = n - active_servers
    return results

# Example usage:
if __name__ == "__main__":
    n = 3
    logs = [[1, 3], [2, 6], [1, 5]]
    x = 5
    queries = [10, 11]
    print(countZeroRequestServers(n, logs, x, queries))  # Output: [1, 2]
← Back to All Questions