Count Zero Request Servers - Video Solutions

Problem Overview: You are given n servers and a list of request logs where each log contains [server_id, time]. For every query time q, count how many servers received zero requests in the time window [q - x, q]. The challenge is efficiently tracking which servers were active inside each window while handling many queries.

Approach 1: Sliding Window with Sorting (O((m + q) log m) time, O(n) space)

Sort the request logs by timestamp and also sort queries while keeping their original indices. Maintain a sliding window over the logs representing the active time range [query - x, query]. Use two pointers to expand the right boundary for logs with time ≤ query and shrink the left boundary when time < query - x. Track how many requests each server has inside the window using a frequency array or hash map. When a server’s count transitions from 0→1 it becomes active; when it drops to 0 it becomes inactive. The number of zero-request servers is simply n - active_servers. This approach works well because each log enters and leaves the window at most once.

This technique relies heavily on concepts from sliding window and sorting. The logs are processed sequentially while the window dynamically adapts to each query time.

Approach 2: Binary Search with Two-Pointer Technique (O(q log m + k) time, O(n) space)

Another option is preprocessing the logs by sorting them by timestamp. For each query, use binary search to locate the first log with time ≥ query - x and the last log with time ≤ query. This gives the subarray of logs inside the window. Then iterate through this range and track which servers appear using a hash table or boolean array. The number of servers not seen in this range equals the result for that query.

The key idea is leveraging binary search to quickly isolate the relevant log segment. However, repeatedly scanning the segment for each query can be expensive when many logs fall in the window. Compared to the sliding window solution, this approach is simpler conceptually but less efficient for dense log distributions.

Core concepts include arrays, hash tables, and binary search over sorted timestamps.

Recommended for interviews: The sliding window approach is the expected solution. It processes logs and queries in sorted order and ensures each log is added and removed from the window exactly once. Interviewers typically want to see you recognize the time-window pattern and apply two pointers with a frequency structure to maintain active servers efficiently.