Implement sliding-window rate limiter with dual thresholds
AtlassianData Scientist · Online AssessmentLast updated
This question evaluates a candidate's skill in implementing efficient online sliding-window rate limiting, covering stream processing, time-based window management, per-key state maintenance, algorithmic complexity analysis, and formal correctness reasoning.
Implement getRequestStatus(urls: List[str]) -> List[str]. The i-th entry in urls represents a single incoming request at timestamp t = i seconds (t starts at 0); the value is the URL being requested. For each request, return '200' if it can be served, else '429' if serving it would violate either limit for that same URL: at most 2 successful requests in any sliding 5-second window [t-4, t], and at most 5 successful requests in any sliding 30-second window [t-29, t]. Important: rejected requests must NOT be recorded as successful and therefore must NOT count toward future windows; successful requests do count. Process the stream online in arrival order. Constraints: 0 ≤ n ≤ 2e5; URLs are arbitrary strings; target O(1) amortized time per event and O(U) memory, where U is the number of distinct URLs seen in the past 30 seconds only. Use only built-in data structures; avoid third-party rate-limiting libraries. Provide: 1) A correct, production-friendly implementation that uses per-URL deques (or equivalent) to maintain only the timestamps still inside the respective windows; 2) Proof of correctness with respect to the two sliding-window constraints and the reject-does-not-count semantics; 3) Tight time and space complexity analysis; 4) Unit tests that cover edge cases such as empty input, alternating URLs, bursts exactly at boundaries (t=4/5 and t=29/30), rapid sequences that flip between '200' and '429', and very long runs where old timestamps must be evicted efficiently.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.