Implement Real-Time Rate Limiting for Web Service Requests
Company: Atlassian
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Scenario
A web service must throttle traffic from clients; you need to decide in real-time whether each incoming request should be served or rejected according to rate-limiting rules.
##### Question
Design and implement getRequestStatus(addresses) where addresses[i] is the URL hit at second i. Return "200" or "429" so that no address receives more than 5 requests in any 30-second window or more than 2 in any 5-second window.
##### Hints
Think sliding windows, per-address queues or deques, and O(
1) updates.
Quick Answer: This question evaluates understanding of real-time rate limiting, time-windowed traffic control, and efficient per-client state management under algorithmic constraints.
Implement get_request_status(addresses) where addresses[i] is the URL hit arriving at integer second i (i starts at 0). For each request, return "200" (accepted) or "429" (rejected) so that, for each address independently, the number of accepted requests never exceeds 2 in any 5-second window and never exceeds 5 in any 30-second window. Windows are inclusive: for a request at time t, the 5-second window is [t-4, t] and the 30-second window is [t-29, t]. Decisions are made online in order of arrival, and counts consider only previously accepted requests for that address.
Constraints
- 0 <= n <= 200000 where n = len(addresses)
- addresses[i] is a non-empty string (1 to 100 characters)
- Request i occurs at time t = i seconds (0-indexed)
- For each address independently: at most 2 accepted in any inclusive 5-second window [t-4, t]
- For each address independently: at most 5 accepted in any inclusive 30-second window [t-29, t]
- Return a list of "200" or "429" of length n
Solution
from typing import List, Dict, Deque, Tuple\nfrom collections import deque\n\ndef get_request_status(addresses: List[str]) -> List[str]:\n limit5, window5 = 2, 5\n limit30, window30 = 5, 30\n\n # Map address -> (deque for last 5s accepted, deque for last 30s accepted)\n windows: Dict[str, Tuple[Deque[int], Deque[int]]] = {}\n result: List[str] = []\n\n for t, addr in enumerate(addresses):\n if addr not in windows:\n windows[addr] = (deque(), deque())\n q5, q30 = windows[addr]\n\n # Inclusive windows: keep times >= t-(L-1)\n w5_start = t - (window5 - 1)\n w30_start = t - (window30 - 1)\n\n while q5 and q5[0] < w5_start:\n q5.popleft()\n while q30 and q30[0] < w30_start:\n q30.popleft()\n\n if len(q5) < limit5 and len(q30) < limit30:\n q5.append(t)\n q30.append(t)\n result.append("200")\n else:\n result.append("429")\n\n return result\nExplanation
Use per-address deques to track timestamps of accepted requests within the last 5 and 30 seconds, respectively. For each incoming request at time t, evict outdated timestamps (those strictly before t-(L-1)) from each deque to maintain inclusive windows [t-4, t] and [t-29, t]. If the counts in both deques are currently below their limits (2 for 5 seconds, 5 for 30 seconds), accept the request (return "200") and append t to both deques. Otherwise, reject (return "429"). This ensures the counts of accepted requests per address never exceed the specified limits in any sliding window.
Time complexity: O(n). Space complexity: O(n).
Hints
- Maintain per-address sliding windows using queues/deques of accepted timestamps.
- For each incoming request at time t, evict timestamps < t-4 from a 5-second deque and < t-29 from a 30-second deque.
- Accept if both deques have sizes strictly below their limits before adding t; otherwise reject.
- Use a hash map from address to its deques for O(1) amortized updates.