Rate Limiter
viaLeetCode
Problem Implement a rate limiter: allow(clientId) returns true if the request is within the client's limit of N requests per time window W, false otherwise. Runnable code passing test cases is expected, not just discussion.
Input / Output
- Input: configured limit N and window W; calls allow(clientId) arriving at arbitrary timestamps.
- Output: boolean per call.
Constraints
- Many clients → per-client state must be compact; calls should be O(1) amortized.
Example
- N=3, W=60s: requests at t=0,10,20 → true; t=30 → false; t=61 → true (the t=0 request expired).
Expected approach
- Sliding-window log: per-client deque of timestamps; evict entries older than W, allow if size < N — exact but O(N) memory per client. Token bucket: per-client tokens refilled at N/W per second — O(1) memory, allows small bursts. Fixed-window counter is simplest but has boundary spikes; sliding-window counter interpolates two fixed windows. Know the trade-offs and be ready to make one thread-safe.
asked …