Build It: Rate Limiter

A rate limiter caps how often a caller may hit a resource. The one-line spec: allow at most N requests per time window W for a given key (a user id, API token, or IP). Everything downstream — a login endpoint, a payment API, an outbound webhook — leans on this to survive abuse and traffic spikes.

Pin down the functional requirements before writing code:

• Per-key limits: user A's traffic must not consume user B's budget.
• A binary decision per request: admit or reject. Rejected calls usually get HTTP 429.
• Configurable N and W so one component serves many endpoints.

The non-functional requirements are where interviews are won:

• Accuracy: how strictly must the limit hold at window edges? Billing APIs care; a "trending" counter does not.
• Memory footprint: state grows with the number of active keys, so per-key cost matters at millions of keys.
• Scope: single-node in-process, or a shared limit across a fleet behind a load balancer?
• Thread safety: many worker threads call allow on the same key concurrently.

Lock the interface first so every algorithm is a drop-in swap behind it:

public interface RateLimiter {
    // Returns true if this request for the given key is admitted, false if it should be rejected.
    boolean allow(String key);
}

With that seam fixed, the rest of the design is just choosing an implementation. Each algorithm below implements exactly this allow(String key) contract, so callers never change when you swap strategies.