Count Zero Request Servers

Count Zero Request Servers

What is this problem about?

In the Count Zero Request Servers interview question, you are given a set of logs representing requests sent to various servers. Each log contains a server ID and a timestamp. You are also given a series of queries, each representing a point in time $t$. For each query, you must find the number of servers that did not receive any requests in the time interval $[t - x, t]$, where $x$ is a fixed time window.

Why is this asked in interviews?

Companies like Amazon and Zomato ask the Count Zero Request Servers coding problem to evaluate a candidate's ability to handle time-series data and sliding window logic across multiple queries. It tests optimization skills: a naive approach would iterate through all logs for every query (O(Q * L)), but an efficient solution uses sorting and a sliding window to process queries in O(Q log Q + L log L).

Algorithmic pattern used

This problem uses Sorting and the Sliding Window technique.

1. Sort everything: Sort the logs by timestamp and the queries by their end time.
2. Two Pointers: Maintain a window of logs that fall within the $[t-x, t]$ interval.
3. Frequency Map: Use a hash map or array to keep track of how many requests each server has in the current window.
4. Counting: The number of "zero request servers" is the total number of servers minus the number of servers currently in our frequency map.

Example explanation

Total servers: 3. Window $x = 5$. Logs: [[1, 3], [2, 6], [1, 7]] (Server, Time) Query: $t = 10$. Interval: $[10-5, 10] = [5, 10]$.

1. Log at time 3: Outside $[5, 10]$. Skip.
2. Log at time 6: Inside. Server 2 has 1 request.
3. Log at time 7: Inside. Server 1 has 1 request.
4. Active servers: {1, 2}. Count = 2.
5. Zero request servers: $3 - 2 = 1$. (Server 3).

Common mistakes candidates make

• Not sorting queries: Trying to process queries in their original order, which breaks the sliding window property and forces O(Q*L) complexity.
• Handling the window start: Forgetting to remove logs from the frequency map when the window slides past their timestamp.
• Off-by-one errors: Incorrectly implementing the inclusive boundaries $[t-x, t]$.

Interview preparation tip

Whenever you have range-based queries on timestamps, sorting both the data and the queries is almost always the first step to an efficient solution.