Implement a rate limiter at scale

## Problem Design and implement a **rate limiter** that enforces request limits per key (e.g., per user ID or API key). ### Requirements - Implement `allow(key, timestamp)` → returns `true` if the request is allowed, else `false`. - Support a policy like: **at most N requests per sliding window of W seconds** (you may choose fixed-window vs sliding-window, but state it clearly). - Handle many distinct keys. ### Follow-up (scale) How would you adapt the design/implementation if the service must handle **100K QPS**? Discuss: - Data structures and time/space complexity - Concurrency/thread safety - Distributed deployment (multiple instances) and correctness trade-offs - Hot-key mitigation and storage choices ### Constraints (assumptions you may make explicit) - Timestamps are in milliseconds or seconds (choose one). - Keys are strings. - Memory is limited; old state should expire.