Implement Real-Time Rate Limiting for Web Service Requests

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.

Real-Time Per-URL Sliding Window Rate Limiter

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

Examples

Example 1

Input: addresses = ["a","a","a","a","a","a","a"]
Output: ["200","200","429","429","429","200","200"]

Explanation: All hits are to the same address at times 0..6. The 3rd, 4th, and 5th requests would exceed the 2-per-5s limit if accepted, so they are rejected. Later requests at 5 and 6 are accepted as earlier ones age out of the 5-second window.

Example 2

Input: addresses = ["a","x1","x2","x3","a","x4","x5","x6","a","x7","x8","x9","a","x10","x11","x12","a","x13","x14","x15","a"]
Output: ["200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","200","429"]

Explanation: The address "a" appears at times 0,4,8,12,16,20 (six hits within a 21-second span). The first five are accepted. The 6th (time 20) would make 6 accepted hits in the last 30 seconds, so it is rejected by the 30-second rule. All unique addresses (x1..x15) are accepted.

Hints

1. Maintain per-address sliding windows using queues/deques of accepted timestamps.
2. For each incoming request at time t, evict timestamps < t-4 from a 5-second deque and < t-29 from a 30-second deque.
3. Accept if both deques have sizes strictly below their limits before adding t; otherwise reject.
4. Use a hash map from address to its deques for O(1) amortized updates.

Approach

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)