Correctness

You're building a ticket booking system for a concert venue. Users can browse available seats and book them. Simple enough. But what happens when two users try to book the same seat at the same time?

Alice wants seat 7A. Bob also wants seat 7A. Here's what should happen:

Alice gets the seat, Bob gets an error. But here's what can happen in a concurrent environment:

Both users checked availability before either completed their booking. Both saw the seat as available. Both proceeded to book it. Bob's write overwrote Alice's, and now Alice thinks she has a ticket but will show up to find Bob in her seat.

This is a correctness problem. Can multiple threads corrupt shared state? Yes—the check ("is the seat available?") and the action ("book it") happened as two separate steps. Another thread snuck in between them and invalidated the assumption. Alice checked, the answer was yes, but by the time she acted on that answer it was no longer true.

The same pattern appears throughout low-level design interviews. Rate limiters checking if under the limit before allowing a request. Connection pools checking if a connection is free before handing it out. Caches checking if there's room before adding an item. Whenever the validity of a check can change before you act on it, you have a correctness problem.

This article walks through four solutions to correctness problems, from simplest to most complex:

Then we cover the two patterns where correctness bugs appear most often in interviews and how to apply the solutions to them.

Every correctness problem can be solved with one of four approaches. We'll walk through them in order of frequency with which they appear in interviews.