All Challenges
6 PointsAdvanced
00:00

Sliding-Window Log & Token Bucket Dual Rate Limiter

Build an API Rate Limiter implementing Token Bucket (for smooth bursts) and Sliding-Window Counter (for strict interval protection) with memory pruning.

### Problem Overview Rate limiting is a fundamental defense against DDoS attacks and brute-force traffic. Fixed window algorithms suffer from boundary burst spikes (2x traffic across boundary windows). Implement a dual-strategy Rate Limiter supporting **Token Bucket** and **Sliding-Window Counter**. ### Functional Requirements 1. **`TokenBucketRateLimiter(capacity: number, refillRatePerSecond: number)`**: - `consume(tokens: number = 1): { allowed: boolean; remainingTokens: number; retryAfterMs?: number }` - Dynamically refills tokens based on elapsed elapsed time without setInterval polling. 2. **`SlidingWindowRateLimiter(maxRequests: number, windowMs: number)`**: - Tracks requests with sub-millisecond precision. - Automatically prunes expired request timestamps to prevent memory leaks. 3. **Multi-Client Isolation (`consumeFor(clientId: string)`)**: - Maintains isolated limits per client IP or API key. - Cleans up inactive client records older than 2x window duration. ### Non-Functional Requirements - **High Concurrency**: Must perform (O(1)) time complexity checks for token bucket and (O(\log K)) for sliding window. - **Zero Memory Leaks**: Inactive client buckets must be automatically garbage collected.
AI Review Rubric Dimensions (1–10 Points):
  • Sliding timestamp accuracy
  • Memory cleanup of inactive clients
  • Rate limit headers metadata
  • Burst control
solution.tsTYPESCRIPT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
28 lines•773 characters•
AI Review Ready