Systems Interview Mastery

1.1The obvious design

Let's design the shortener the way most people first would. A visitor pastes a long address, such as a newspaper article's link, and the service hands back a short code like k3Zp, so the visitor can share short.example/k3Zp instead. Later, when anyone opens that short link, the service looks the code up in a table of code → long address and redirects them. The table is the whole state of the system.

The only decision in there that isn't obvious is how to pick the codes. They have to be short, and each code can lead to only one address, so no two addresses may ever be given the same code. The simplest way to get unique-looking codes is to pick them at random from the 62 letters and digits and use whatever comes out. With four characters, that's 62 × 62 × 62 × 62 = 14,776,336 possible codes. Fourteen million sounds like plenty of room.

1.2How soon do random codes repeat?

Before you run anything, make a guess.

The script draws random 4-character codes until one repeats, and does that 200 times to get a typical answer. For 6 and 7 characters the space is too big to simulate quickly, so it uses a formula instead. The formula is the birthday bound, named after the surprise that 23 people in a room are enough for two of them to share a birthday with even odds. It says a repeat becomes a coin flip after roughly the square root of the size of the space. Save the script as collide.py and run it.

import math, random, string
 
alphabet = string.ascii_letters + string.digits          # 62 characters
rng = random.Random(9)
 
def first_collision(length):
    seen = set(); n = 0
    while True:
        n += 1
        code = "".join(rng.choices(alphabet, k=length))
        if code in seen: return n
        seen.add(code)
 
trials = sorted(first_collision(4) for _ in range(200))
print(f"4-character codes ({62**4:,} possible): first repeat after a median of {trials[100]:,} codes")
for length in (6, 7):
    space = 62 ** length
    half = math.sqrt(2 * space * math.log(2))             # birthday bound for a 50% chance of a repeat
    print(f"{length}-character codes ({space:,} possible): 50% chance of a repeat by about {half:,.0f} codes")

4-character codes (14,776,336 possible): first repeat after a median of 4,360 codes
6-character codes (56,800,235,584 possible): 50% chance of a repeat by about 280,610 codes
7-character codes (3,521,614,606,208 possible): 50% chance of a repeat by about 2,209,524 codes

The first line is a real simulation. With 14.8 million possible codes, the first repeat came after only 4,360 codes at the median, about 0.03% of the space. The 6- and 7-character lines aren't simulated, they come from the birthday bound, and they tell the same story at a bigger scale: a service that has issued about two million 7-character codes, out of 3.5 trillion possible, has roughly even odds of having handed out a duplicate.

Here is the same thing drawn on one small example. Watch what happens to the link of the person who shortens the news article.

1.3Why this is the hard part

Picking a code at random looks fine and fails much sooner than the size of the space suggests. The obvious repair is to look the code up before storing it and draw again if it's taken. On a single database that lookup is cheap, but a real shortener runs on many servers, and two of them can check the same code at the same moment, both see it free, and both hand it out. The only way to stop that with a lookup is to send every new code through one central database that decides for everyone, and then that one machine is on the path of every new link: if it's slow, every link is slow, and if it's down, nobody can shorten anything. So the design question is how to make codes unique without every server asking one central machine each time. Section 6.3 gives the answer interviewers expect, Snowflake-style identifiers, and most of the follow-up questions you'd get on this prompt come out of it.

Every classic question has a part like this one, small and easy to walk past while you draw the obvious boxes. Finding it is half the interview, and the interviewer knows exactly which part they hid. That raises the next question: how does anyone check that you found it? The answer is a scoring sheet, so let's look at what's on it.

2.1Why companies use a structured interview

The format exists because it predicts job performance better than a chat does. Schmidt and Hunter's 1998 meta-analysis (a study that combines the results of many earlier studies) covered 85 years of research on hiring methods (Psychological Bulletin 124(2)). It rated each method by its validity, a correlation between the method's scores and later job performance, where 0 means the scores tell you nothing and 1 would mean they predict it perfectly. It put structured interviews at 0.51, against 0.38 for unstructured ones.

"Structured" means every candidate gets comparable questions, and interviewers score against written criteria instead of an overall impression. That's the rubric from the opening. It exists because impressions are less reliable than criteria.

?What does that mean for you?

