Katkat
Back

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

MongoDBSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Coding and design question from a technical screen: implement a rate limiter that admits at most n requests in any k-second sliding window, then make it thread-safe and key-specific. It tests window boundary semantics, amortized complexity, race conditions and locking, per-key state creation and memory bounds.

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.

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.

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.

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

Hints

Hint 1

What must you remember?: Decide exactly which past requests can still affect a decision, and how to discard the rest cheaply.

Hint 2

Find the race: Walk two threads through the check and the update at the same moment.

Hint 3

Two levels of shared state: Think of the map of keys and the per-key windows as separate things that both need protection.

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?