Quick Overview

This question evaluates understanding of real-time rate limiting, time-windowed traffic control, and efficient per-client state management under algorithmic constraints.

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.

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

  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.

Loading coding console...

Show the approach

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)