It means the interviewer is filling in a sheet as you talk, and they can only score what they see or hear. A trade-off you considered silently and didn't say out loud doesn't exist on their sheet. So the first rule of the interview is to think aloud. The next question is what the sheet asks for.

2.2The axes a design answer is scored on

Companies don't publish their rubrics, but the widely used prep frameworks agree on what interviewers look for. Alex Xu's framework (ByteByteGo) lists the "ability to collaborate, to work under pressure, and to resolve ambiguity constructively" and "the ability to ask good questions". Hello Interview's delivery guide says "more senior candidates should be able to identify these places themselves and lead the discussion". Put together, they come to roughly four axes:

Finding the shortener's hard part, which we did in section 1, is the first row. Explaining how its codes become unique is the third.

?Why isn't "the right answer" on the list?

Because there isn't one. A news feed can be built by doing the work when someone posts (fan-out on write: copy the post into every follower's list) or when someone reads (fan-out on read: look up everyone they follow and merge). Both are defensible for some requirements. What's scored is whether you picked for a stated reason, and whether you know what your pick costs.

2.3The question behind the question

The shortener's hard part was unique codes. Every classic prompt is written around one or two parts like that, and the interviewer knows what they are. Most of your score depends on whether you find them and spend your deep-dive time there. Here are eight common prompts and what each one hides. The last column names the mechanism that answers it, and the later sections explain the ones you haven't met yet.

?How do you find the hard part if you don't recognise the prompt?

Ask which requirement is most expensive to meet at the stated scale. It's probably the one where a naive design does work proportional to something huge: followers per post, open connections per server, retries per failure. In the shortener it was the cost of making sure a new code hasn't been used, which grows with every code issued. Name the part out loud once you've found it: "the interesting part here is the fan-out".

Finding it early only pays off if you leave yourself the time to dig into it, and forty-five minutes goes quickly.

3.1Two frameworks, one shape

Here's the answer as a pipeline, with what each phase should leave on the board. Two terms appear in its first step. Functional requirements say what the system does: shorten a link, follow a link. Non-functional requirements say how well it does it: how fast, how often it may be down, how much it may lose. We'll use the later phases in sections 4 to 6, so treat this as the map.

For the shortener, the two API calls in the third step are the whole interface: one call creates a code for a long address, and one looks a code up. The first phase, though, needs more care than it gets.

3.2Requirements: turning adjectives into numbers

"Highly available, low latency, scalable" describes every system and constrains none of them. A non-functional requirement (one about how well the system behaves, not what it does) is useful only when it's a number you could be wrong about. Several of the numbers below need a word first. p99 latency is the response time that 99 out of 100 requests beat, so it describes the slow end. Availability is the share of time the system works, and 99.9% over a month leaves about 43 minutes of downtime. Read-your-writes means a user always sees their own latest change, even if other people see it a little later.

?Why spend precious minutes on this?

Because every later decision is justified against these numbers. "I'm using async replication because the requirement is five seconds of staleness" is a design argument. "I'm using async replication" is a preference.

Once the requirements are numbers, the next phase turns them into more numbers. That's the phase the two frameworks disagree about.

4.1Numbers worth carrying

Round everything. The goal is the order of magnitude.

Norvig's figures are from a "typical PC" of their time, and the others come from the experiments in chapters 02, 07 and 09 on a recent laptop. Neither is a promise about yours, but both are the right order of magnitude, which is all an estimate needs. Notice the spread: from half a nanosecond to 150 milliseconds is a factor of 300 million, so one round trip across the ocean costs as much as hundreds of millions of L1 cache hits.

4.2A worked estimate: does the feed fit?

Say the prompt is a feed for 100 million daily users, each opening the app five times a day and posting once every ten days. We divide a day's totals by the 10⁵ seconds in a day.

Two decisions fall out of it. Reads outnumber posts fifty to one, so it's worth doing work at write time to make reads cheap: the 20,000 inserts a second is a price a read-heavy system can pay. And 3.6 TB a year of posts is small enough that the storage choice is about access pattern, not volume.

A real system had almost exactly this ratio, and it learned something from it.

4.3The estimates that change designs

Each estimate is useful because of what you do when it comes out one way or the other:

The feed's numbers said to do the work when a post is written. Now we have to draw that, and the drawing has to be something you can follow one post through.

5.1Walk one request through the boxes

