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

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

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

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

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.