Problem
Implement a RateLimiter that decides whether a given request is allowed under a rate limit — e.g. at most N requests per time window per client/key. Delivered as a single 45-minute coding question.
Requirements
- Public API:
allow(key) -> bool (whether the request is permitted now); optionally allow(key, timestamp) to make time injectable for testing.
- Enforce N requests per window W per key.
Core design
- Per-key state in a map (key -> counters/timestamps). Choose an algorithm: fixed-window counter, sliding-window log, sliding-window counter, token bucket, or leaky bucket. Token/leaky bucket smooth bursts; sliding-window log is exact but memory-heavy.
- Keep window bookkeeping compact and evict stale keys to bound memory.
Discussion points
- Thread-safety under concurrent
allow calls (per-key locks / atomic counters).
- Accuracy at window boundaries vs memory usage trade-off.
- Distributed extension (shared store like Redis, atomic INCR + TTL) and clock-skew handling.