A box earns its place when you can say what it does to a specific request. Here's the write path of the hybrid feed from section 4.2, with one post followed through it as you'd narrate it. The post service is the first box, which stores posts and answers the app. A queue is a waiting line for jobs: the post service drops a message on it and moves on, and fan-out workers pick messages up when they can. The timeline cache keeps, for each user, a short list of the IDs of the posts they should see.

?Why narrate a request instead of describing components?

Because it exposes gaps. Describing a "fan-out service" sounds complete. Walking a post through it forces the questions an interviewer will ask anyway: what happens when the author has 30 million followers, and does the user wait for it? The frames above answer both because we followed one post, then a second one that behaved differently.

5.2Choosing components, with reasons

The queue and the cache in that picture were choices, and every component choice is a trade-off. Each should come with a one-line reason tied to a requirement, and with the cost it brings:

Once the boxes are on the board, the interviewer stops listening to the whole design and picks one box. What they ask next is where most answers fall apart.

6.1What a probe looks like

Here's a third prompt, a rate limiter (a service that caps how many requests one user may make), a few minutes into the deep dive. Notice that each question takes the previous answer one layer down. A token bucket is the mechanism the candidate names: each user has a bucket that refills slowly with tokens, every request takes one, and an empty bucket means the request is rejected.

?What's the interviewer looking for in a probe?

Whether your knowledge has a floor. Anyone can say "use Redis". The follow-ups test whether you know what that choice does to latency, what happens when it fails, and what you'd do instead. Running out of knowledge at roughly the fourth question is normal. Running out at the first is the signal they're checking for.

6.2Three probes every deep dive gets

You can prepare for most follow-ups because they come in three kinds. The rate limiter conversation above contained two of them: the second question was about scale, and the last was about failure.

Answer each at the level of mechanism, meaning what each machine does and in what order. "It fails over" doesn't say that. Take a database with a leader, the one machine that accepts writes, and a replica, a copy of the data on another machine. The leader sends the replica a regular "I'm alive" message, a heartbeat. A mechanism-level answer sounds like this: "The replica notices the missed heartbeats after a few seconds, a new leader is elected, and writes acknowledged by the previous leader but not yet copied are lost, unless replication was synchronous."

The shortener from section 1 is still unanswered, and it makes a good place to practise all three.

6.3Back to the shortener: unique IDs without asking anyone

Recall the problem from section 1. Random codes collide early, and checking each one before storing it only works if every server asks the same central database, which then slows down or stops every new link when it does. Handing out numbers from one central counter has the same flaw. The answer interviewers expect is to build uniqueness into the identifier itself, so that each machine can issue IDs alone and never produce one another machine could produce.

Twitter's Snowflake does this with a number cut into three fields. The top 41 bits are the time in milliseconds since a custom starting date (an epoch), the next 10 bits identify the machine, and the last 12 bits are a sequence, a counter that restarts every millisecond. That's 63 bits, so the whole ID fits in one 64-bit integer. Two machines can't produce the same ID because their machine fields differ. One machine can't repeat one because the timestamp or the sequence differs. (A shortener then writes the number in base 62, using the same letters and digits as before, to get a short code.)

?Why Snowflake's layout in particular?

Because it's a compact answer to a question most shorteners and feeds hit, and every field has a reason. Twelve bits of sequence give 4,096 IDs per millisecond per machine, 10 bits of machine give up to 1,024 machines, and 41 bits of milliseconds cover 69 years from a custom epoch. The README also says what happens when the clock runs backwards: Snowflake "will refuse to generate ids" until time passes the last one it issued. That's the failure mode, and interviewers ask about it. It's also a correctness probe and a failure probe at once, so you can practise both on it.

Another approach is to hand each server a block of numbers from a shared counter and let it count through the block alone, writing them in base 62. The server still asks a central counter, but once per block instead of once per link, so a short outage of the counter goes unnoticed while servers have numbers left. That trades the clock problem for the need to keep the counter safe and never hand out the same block twice, and it's a reasonable alternative as long as you say what it costs.

6.4Making retries safe: idempotency keys

The same pattern, find the failure and build the answer into the data, solves the payments prompt. A client sends a request to charge a card and the network drops the reply. The client can't tell whether the charge happened, so it retries, and now the card may be charged twice.

