OA — Sliding-Window Rate Limiter

A standalone 45-minute single-problem OA (Applied AI Engineer pipeline): given time-sorted requests with source IPs, accept or reject each so that no IP exceeds a per-window limit. Sliding window + per-IP queue. Requirements Write a rate limiter. Given a stream of requests, decide per request whether to accept (1) or reject (0) based on how many requests the same IP has had accepted within a sliding time window. Input timestamps — request times in milliseconds, already sorted in non-decreasing order. ipAddresses — source IP for each request (parallel array). limit — max accepted requests per IP within the window. timeWindow — window length in milliseconds. Output — an array where index i is 1 if request i is accepted, else 0. A request at time timestamps[i] from IP ipAddresses[i] is accepted iff the number of previously accepted requests from the same IP that still fall inside the rolling window (timestamps[i] - timeWindow, timestamps[i]] is strictly less than limit. Window semantics (the load-bearing detail) The window is the half-open interval (timestamps[i] - timeWindow, timestamps[i]] — exclusive on the left, inclusive on the right. A prior accepted request at time t0 still counts at time t only while t0 + timeWindow > t. Equivalently, an accept expires exactly timeWindow ms after it was accepted: when t0 + timeWindow == t it has already left the window and no longer counts. Rejected requests are never tracked and never count toward the limit — only accepted requests occupy window slots. Constraints (large scale) 1 <= timestamps.length <= 10^8 (timestamps.length == ipAddresses.length). 0 <= timestamps[i] <= 10^9; timestamps sorted non-decreasing. ipAddresses[i] is a non-empty string of length at most 50. 1 <= limit <= 10^5. 1 <= timeWindow <= 10^9 ms. At 1e8 requests a per-request O(1)-amortized eviction (each accept enqueued/dequeued once) is required; anything super-linear will TLE. Examples timestamps = [1600040547954, 1600040547957, 1600040547958] ipAddresses = ["127.105.232.211", "127.105.232.211", "127.105.232.211"] limit = 1, timeWindow = 3 Output = [1, 1, 0] (The first request at t = 1600040547954 is accepted. At the second request t = 1600040547957, the first accept expires exactly at 954 + 3 = 957 — under the exclusive-left rule it has already left the window — so the single slot is free and the second request is accepted. At the third request t = 1600040547958, the second accept is still inside its window (957 + 3 = 960 > 958) and the slot is used, so it's rejected.) Notes Because input is pre-sorted by time, a sliding window + hashmap keyed by IP works: keep a queue of each IP's recent accepted request times, evict entries older than timeWindow, and accept only if the remaining count is below limit. Apply the exclusive-left rule when evicting: from the front of an IP's deque, pop every accepted time t0 for which t0 + timeWindow <= t (i.e. keep only those with t0 + timeWindow > t). A request exactly timeWindow apart from a prior accept is the boundary case — that prior accept is already expired, so it frees a slot. Accept iff the deque size after eviction is < limit; on accept, push the current timestamp. Rejected requests count toward nothing, so never push them. This was a single-problem, 45-minute OA on the Applied AI Engineer pipeline, distinct from the four-level CodeSignal framework. Preparation Implement the per-IP sliding window with a deque and test boundary timing (a request exactly timeWindow apart from a prior accept — it should re-open a slot, since t0 + timeWindow == t is expired). Confirm rejected requests do not occupy window slots, and handle multiple interleaved IPs independently. Sanity-check the scale: with up to 1e8 requests each accept must enter and leave its deque at most once (amortized O(1) per request); use a fast IP -> deque map and avoid re-scanning the window.