The danger is silent wrong answers
Correctness is about preventing data corruption when threads share state. Two threads book the same seat. A counter that should be 1000 reads 847. A balance missing deposits. The danger isn’t usually deadlock theater — it’s silently producing wrong results.
Alice and Bob both want seat 7A. Correct: Alice checks under a lock, books, releases; Bob then sees BOOKED and fails. Broken: both check while status is AVAILABLE, both book; last write wins and Alice thinks she has a ticket she doesn’t.
Same shape everywhere: rate limiter check-then-allow, connection pool check-then-hand-out, cache check-then-insert. Whenever a check can become false before you act, you have a correctness problem.
Analogy: bathroom key (critical section)
Correctness bugs are two cashiers selling the last concert ticket because both looked at the screen before either hit “sold.” The fix is the same bathroom key: look and mark sold before you hand the key back.
Coarse-grained locking (default answer)
One lock guards all related booking ops. Check and update stay inside the same critical section — no interleaving.
from threading import Lock
class TicketBooking:
def __init__(self):
self._lock = Lock()
self._owners: dict[str, str] = {}
def book(self, seat_id: str, visitor_id: str) -> bool:
with self._lock:
if seat_id in self._owners:
return False
self._owners[seat_id] = visitor_id
return Trueimport java.util.HashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
class TicketBooking {
private final ReentrantLock lock = new ReentrantLock();
private final Map<String, String> owners = new HashMap<>();
boolean book(String seatId, String visitorId) {
lock.lock();
try {
if (owners.containsKey(seatId)) return false;
owners.put(seatId, visitorId);
return true;
} finally {
lock.unlock();
}
}
}# BROKEN — lock released between check and update
def book_broken(self, seat_id, visitor_id):
with self._lock:
available = seat_id not in self._owners
if available: # race window
self._owners[seat_id] = visitor_id
return True
return False// BROKEN — lock released between check and update
boolean bookBroken(String seatId, String visitorId) {
boolean available;
lock.lock();
try {
available = !owners.containsKey(seatId);
} finally {
lock.unlock();
}
if (available) { // race window
owners.put(seatId, visitorId);
return true;
}
return false;
}Read-write locks (read-heavy workloads)
Many readers, rare writers (config store, warm cache). Shared read lock; exclusive write lock. Mention when the interviewer skews read-heavy. Near 50/50 read/write, a simple mutex is often faster.
from threading import RLock # stdlib has no RWLock; illustrate idea
# In Java: ReentrantReadWriteLock — many readers OR one writer
# Pattern: read_lock around get; write_lock around putimport java.util.concurrent.locks.ReentrantReadWriteLock;
// ReentrantReadWriteLock — many readers OR one writer
ReentrantReadWriteLock rw = new ReentrantReadWriteLock();
// Pattern: readLock around get; writeLock around put
rw.readLock().lock();
try { /* get */ } finally { rw.readLock().unlock(); }
rw.writeLock().lock();
try { /* put */ } finally { rw.writeLock().unlock(); }Fine-grained locking (scale follow-up)
One lock per seat (or per partition). Alice on 7A and Bob on 12B don’t wait. Worth naming when asked about contention under machine-scale traffic.
from threading import Lock
from collections import defaultdict
class FineBooking:
def __init__(self):
self._locks: dict[str, Lock] = defaultdict(Lock)
self._owners: dict[str, str] = {}
self._meta = Lock() # only for creating lock entries if needed
def book(self, seat_id: str, visitor_id: str) -> bool:
lock = self._locks[seat_id]
with lock:
if seat_id in self._owners:
return False
self._owners[seat_id] = visitor_id
return Trueimport java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;
class FineBooking {
private final ConcurrentHashMap<String, ReentrantLock> locks = new ConcurrentHashMap<>();
private final Map<String, String> owners = new ConcurrentHashMap<>();
boolean book(String seatId, String visitorId) {
ReentrantLock lock = locks.computeIfAbsent(seatId, k -> new ReentrantLock());
lock.lock();
try {
if (owners.containsKey(seatId)) return false;
owners.put(seatId, visitorId);
return true;
} finally {
lock.unlock();
}
}
}Atomic variables
For one variable, CAS-based atomics avoid lock parking. Great for counters and flags. Python lacks a first-class AtomicInteger — use a Lock, or note Java/Go/C++ atomics in the interview language.
# Java-style intent in Python with a lock (or use multiprocessing.Value)
from threading import Lock
class BookingStats:
def __init__(self):
self._n = 0
self._lock = Lock()
def on_booked(self) -> None:
with self._lock:
self._n += 1
def get(self) -> int:
with self._lock:
return self._n
# Optimistic CAS loop (concept): read → compute → compare-and-set → retry on failimport java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
class BookingStats {
private final AtomicInteger n = new AtomicInteger(0);
// or with a lock:
// private int n; private final ReentrantLock lock = new ReentrantLock();
void onBooked() {
n.incrementAndGet();
}
int get() {
return n.get();
}
}
// Optimistic CAS loop (concept): read → compute → compareAndSet → retry on failThread confinement (shared nothing)
If only one thread touches a slice of data, races vanish. Partition seats A–M vs N–Z; actors; Dragonfly-style key ownership. Tradeoff: cross-partition ops need coordination; load imbalance; accidental cross-access reintroduces races.
Bug pattern: check-then-act
Check a condition, decide, act. Another thread invalidates the check in between. Booking, rate limit allow, pool checkout, LRU size check, parking spot assign, lazy singleton — same shape.
# BROKEN rate limiter
def allow(self, user_id: str) -> bool:
count = self._counts.get(user_id, 0)
if count < self._max:
self._counts[user_id] = count + 1 # race
return True
return False
# FIXED — check and act under one lock
def allow(self, user_id: str) -> bool:
with self._lock:
count = self._counts.get(user_id, 0)
if count < self._max:
self._counts[user_id] = count + 1
return True
return False// BROKEN rate limiter
boolean allowBroken(String userId) {
int count = counts.getOrDefault(userId, 0);
if (count < max) {
counts.put(userId, count + 1); // race
return true;
}
return false;
}
// FIXED — check and act under one lock
boolean allow(String userId) {
lock.lock();
try {
int count = counts.getOrDefault(userId, 0);
if (count < max) {
counts.put(userId, count + 1);
return true;
}
return false;
} finally {
lock.unlock();
}
}Bug pattern: read-modify-write
Read, compute, write — always write, no branch. Two threads read the same value and both write → lost update.
count++ is three steps.# Single counter → atomic / locked increment
# Multi-field (sum + count, balance) → one lock around the whole update
class BankAccount:
def __init__(self):
self._lock = Lock()
self._balance = 0
def deposit(self, amount: int) -> None:
with self._lock:
self._balance += amountimport java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
// Single counter → AtomicInteger / locked increment
// Multi-field (sum + count, balance) → one lock around the whole update
class BankAccount {
private final ReentrantLock lock = new ReentrantLock();
private int balance = 0;
void deposit(int amount) {
lock.lock();
try {
balance += amount;
} finally {
lock.unlock();
}
}
}- Hit counter → atomic / locked increment
- Bank deposits racing → lock around balance
- Inventory last unit → often check-then-act and RMW together
Decision tree
Worked mini-example: RMW counter vs mutex
# Lost updates
balance = balance + delta # read-modify-write race
# Mutex
with lock:
balance += delta
# Atomic (when it’s a single counter)
atomic_balance.add(delta)// Lost updates
balance = balance + delta; // read-modify-write race
// Mutex
synchronized (lock) {
balance += delta;
}
// Atomic (when it's a single counter)
atomicBalance.addAndGet(delta);Correctness anti-patterns
- Fine-grained locks first → deadlock spaghetti.
- Lock ordering undefined across two warehouses.
- Publishing a reference then mutating without happens-before.
- Double-checked locking recited wrong for the language.
Correctness checklist
- Invariant stated?
- Critical section minimal but complete?
- Lock order documented if multiple locks?
- Failure path releases locks (try/finally)?
- Test trace with two threads described?
Common interview pitfalls
These mistakes show up constantly on this prompt. Name the trap, then show the fix in your design — don’t wait for the interviewer to catch you.
- Coarse lock forever with no mention of contention trade-off.
- Fine locks without order → deadlock.
- Atomics used for multi-field invariants.
- RW locks where writers are frequent.
- Forgetting to release on exceptions.
Interview script (say this)
Read this once out loud before a mock. It’s the spine of a strong answer — not a script to recite robotically.
- Correctness: protect invariants under concurrent mutation.
- Start coarse-grained lock on the aggregate.
- Refine with RW locks / striping / atomics when pressed.
- Call out check-then-act explicitly.
- Show a broken trace and a fixed trace.
- Deadlock: lock ordering for multi-resource updates.
- Confine state to one thread when possible — simplest correctness.
- Tie back to booking/parking/inventory examples.
Extra verification traces
Walk these three traces on the board. If you can narrate them cleanly, your implementation section usually follows.
Staff-level follow-ups
At staff+, they twist the prompt. Answer in one sentence that names the seam — don’t redesign the whole board.
- Lock-free? — Only for single CAS-shaped invariants; don’t force it.
- STM? — Mention as research/production niche; prefer locks in interview.
- DB transactions? — Same invariant story at SQL isolation level.
Complete solution: inventory transfer (ordered locks)
Two warehouses, one SKU. Naive nested locks deadlock under crossed transfers. Complete interview answer: sort lock order by warehouse id.
from threading import Lock
class Warehouse:
def __init__(self, wid: str):
self.id = wid
self.qty: dict[str, int] = {}
self.lock = Lock()
def _add(self, sku: str, n: int) -> None:
self.qty[sku] = self.qty.get(sku, 0) + n
def _remove(self, sku: str, n: int) -> bool:
if self.qty.get(sku, 0) < n:
return False
self.qty[sku] -= n
return True
class Inventory:
def __init__(self, warehouses: list[Warehouse]):
self.by_id = {w.id: w for w in warehouses}
def transfer(self, src_id: str, dst_id: str, sku: str, n: int) -> bool:
if n <= 0 or src_id == dst_id:
return False
a, b = self.by_id[src_id], self.by_id[dst_id]
first, second = (a, b) if a.id < b.id else (b, a)
with first.lock:
with second.lock:
if not a._remove(sku, n): # always mutate logical src/dst
return False
b._add(sku, n)
return True
# Race without locks: both transfers read qty=5, both remove → negative stock.
# Deadlock without ordering: T1 locks A then B; T2 locks B then A.import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
class Warehouse {
final String id;
final Map<String, Integer> qty = new HashMap<>();
final ReentrantLock lock = new ReentrantLock();
Warehouse(String wid) { this.id = wid; }
void add(String sku, int n) {
qty.merge(sku, n, Integer::sum);
}
boolean remove(String sku, int n) {
if (qty.getOrDefault(sku, 0) < n) return false;
qty.put(sku, qty.get(sku) - n);
return true;
}
}
class Inventory {
private final Map<String, Warehouse> byId;
Inventory(List<Warehouse> warehouses) {
byId = new HashMap<>();
for (Warehouse w : warehouses) byId.put(w.id, w);
}
boolean transfer(String srcId, String dstId, String sku, int n) {
if (n <= 0 || srcId.equals(dstId)) return false;
Warehouse a = byId.get(srcId), b = byId.get(dstId);
Warehouse first = a.id.compareTo(b.id) < 0 ? a : b;
Warehouse second = first == a ? b : a;
first.lock.lock();
try {
second.lock.lock();
try {
if (!a.remove(sku, n)) return false; // always mutate logical src/dst
b.add(sku, n);
return true;
} finally {
second.lock.unlock();
}
} finally {
first.lock.unlock();
}
}
}
// Race without locks: both transfers read qty=5, both remove → negative stock.
// Deadlock without ordering: T1 locks A then B; T2 locks B then A.Complete solution: request counter (RMW)
from threading import Lock
class Metrics:
def __init__(self):
self._lock = Lock()
self._hits = 0
def hit(self) -> int:
with self._lock:
self._hits += 1 # read-modify-write under lock
return self._hits
def snapshot(self) -> int:
with self._lock:
return self._hits
# Broken: self._hits += 1 without lock → lost updates under load.
# AtomicInteger exists in Java; in Python prefer Lock for interview clarity.import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.ReentrantLock;
class Metrics {
private final ReentrantLock lock = new ReentrantLock();
private int hits = 0;
// Alternative: AtomicInteger hits = new AtomicInteger(0);
int hit() {
lock.lock();
try {
hits += 1; // read-modify-write under lock
return hits;
} finally {
lock.unlock();
}
}
int snapshot() {
lock.lock();
try {
return hits;
} finally {
lock.unlock();
}
}
}
// Broken: hits += 1 without lock → lost updates under load.
// AtomicInteger exists in Java; prefer it for a single counter.