Count Zero Request Servers

Medium

Flexport

2 views

Topics:

ArraysTwo PointersSliding Windows

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]].

Note that the time intervals are inclusive.

Example 1:

Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
Explanation: 
For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests.
For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.

Example 2:

Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
Output: [0,1]
Explanation: 
For queries[0]: All servers get at least one request in the duration of [1, 3].
For queries[1]: Only server with id 3 gets no request in the duration [2,4].

Constraints:

1 <= n <= 10⁵
1 <= logs.length <= 10⁵
1 <= queries.length <= 10⁵
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10⁶
1 <= x <= 10⁵
x < queries[i] <= 10⁶

Count Zero Request Servers

Medium

Flexport

2 views

Topics:

ArraysTwo PointersSliding Windows

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]].

Note that the time intervals are inclusive.

Example 1:

Input: n = 3, logs = [[1,3],[2,6],[1,5]], x = 5, queries = [10,11]
Output: [1,2]
Explanation: 
For queries[0]: The servers with ids 1 and 2 get requests in the duration of [5, 10]. Hence, only server 3 gets zero requests.
For queries[1]: Only the server with id 2 gets a request in duration of [6,11]. Hence, the servers with ids 1 and 3 are the only servers that do not receive any requests during that time period.

Example 2:

Input: n = 3, logs = [[2,4],[2,1],[1,2],[3,1]], x = 2, queries = [3,4]
Output: [0,1]
Explanation: 
For queries[0]: All servers get at least one request in the duration of [1, 3].
For queries[1]: Only server with id 3 gets no request in the duration [2,4].

Constraints:

1 <= n <= 10⁵
1 <= logs.length <= 10⁵
1 <= queries.length <= 10⁵
logs[i].length == 2
1 <= logs[i][0] <= n
1 <= logs[i][1] <= 10⁶
1 <= x <= 10⁵
x < queries[i] <= 10⁶

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of values for the server request times?
Can the input server request times be empty or null?
If no servers have zero requests, what should the function return?
Are the request times sorted or can they appear in any order?
What data type should the server request times be (e.g., integers, floats)?

Brute Force Solution

Approach

We have servers and requests. We want to find, for each server, how many requests fall within its active time window. The brute force method checks every possible request for every server to see if it falls within the server's time window.

Here's how the algorithm would work step-by-step:

For the first server, take the first request.
Check if the request's time is within the start and end time of the first server.
If it is, increase the count for the first server.
Repeat this check for every single request for the first server.
Once all requests have been checked for the first server, move to the next server.
Repeat the entire process of checking every single request for the second server, and so on, until you have checked every server.
The final result will be a count for each server of how many requests are within its time window.

Code Implementation

def count_zero_request_servers_brute_force(servers, requests):
    server_request_counts = []

    for server_index in range(len(servers)):
        request_count_for_server = 0

        # Iterate through each request to check its relevance to the current server

        for request_index in range(len(requests)):
            request_time = requests[request_index]
            server_start_time = servers[server_index][0]
            server_end_time = servers[server_index][1]

            # Checks if the request falls within the server's active time window

            if server_start_time <= request_time <= server_end_time:

                request_count_for_server += 1

        server_request_counts.append(request_count_for_server)

    return server_request_counts

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of servers and m be the number of requests. The algorithm iterates through each of the n servers. For each server, it iterates through all m requests to check if the request time falls within the server's active time window. Therefore, the total number of operations is proportional to n * m. Hence, the time complexity is O(n*m).

Space Complexity

O(1) – The provided brute force approach iterates through servers and requests, maintaining a count for each server. This implementation does not create any auxiliary data structures that scale with the input size. The algorithm only uses a few constant space variables to store intermediate values and loop counters, independent of the number of servers or requests. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

We need to figure out, for each server, how many requests it didn't handle (requests equal to zero). The efficient way is to pre-calculate the number of requests each server handles up to a certain time, then quickly find the number of zero requests for each server by looking at the right time range.

Here's how the algorithm would work step-by-step:

First, create a running total of requests for each server. This running total will tell us the total requests a server handles from the beginning up to any given time.
For each server, we are given time ranges to check for zero requests. For each time range, find the difference between the running totals at the end and start of the range. This tells us the number of requests the server handled during that specific range.
If the number of requests handled in that range is zero, then we know this server had zero requests for that time range, so increment the zero-request counter for that server.
After checking all time ranges for a given server, we have the total count of time ranges where that server had zero requests.
Repeat this process for each server to get the final result.

Code Implementation

def count_zero_request_servers(number_of_servers, logs, ranges):

    running_totals = [([0] * (len(logs) + 1)) for _ in range(number_of_servers)]

    for server_index in range(number_of_servers):
        for log_index in range(len(logs)):
            running_totals[server_index][log_index + 1] = running_totals[server_index][log_index] + (1 if logs[log_index][0] == server_index else 0)

    zero_request_counts = [0] * number_of_servers

    # Iterate through each server.
    for server_index in range(number_of_servers):

        # Check each time range for the current server.
        for time_range in ranges:
            start_time, end_time = time_range

            # Calculate requests handled in the given time range.
            requests_handled = running_totals[server_index][end_time + 1] - running_totals[server_index][start_time]

            # Increment counter if no requests were handled.
            if requests_handled == 0:
                zero_request_counts[server_index] += 1

    return zero_request_counts

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm first calculates the running total of requests for each server, which takes O(n) time where n is the number of timestamps in the request array. Then, for each of the n servers, it iterates through m time ranges. Within each time range, it performs a constant number of operations to find the difference between running totals. Therefore, the dominant cost is iterating through all servers and all their time ranges, resulting in O(n*m) time complexity.

Space Complexity

O(N) – The algorithm constructs a running total of requests for each server. If we have N servers, this running total is stored in an auxiliary data structure (e.g., a 2D array or list of lists) of size N x T, where T is the number of time points. However, the problem statement implies that we process one server at a time, so we only need space to store the running totals for one server at a time. Assuming there are N servers, and we are storing cumulative requests up to a maximum time which is also N (worst case where the time ranges are from 0 to N), then we store the running total in a list of size N, therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty arrival or departure array	Return an empty list since no requests can be processed with empty input.
Null arrival or departure array	Throw an IllegalArgumentException or return null to indicate invalid input.
Arrival and departure arrays have different lengths	Throw an IllegalArgumentException indicating that the arrays must be of equal size.
q array is empty	Return a list of zeros of the same size, because no requests will be counted since there are no queries.
Large input arrays (arrival, departure, q)	Ensure the solution's time complexity is efficient (e.g., O(n log n)) to handle large inputs without exceeding time limits.
Queries outside the range of arrival/departure times	Correctly handle these by considering all arrival/departure times when they are inside each query range.
Overlapping intervals in arrival and departure arrays.	The solution should correctly count the active servers at each query time regardless of overlapping intervals.
Queries with very close or identical values	Verify the inclusiveness/exclusiveness of the query range endpoints is handled correctly (i.e., [start, end]).