Design and Implement Per-Client Rate Limiting

Implement a rate limiter that restricts how many requests each client or key may make within a specified time window. Requests for different keys must be limited independently. The report does not specify fixed versus rolling windows, boundary behavior, or whether rejected requests consume capacity. Explain and confirm those choices before presenting the data structures and request-decision logic; there is no supplied exact callable contract. ### Constraints & Assumptions - State is independent for each client/key. - Define the request limit and window duration as configuration. - Clarify clock behavior, concurrent requests, and whether the limiter is local to one process or shared across instances. ### Clarifying Questions to Ask - Is the limit for aligned fixed windows or for the preceding rolling duration? - Are requests exactly at the window boundary included? - Do rejected attempts count, and must decisions be consistent across service instances? ```hint A thread-safe map does not by itself make expiration, counting, and recording a request one atomic operation. ``` ### What a Strong Answer Covers Present a complete algorithm for an explicitly chosen window model, including key lookup, expiry, decision, and update order. Explain concurrency and idle-key cleanup, then distinguish the guarantees and costs of other window choices. ### Follow-up Questions - Why can fixed-window limits allow a burst across a boundary? - How would the design change when several application instances serve one key? - What should happen when the shared limiter store is unavailable?