Implement a rate limiter class

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.