Topic 14.4
LLM-Flavoured Coding Problems
In one line
Four small coding-round problems taken from real LLM plumbing: a token-bucket rate limiter, retry with full jitter, a streaming line parser that survives split chunks, and a history trimmer that keeps the system message. Each has tests that print PASS or FAIL, in three languages.
Think of it like this
The ticket jar at a fairground ride. The attendant drops one new ticket into the jar every few seconds. Each rider takes a ticket. If the jar is empty, you wait. The jar holds only so many, so a quiet hour does not let a crowd rush in all at once. That jar is a token bucket, the first problem below.
Words you'll meet
New words in this topic, in plain English. Come back here whenever one feels fuzzy.
- Token bucket
- A limiter with a level that refills at a steady rate up to a maximum. Each request takes from it, and an empty bucket means wait or refuse.
- Burst
- Many requests arriving at once. A bucket allows a burst up to its capacity.
- Full jitter
- Waiting a random time between zero and a growing limit, instead of waiting exactly the limit.
- Chunk boundary
- The point where one piece of a stream ends and the next begins. It can fall in the middle of a line.
- Token budget
- The most tokens you allow in one request, so the reply still fits in the context window.
- Retry-After
- A header in which a server says how long to wait before trying again. A client should never retry sooner.
- Thundering herd
- Many clients failing together and retrying together, so the recovering server is hit by a wave again.
- Injected dependency
- Something the code needs (the time, a random generator, a sleep function) passed in as an argument so tests can control it.
Step by step
01Step 1: restate, ask, then write tests first
Before any code, say the interface and three tests out loud. For the limiter: five allowed, the sixth denied; a token back after half a second at two per second; after a long pause only capacity allowed. Interviewers watch whether you think of the edge cases before they do.
02Step 2: the token bucket
Run the first example. The state is level and last_ms. On each call, add elapsed * rate (capped at capacity), then compare the cost with the level. Notice the two design choices the tests pin down: a denied request takes nothing, and an earlier timestamp neither crashes nor refills.
03Step 3: retry with full jitter
The second example takes the call, the random generator and the sleep function as arguments. The waits for seed 42 are 0, 228, 205 and 716 ms: all different and below their ceilings (200, 400, 800, 1,600). A wait of 0 is fine and intended: it spreads clients out. The Retry-After test shows the server's request beats the random wait.
04Step 4: the SSE parser
The third example keeps a buffer, splits it on newlines and keeps the unfinished tail. The diagram shows the loop for one feed call. The character-by-character test is the one that catches buffering bugs, so write it first.
05Step 5: the history trimmer
The fourth example walks from the newest message back, adds what fits and stops at the first message that does not. With a budget of 40 the history keeps the system message and the last user message only, because the assistant message before it would start the history with an answer whose question is gone. The last test covers a budget of 15: after the 12-token system message only 3 tokens remain, the newest message needs 9, so the function raises an error instead of returning a request with no question.
06Step 6: say what you tested and what you did not
End by listing the tests, the complexity (each problem is linear in its input), and what you would add next: for the limiter, a shared store for many servers; for the retry, a circuit breaker; for the parser, an event: field; for the trimmer, the real tokenizer.
Try it yourself
- 1
Change the bucket
In the limiter example, change the capacity to 2 and the refill to 1 per second. Predict the first six results at time 0, then at time 1,000 ms and 2,000 ms. Run and check.
- 2
Watch the jitter
Change the seed in the retry example from 42 to 7 and run it. Do the waits change? Are they still below their ceilings? Why does a seeded generator make the test repeatable and the production code still random enough?
- 3
Add a failing test
Add a parser test where a chunk ends in the middle of the word
dataand the next starts with the colon. Does it pass? Then add one where an event has nodata:line at all, only a comment, and decide what the right output is.
Code & diagrams
Time is an argument and the level is kept in thousandths of a token, so the tests are exact.
Expected output
PASS a burst of 5 is allowed, the 6th is denied
PASS half a second later one token is back
PASS after a long pause only `capacity` is allowed
PASS a request bigger than the bucket is never allowed
PASS an earlier timestamp does not crash or refill
5 of 5 passedUses the course's seeded generator (state * 48271 mod 2147483647), so every language prints the same waits.
Expected output
PASS a call that works is made once, with no waiting
PASS four failures then success: 5 calls, 4 waits
waits for seed 42: 0, 228, 205, 716 ms
PASS each wait is at most its ceiling (200, 400, 800, 1600)
PASS always failing: gives up after 5 calls and 4 waits
PASS a bad request is not retried
PASS Retry-After of 5000 ms is respected
PASS the cap holds: no wait above 1000 ms
7 of 7 passedThe parser keeps the text after the last complete line, so a chunk can end anywhere.
Expected output
PASS one chunk with three events
PASS cut in the middle of a line
PASS one character at a time
PASS CRLF line endings, split between CR and LF
PASS comment lines are ignored
PASS two data lines make one event
PASS an unfinished event is not delivered
PASS no chunks, empty chunks and stray blank lines give no events
8 of 8 passedA stand-in tokenizer (about 4 characters per token plus 4 per message). In production, pass the model's real counter.
Expected output
whole history: 77 tokens
PASS everything fits: nothing is dropped
budget 40 keeps: system,user
PASS the system message survives
PASS it fits the budget
PASS the newest message is kept
PASS order is preserved and the history starts with a user message
budget 49 keeps: system,user,assistant,user
PASS a bigger budget keeps more, still starting with a user message
PASS a system message bigger than the budget is an error
PASS a budget too small for the newest message is an error
8 of 8 passedBreak it on purpose
Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.
Break #1
Let the bucket overfill
In allow, remove the cap: use self.level = self.level + (now_ms - self.last_ms) * self.rate instead of the min(self.capacity, ...) line (Python).
Break #2
Forget the buffer
In feed, replace self.buffer += chunk with self.buffer = chunk (Python), so text left over from the last chunk is thrown away.
Myth vs fact
Myth
A fixed window of N requests per minute is just as good as a bucket.
Fact
A fixed window lets N requests through at the end of one window and N at the start of the next. The practice answer below shows six requests in 120 ms passing a limit of three per second.
Myth
Exponential backoff alone is enough.
Fact
If a thousand clients fail together and all wait exactly 200 ms, they all retry together again. The random part (jitter) spreads them out.
Myth
Each streamed chunk contains whole lines.
Fact
Network chunks can end anywhere, so a parser that splits each chunk on its own will break lines in two.
Interview problem
The problem
A limiter in front of the model API
Your service calls a model API that allows 60 requests per minute and 100,000 tokens per minute. Write a client-side limiter that smooths bursts, then extend it to count tokens.
You're given
- Allow short bursts, but hold the average at the limit.
- A denied request must not use up capacity.
- Deterministic tests: time is passed in.
- Many users: each user gets their own bucket, plus one shared bucket for the provider's limit.
The interviewer follows up
How does this work with ten servers?
What do you return when a request is denied?
How do you stop one user from using the whole limit?
Pro corner
Extra depth for experienced readers. New to this? Skip it for now and come back later.
- ▸
For real systems prefer a library for retries and rate limits (tenacity, resilience4j, p-retry, a gateway's built-in limits), but be able to write the core in 15 minutes: the interviewer is checking that you understand what the library does (Topic 6.8).
- ▸
The trimmer's "no gaps" rule matters: dropping an old message from the middle can leave a tool result without its tool call, which many APIs reject with a 400 error.
- ▸
SSE has more fields (
event:,id:,retry:). The OpenAI-style chat streams only usedata:lines ending with[DONE]; handle other fields only if your provider sends them.
Remember this
- 1
Why this exists. Coding rounds for LLM roles rarely ask you to build a transformer. They ask for small, sharp pieces of the plumbing around a model: limit how fast you call it, retry when it fails, read its streamed reply, keep the conversation inside the context window. Each one is short enough to finish in 20 minutes and rich enough in edge cases to show how you think.
- 2
How to run the round. Restate the problem in your own words, ask about edge cases (what if time goes backwards, what if the chunk ends mid-line), agree an interface, write two or three tests first, then the code, then run it. Make time and randomness parameters (a
now_msargument, a seeded random generator, asleepfunction you can replace), because code that reads the clock or calls a real random generator cannot be tested the way an interviewer wants. - 3
Problem 1: token bucket. Keep a level that refills at a steady rate up to a capacity. A request takes
costfrom the level or is denied; a denied request takes nothing. Refill on each call from the time since the last call, and ignore a clock that moves backwards. Integer maths (the level in thousandths of a token) avoids floating-point drift. It allows a burst up to the capacity, then holds the average at the refill rate, which is why API providers use it. - 4
Problem 2: retry with full jitter. After the n-th failure wait a random time between zero and
min(cap, base * 2^n). The random part (the jitter) stops thousands of clients from retrying at the same moment. Retry only errors worth retrying (timeouts, 5xx and a 429 that is a rate limit, but not a 429 that says your quota or spend cap is used up, which does not clear on retry: Topic 2.6), stop after a maximum number of attempts and re-raise, and never wait less than aRetry-Afterthe server sent. Injectsleepand the random generator so tests run instantly and repeatably. - 5
Problem 3: SSE parser. A streamed reply arrives in chunks that can end anywhere, even between the
\rand\nof a line ending. Keep a buffer of text after the last complete line. A line starting withdata:adds to the current event, a blank line finishes it, a line starting with:is a comment, and an event that never got its blank line is not delivered. The best test feeds the same stream one character at a time and expects the same events. - 6
Problem 4: token-budget trimmer. Keep the system message always, then add the newest messages while they fit, stopping at the first one that does not (no gaps in the middle of the conversation). Make sure the kept history starts with a user message, and fail loudly in two cases: the system message alone is over the budget, or not even the newest message fits (otherwise you would send the model a request with no question in it). The token counter is a function you pass in, so a test can use a simple one and production can use the model's tokenizer.
Explain it without notes
Why use a token bucket instead of a fixed-window counter for rate limiting?
Why does retry need jitter, and why a cap?
Why does a streaming parser need to keep a buffer between chunks, and which edge cases do you test?
In the history trimmer, why keep the system message, drop the oldest messages first and avoid gaps?
Practice
Write fixed_window(times_ms, limit, window_ms) that returns "yes" or "no" for each request time, allowing at most limit requests per window. Show it on two lists, and explain from the output why a token bucket is better.
Write ceiling(attempt, base_ms=200, cap_ms=10_000) that gives the largest wait for a retry attempt, and print the ceilings for attempts 0 to 7.
Trade-offs
- ↔
A per-server bucket is simple and fast but allows a multiple of the limit across servers; a shared store is exact but adds a network hop.
- ↔
More retry attempts raise the success rate but add latency and load during an outage; two or three attempts with jitter and a deadline is a common balance.
- ↔
A strict parser rejects odd streams early; a tolerant one survives provider quirks. Parse leniently, log the oddities.
Done when you can
Done when you can write a token bucket with injected time and explain each edge-case test.
Done when you can write retry with full jitter, a cap and Retry-After handling, and show the waits.
Done when you can write an SSE parser that passes the one-character-at-a-time test.
Done when you can write a trimmer that keeps the system message and refuses an impossible budget.
Done when you can explain why time and randomness are parameters.