Rate Limiter with Separate Limits for Each Field of a Multi-Field Request

Implement a rate limiter, then extend it so that a request carrying several fields is rate-limited on each field separately. The report describes a 45-minute screen covering both parts on a tight clock, and it does not restate the exact limiting rule of the first part, so agree on the interface and the rule with the interviewer quickly. ### Constraints and Clarifications - Not given: the limiting algorithm, the limits and windows, whether time is passed in or read from a clock, and whether the limiter is shared across threads or servers. Ask, or state your assumptions. ### Clarifying Questions - What does a limit mean: at most a number of requests per key in a time window, or a sustained rate that allows bursts? If a window, is it aligned to clock boundaries or sliding? - Is the time of each request passed in by the caller, or read from a clock? Can times arrive out of order? - Does a rejected request count toward the limit? - Is the answer only allow or deny, or should the caller also learn when to retry? - One process or many servers? Is the limiter called from several threads? - How many distinct keys are expected, and must keys that go idle be cleaned up? ### Part 1 — Rate limiter Implement a rate limiter with a method that, given a key (for example a client id) and the time of a request, decides whether to allow the request. ```hint What must be remembered For the rule you agreed, work out the least state per key that still decides the next request exactly, and when that state can be thrown away. ``` #### What This Part Should Cover - A precise rule, including what happens to a request exactly at the window boundary - Per-key state, its memory cost, and cleanup of idle keys - Time and space complexity per request - Tests driven by explicit timestamps, including the boundary ### Part 2 — Separate limits for each field Requests now carry several fields, for example a user id, an IP address and an endpoint (illustrative). Each field has its own limit, and the limiter must enforce the limit of every field separately. ```hint Partial success Take a request that is within the limit for two fields but over it for the third. Decide what should happen to the first two fields' counts, and make sure your code cannot leave them half-updated. ``` #### Clarifying Questions for this Part - Is the request allowed only when it is within the limit on every field, or is each field's decision reported on its own? - When a request is rejected because of one field, does it still use up quota on the other fields? - Can a field be missing from a request? Can limits differ per field, or per value of a field? #### What This Part Should Cover - A configuration that maps each field to its limit and reuses the Part 1 limiter - An all-or-nothing check-then-record step and its behavior under concurrent calls - What the caller is told on rejection: which field, and when to retry - Cost per request as the number of fields grows ### What a Strong Answer Covers - Settles the limiting rule, time source and rejection semantics before coding - Exact window-boundary behavior, tested with injected timestamps - Bounded per-key memory with cleanup of idle keys - Correct multi-field semantics with no partial updates, including under concurrent calls - Knows the main limiting algorithms and the trade-offs between exactness, memory and burst behavior ### Follow-up Questions - The limits must now hold across many servers. Where does the state live, and how do you keep the multi-field check atomic? - One limit applies to a combination of fields, such as one user on one endpoint. How does your configuration express it? - A key's limit is tens of thousands of requests per window. What does that do to your memory, and what would you change? - How would you tell a rejected client when to retry?