Implement sliding-window rate limiter with dual thresholds
Company: Atlassian
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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.
Quick Answer: 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.
For each request at second i, return 200 unless serving it would exceed two successes in [t-4,t] or five successes in [t-29,t]. Rejected requests do not count.
Constraints
- Timestamp equals request index in seconds
Examples
Input: ([],)
Expected Output: []
Explanation: No requests.
Input: (['a', 'a', 'a'],)
Expected Output: ['200', '200', '429']
Explanation: Third request in five seconds rejected.
Hints
- Keep successful timestamps only; evict entries older than 29 seconds.