Per-IP Sliding-Window Rate Limiter: Accept or Reject Each Request

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.