Per-IP Sliding-Window Rate Limiter: Accept or Reject Each Request
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A service receives a sequence of requests. Request `i` arrives at time `timestamps[i]` from the IP address `ip_addresses[i]`. Each IP address may have at most `limit` accepted requests inside a sliding time window of length `time_window`. Process the requests in the given order and decide, for each one, whether it is accepted (`1`) or rejected (`0`).
A request is checked only against earlier accepted requests from the same IP address. Rejected requests are not recorded, so they never count toward the limit.
### Function Signature
```python
def rate_limit(timestamps: list[int], ip_addresses: list[str], limit: int, time_window: int) -> list[int]:
```
### Rules
- Requests are processed in index order `0, 1, ..., n - 1`. Timestamps are non-decreasing, and requests with equal timestamps are processed in index order.
- For request `i` at time `t = timestamps[i]` from IP address `ip`, count the earlier requests `j < i` such that `ip_addresses[j] == ip`, request `j` was accepted, and `timestamps[j] > t - time_window`. A request made at exactly `t - time_window` is outside the window.
- If that count is less than `limit`, accept request `i` and output `1`; otherwise reject it and output `0`.
- IP addresses are compared as exact strings. Requests from different IP addresses never affect each other.
- Return a list of length `n` whose `i`-th value is the decision for request `i`.
### Constraints
- `1 <= n <= 10^5`, where `n = len(timestamps) == len(ip_addresses)`
- `0 <= timestamps[i] <= 10^9`, and `timestamps[i] <= timestamps[i + 1]` for every `0 <= i < n - 1`
- `1 <= limit <= 10^5`
- `1 <= time_window <= 10^9`
- Each `ip_addresses[i]` is a non-empty string of at most 45 characters, such as a dotted IPv4 address.
- All values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: timestamps = [1, 2, 3, 4, 4]
ip_addresses = ["10.0.0.1", "10.0.0.1", "10.0.0.1", "10.0.0.1", "10.0.0.2"]
limit = 2
time_window = 3
Output: [1, 1, 0, 1, 1]
```
At time `3`, address `10.0.0.1` already has two accepted requests (times `1` and `2`) in the window `(0, 3]`, so the request is rejected. At time `4` the window is `(1, 4]`: the request at time `1` has left the window, and the rejected request at time `3` was never recorded, so only the request at time `2` counts and the new request is accepted. The first request from `10.0.0.2` is accepted.
**Example 2**
```text
Input: timestamps = [5, 5, 5]
ip_addresses = ["192.168.1.7", "192.168.1.7", "192.168.1.7"]
limit = 1
time_window = 10
Output: [1, 0, 0]
```
**Example 3**
```text
Input: timestamps = [0, 10, 19, 20]
ip_addresses = ["1.1.1.1", "1.1.1.1", "1.1.1.1", "1.1.1.1"]
limit = 1
time_window = 10
Output: [1, 1, 0, 1]
```
At time `10` the request at time `0` is exactly `time_window` old, so it is outside the window and the request is accepted. At time `19` the accepted request at time `10` is still inside `(9, 19]`, so the request is rejected. At time `20` the window is `(10, 20]`, which holds no accepted request, so the request is accepted.
Overview: Implement a per-IP sliding-window rate limiter: given request timestamps, IP addresses, a request limit and a window length, decide in order whether each request is accepted or rejected. Tests exact window-boundary semantics, per-IP state, and processing a request log efficiently.
A service receives a sequence of `n` requests. Request `i` arrives at time `timestamps[i]` from the IP address `ip_addresses[i]`. Each IP address may have at most `limit` accepted requests inside a sliding time window of length `time_window`. Process the requests in the given order and decide, for each one, whether it is accepted (`1`) or rejected (`0`).
A request is checked only against earlier **accepted** requests from the **same** IP address. Rejected requests are not recorded, so they never count toward the limit.
Implement `rate_limit(timestamps, ip_addresses, limit, time_window)` and return the list of decisions.
### Rules
- Requests are processed in index order `0, 1, ..., n - 1`. Timestamps are non-decreasing, and requests with equal timestamps are processed in index order.
- For request `i` at time `t = timestamps[i]` from IP address `ip`, count the earlier requests `j < i` such that `ip_addresses[j] == ip`, request `j` was accepted, and `timestamps[j] > t - time_window`. A request made at exactly `t - time_window` is outside the window.
- If that count is less than `limit`, accept request `i` and output `1`; otherwise reject it and output `0`.
- IP addresses are compared as exact strings. Requests from different IP addresses never affect each other.
- Return a list of length `n` whose `i`-th value is the decision for request `i`.
### Constraints
- `1 <= n <= 10^5`, where `n = len(timestamps) == len(ip_addresses)`
- `0 <= timestamps[i] <= 10^9`, and `timestamps[i] <= timestamps[i + 1]` for every `0 <= i < n - 1`
- `1 <= limit <= 10^5`
- `1 <= time_window <= 10^9`
- Each `ip_addresses[i]` is a non-empty string of at most 45 characters, such as a dotted IPv4 address.
- All values fit in a 32-bit signed integer. No value exceeds `2^31 - 1`; in particular `t - time_window` lies in `[-10^9, 10^9]`.
### Example 1
```text
Input: timestamps = [1, 2, 3, 4, 4]
ip_addresses = ["10.0.0.1", "10.0.0.1", "10.0.0.1", "10.0.0.1", "10.0.0.2"]
limit = 2
time_window = 3
Output: [1, 1, 0, 1, 1]
```
At time `3`, address `10.0.0.1` already has two accepted requests (times `1` and `2`) in the window `(0, 3]`, so the request is rejected. At time `4` the window is `(1, 4]`: the request at time `1` has left the window, and the rejected request at time `3` was never recorded, so only the request at time `2` counts and the new request is accepted. The first request from `10.0.0.2` is accepted.
### Example 2
```text
Input: timestamps = [0, 10, 19, 20]
ip_addresses = ["1.1.1.1", "1.1.1.1", "1.1.1.1", "1.1.1.1"]
limit = 1
time_window = 10
Output: [1, 1, 0, 1]
```
At time `10` the request at time `0` is exactly `time_window` old, so it is outside the window and the request is accepted. At time `19` the accepted request at time `10` is still inside `(9, 19]`, so the request is rejected. At time `20` the window is `(10, 20]`, which holds no accepted request, so the request is accepted.
Constraints
- 1 <= n <= 10^5, where n = len(timestamps) == len(ip_addresses)
- 0 <= timestamps[i] <= 10^9, and timestamps[i] <= timestamps[i + 1] for every 0 <= i < n - 1
- 1 <= limit <= 10^5
- 1 <= time_window <= 10^9
- Each ip_addresses[i] is a non-empty string of at most 45 characters, such as a dotted IPv4 address.
- All values fit in a 32-bit signed integer.
Examples
Input: ([1, 2, 3, 4, 4], ['10.0.0.1', '10.0.0.1', '10.0.0.1', '10.0.0.1', '10.0.0.2'], 2, 3)
Expected Output: [1, 1, 0, 1, 1]
Explanation: Source example 1: the rejected request at time 3 is never recorded, so time 4 is accepted; the new address is independent.
Input: ([5, 5, 5], ['192.168.1.7', '192.168.1.7', '192.168.1.7'], 1, 10)
Expected Output: [1, 0, 0]
Explanation: Source example 2: equal timestamps with limit 1 accept only the first request in index order.
Hints
- Deciding request i only involves earlier requests that were accepted and that came from exactly the same IP string; everything else can be ignored.
- Timestamps never decrease, so an accepted request whose time is at most t - time_window is outside the window for request i and for every later request as well.
- Check the boundary carefully: the window is (t - time_window, t], and a rejected request must leave no trace.