Quick Overview

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 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

  1. Keep successful timestamps only; evict entries older than 29 seconds.

Loading coding console...