The fix is an idempotency key: the client invents a unique key for each logical operation, such as one checkout, and sends the same key with every attempt. The server stores the key together with the result, in the same database transaction as the charge itself, so either both are saved or neither is. When a repeat arrives with a key the server has seen, it returns the stored result instead of charging again. Clients should also retry with exponential backoff (waiting longer after each failure) and jitter (adding some randomness to the wait), so that a recovering server isn't flattened by every client retrying at the same moment. Stripe describes this design in Designing robust and predictable APIs with idempotency.

6.5Deep-dive material, by topic

These topics come up constantly, and each is a mechanism you can explain from first principles. The last column says where this book goes deeper.

So far every prompt has been a design question. Some interviews ask about something that already exists instead.

7.1Two kinds of systems question

?How deep should "what happens when you type a URL" go?

As deep as the interviewer steers. Give a complete, shallow pass first: DNS (turning the name into an address), TCP (opening the connection), TLS (encrypting it), HTTP (the request itself), the server, the response, rendering. Then offer to go deeper on one layer, or follow where they point. A complete shallow walk followed by one deep layer beats a deep first layer that never reaches the server.

7.2A debugging answer, step by step

The debugging question is a method test, and the method is the same one the deep dive rewards: narrow the space, name the evidence. Here's the shape of a strong answer to "p99 doubled after a deploy, CPU is flat". Its first step compares p99 with p50, the median response time, which describes a typical request. Three more ideas come up. Off-CPU time is time a request spends waiting, for a lock, a connection or a slow dependency, instead of running code. Little's Law says the average number of requests inside a system equals the arrival rate times the time each one stays, which tells you how big a pool of connections has to be. A USE pass is a walk through every resource (CPU, memory, disk, network, pools), checking its utilisation (how busy it is), saturation (whether work is queueing for it) and errors.

The interviewer scores the structure more than the final guess: narrowing the space, naming the evidence, and ordering hypotheses from cheap to check to expensive.

7.3Where the depth for these lives

Each systems question is a walk down several layers of the stack, and this book has a chapter for most layers. The table only names the layers; the chapters it points to explain them:

Whichever kind of question you get, what counts as a good answer also depends on the level you're interviewing for.

8.1The same question at three levels

Hello Interview's guide makes the key distinction: "More junior candidates can expect the interviewer to jump in here and point out places where the design could be improved. More senior candidates should be able to identify these places themselves and lead the discussion." Extending that:

On the shortener, a mid-level answer might be a working table and a cache, with the ID question raised by the interviewer. A senior answer raises the collision problem unprompted and brings the numbers. A staff answer might ask whether the shortener needs short codes at all for the stated use, and how existing links would move to a new scheme.

?Does "staff" mean a bigger design?

No. It usually means a more selective one. Staff answers are often smaller than senior ones, because they cut features the requirements don't need and spend the saved time on migration, operability and how the system fails.

Knowing the bar still doesn't guarantee passing it, and good engineers miss for the same few reasons again and again.

9.1Symptom, cause, fix

Almost every failure traces back to a section of this chapter, which makes the table below a checklist for reviewing your own practice runs:

9.2Handling what you don't know

You'll hit questions past your knowledge, because the interviewer keeps asking until you do. The scored behaviour is how you handle the edge:

• Say where your knowledge ends. "I haven't operated Cassandra, but I'd expect a write here to go to the commit log and memtable first. Is that the part you want to explore?"
• Reason from principles. You may not know a system's exact default, but you can probably reason about what it must do and what that would cost.
• Don't invent specifics. A made-up number or config flag is worse than "I'd measure it". Interviewers often know the real value.

Knowing the failure modes tells you what to fix. The last question is how to practise fixing it.

10.1A practice plan

Each step below trains one of the things the sections above said gets scored, so you can stop when you've covered the ones you're weakest at.

1. Pick eight prompts from section 2.3 and, for each, write down the hard part and the mechanism before you design anything.
2. Rehearse against a clock. Forty-five minutes, out loud, with the phase budget from section 3.1. Record it, or practise with someone who'll interrupt.
3. Learn one system deeply per category: one database, one cache, one queue, one load balancer. Deep-dive answers come from knowing one real thing well, not ten things by name.
4. Drill the three probes (failure, scale, correctness) against every design you practise.
5. Keep a numbers sheet like section 4.1, filled in with numbers you've timed yourself where you can.
6. Review each practice run against the four axes in section 2.2. Which one lost points?