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