Build a Rate Limiter

You've inherited a small JSON API that works but has no protection against a single client hammering it. You're asked to add rate limiting: cap how many requests a client can make in a window, return HTTP 429 once they go over, and leave every request under the limit behaving exactly as it does now.

The service is already running when you arrive. Nothing about the endpoints changes, which means the whole exercise is about finding the right place to intervene in code someone else wrote.

What's in the codebase

• run.py. The entrypoint that starts the HTTP server.
• app/server.py. Turns raw HTTP requests into Request and Response objects.
• app/router.py. The Request and Response types, plus the (method, path) to handler table.
• app/middleware.py. The ordered chain every request flows through. This is the seam you're looking for.
• app/handlers.py. The endpoints: POST /login, GET /search, POST /messages, GET /health.
• app/store.py. Trivial in-memory data the handlers read and write.
• app/config.py. Host, port, and header names.
• tests/test_api.py. The existing endpoint tests, which pass now and must stay green.
• tests/test_rate_limit.py. The rate limiting tests, which fail until you implement.

The problem ships in Python and Java. Both folders are self-contained with the same staged prompts, so pick whichever language you'd interview in. The Java version runs with mvn -q compile exec:java and mvn -q test.

Your task

Add rate limiting so a single client can't hammer the API. Cap the number of requests in a window, return 429 once a client exceeds it, and keep everything under the limit working as it does today.

Read middleware.py before you write anything. The chain already exists, and how you insert into it determines whether your limiter runs before or after authentication, which is a real decision with real consequences.

What to focus on

• Identifying the client. The word "client" in the prompt is doing a lot of unexamined work. An IP address, an API key, an authenticated user ID, and a session all give different answers, and they behave differently behind a proxy or a corporate NAT. Pick one, say why, and name what it gets wrong.
• Where the limiter sits. Limiting before authentication protects you from unauthenticated floods but leaves you keying on IP addresses. Limiting after it gives you a real user ID, at the cost of having already done the authentication work for a request you're about to reject. Either is defensible as long as you know which one you chose.
• Testing time without waiting for it. A limiter is a function of the clock. If your tests call time.sleep, they're slow and flaky. Inject the clock so tests can advance it by hand.

The follow-ups

Expect the limit to get harder in stages once the basic version works.

A fixed window is the usual first implementation, and it has a specific flaw: a client can send a full window's worth of requests at the end of one window and again at the start of the next, so a limit of 100 per minute allows 200 requests across two adjacent seconds. A token bucket smooths that out and lets legitimate bursts through. When you start rejecting requests, tell the client when to come back with a Retry-After header.

Then the limits stop being uniform. Login should be stricter than search. And if you're storing one counter per client key in a dictionary, ask what happens to that dictionary after a million distinct keys, because nothing in the code evicts them.

Using AI on this problem

A token bucket is short enough that an agent will produce a working one, so the value is in the parts AI can't decide for you. Ask it to lay out the tradeoffs between fixed window, sliding window, and token bucket for this specific service, then choose one yourself and defend it.

If you do generate the limiter, check two things by hand: whether it reads the wall clock directly, which will make your tests slow, and whether the counter map ever shrinks.

Leveling signals