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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Zero Request Servers

Difficulty: Medium

Problem Description

You are given an integer n denoting the total number of servers and a 2D 0-indexed integer array logs, where logs[i] = [server_id, time] denotes that the server with id server_id received a request at time time. You are also given an integer x and a 0-indexed integer array queries. Return a 0-indexed integer array arr of length queries.length where arr[i] represents the number of servers that did not receive any requests during the time interval [queries[i] - x, queries[i]].

Key Insights

  • Each server can receive multiple requests at different times.
  • We need to efficiently count the number of servers that do not receive any requests within specific time intervals.
  • Using a hash table or a set can help keep track of which servers received requests during given intervals.
  • Sorting the logs can allow for more efficient querying.

Space and Time Complexity

Time Complexity: O(m + q log q), where m is the number of logs and q is the number of queries. We sort the logs and process each query in linear time. Space Complexity: O(n + m), where n is the number of servers and m is the number of logs. We may need to store the logs and a set of active servers.

Solution

To solve the problem, we can follow these steps:

  1. First, we will parse the logs to identify which servers received requests and when.
  2. We will create a map to track the servers that received requests within the time intervals defined by each query.
  3. For each query, we will count the servers that did not receive any requests by checking against the map.
  4. We will return the counts for each query in an array.

We will use a combination of sorting and a sliding window technique to efficiently find the number of servers that did not receive any requests during the specified time intervals.

Code Solutions

def countZeroRequestServers(n, logs, x, queries):
    from collections import defaultdict
    import bisect
    
    # Create a dictionary to store the request times for each server
    server_requests = defaultdict(list)
    
    # Populate the server_requests dictionary
    for server_id, time in logs:
        server_requests[server_id].append(time)
    
    # Sort the request times for each server
    for server_id in server_requests:
        server_requests[server_id].sort()
    
    # Prepare the result array
    result = []
    
    # Process each query
    for query in queries:
        start_time = query - x
        end_time = query
        
        # Track which servers received requests in the interval
        active_servers = set()
        
        for server_id in range(1, n + 1):
            if server_id in server_requests:
                times = server_requests[server_id]
                # Use binary search to check if there are requests in the interval
                left_index = bisect.bisect_left(times, start_time)
                right_index = bisect.bisect_right(times, end_time)
                if left_index < right_index:  # There's at least one request in the interval
                    active_servers.add(server_id)
        
        # Calculate the number of servers that did NOT receive requests
        zero_request_count = n - len(active_servers)
        result.append(zero_request_count)
    
    return result
← Back to All Questions