Implement a sliding-window rate limiter (n requests per k seconds), then make it per key

In a technical screen you are asked to implement a rate limiter that admits a request only if fewer than `n` requests have already been admitted in the last `k` seconds. Define the API, write the code, and then discuss the locking and concurrency problems the limiter would face in production. The follow-up makes the limiter key-specific: each key (for example a user or an API token) gets its own independent allowance of `n` requests per `k` seconds. ### Constraints and Clarifications - `n` and `k` are positive configuration values; no specific values are given. - A rejected request is not admitted and does not count toward the limit (confirm this with the interviewer). - In production the limiter is called from many threads at once. ### Clarifying Questions - Does "the last k seconds" include a request that is exactly `k` seconds old? - Does the caller pass the timestamp, or does the limiter read the clock itself? - Must the limit be exact, or is an approximation acceptable for large `n`? - In the per-key version, how many distinct keys should we expect, and must idle keys be forgotten? - Is this a single process, or shared across several servers? ### Part 1 — API and a single limiter Define the interface and implement one limiter with an exact sliding window. State the time and memory cost. ```hint What must you remember? Decide exactly which past requests can still affect a decision, and how to discard the rest cheaply. ``` #### What This Part Should Cover - A clear interface and window boundary semantics - An exact sliding-window implementation - Amortized time and bounded memory ### Part 2 — Locking and concurrency in production The limiter is shared by many request threads. Explain what can go wrong without synchronization, how you would fix it, and what the locking costs. ```hint Find the race Walk two threads through the check and the update at the same moment. ``` #### What This Part Should Cover - The check-then-act race and how it lets extra requests through - Lock scope and granularity - Alternatives to a single lock and their trade-offs ### Part 3 — Make it key-specific Extend the limiter so that each key has its own independent limit. ```hint Two levels of shared state Think of the map of keys and the per-key windows as separate things that both need protection. ``` #### What This Part Should Cover - The data structure for per-key windows - Safe creation of state for a new key under concurrency - Memory growth from many keys and how to bound it - How the design extends to several servers ### What a Strong Answer Covers - Window semantics agreed before coding, including the boundary case - Correct, readable code with amortized constant time and memory bounded by `n` - A precise explanation of the race and a lock that covers the whole decision - Per-key state created safely and evicted when idle - Awareness of approximate alternatives and of the distributed version ### Follow-up Questions - How would you support a different `n` and `k` for each key? - What changes if the limit must hold across a fleet of servers? - For very large `n`, the exact log becomes expensive. What approximation would you use, and what does it cost in accuracy? - How would you test the concurrent behavior?