Count Servers With No Requests in Each Query's Time Window
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
A system has `n` servers with ids `1` through `n`. You are given a request log in which each entry `[server_id, time]` records that server `server_id` received a request at `time`. You are also given an integer `x` and a list of query times. For each query time `q`, count how many of the `n` servers received no request at all during the inclusive time window `[q - x, q]`.
This was one of two problems in a 75-minute online assessment.
### Function Signature
```python
def count_idle_servers(n: int, logs: list[list[int]], x: int, queries: list[int]) -> list[int]:
```
### Rules
- Each log entry is `[server_id, time]`. The log is not sorted, and the same server may appear many times, including several times at the same time.
- For a query time `q`, a server is idle when none of its log entries has a time `t` with `q - x <= t <= q`. Both ends of the window are inclusive.
- A server that never appears in the log is idle for every query.
- Return a list with one integer per query, in the same order as `queries`: the `i`-th value is the number of idle servers for `queries[i]`. Queries are independent of each other, may come in any order, and may repeat.
### Constraints
- `1 <= n <= 10^5`
- `1 <= len(logs) <= 10^5`, and every entry has exactly two integers
- `1 <= server_id <= n`
- `1 <= time <= 10^6`
- `1 <= x <= 10^5`
- `1 <= len(queries) <= 10^5`
- `x < queries[i] <= 10^6` for every `i`
- Every input value and every result fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: n = 4, logs = [[1, 2], [2, 4], [3, 4], [1, 7]], x = 3, queries = [4, 8, 10]
Output: [1, 3, 3]
```
For `q = 4` the window is `[1, 4]`; servers 1, 2 and 3 have requests at times 2, 4 and 4, so only server 4 is idle. For `q = 8` the window is `[5, 8]` and contains only server 1's request at time 7, so servers 2, 3 and 4 are idle. For `q = 10` the window `[7, 10]` again contains only the request at time 7.
**Example 2**
```text
Input: n = 2, logs = [[2, 1], [2, 5], [1, 5]], x = 2, queries = [9, 3, 5]
Output: [2, 1, 0]
```
The window for `q = 9` is `[7, 9]` and holds no requests, so both servers are idle. The window for `q = 3` is `[1, 3]`; it includes server 2's request at time 1 because the lower end is inclusive, so only server 1 is idle. The window for `q = 5` is `[3, 5]` and contains requests from both servers at time 5, so no server is idle.
Overview: Given an unsorted request log of server ids and timestamps, a window length and a list of query times, return for each query how many servers received no request in the inclusive window ending at that time. It tests answering many overlapping time-window queries efficiently.
A system has `n` servers with ids `1` through `n`. You are given a request log `logs` in which each entry `[server_id, time]` records that server `server_id` received a request at time `time`. You are also given an integer `x` and a list of query times `queries`. For each query time `q`, count how many of the `n` servers received no request at all during the inclusive time window `[q - x, q]`.
Implement `count_idle_servers(n, logs, x, queries)`.
**Rules**
- Each log entry is `[server_id, time]`. The log is not sorted, and the same server may appear many times, including several times at the same time.
- For a query time `q`, a server is idle when none of its log entries has a time `t` with `q - x <= t <= q`. Both ends of the window are inclusive.
- A server that never appears in the log is idle for every query.
- Return a list with one integer per query, in the same order as `queries`: the `i`-th value is the number of idle servers for `queries[i]`. Queries are independent of each other, may come in any order, and may repeat.
**Example 1**
```text
Input: n = 4, logs = [[1, 2], [2, 4], [3, 4], [1, 7]], x = 3, queries = [4, 8, 10]
Output: [1, 3, 3]
```
For `q = 4` the window is `[1, 4]`; servers 1, 2 and 3 have requests at times 2, 4 and 4, so only server 4 is idle. For `q = 8` the window is `[5, 8]` and contains only server 1's request at time 7, so servers 2, 3 and 4 are idle. For `q = 10` the window `[7, 10]` again contains only the request at time 7.
**Example 2**
```text
Input: n = 2, logs = [[2, 1], [2, 5], [1, 5]], x = 2, queries = [9, 3, 5]
Output: [2, 1, 0]
```
The window for `q = 9` is `[7, 9]` and holds no requests, so both servers are idle. The window for `q = 3` is `[1, 3]`; it includes server 2's request at time 1 because the lower end is inclusive, so only server 1 is idle. The window for `q = 5` is `[3, 5]` and contains requests from both servers at time 5, so no server is idle.
**Constraints**
- `1 <= n <= 10^5`
- `1 <= len(logs) <= 10^5`, and every entry has exactly two integers `[server_id, time]`
- `1 <= server_id <= n`
- `1 <= time <= 10^6`
- `1 <= x <= 10^5`
- `1 <= len(queries) <= 10^5`
- `x < queries[i] <= 10^6` for every `i` (so `q - x >= 1`)
- Every input value and every result fits in a 32-bit signed integer: no value exceeds 2^31 - 1, so a 32-bit `int` is sufficient in every language.
Constraints
- 1 <= n <= 10^5
- 1 <= len(logs) <= 10^5, and every entry has exactly two integers [server_id, time]
- 1 <= server_id <= n
- 1 <= time <= 10^6
- 1 <= x <= 10^5
- 1 <= len(queries) <= 10^5
- x < queries[i] <= 10^6 for every i
- Every input value and every result fits in a 32-bit signed integer (no value exceeds 2^31 - 1)
Examples
Input: (4, [[1, 2], [2, 4], [3, 4], [1, 7]], 3, [4, 8, 10])
Expected Output: [1, 3, 3]
Explanation: Source Example 1: windows [1, 4], [5, 8] and [7, 10] hold three, one and one busy servers.
Input: (2, [[2, 1], [2, 5], [1, 5]], 2, [9, 3, 5])
Expected Output: [2, 1, 0]
Explanation: Source Example 2: empty window, inclusive lower end at time 1, and both servers busy at time 5; answers follow the query order.
Hints
- A server counts once for a query no matter how many of its log entries fall inside the window, and a server that never appears in the log is always idle.
- Both window ends are inclusive: a request at exactly q - x or exactly q makes its server busy, while one at q - x - 1 or q + 1 does not.
- Queries are independent and may arrive in any order or repeat, but each answer must be returned at its query's original position.