Rate Limiter

Amazon's "Rate Limiter" interview question, tagged with Design, Sliding Window, and Queue, typically asks candidates to design and implement a rate-limiting system that enforces a maximum number of requests per client within a sliding time window using a queue-based approach.[1][2]

Problem Statement

Design a RateLimiter class that limits requests from a client (identified by a key like a user ID or IP) to at most maxRequests within any timeWindow seconds. Use a sliding window with a queue to track request timestamps: dequeue timestamps older than the current window start, and approve if the queue size is under the limit before enqueuing the new timestamp. This handles burst prevention better than fixed windows.[2][3][1]

Input/Output Examples

Implement bool allowRequest(String clientId, int time) (time in seconds since epoch).

• Example 1 (5 requests/10s window): limiter = RateLimiter(5, 10) limiter.allowRequest("A", 1) → true (queue: [1]) limiter.allowRequest("A", 2) → true (queue: [1,2]) limiter.allowRequest("A", 3) → true (queue: [1,2,3]) limiter.allowRequest("A", 4) → true (queue: [1,2,3,4]) limiter.allowRequest("A", 5) → true (queue: [1,2,3,4,5]) limiter.allowRequest("A", 6) → false (queue size 5 ≥ 5; no dequeue as 6-10= -4, all valid) limiter.allowRequest("A", 11) → true (dequeue 1 as 11-10=1; queue: [2,3,4,5,11]) limiter.allowRequest("A", 12) → true (dequeue 2; queue: [3,4,5,11,12]) Output reflects sliding: old requests expire dynamically.[3][2]

• Example 2 (10 requests/60s): limiter.allowRequest("B", 0) → true // 9 more at t=1-9 → all true (queue size=10) limiter.allowRequest("B", 10) → false limiter.allowRequest("B", 60) → true (dequeues all <60) Demonstrates per-client queues and expiration.[3]

Constraints

• 1 ≤ maxRequests ≤ 10^4
• 1 ≤ timeWindow ≤ 10^4 (seconds)
• 0 ≤ time ≤ 10^9
• Up to 10^5 calls to allowRequest
• Multiple clients; use a map of clientId to deque/timestamps
• Time complexity: amortized O(1) per call (queue ops efficient)
• Space: O(number of recent requests across clients)[8][1][2][3]