Rate Limiter — Sliding Window Counter

Difficulty: Medium · Topics: Sliding Window, Design, Concurrency

Difficulty: Medium | Tags: Design, Sliding Window, Concurrency

Description

Design a rate limiter that allows at most maxRequests requests within a sliding time window of windowSizeMs milliseconds.

Implement:

RateLimiter(maxRequests, windowSizeMs)
allowRequest(timestamp) → boolean — returns true if the request is allowed.

Examples

RateLimiter limiter = new RateLimiter(3, 1000);  // 3 req per second

limiter.allowRequest(100);    // true  (1st request)
limiter.allowRequest(400);    // true  (2nd)
limiter.allowRequest(800);    // true  (3rd)
limiter.allowRequest(900);    // false (4th in same 1s window)
limiter.allowRequest(1200);   // true  (request at t=100 is now outside window)

Constraints

Timestamps are strictly non-decreasing.
1 <= maxRequests <= 10^6
1 <= windowSizeMs <= 10^9

Hints

Hint 1

Use a queue/deque to store timestamps. On each request, remove timestamps older than currentTime - windowSize, then check if the queue size < maxRequests.

Practice this problem

Solve Rate Limiter — Sliding Window Counter in the browser