Concurrency Interview Problems, Solved
Concurrency rounds use a small, well-worn set of problems. They are short to state, the code is rarely over 40 lines, and they are very easy to get subtly wrong. What the interviewer is really checking is whether you can argue that your code is correct: no deadlock, no lost wake-up, no busy-waiting, and no thread left blocked forever when the work is done.
This page solves every problem in that set in Java, Python and Go. Each problem follows the same format:
- Problem — restated in plain words.
- What makes it tricky — the trap most first attempts fall into.
- Key idea — the single sentence you should say out loud before writing code.
- Solutions — complete, runnable code in three languages. Java usually shows two approaches, because interviewers like to ask "now do it without semaphores".
- Why it is correct — the argument you would make at the whiteboard.
- Follow-ups — what the interviewer asks next.
Theory lives next door
This page is about solving problems under interview conditions. For the theory behind them (critical sections, Peterson's and Bakery algorithms, producer-consumer, readers-writers, the five classic dining-philosophers solutions, sleeping barber, cigarette smokers, Santa Claus), read Classic Synchronization Problems. For the primitives themselves, see Mutex, Semaphore & Monitor.
The Toolkit in One Table
Nearly every problem here is solved by one of five tools. Learn what each looks like in all three languages and most problems come down to choosing the right one.
| Tool | Java | Python | Go |
|---|---|---|---|
| Mutex | synchronized, ReentrantLock | threading.Lock | sync.Mutex |
| Condition variable | wait/notifyAll, Condition.await/signalAll | threading.Condition | sync.Cond |
| Counting semaphore | java.util.concurrent.Semaphore | threading.Semaphore | buffered chan struct{} |
| One-shot gate | CountDownLatch | threading.Event | close(ch) |
| Barrier | CyclicBarrier, Phaser | threading.Barrier | hand-rolled with sync.Cond |
The rule that holds for all of them: a thread waits on a predicate over shared state, never on the bare fact that it was woken up. Semaphores and channels bundle the predicate into their counter. With condition variables you write the predicate yourself, always in a while loop.
flowchart TD
Q["What shape is the problem?"] --> O["Fixed order between threads"]
Q --> A["Strict alternation or rotation"]
Q --> G["Wait until a group forms"]
Q --> R["At most N at a time"]
Q --> F["Fan out work, then collect"]
O --> O1["Semaphore at 0 or latch per edge"]
A --> A1["Paired semaphores or one condition with a turn variable"]
G --> G1["Barrier plus counting semaphores"]
R --> R1["Counting semaphore or bounded queue"]
F --> F1["Worker pool plus pending counter or channels"]
1. Print in Order
Problem. One object is shared by three threads. Thread A calls first(), thread B calls second(), thread C calls third(). The threads are started in any order, but the output must always be first, second, third.
What makes it tricky. The scheduler may start third() first. A naive answer that sets a boolean flag and spins on it (while (!firstDone) {}) is wrong twice: it burns a CPU core, and in Java a non-volatile flag may never become visible to the spinning thread, so it can loop forever.
Key idea. There are two "happens-before" edges, first→second and second→third. Give each edge a gate that starts closed. Each method opens the gate for the next one.
sequenceDiagram
participant C as Thread C
participant B as Thread B
participant A as Thread A
C->>C: third waits on gate 2
B->>B: second waits on gate 1
A->>A: print first
A->>B: release gate 1
B->>B: print second
B->>C: release gate 2
C->>C: print third
import java.util.concurrent.Semaphore;
class Foo {
// Both gates start closed: zero permits.
private final Semaphore firstDone = new Semaphore(0);
private final Semaphore secondDone = new Semaphore(0);
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
firstDone.release(); // open gate 1
}
public void second(Runnable printSecond) throws InterruptedException {
firstDone.acquire(); // blocks until first() has printed
printSecond.run();
secondDone.release(); // open gate 2
}
public void third(Runnable printThird) throws InterruptedException {
secondDone.acquire();
printThird.run();
}
}
import java.util.concurrent.CountDownLatch;
class Foo {
private final CountDownLatch firstDone = new CountDownLatch(1);
private final CountDownLatch secondDone = new CountDownLatch(1);
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
firstDone.countDown();
}
public void second(Runnable printSecond) throws InterruptedException {
firstDone.await();
printSecond.run();
secondDone.countDown();
}
public void third(Runnable printThird) throws InterruptedException {
secondDone.await();
printThird.run();
}
}
class Foo {
private int stage = 1; // which method may run next; guarded by "this"
public synchronized void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
stage = 2;
notifyAll();
}
public synchronized void second(Runnable printSecond) throws InterruptedException {
while (stage != 2) wait(); // while, not if
printSecond.run();
stage = 3;
notifyAll();
}
public synchronized void third(Runnable printThird) throws InterruptedException {
while (stage != 3) wait();
printThird.run();
}
}
from threading import Event
from typing import Callable
class Foo:
def __init__(self) -> None:
self.first_done = Event()
self.second_done = Event()
def first(self, printFirst: Callable[[], None]) -> None:
printFirst()
self.first_done.set()
def second(self, printSecond: Callable[[], None]) -> None:
self.first_done.wait()
printSecond()
self.second_done.set()
def third(self, printThird: Callable[[], None]) -> None:
self.second_done.wait()
printThird()
package main
import (
"fmt"
"sync"
)
type Foo struct {
firstDone, secondDone chan struct{}
}
func NewFoo() *Foo {
return &Foo{firstDone: make(chan struct{}), secondDone: make(chan struct{})}
}
func (f *Foo) First(print func()) {
print()
close(f.firstDone) // a closed channel releases every receiver, now and later
}
func (f *Foo) Second(print func()) {
<-f.firstDone
print()
close(f.secondDone)
}
func (f *Foo) Third(print func()) {
<-f.secondDone
print()
}
func main() {
f := NewFoo()
var wg sync.WaitGroup
wg.Add(3)
go func() { defer wg.Done(); f.Third(func() { fmt.Print("third") }) }()
go func() { defer wg.Done(); f.Second(func() { fmt.Print("second") }) }()
go func() { defer wg.Done(); f.First(func() { fmt.Print("first") }) }()
wg.Wait()
fmt.Println()
}
Why it is correct.
- Ordering.
secondcannot passacquire()untilfirsthas calledrelease(), and that call comes afterprintFirst.run(). Semaphores, latches, monitors and channel closes all create a happens-before edge, so the print is also visible in order, not only scheduled in order. - No lost wake-up. A semaphore remembers a
release()that happened before anyone waited: the permit stays there. A latch stays open, a closed channel stays closed. In the monitor version the waiter checksstagebefore sleeping, so anotifyAllthat came earlier does no harm because the state already says "go". - No busy-waiting. Every waiting thread is parked by the runtime.
Follow-ups.
- Why
whileand notifaroundwait()? Spurious wake-ups are allowed by the JVM spec, andnotifyAllwakes threads whose condition is still false (thethirdthread wakes when stage becomes 2). See Common Mistakes. - What if
first()might be called twice? A semaphore would bank two permits. A latch or a closed channel is idempotent, but in Go callingclosetwice panics, so you would guard it withsync.Once. - Generalise to N stages. Use a list of N−1 gates, or a single monitor with
stage.
2. Print FooBar Alternately
Problem. Thread A calls foo() and thread B calls bar(). Each method loops n times printing its word. The output must be foobarfoobar… with n pairs.
What makes it tricky. This is no longer a one-off ordering: it is a repeating hand-off. One-shot tools (latches, closing a channel) don't work. A single shared semaphore doesn't work either, because the thread that releases it may grab it straight back.
Key idea. Two semaphores, one per turn. fooTurn starts with one permit and barTurn with zero. Each thread takes its own permit and hands one to the other thread. It is a token being passed back and forth.
import java.util.concurrent.Semaphore;
class FooBar {
private final int n;
private final Semaphore fooTurn = new Semaphore(1); // foo goes first
private final Semaphore barTurn = new Semaphore(0);
public FooBar(int n) { this.n = n; }
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
fooTurn.acquire();
printFoo.run();
barTurn.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
barTurn.acquire();
printBar.run();
fooTurn.release();
}
}
}
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
class FooBar {
private final int n;
private final ReentrantLock lock = new ReentrantLock();
private final Condition fooCanRun = lock.newCondition();
private final Condition barCanRun = lock.newCondition();
private boolean fooTurn = true; // guarded by lock
public FooBar(int n) { this.n = n; }
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (!fooTurn) fooCanRun.await();
printFoo.run();
fooTurn = false;
barCanRun.signal(); // exactly one waiter can care
} finally {
lock.unlock();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (fooTurn) barCanRun.await();
printBar.run();
fooTurn = true;
fooCanRun.signal();
} finally {
lock.unlock();
}
}
}
}
from threading import Semaphore
from typing import Callable
class FooBar:
def __init__(self, n: int) -> None:
self.n = n
self.foo_turn = Semaphore(1)
self.bar_turn = Semaphore(0)
def foo(self, printFoo: Callable[[], None]) -> None:
for _ in range(self.n):
self.foo_turn.acquire()
printFoo()
self.bar_turn.release()
def bar(self, printBar: Callable[[], None]) -> None:
for _ in range(self.n):
self.bar_turn.acquire()
printBar()
self.foo_turn.release()
package main
import (
"fmt"
"sync"
)
type FooBar struct {
n int
fooTurn, barTurn chan struct{}
}
func NewFooBar(n int) *FooBar {
fb := &FooBar{n: n, fooTurn: make(chan struct{}, 1), barTurn: make(chan struct{}, 1)}
fb.fooTurn <- struct{}{} // the token starts on foo's side
return fb
}
func (fb *FooBar) Foo(print func()) {
for i := 0; i < fb.n; i++ {
<-fb.fooTurn
print()
fb.barTurn <- struct{}{}
}
}
func (fb *FooBar) Bar(print func()) {
for i := 0; i < fb.n; i++ {
<-fb.barTurn
print()
fb.fooTurn <- struct{}{} // buffer of 1 means the final send never blocks
}
}
func main() {
fb := NewFooBar(5)
var wg sync.WaitGroup
wg.Add(2)
go func() { defer wg.Done(); fb.Bar(func() { fmt.Print("bar") }) }()
go func() { defer wg.Done(); fb.Foo(func() { fmt.Print("foo") }) }()
wg.Wait()
fmt.Println()
}
Why it is correct.
- Invariant:
fooTurn.permits + barTurn.permits <= 1at all times, so at most one thread is ever between itsacquireand itsrelease. Each release targets the other semaphore, which forces strict alternation. - Foo starts: only
fooTurnhas a permit at the beginning. - Termination: both loops run exactly
ntimes. The lastfooTurn.release()frombarleaves one unused permit, which is harmless. In Go the buffer of 1 is what lets that last send complete without a receiver. - Lock + Condition version:
signal()(notsignalAll) is safe here because only one thread can ever be waiting on each condition. With more threads per role you would needsignalAllor one condition per thread.
Follow-ups.
- Why not
synchronized+notify()? With one monitor there is one wait set. With two roles,notify()may wake a thread of the wrong role that goes back to sleep, and then nobody wakes the right thread. UsenotifyAll(), or use twoConditions as above. - Three words in rotation (
foo,bar,baz)? Three semaphores in a ring. This generalises to K threads in round-robin. - Can you do it lock-free? Spin on an
AtomicIntegerturn counter withThread.onSpinWait(). It works, but it busy-waits, so mention that cost.
3. Print Zero Even Odd
Problem. Three threads share an object built with n. One calls zero(), one calls even(), one calls odd(). Together they must print 0 1 0 2 0 3 … 0 n: a zero before every number, and the numbers printed by the thread matching their parity.
What makes it tricky. It is a three-party hand-off where the next party depends on data: after a zero, the token goes to odd or to even depending on which number comes next. Each thread must also know when to stop, or one of them will block forever on a turn that never comes.
Key idea. zero is the dispatcher. It holds the only initial permit. After printing 0 it hands the token to odd or even based on i, and they always hand it back to zero. Each worker loops over exactly the numbers it owns, so termination needs no extra signal.
import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;
class ZeroEvenOdd {
private final int n;
private final Semaphore zeroTurn = new Semaphore(1);
private final Semaphore oddTurn = new Semaphore(0);
private final Semaphore evenTurn = new Semaphore(0);
public ZeroEvenOdd(int n) { this.n = n; }
public void zero(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i++) {
zeroTurn.acquire();
printNumber.accept(0);
if (i % 2 == 1) oddTurn.release(); else evenTurn.release();
}
}
public void even(IntConsumer printNumber) throws InterruptedException {
for (int i = 2; i <= n; i += 2) {
evenTurn.acquire();
printNumber.accept(i);
zeroTurn.release();
}
}
public void odd(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i += 2) {
oddTurn.acquire();
printNumber.accept(i);
zeroTurn.release();
}
}
}
import java.util.function.IntConsumer;
class ZeroEvenOdd {
private final int n;
private int next = 1; // next non-zero number to print
private boolean zeroTurn = true; // both guarded by "this"
public ZeroEvenOdd(int n) { this.n = n; }
public synchronized void zero(IntConsumer printNumber) throws InterruptedException {
for (int i = 0; i < n; i++) {
while (!zeroTurn) wait();
printNumber.accept(0);
zeroTurn = false;
notifyAll();
}
}
public synchronized void even(IntConsumer printNumber) throws InterruptedException {
for (int i = 2; i <= n; i += 2) {
while (zeroTurn || next != i) wait();
printNumber.accept(i);
next++;
zeroTurn = true;
notifyAll();
}
}
public synchronized void odd(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i += 2) {
while (zeroTurn || next != i) wait();
printNumber.accept(i);
next++;
zeroTurn = true;
notifyAll();
}
}
}
from threading import Semaphore
from typing import Callable
class ZeroEvenOdd:
def __init__(self, n: int) -> None:
self.n = n
self.zero_turn = Semaphore(1)
self.odd_turn = Semaphore(0)
self.even_turn = Semaphore(0)
def zero(self, printNumber: Callable[[int], None]) -> None:
for i in range(1, self.n + 1):
self.zero_turn.acquire()
printNumber(0)
(self.odd_turn if i % 2 else self.even_turn).release()
def even(self, printNumber: Callable[[int], None]) -> None:
for i in range(2, self.n + 1, 2):
self.even_turn.acquire()
printNumber(i)
self.zero_turn.release()
def odd(self, printNumber: Callable[[int], None]) -> None:
for i in range(1, self.n + 1, 2):
self.odd_turn.acquire()
printNumber(i)
self.zero_turn.release()
package main
import (
"fmt"
"sync"
)
type ZeroEvenOdd struct {
n int
zero, odd, even chan struct{}
}
func NewZeroEvenOdd(n int) *ZeroEvenOdd {
z := &ZeroEvenOdd{n: n,
zero: make(chan struct{}, 1), odd: make(chan struct{}, 1), even: make(chan struct{}, 1)}
z.zero <- struct{}{}
return z
}
func (z *ZeroEvenOdd) Zero(print func(int)) {
for i := 1; i <= z.n; i++ {
<-z.zero
print(0)
if i%2 == 1 {
z.odd <- struct{}{}
} else {
z.even <- struct{}{}
}
}
}
func (z *ZeroEvenOdd) Even(print func(int)) {
for i := 2; i <= z.n; i += 2 {
<-z.even
print(i)
z.zero <- struct{}{}
}
}
func (z *ZeroEvenOdd) Odd(print func(int)) {
for i := 1; i <= z.n; i += 2 {
<-z.odd
print(i)
z.zero <- struct{}{}
}
}
func main() {
z := NewZeroEvenOdd(5)
p := func(x int) { fmt.Print(x) }
var wg sync.WaitGroup
wg.Add(3)
go func() { defer wg.Done(); z.Even(p) }()
go func() { defer wg.Done(); z.Odd(p) }()
go func() { defer wg.Done(); z.Zero(p) }()
wg.Wait()
fmt.Println() // 0102030405
}
Why it is correct.
- One token: the total permits across the three semaphores is always at most 1, so exactly one thread prints at a time.
- Right recipient:
zeroat iterationisends the token to the thread that ownsi. That thread's own loop counter is also ati, because it has printed every earlier number it owns. - Termination:
zerodoesniterations,odddoes ⌈n/2⌉,evendoes ⌊n/2⌋. The number of releases into each semaphore matches the number of acquires, so no thread waits for a permit that never comes. Whenn = 1,evenruns zero iterations and returns at once, which is correct. - Monitor version: the predicate
zeroTurn || next != iis evaluated under the lock, andnotifyAllis required because three threads share a single wait set.
Follow-ups.
- Why is
notify()wrong in the monitor version? Afterzeroprints,notify()might wakeevenwhenoddis the one that should run.evengoes back to sleep and nobody else wakes up, so the program hangs. That is a lost wake-up caused by waking the wrong waiter. - Make the zero thread print every k-th number instead? The dispatcher pattern still works: only the routing condition changes.
4. Building H2O
Problem. Hydrogen and oxygen threads arrive at random. Each must call its release callback, but only as part of a complete molecule: in the output, every consecutive group of three releases must contain exactly two H and one O, and the threads of one molecule must all release before any thread of the next molecule does.
What makes it tricky. Two constraints overlap: admission (no more than 2 H and 1 O inside the current molecule) and grouping (no one leaves until the molecule is complete). Admission alone lets a third H slip in when an O is slow. Grouping alone (a barrier of 3) can form a molecule of HHH.
Key idea. Counting semaphores limit admission (H = 2, O = 1). A barrier of 3 forms the group. Release your admission slot only after the barrier trips, so the next molecule's atoms can only enter once this molecule is complete.
flowchart LR
H1["H thread"] --> HS["H slots: 2"]
H2["H thread"] --> HS
O1["O thread"] --> OS["O slot: 1"]
HS --> B["Barrier of 3"]
OS --> B
B --> REL["Bond, then give slots back"]
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Semaphore;
class H2O {
private final Semaphore hSlots = new Semaphore(2);
private final Semaphore oSlots = new Semaphore(1);
private final CyclicBarrier molecule = new CyclicBarrier(3);
public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
hSlots.acquire();
try {
releaseHydrogen.run(); // print inside the molecule
molecule.await(); // wait until 2H + 1O have all printed
} catch (BrokenBarrierException e) {
throw new IllegalStateException(e);
} finally {
hSlots.release(); // only now can the next molecule's H enter
}
}
public void oxygen(Runnable releaseOxygen) throws InterruptedException {
oSlots.acquire();
try {
releaseOxygen.run();
molecule.await();
} catch (BrokenBarrierException e) {
throw new IllegalStateException(e);
} finally {
oSlots.release();
}
}
}
class H2O {
private int h = 0, o = 0; // atoms released in the current molecule; guarded by "this"
public synchronized void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
while (h == 2) wait(); // this molecule already has its two H
releaseHydrogen.run();
h++;
completeIfFull();
}
public synchronized void oxygen(Runnable releaseOxygen) throws InterruptedException {
while (o == 1) wait();
releaseOxygen.run();
o++;
completeIfFull();
}
private void completeIfFull() {
if (h == 2 && o == 1) { h = 0; o = 0; } // start the next molecule
notifyAll();
}
}
from threading import Barrier, Semaphore
from typing import Callable
class H2O:
def __init__(self) -> None:
self.h_slots = Semaphore(2)
self.o_slots = Semaphore(1)
self.molecule = Barrier(3)
def hydrogen(self, releaseHydrogen: Callable[[], None]) -> None:
with self.h_slots: # acquire, and release on the way out
releaseHydrogen()
self.molecule.wait()
def oxygen(self, releaseOxygen: Callable[[], None]) -> None:
with self.o_slots:
releaseOxygen()
self.molecule.wait()
package main
import (
"fmt"
"sync"
)
// Barrier is a reusable (cyclic) barrier for n goroutines.
type Barrier struct {
mu sync.Mutex
cond *sync.Cond
n, count int
generation int
}
func NewBarrier(n int) *Barrier {
b := &Barrier{n: n}
b.cond = sync.NewCond(&b.mu)
return b
}
func (b *Barrier) Await() {
b.mu.Lock()
defer b.mu.Unlock()
gen := b.generation
b.count++
if b.count == b.n { // last arrival trips the barrier and resets it
b.count = 0
b.generation++
b.cond.Broadcast()
return
}
for gen == b.generation {
b.cond.Wait()
}
}
type H2O struct {
hSlots, oSlots chan struct{}
molecule *Barrier
}
func NewH2O() *H2O {
return &H2O{hSlots: make(chan struct{}, 2), oSlots: make(chan struct{}, 1), molecule: NewBarrier(3)}
}
func (w *H2O) Hydrogen(release func()) {
w.hSlots <- struct{}{} // acquire a slot
defer func() { <-w.hSlots }() // give it back after the barrier
release()
w.molecule.Await()
}
func (w *H2O) Oxygen(release func()) {
w.oSlots <- struct{}{}
defer func() { <-w.oSlots }()
release()
w.molecule.Await()
}
func main() {
w := NewH2O()
var wg sync.WaitGroup
for _, c := range "OOHHHHHHO" { // 6 H, 3 O, arriving in a scrambled order
wg.Add(1)
go func(c rune) {
defer wg.Done()
if c == 'H' {
w.Hydrogen(func() { fmt.Print("H") })
} else {
w.Oxygen(func() { fmt.Print("O") })
}
}(c)
}
wg.Wait()
fmt.Println()
}
Why it is correct.
- Admission: at most 2 H and 1 O hold slots at any time, so at most three atoms can be printing or waiting at the barrier.
- Composition: the barrier needs three parties, and only three slots exist (2 H + 1 O). So the three threads at the barrier are always exactly
HHO. - Grouping: slots are given back only after the barrier trips, and it trips only after all three have printed. So no atom of molecule k+1 can print before every atom of molecule k has printed.
- Generation counter (Go): without it, a fast thread from the next round could increment
countbefore a slow waiter from this round wakes, and the slow waiter would then sleep forever. Each waiter remembers the generation it arrived in and waits for that generation to end, not forcountto reach some value. - Monitor version: it meets the output rule (every block of three is valid) but threads don't wait for their partners. Say this out loud. Some interviewers accept it, others want the barrier.
Follow-ups.
- What if the input has the wrong ratio, e.g. 3 H and 0 O? The H threads block forever. Real systems would add a timeout (
await(timeout, unit)) and break the barrier. - Make it work for any molecule (C₂H₆O)? One semaphore per element, sized to its count, and a barrier sized to the total number of atoms.
5. Fizz Buzz Multithreaded
Problem. Four threads share an object built with n. For each i from 1 to n, exactly one thread prints: fizz() prints "fizz" when i is divisible by 3 but not by 5, buzz() prints "buzz" when divisible by 5 but not by 3, fizzbuzz() prints "fizzbuzz" when divisible by 15, and number() prints i otherwise. The output must be in order.
What makes it tricky. Four threads, a shared counter, and an owner for each step that depends on the data. The usual bug is termination: three threads are waiting for their next turn when i passes n, and if nobody wakes them they never return.
Key idea. Either (a) a monitor where each thread waits for "i is mine, or i > n", using notifyAll after each step; or (b) number() acts as dispatcher with a semaphore per worker, where each worker computes in advance how many times it will print.
import java.util.function.IntConsumer;
import java.util.function.IntPredicate;
class FizzBuzz {
private final int n;
private int i = 1; // guarded by "this"
public FizzBuzz(int n) { this.n = n; }
public void fizz(Runnable printFizz) throws InterruptedException {
loop(k -> k % 3 == 0 && k % 5 != 0, k -> printFizz.run());
}
public void buzz(Runnable printBuzz) throws InterruptedException {
loop(k -> k % 5 == 0 && k % 3 != 0, k -> printBuzz.run());
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
loop(k -> k % 15 == 0, k -> printFizzBuzz.run());
}
public void number(IntConsumer printNumber) throws InterruptedException {
loop(k -> k % 3 != 0 && k % 5 != 0, printNumber);
}
private synchronized void loop(IntPredicate mine, IntConsumer action) throws InterruptedException {
while (true) {
while (i <= n && !mine.test(i)) wait();
if (i > n) return; // done: the last notifyAll wakes everyone
action.accept(i);
i++;
notifyAll();
}
}
}
import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;
class FizzBuzz {
private final int n;
private final Semaphore numTurn = new Semaphore(1);
private final Semaphore fizzTurn = new Semaphore(0);
private final Semaphore buzzTurn = new Semaphore(0);
private final Semaphore fizzBuzzTurn = new Semaphore(0);
public FizzBuzz(int n) { this.n = n; }
public void number(IntConsumer printNumber) throws InterruptedException {
for (int i = 1; i <= n; i++) {
numTurn.acquire();
if (i % 15 == 0) fizzBuzzTurn.release();
else if (i % 3 == 0) fizzTurn.release();
else if (i % 5 == 0) buzzTurn.release();
else { printNumber.accept(i); numTurn.release(); }
}
}
public void fizz(Runnable printFizz) throws InterruptedException {
for (int i = 3; i <= n; i += 3) {
if (i % 5 == 0) continue; // that one belongs to fizzbuzz
fizzTurn.acquire();
printFizz.run();
numTurn.release();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
for (int i = 5; i <= n; i += 5) {
if (i % 3 == 0) continue;
buzzTurn.acquire();
printBuzz.run();
numTurn.release();
}
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
for (int i = 15; i <= n; i += 15) {
fizzBuzzTurn.acquire();
printFizzBuzz.run();
numTurn.release();
}
}
}
from threading import Condition
from typing import Callable
class FizzBuzz:
def __init__(self, n: int) -> None:
self.n = n
self.i = 1
self.cv = Condition()
def _loop(self, mine: Callable[[int], bool], action: Callable[[int], None]) -> None:
with self.cv:
while True:
self.cv.wait_for(lambda: self.i > self.n or mine(self.i))
if self.i > self.n:
return
action(self.i)
self.i += 1
self.cv.notify_all()
def fizz(self, printFizz: Callable[[], None]) -> None:
self._loop(lambda k: k % 3 == 0 and k % 5 != 0, lambda k: printFizz())
def buzz(self, printBuzz: Callable[[], None]) -> None:
self._loop(lambda k: k % 5 == 0 and k % 3 != 0, lambda k: printBuzz())
def fizzbuzz(self, printFizzBuzz: Callable[[], None]) -> None:
self._loop(lambda k: k % 15 == 0, lambda k: printFizzBuzz())
def number(self, printNumber: Callable[[int], None]) -> None:
self._loop(lambda k: k % 3 != 0 and k % 5 != 0, printNumber)
package main
import (
"fmt"
"strconv"
"sync"
)
type FizzBuzz struct {
n, i int
mu sync.Mutex
cond *sync.Cond
}
func NewFizzBuzz(n int) *FizzBuzz {
fb := &FizzBuzz{n: n, i: 1}
fb.cond = sync.NewCond(&fb.mu)
return fb
}
func (fb *FizzBuzz) loop(mine func(int) bool, action func(int)) {
fb.mu.Lock()
defer fb.mu.Unlock()
for {
for fb.i <= fb.n && !mine(fb.i) {
fb.cond.Wait()
}
if fb.i > fb.n {
return
}
action(fb.i)
fb.i++
fb.cond.Broadcast()
}
}
func (fb *FizzBuzz) Fizz(p func()) { fb.loop(func(k int) bool { return k%3 == 0 && k%5 != 0 }, func(int) { p() }) }
func (fb *FizzBuzz) Buzz(p func()) { fb.loop(func(k int) bool { return k%5 == 0 && k%3 != 0 }, func(int) { p() }) }
func (fb *FizzBuzz) FizzBuzz(p func()) { fb.loop(func(k int) bool { return k%15 == 0 }, func(int) { p() }) }
func (fb *FizzBuzz) Number(p func(int)) {
fb.loop(func(k int) bool { return k%3 != 0 && k%5 != 0 }, p)
}
func main() {
fb := NewFizzBuzz(15)
var wg sync.WaitGroup
wg.Add(4)
go func() { defer wg.Done(); fb.Fizz(func() { fmt.Print("fizz ") }) }()
go func() { defer wg.Done(); fb.Buzz(func() { fmt.Print("buzz ") }) }()
go func() { defer wg.Done(); fb.FizzBuzz(func() { fmt.Print("fizzbuzz ") }) }()
go func() { defer wg.Done(); fb.Number(func(k int) { fmt.Print(strconv.Itoa(k) + " ") }) }()
wg.Wait()
fmt.Println()
}
Why it is correct.
- Exactly one owner per
i: the four predicates partition the integers, so exactly one thread passes the wait for any giveni. - Monitor termination: the thread that prints
nincrementsiton + 1and callsnotifyAll. Every waiter wakes, seesi > n, and returns. Without thei <= n &&part in the wait condition, the other three would sleep forever. This is the bug interviewers look for. - Dispatcher termination: each worker's loop runs exactly as many times as
numberreleases its semaphore (count the multiples), so everyacquireis matched. - Trade-off: the monitor wakes all four threads at every step (a "thundering herd" of 3 useless wake-ups). The dispatcher wakes exactly one thread. For n = 10⁶ the dispatcher is noticeably faster.
Follow-ups.
- Which version scales to K rule-threads? The dispatcher, using one semaphore per rule. With the monitor, cost per step grows with K.
- Remove the dispatcher? You could use one
Conditionper role with a singleReentrantLock, and after each step signal only the condition of the next owner, which you can compute fromi + 1.
6. The Dining Philosophers
Problem. Five philosophers sit at a round table with one fork between each pair of neighbours. Implement wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork). It is called from many threads, many times per philosopher. A philosopher must hold both adjacent forks while calling eat. Number the forks so that philosopher p has fork p on the left and fork (p + 1) % 5 on the right. The solution must never deadlock.
What makes it tricky. The obvious code (lock the left fork, then lock the right fork) deadlocks when all five philosophers pick up their left fork at the same moment. That is a perfect circular wait. Wrapping everything in one global lock is correct, but then only one philosopher eats at a time, even though two can eat at once.
Key idea. Break one of the four Coffman conditions. The easiest to break is circular wait: always lock the lower-numbered fork first. Philosopher 4 then reaches for fork 0 before fork 4, so the cycle cannot close. The second option is to let at most four philosophers reach for forks at the same time (a counting semaphore acting as a "doorman"). By pigeonhole, one of the four always gets both forks.
The full theory
Five solutions (resource hierarchy, doorman, Chandy–Misra, asymmetric, monitor with states) and their starvation properties are covered in Classic Synchronization Problems. Here we write the two that interviewers expect.
import java.util.concurrent.locks.ReentrantLock;
class DiningPhilosophers {
private final ReentrantLock[] forks = new ReentrantLock[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
}
public void wantsToEat(int philosopher,
Runnable pickLeftFork, Runnable pickRightFork, Runnable eat,
Runnable putLeftFork, Runnable putRightFork) throws InterruptedException {
int left = philosopher, right = (philosopher + 1) % 5;
ReentrantLock first = forks[Math.min(left, right)];
ReentrantLock second = forks[Math.max(left, right)];
first.lock();
try {
second.lock();
try {
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
} finally {
second.unlock();
}
} finally {
first.unlock();
}
}
}
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.ReentrantLock;
class DiningPhilosophers {
private final ReentrantLock[] forks = new ReentrantLock[5];
private final Semaphore seats = new Semaphore(4); // at most 4 reach for forks
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();
}
public void wantsToEat(int philosopher,
Runnable pickLeftFork, Runnable pickRightFork, Runnable eat,
Runnable putLeftFork, Runnable putRightFork) throws InterruptedException {
ReentrantLock left = forks[philosopher];
ReentrantLock right = forks[(philosopher + 1) % 5];
seats.acquire();
try {
left.lock();
try {
right.lock();
try {
pickLeftFork.run();
pickRightFork.run();
eat.run();
putLeftFork.run();
putRightFork.run();
} finally {
right.unlock();
}
} finally {
left.unlock();
}
} finally {
seats.release();
}
}
}
from threading import Lock
from typing import Callable
class DiningPhilosophers:
def __init__(self) -> None:
self.forks = [Lock() for _ in range(5)]
def wantsToEat(self, philosopher: int,
pickLeftFork: Callable[[], None], pickRightFork: Callable[[], None],
eat: Callable[[], None],
putLeftFork: Callable[[], None], putRightFork: Callable[[], None]) -> None:
left, right = philosopher, (philosopher + 1) % 5
first, second = sorted((left, right))
with self.forks[first], self.forks[second]:
pickLeftFork()
pickRightFork()
eat()
putLeftFork()
putRightFork()
package main
import (
"fmt"
"sync"
)
type DiningPhilosophers struct {
forks [5]sync.Mutex
}
func (d *DiningPhilosophers) WantsToEat(p int, pickLeft, pickRight, eat, putLeft, putRight func()) {
left, right := p, (p+1)%5
first, second := min(left, right), max(left, right)
d.forks[first].Lock()
defer d.forks[first].Unlock()
d.forks[second].Lock()
defer d.forks[second].Unlock()
pickLeft()
pickRight()
eat()
putLeft()
putRight()
}
func main() {
var d DiningPhilosophers
var mu sync.Mutex
meals := [5]int{}
var wg sync.WaitGroup
for p := 0; p < 5; p++ {
wg.Add(1)
go func(p int) {
defer wg.Done()
for i := 0; i < 1000; i++ {
noop := func() {}
d.WantsToEat(p, noop, noop, func() { mu.Lock(); meals[p]++; mu.Unlock() }, noop, noop)
}
}(p)
}
wg.Wait()
fmt.Println(meals) // [1000 1000 1000 1000 1000], and no deadlock
}
Why it is correct.
- Mutual exclusion on forks: each fork is a lock, so two neighbours never hold the same fork.
- No deadlock (ordering): every thread acquires locks in increasing index order. A cycle in the wait-for graph would need some thread holding a higher-numbered lock while waiting for a lower one, and that never happens.
- No deadlock (doorman): with at most 4 philosophers competing for 5 forks, at least one philosopher can get both forks, eat, and release them.
- Release always happens: nested
try/finallyin Java,within Python anddeferin Go release the forks even ifeatthrows. This matters: a leaked lock is a deadlock waiting to happen. - Concurrency is preserved: non-adjacent philosophers (for example 0 and 2) eat at the same time.
Follow-ups.
- Is it starvation-free?
ReentrantLockandsync.Mutexare not fair by default, so in theory a philosopher can lose every race.new ReentrantLock(true)gives FIFO handoff at a throughput cost. Chandy–Misra is the classic starvation-free algorithm. - Use
tryLockinstead? Lock left, thentryLockright; if that fails, release left and retry after a random back-off. This avoids deadlock but allows livelock if everyone backs off in lockstep, so the back-off must be randomised. - What does this teach about real systems? Database row locks taken in a consistent key order: see Deadlocks.
7. Web Crawler Multithreaded
Problem. You are given a start URL and an HtmlParser whose getUrls(url) is slow (it blocks on the network). Return every URL reachable from the start URL that has the same hostname, fetching pages in parallel. Each URL must be fetched at most once.
What makes it tricky. Three things at once:
- The visited set is checked and updated by many threads. "Check, then add" must be one atomic step, or two threads will both crawl the same page.
- Bounded parallelism. One thread per URL falls over on a site with 100,000 pages. You need a fixed pool.
- Termination detection. The hard one. "The queue is empty" does not mean the crawl is done, because a worker that is still fetching may be about to add 50 new URLs. You are done only when the queue is empty and no task is in flight.
Key idea. Keep a counter of outstanding tasks. Increment it before submitting a task and decrement it after the task has submitted all of its children. The counter can only reach zero when no work exists and none can appear. Alternatively, let one coordinator thread own all the state and have workers only fetch.
flowchart TD
S["Start URL"] --> V{"visited.add url succeeds?"}
V -- "no" --> X["Skip"]
V -- "yes" --> I["pending++ then submit"]
I --> W["Worker fetches getUrls"]
W --> C["For each same-host child, try visited.add"]
C --> D["pending--"]
D --> Z{"pending == 0?"}
Z -- "yes" --> DONE["Signal done"]
Z -- "no" --> WAIT["Other tasks still running"]
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
interface HtmlParser {
List<String> getUrls(String url);
}
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
return new Crawler(startUrl, htmlParser, 8).run();
}
}
class Crawler {
private final String host;
private final HtmlParser parser;
private final ExecutorService pool;
private final Set<String> visited = ConcurrentHashMap.newKeySet();
private final AtomicInteger pending = new AtomicInteger();
private final CountDownLatch done = new CountDownLatch(1);
private final String startUrl;
Crawler(String startUrl, HtmlParser parser, int threads) {
this.startUrl = startUrl;
this.parser = parser;
this.host = hostOf(startUrl);
this.pool = Executors.newFixedThreadPool(threads);
}
List<String> run() {
visited.add(startUrl);
schedule(startUrl);
try {
done.await();
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} finally {
pool.shutdownNow();
}
return new ArrayList<>(visited);
}
private void schedule(String url) {
pending.incrementAndGet(); // BEFORE submit
pool.execute(() -> {
try {
for (String next : parser.getUrls(url)) {
// add() is the atomic check-and-insert
if (hostOf(next).equals(host) && visited.add(next)) schedule(next);
}
} finally {
if (pending.decrementAndGet() == 0) done.countDown();
}
});
}
static String hostOf(String url) {
int start = url.indexOf("//") + 2;
int end = url.indexOf('/', start);
return end == -1 ? url.substring(start) : url.substring(start, end);
}
}
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
interface HtmlParser {
List<String> getUrls(String url);
}
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = hostOf(startUrl);
Set<String> visited = new HashSet<>(); // touched only by this thread
visited.add(startUrl);
List<String> frontier = List.of(startUrl);
ExecutorService pool = Executors.newFixedThreadPool(8);
try {
while (!frontier.isEmpty()) {
List<Callable<List<String>>> tasks = new ArrayList<>();
for (String url : frontier) tasks.add(() -> htmlParser.getUrls(url));
List<String> nextFrontier = new ArrayList<>();
for (Future<List<String>> f : pool.invokeAll(tasks)) { // waits for the whole level
for (String next : f.get()) {
if (hostOf(next).equals(host) && visited.add(next)) nextFrontier.add(next);
}
}
frontier = nextFrontier;
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
} catch (ExecutionException e) {
throw new RuntimeException(e.getCause());
} finally {
pool.shutdownNow();
}
return new ArrayList<>(visited);
}
static String hostOf(String url) {
int start = url.indexOf("//") + 2;
int end = url.indexOf('/', start);
return end == -1 ? url.substring(start) : url.substring(start, end);
}
}
from concurrent.futures import FIRST_COMPLETED, ThreadPoolExecutor, wait
from typing import List
from urllib.parse import urlsplit
class HtmlParser:
def getUrls(self, url: str) -> List[str]:
raise NotImplementedError
class Solution:
def crawl(self, startUrl: str, htmlParser: HtmlParser) -> List[str]:
host = urlsplit(startUrl).hostname
visited = {startUrl} # owned by this (coordinator) thread only
with ThreadPoolExecutor(max_workers=8) as pool:
pending = {pool.submit(htmlParser.getUrls, startUrl)}
while pending: # termination: nothing in flight
done, pending = wait(pending, return_when=FIRST_COMPLETED)
for fut in done:
for url in fut.result():
if url not in visited and urlsplit(url).hostname == host:
visited.add(url)
pending.add(pool.submit(htmlParser.getUrls, url))
return list(visited)
package main
import (
"fmt"
"net/url"
"sort"
)
type HtmlParser interface {
GetUrls(u string) []string
}
func hostOf(raw string) string {
u, err := url.Parse(raw)
if err != nil {
return ""
}
return u.Hostname()
}
// Crawl runs `workers` fetchers. The calling goroutine is the coordinator:
// it alone touches visited/queue/inFlight, so they need no lock.
func Crawl(start string, parser HtmlParser, workers int) []string {
host := hostOf(start)
jobs := make(chan string)
results := make(chan []string)
for i := 0; i < workers; i++ {
go func() {
for u := range jobs {
results <- parser.GetUrls(u)
}
}()
}
visited := map[string]bool{start: true}
queue := []string{start}
inFlight := 0
for len(queue) > 0 || inFlight > 0 {
var send chan string // nil channel: that select case is disabled
var next string
if len(queue) > 0 {
send, next = jobs, queue[0]
}
select {
case send <- next:
queue = queue[1:]
inFlight++
case urls := <-results:
inFlight--
for _, u := range urls {
if !visited[u] && hostOf(u) == host {
visited[u] = true
queue = append(queue, u)
}
}
}
}
close(jobs) // workers are idle in `range jobs` now, so this ends them
out := make([]string, 0, len(visited))
for u := range visited {
out = append(out, u)
}
return out
}
type fakeParser map[string][]string
func (f fakeParser) GetUrls(u string) []string { return f[u] }
func main() {
web := fakeParser{
"http://news.example.com/": {"http://news.example.com/a", "http://other.com/x"},
"http://news.example.com/a": {"http://news.example.com/b", "http://news.example.com/"},
"http://news.example.com/b": {"http://news.example.com/a"},
}
got := Crawl("http://news.example.com/", web, 4)
sort.Strings(got)
fmt.Println(got)
}
Why it is correct.
- Each URL is fetched at most once. In Java,
ConcurrentHashMap.newKeySet().add()is an atomic test-and-set, so only the thread that seestrueschedules the URL. In Python and Go only the coordinator ever touchesvisited, so no other thread can race on it. - Termination (pending counter): a parent finishes all its
schedule(child)calls, each of which increments first, before it decrements itself. Sopendingcannot hit zero while a child is still waiting to run. When it does hit zero, no task exists and none can be created. - Termination (coordinator): the loop ends only when the queue is empty and
inFlight == 0. In Go thenil-channel trick turns off the send case when the queue is empty. Without it you would block sending to busy workers while those workers block sending results back to you, and each side would wait on the other forever. - Bounded: the pool size fixes concurrency at 8 (or
workers), however large the site. - Level-by-level BFS: simpler termination (an empty frontier), but a slow page holds up the whole level. That is the trade-off to mention.
Follow-ups.
- Rate-limit requests per host? Give each host a token bucket. See the thread-safe rate limiter below and Build a Rate Limiter.
- Crawl across many machines? Partition URLs by
hash(host)so one machine owns each host's visited set and politeness rules. Replace the in-memory set with a Bloom filter or a key-value store. - Cancellation and timeouts? Wrap each fetch with a deadline. In Go pass a
context.Contextdown to the fetch. In Java useFuture.get(timeout)orCompletableFuture.orTimeout. - Why not one thread per URL? Memory per thread (around 1 MB of stack for a platform thread) and contention. Java 21 virtual threads make "one per task" reasonable again, but you still need to cap the number of concurrent requests.
8. Design a Bounded Blocking Queue
Problem. Implement a thread-safe FIFO queue with a fixed capacity. enqueue(x) blocks while the queue is full, dequeue() blocks while it is empty, and size() returns the current number of elements. Many producers and consumers call it at the same time.
What makes it tricky. This is producer-consumer in its purest form, and it collects every classic mistake: if instead of while, a single condition used for two different predicates combined with signal(), and forgetting to unlock when an exception is thrown.
Key idea. One lock and two conditions with separate predicates: notFull (producers wait on it) and notEmpty (consumers wait on it). Every state change signals the side that might now be able to proceed.
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
class BoundedBlockingQueue {
private final int capacity;
private final Deque<Integer> items = new ArrayDeque<>();
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
public BoundedBlockingQueue(int capacity) { this.capacity = capacity; }
public void enqueue(int element) throws InterruptedException {
lock.lock();
try {
while (items.size() == capacity) notFull.await();
items.addLast(element);
notEmpty.signal(); // one item added, so one consumer can proceed
} finally {
lock.unlock();
}
}
public int dequeue() throws InterruptedException {
lock.lock();
try {
while (items.isEmpty()) notEmpty.await();
int x = items.removeFirst();
notFull.signal(); // one slot freed, so one producer can proceed
return x;
} finally {
lock.unlock();
}
}
public int size() {
lock.lock();
try {
return items.size();
} finally {
lock.unlock();
}
}
}
import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.Semaphore;
class BoundedBlockingQueue {
private final Semaphore freeSlots;
private final Semaphore filledSlots = new Semaphore(0);
private final ConcurrentLinkedDeque<Integer> items = new ConcurrentLinkedDeque<>();
public BoundedBlockingQueue(int capacity) { freeSlots = new Semaphore(capacity); }
public void enqueue(int element) throws InterruptedException {
freeSlots.acquire(); // reserve a slot
items.addLast(element); // thread-safe deque
filledSlots.release(); // publish the item
}
public int dequeue() throws InterruptedException {
filledSlots.acquire(); // there is now guaranteed to be an item
int x = items.pollFirst();
freeSlots.release();
return x;
}
public int size() {
return items.size(); // O(n) and only a snapshot, fine for monitoring
}
}
from collections import deque
from threading import Condition, Lock
class BoundedBlockingQueue:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.items: deque = deque()
lock = Lock()
self.not_full = Condition(lock) # both conditions share ONE lock
self.not_empty = Condition(lock)
def enqueue(self, element: int) -> None:
with self.not_full:
self.not_full.wait_for(lambda: len(self.items) < self.capacity)
self.items.append(element)
self.not_empty.notify()
def dequeue(self) -> int:
with self.not_empty:
self.not_empty.wait_for(lambda: len(self.items) > 0)
x = self.items.popleft()
self.not_full.notify()
return x
def size(self) -> int:
with self.not_full:
return len(self.items)
package main
import (
"fmt"
"sync"
)
// In Go, a buffered channel IS a bounded blocking queue.
type BoundedBlockingQueue struct {
ch chan int
}
func NewBoundedBlockingQueue(capacity int) *BoundedBlockingQueue {
return &BoundedBlockingQueue{ch: make(chan int, capacity)}
}
func (q *BoundedBlockingQueue) Enqueue(x int) { q.ch <- x } // blocks when full
func (q *BoundedBlockingQueue) Dequeue() int { return <-q.ch } // blocks when empty
func (q *BoundedBlockingQueue) Size() int { return len(q.ch) }
func main() {
q := NewBoundedBlockingQueue(2)
var wg sync.WaitGroup
for p := 0; p < 3; p++ {
wg.Add(1)
go func(p int) {
defer wg.Done()
for i := 0; i < 5; i++ {
q.Enqueue(p*100 + i)
}
}(p)
}
sum := 0
for i := 0; i < 15; i++ {
sum += q.Dequeue()
}
wg.Wait()
fmt.Println(sum, q.Size()) // 1530 0
}
Why it is correct.
- Safety: all access to
itemshappens under the lock (or through a thread-safe deque in the semaphore version), and the size invariant0 <= size <= capacityis checked under the same lock that changes it. - No lost wake-ups: a waiter re-checks the predicate in a
whileloop under the lock, so a signal sent before it started waiting doesn't matter, because the predicate is already true. - Why
signal()and notsignalAll()is safe here: each condition has exactly one predicate. All its waiters wait for the same thing, and one state change (one item or one slot) satisfies exactly one of them. If you used a single condition for both "not full" and "not empty",signal()could wake a producer when a consumer was needed, and you would be back to the lost-wake-up hang. In that case you would needsignalAll(). - Semaphore version:
freeSlots + filledSlots + (operations in progress) == capacity. A dequeuer who has acquiredfilledSlotsis guaranteed that an item has already been added (the add happens before the release), sopollFirst()never returnsnull.
Follow-ups.
- Add
offer(x, timeout)? UsenotFull.awaitNanos(remaining)in the loop and returnfalsewhen the time runs out. In Go useselectwithtime.After. - Is a single lock a bottleneck?
LinkedBlockingQueueuses two locks (aputLockand atakeLock) and an atomic count, so producers and consumers don't block each other.ArrayBlockingQueueuses one lock, as above. - Support closing the queue? Add a
closedflag. Waiters checkwhile (empty && !closed), andclose()callssignalAllon both conditions. In Go,close(ch)plusv, ok := <-ch.
9. Traffic Light Controlled Intersection
Problem. Two roads cross: road A (directions 1 and 2) and road B (directions 3 and 4). There is one traffic light, green for road A at the start. Cars arrive on their own threads and call carArrived(carId, roadId, direction, turnGreen, crossCar). A car may cross only when its road is green. If it is not, the car must call turnGreen first. Calling turnGreen when the light is already green for that road is not allowed, and cars from both roads must never be in the intersection at the same time.
What makes it tricky. Almost nothing, and that is the trap. Candidates over-engineer it with semaphores per road. The intended answer is one mutex around "fix the light if needed, then cross". The discussion afterwards is where the interview really happens: what if cars on the same road could cross at the same time?
Key idea. The light colour and the act of crossing must be updated and done atomically together. A single lock makes "check light, maybe flip it, cross" one critical section.
class TrafficLight {
private int greenRoad = 1; // guarded by "this"
public synchronized void carArrived(int carId, int roadId, int direction,
Runnable turnGreen, Runnable crossCar) {
if (greenRoad != roadId) { // "if" is right here: we never wait
turnGreen.run();
greenRoad = roadId;
}
crossCar.run();
}
}
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
// Follow-up version: cars on the green road cross concurrently. The light
// may switch only when the intersection is empty (readers-writers shape).
class TrafficLight {
private final ReentrantLock lock = new ReentrantLock();
private final Condition empty = lock.newCondition();
private int greenRoad = 1;
private int crossing = 0; // cars currently in the intersection
public void carArrived(int carId, int roadId, int direction,
Runnable turnGreen, Runnable crossCar) throws InterruptedException {
lock.lock();
try {
while (greenRoad != roadId && crossing > 0) empty.await();
if (greenRoad != roadId) {
turnGreen.run();
greenRoad = roadId;
}
crossing++;
} finally {
lock.unlock();
}
try {
crossCar.run(); // outside the lock, so cars overlap
} finally {
lock.lock();
try {
if (--crossing == 0) empty.signalAll();
} finally {
lock.unlock();
}
}
}
}
from threading import Lock
from typing import Callable
class TrafficLight:
def __init__(self) -> None:
self.green_road = 1
self.lock = Lock()
def carArrived(self, carId: int, roadId: int, direction: int,
turnGreen: Callable[[], None], crossCar: Callable[[], None]) -> None:
with self.lock:
if self.green_road != roadId:
turnGreen()
self.green_road = roadId
crossCar()
package main
import (
"fmt"
"sync"
)
type TrafficLight struct {
mu sync.Mutex
greenRoad int
}
func NewTrafficLight() *TrafficLight { return &TrafficLight{greenRoad: 1} }
func (t *TrafficLight) CarArrived(carID, roadID, direction int, turnGreen, crossCar func()) {
t.mu.Lock()
defer t.mu.Unlock()
if t.greenRoad != roadID {
turnGreen()
t.greenRoad = roadID
}
crossCar()
}
func main() {
t := NewTrafficLight()
var wg sync.WaitGroup
for car := 1; car <= 6; car++ {
wg.Add(1)
go func(car int) {
defer wg.Done()
road := 1 + car%2
t.CarArrived(car, road, 0,
func() { fmt.Printf("light -> road %d\n", road) },
func() { fmt.Printf("car %d crosses on road %d\n", car, road) })
}(car)
}
wg.Wait()
}
Why it is correct.
- Basic version: the lock serialises every car, so no two cars are ever in the intersection together, and
turnGreenis only called when the colour is actually wrong. Anifis right here (not awhile) because the thread never waits. It just fixes the state and goes on. - Concurrent version:
crossingcounts the cars inside the intersection. A car from the red road waits untilcrossing == 0, so the light flips only when the intersection is empty. Once it flips, any newly arriving car from the old road seesgreenRoad != roadId && crossing > 0and waits. This is the "lightswitch" pattern from readers-writers.
Follow-ups.
- Starvation in the concurrent version? A steady stream of road-A cars keeps
crossing > 0, so road B waits forever. Fix it by counting waiting cars per road and refusing new entries to the green road while the other road has waiters (writer-preference), or by switching after a maximum batch size. - Make it fair (FIFO)?
new ReentrantLock(true)in the basic version.
10. Bonus Classics Interviewers Ask
These don't appear on the usual practice lists, but they come up all the time in real interviews, often as the "build it yourself" follow-up to one of the problems above.
Thread-Safe Singleton
Problem. Create an instance lazily on first use, exactly once, even when many threads ask for it at the same moment, and without taking a lock on every call.
What makes it tricky. Double-checked locking (DCL) looks obviously right and is broken in Java unless the field is volatile. instance = new Config() is really three steps: allocate memory, run the constructor, publish the reference. The JIT and the CPU may reorder the last two. Another thread can then see a non-null instance on the first, unlocked check and use an object whose constructor hasn't finished. volatile forbids that reordering and gives a happens-before edge from the write to every later read.
import java.util.Map;
final class Config {
private static volatile Config instance; // volatile is NOT optional
private final Map<String, String> values;
private Config() { values = Map.of("region", "eu-west-1"); }
static Config getInstance() {
Config local = instance; // one volatile read on the fast path
if (local == null) {
synchronized (Config.class) {
local = instance; // second check, under the lock
if (local == null) {
instance = local = new Config();
}
}
}
return local;
}
String get(String key) { return values.get(key); }
}
import java.util.Map;
final class Config {
private final Map<String, String> values;
private Config() { values = Map.of("region", "eu-west-1"); }
// The JVM initialises Holder lazily, on first access, and class
// initialisation is guaranteed to be thread-safe. No locks, no volatile.
private static final class Holder {
static final Config INSTANCE = new Config();
}
static Config getInstance() { return Holder.INSTANCE; }
String get(String key) { return values.get(key); }
}
import threading
class Config:
_instance = None
_lock = threading.Lock()
def __init__(self) -> None:
self.values = {"region": "eu-west-1"}
@classmethod
def instance(cls) -> "Config":
if cls._instance is None: # fast path, no lock
with cls._lock:
if cls._instance is None: # second check, under the lock
cls._instance = cls()
return cls._instance
# Idiomatic Python: a module-level object. Imports run once per process,
# under the import lock.
package main
import (
"fmt"
"sync"
)
type Config struct{ values map[string]string }
var (
instance *Config
once sync.Once
)
func GetConfig() *Config {
once.Do(func() { // runs exactly once; every caller waits until it finishes
instance = &Config{values: map[string]string{"region": "eu-west-1"}}
})
return instance
}
func main() {
var wg sync.WaitGroup
for i := 0; i < 10; i++ {
wg.Add(1)
go func() { defer wg.Done(); _ = GetConfig() }()
}
wg.Wait()
fmt.Println(GetConfig().values["region"], GetConfig() == GetConfig())
}
What to say in the interview
"I'd use the holder idiom or an enum singleton in Java, and sync.Once in Go. If you want DCL, the field has to be volatile because of reordering during publication. Without it a thread can see a half-built object." The local variable is a small optimisation: it reads the volatile field once on the fast path instead of twice.
Implement a CountDownLatch and a Cyclic Barrier
Problem. Build a latch (countDown(), await() blocks until the count reaches 0) and a reusable barrier (await() blocks until parties threads have arrived, then all are released and the barrier resets) using only a mutex and a condition variable.
What makes it tricky. The latch is simple. The barrier has a famous bug: if waiters wait on while (count < parties), the last arriving thread resets count to 0 for the next round, and the waiters wake up, see 0 < parties, and sleep forever. The fix is a generation counter: each waiter waits for its generation to end.
class SimpleLatch {
private int count; // guarded by "this"
SimpleLatch(int count) {
if (count < 0) throw new IllegalArgumentException("count < 0");
this.count = count;
}
public synchronized void countDown() {
if (count > 0 && --count == 0) notifyAll();
}
public synchronized void await() throws InterruptedException {
while (count > 0) wait();
}
}
class SimpleBarrier {
private final int parties;
private int arrived = 0;
private long generation = 0; // both guarded by "this"
SimpleBarrier(int parties) { this.parties = parties; }
public synchronized void await() throws InterruptedException {
long myGeneration = generation;
if (++arrived == parties) { // last one in: release everyone, reset
arrived = 0;
generation++;
notifyAll();
return;
}
while (myGeneration == generation) wait();
}
}
from threading import Condition
class SimpleLatch:
def __init__(self, count: int) -> None:
if count < 0:
raise ValueError("count < 0")
self.count = count
self.cv = Condition()
def count_down(self) -> None:
with self.cv:
if self.count > 0:
self.count -= 1
if self.count == 0:
self.cv.notify_all()
def wait(self) -> None:
with self.cv:
self.cv.wait_for(lambda: self.count == 0)
class SimpleBarrier:
def __init__(self, parties: int) -> None:
self.parties = parties
self.arrived = 0
self.generation = 0
self.cv = Condition()
def wait(self) -> None:
with self.cv:
gen = self.generation
self.arrived += 1
if self.arrived == self.parties:
self.arrived = 0
self.generation += 1
self.cv.notify_all()
return
self.cv.wait_for(lambda: self.generation != gen)
package main
import (
"fmt"
"sync"
)
type Latch struct {
mu sync.Mutex
cond *sync.Cond
count int
}
func NewLatch(n int) *Latch {
l := &Latch{count: n}
l.cond = sync.NewCond(&l.mu)
return l
}
func (l *Latch) CountDown() {
l.mu.Lock()
defer l.mu.Unlock()
if l.count > 0 {
l.count--
if l.count == 0 {
l.cond.Broadcast()
}
}
}
func (l *Latch) Await() {
l.mu.Lock()
defer l.mu.Unlock()
for l.count > 0 {
l.cond.Wait()
}
}
func main() {
ready := NewLatch(3)
for i := 0; i < 3; i++ {
go func(i int) { fmt.Println("worker", i, "ready"); ready.CountDown() }(i)
}
ready.Await()
fmt.Println("all workers ready")
// For the barrier, see the Barrier type in the H2O solution above.
}
Follow-ups. How does await handle interruption? The real CyclicBarrier marks the barrier broken and wakes everyone with BrokenBarrierException, so that one dead party doesn't leave the rest hanging. Why not sync.WaitGroup in Go? It is a latch (with Add/Done/Wait), and it is the right choice in real code. The point of the exercise is to build one.
Thread-Safe Rate Limiter
Problem. Implement tryAcquire() that returns true at most rate times per second on average, allows bursts up to capacity, and is safe to call from many threads.
What makes it tricky. Refilling tokens and taking one must be a single atomic step. A version that refills in one locked section and takes in another lets two threads both see one token and both take it. Also, don't use a background thread that adds tokens every tick: calculate refills lazily from elapsed time.
class TokenBucket {
private final double capacity;
private final double refillPerNano;
private double tokens; // guarded by "this"
private long lastRefill; // guarded by "this"
TokenBucket(double capacity, double ratePerSecond) {
this.capacity = capacity;
this.refillPerNano = ratePerSecond / 1_000_000_000.0;
this.tokens = capacity;
this.lastRefill = System.nanoTime(); // monotonic, unlike currentTimeMillis
}
public synchronized boolean tryAcquire() {
long now = System.nanoTime();
tokens = Math.min(capacity, tokens + (now - lastRefill) * refillPerNano);
lastRefill = now;
if (tokens >= 1.0) {
tokens -= 1.0;
return true;
}
return false;
}
}
import threading
import time
class TokenBucket:
def __init__(self, capacity: float, rate_per_second: float) -> None:
self.capacity = capacity
self.rate = rate_per_second
self.tokens = capacity
self.last = time.monotonic()
self.lock = threading.Lock()
def try_acquire(self) -> bool:
with self.lock:
now = time.monotonic()
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
package main
import (
"fmt"
"sync"
"time"
)
type TokenBucket struct {
mu sync.Mutex
capacity float64
rate float64 // tokens per second
tokens float64
last time.Time
}
func NewTokenBucket(capacity, rate float64) *TokenBucket {
return &TokenBucket{capacity: capacity, rate: rate, tokens: capacity, last: time.Now()}
}
func (b *TokenBucket) TryAcquire() bool {
b.mu.Lock()
defer b.mu.Unlock()
now := time.Now() // carries a monotonic reading, so Sub is safe
b.tokens = min(b.capacity, b.tokens+now.Sub(b.last).Seconds()*b.rate)
b.last = now
if b.tokens >= 1 {
b.tokens--
return true
}
return false
}
func main() {
b := NewTokenBucket(5, 1)
var mu sync.Mutex
allowed := 0
var wg sync.WaitGroup
for i := 0; i < 100; i++ {
wg.Add(1)
go func() {
defer wg.Done()
if b.TryAcquire() {
mu.Lock()
allowed++
mu.Unlock()
}
}()
}
wg.Wait()
fmt.Println("allowed:", allowed) // 5: the burst capacity
}
Follow-ups. Blocking acquire()? Work out how long until the next token arrives, then sleep outside the lock and retry. Lock-free? Pack the token count and timestamp into one AtomicLong and update it in a CAS loop. Across servers? An atomic Redis Lua script, as covered in Build a Rate Limiter and Distributed Rate Limiting.
Implement a Read-Write Lock
Problem. Many readers may hold the lock together. A writer needs it exclusively. Readers arriving while a writer waits must not starve the writer.
What makes it tricky. The naive version (readers wait only while a writer is active) is correct but writer-starving: a steady stream of readers keeps readers > 0 forever. The fix is to count waiting writers and make new readers defer to them.
class SimpleRWLock {
private int readers = 0; // active readers
private int waitingWriters = 0;
private boolean writing = false; // all guarded by "this"
public synchronized void lockRead() throws InterruptedException {
while (writing || waitingWriters > 0) wait(); // writer preference
readers++;
}
public synchronized void unlockRead() {
if (--readers == 0) notifyAll();
}
public synchronized void lockWrite() throws InterruptedException {
waitingWriters++;
try {
while (writing || readers > 0) wait();
} finally {
waitingWriters--; // also undone if interrupted
}
writing = true;
}
public synchronized void unlockWrite() {
writing = false;
notifyAll(); // wake readers AND writers; they re-check
}
}
from threading import Condition
class RWLock:
def __init__(self) -> None:
self.cv = Condition()
self.readers = 0
self.waiting_writers = 0
self.writing = False
def acquire_read(self) -> None:
with self.cv:
self.cv.wait_for(lambda: not self.writing and self.waiting_writers == 0)
self.readers += 1
def release_read(self) -> None:
with self.cv:
self.readers -= 1
if self.readers == 0:
self.cv.notify_all()
def acquire_write(self) -> None:
with self.cv:
self.waiting_writers += 1
try:
self.cv.wait_for(lambda: not self.writing and self.readers == 0)
finally:
self.waiting_writers -= 1
self.writing = True
def release_write(self) -> None:
with self.cv:
self.writing = False
self.cv.notify_all()
package main
import (
"fmt"
"sync"
)
type RWLock struct {
mu sync.Mutex
cond *sync.Cond
readers int
waitingWriters int
writing bool
}
func NewRWLock() *RWLock {
l := &RWLock{}
l.cond = sync.NewCond(&l.mu)
return l
}
func (l *RWLock) RLock() {
l.mu.Lock()
for l.writing || l.waitingWriters > 0 {
l.cond.Wait()
}
l.readers++
l.mu.Unlock()
}
func (l *RWLock) RUnlock() {
l.mu.Lock()
l.readers--
if l.readers == 0 {
l.cond.Broadcast()
}
l.mu.Unlock()
}
func (l *RWLock) Lock() {
l.mu.Lock()
l.waitingWriters++
for l.writing || l.readers > 0 {
l.cond.Wait()
}
l.waitingWriters--
l.writing = true
l.mu.Unlock()
}
func (l *RWLock) Unlock() {
l.mu.Lock()
l.writing = false
l.cond.Broadcast()
l.mu.Unlock()
}
func main() {
l := NewRWLock()
shared := 0
var wg sync.WaitGroup
for i := 0; i < 50; i++ {
wg.Add(2)
go func() { defer wg.Done(); l.Lock(); shared++; l.Unlock() }()
go func() { defer wg.Done(); l.RLock(); _ = shared; l.RUnlock() }()
}
wg.Wait()
fmt.Println(shared) // 50. In real code, use sync.RWMutex.
}
Follow-ups. Can a reader upgrade to a writer? Not safely in general: two readers that both try to upgrade will deadlock, each waiting for the other to leave. ReentrantReadWriteLock doesn't allow upgrading, but it does allow downgrading (take the read lock while holding the write lock, then release the write lock). Should readers or writers win? It depends on the workload. Mostly-read caches favour readers; a config store whose updates must be applied quickly favours writers. Java's StampedLock adds optimistic reads that take no lock at all.
Print 1 to N with K Threads in Round-Robin
Problem. K threads print the numbers 1 to N in order. Thread 0 prints 1, thread 1 prints 2, …, thread K−1 prints K, thread 0 prints K+1, and so on.
What makes it tricky. The monitor solution (one shared counter, notifyAll) is correct but wakes all K threads for every number, even though only one of them can run. With K = 64 that is 63 wasted context switches per number. The better answer gives each thread its own semaphore and passes a token around a ring.
import java.util.concurrent.Semaphore;
class RoundRobinPrinter {
public static void main(String[] args) throws InterruptedException {
int n = 20, k = 4;
Semaphore[] turn = new Semaphore[k];
for (int i = 0; i < k; i++) turn[i] = new Semaphore(i == 0 ? 1 : 0);
Thread[] threads = new Thread[k];
for (int t = 0; t < k; t++) {
final int id = t;
threads[t] = new Thread(() -> {
try {
for (int x = id + 1; x <= n; x += k) { // the numbers I own
turn[id].acquire();
System.out.println("thread " + id + ": " + x);
turn[(id + 1) % k].release(); // pass the token on
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
});
threads[t].start();
}
for (Thread th : threads) th.join();
}
}
class RoundRobinMonitor {
private final int n, k;
private int next = 1; // guarded by "this"
RoundRobinMonitor(int n, int k) { this.n = n; this.k = k; }
synchronized void run(int id) throws InterruptedException {
while (true) {
while (next <= n && (next - 1) % k != id) wait();
if (next > n) return; // the last increment wakes everyone to exit
System.out.println("thread " + id + ": " + next);
next++;
notifyAll(); // O(K) wake-ups per number
}
}
public static void main(String[] args) throws InterruptedException {
RoundRobinMonitor m = new RoundRobinMonitor(20, 4);
Thread[] ts = new Thread[4];
for (int i = 0; i < 4; i++) {
final int id = i;
ts[i] = new Thread(() -> {
try { m.run(id); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
ts[i].start();
}
for (Thread t : ts) t.join();
}
}
import threading
N, K = 20, 4
turn = [threading.Semaphore(1 if i == 0 else 0) for i in range(K)]
def worker(tid: int) -> None:
for x in range(tid + 1, N + 1, K):
turn[tid].acquire()
print(f"thread {tid}: {x}")
turn[(tid + 1) % K].release()
threads = [threading.Thread(target=worker, args=(i,)) for i in range(K)]
for t in threads:
t.start()
for t in threads:
t.join()
package main
import (
"fmt"
"sync"
)
func main() {
const n, k = 20, 4
turn := make([]chan struct{}, k)
for i := range turn {
turn[i] = make(chan struct{}, 1)
}
turn[0] <- struct{}{}
var wg sync.WaitGroup
for id := 0; id < k; id++ {
wg.Add(1)
go func(id int) {
defer wg.Done()
for x := id + 1; x <= n; x += k {
<-turn[id]
fmt.Printf("goroutine %d: %d\n", id, x)
turn[(id+1)%k] <- struct{}{}
}
}(id)
}
wg.Wait()
}
Why it is correct. Exactly one permit exists in the ring, so exactly one thread prints at a time, and the permit always moves to (id + 1) % k, which owns the next number. Each thread loops over exactly the numbers it owns, so there are as many releases into turn[id] as acquires on it. The last release of all lands in a buffer and is never consumed, which is harmless. (In Go, if the leftover token went to a full buffer the send would block, but the ring only ever holds one token, so the buffer always has room.)
Concurrent LRU Cache
Problem. An LRU cache with get(key) and put(key, value), both O(1), safe under concurrent access.
What makes it tricky. People reach for a read-write lock because "get is a read". It isn't: get moves the entry to the front of the recency list, which is a write to the linked list. With a read lock on get, two readers corrupt the list. The simple correct answer is one exclusive lock around a hash map plus a doubly-linked list.
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReentrantLock;
class LRUCache<K, V> {
private final ReentrantLock lock = new ReentrantLock();
private final LinkedHashMap<K, V> map;
LRUCache(int capacity) {
// accessOrder = true: get() moves the entry to the tail (most recent)
this.map = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
}
public V get(K key) {
lock.lock(); // exclusive: get() changes the order
try {
return map.get(key);
} finally {
lock.unlock();
}
}
public void put(K key, V value) {
lock.lock();
try {
map.put(key, value);
} finally {
lock.unlock();
}
}
}
from collections import OrderedDict
from threading import Lock
from typing import Any, Optional
class LRUCache:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.data: "OrderedDict[Any, Any]" = OrderedDict()
self.lock = Lock()
def get(self, key: Any) -> Optional[Any]:
with self.lock:
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key: Any, value: Any) -> None:
with self.lock:
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False) # evict least recently used
package main
import (
"container/list"
"fmt"
"sync"
)
type entry struct {
key, value string
}
type LRUCache struct {
mu sync.Mutex
capacity int
order *list.List // front = most recent
items map[string]*list.Element
}
func NewLRUCache(capacity int) *LRUCache {
return &LRUCache{capacity: capacity, order: list.New(), items: map[string]*list.Element{}}
}
func (c *LRUCache) Get(key string) (string, bool) {
c.mu.Lock()
defer c.mu.Unlock()
el, ok := c.items[key]
if !ok {
return "", false
}
c.order.MoveToFront(el)
return el.Value.(*entry).value, true
}
func (c *LRUCache) Put(key, value string) {
c.mu.Lock()
defer c.mu.Unlock()
if el, ok := c.items[key]; ok {
el.Value.(*entry).value = value
c.order.MoveToFront(el)
return
}
c.items[key] = c.order.PushFront(&entry{key, value})
if c.order.Len() > c.capacity {
oldest := c.order.Back()
c.order.Remove(oldest)
delete(c.items, oldest.Value.(*entry).key)
}
}
func main() {
c := NewLRUCache(2)
c.Put("a", "1")
c.Put("b", "2")
c.Get("a") // a is now most recent
c.Put("c", "3") // evicts b
_, hasB := c.Get("b")
fmt.Println(hasB) // false
}
Follow-ups. It's a bottleneck at 32 cores. Shard it: N independent caches, choose one with hash(key) % N. LRU then becomes approximate per shard, which is almost always fine. What do production caches do? Caffeine (Java) records accesses in lock-free ring buffers and applies them to the LRU structure in batches under a tryLock, so get almost never blocks. What about a slow loader? Use computeIfAbsent-style single-flight, so that ten threads missing on the same key trigger one load, not ten (see Thundering Herd).
Find the Race
Interviewers show you a short snippet and ask "what's wrong?". Here are the five you are most likely to see. Try each one before opening the answer.
Race 1: check-then-act on a concurrent map.
ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
void record(String word) {
Integer c = counts.get(word);
counts.put(word, c == null ? 1 : c + 1);
}
Solution
Each call is thread-safe on its own, but the get followed by put is not atomic. Two threads read 5 and both write 6, so one increment is lost. A thread-safe collection does not make compound operations atomic. Fix:
counts.merge(word, 1, Integer::sum); // atomic read-modify-write
compute, computeIfAbsent and putIfAbsent are the other atomic compound operations. For heavily contended counters, ConcurrentHashMap<String, LongAdder> with computeIfAbsent(word, k -> new LongAdder()).increment() scales better.
Race 2: the stop flag that never stops.
class Worker implements Runnable {
private boolean running = true;
public void stop() { running = false; }
public void run() {
while (running) {
doWork();
}
}
private void doWork() { /* pure computation, no synchronization */ }
}
Solution
This isn't a data race on a value. It is a visibility problem. Nothing creates a happens-before edge between stop() on one thread and the read in run() on another, so the JIT may hoist the read out of the loop (if (running) while (true) …), and the worker spins forever. Fix: private volatile boolean running = true; (or an AtomicBoolean). Better still, use thread interruption: while (!Thread.currentThread().isInterrupted()).
Race 3: WaitGroup.Add in the wrong place (Go).
var wg sync.WaitGroup
for _, job := range jobs {
go func(j Job) {
wg.Add(1)
defer wg.Done()
process(j)
}(job)
}
wg.Wait()
Solution
wg.Wait() may run before any goroutine has called Add. It sees a counter of 0 and returns at once, while the jobs are still running. Add must happen before the go statement, in the goroutine that will call Wait:
for _, job := range jobs {
wg.Add(1)
go func(j Job) {
defer wg.Done()
process(j)
}(job)
}
wg.Wait()
Run tests with go test -race. The race detector catches this pattern and most of the others on this page.
Race 4: check-then-act on a balance (Python).
import threading
balance = 100
def withdraw(amount: int) -> bool:
global balance
if balance >= amount:
# (any I/O, logging or even a bytecode boundary here)
balance -= amount
return True
return False
threads = [threading.Thread(target=withdraw, args=(80,)) for _ in range(2)]
Solution
Both threads can pass the if before either subtracts, which leaves balance == -60. The GIL does not help: it switches threads between bytecodes, and balance -= amount alone is several bytecodes (load, subtract, store). On free-threaded Python 3.13+ there is no GIL at all. Fix: put the check and the update in the same critical section.
lock = threading.Lock()
def withdraw(amount: int) -> bool:
global balance
with lock:
if balance >= amount:
balance -= amount
return True
return False
In a database the same bug is fixed with UPDATE accounts SET balance = balance - 80 WHERE id = 1 AND balance >= 80 and a check of the row count. See Race Conditions.
Race 5: the lost wake-up.
class Signal {
public synchronized void waitForSignal() throws InterruptedException {
wait();
}
public synchronized void sendSignal() {
notify();
}
}
Solution
If sendSignal() runs before waitForSignal(), the notify goes nowhere, because condition variables have no memory. The waiter then sleeps forever. A spurious wake-up can also return from wait() even though no signal was sent. The fix is the rule from the top of this page: wait on a predicate over state, in a while loop.
class Signal {
private boolean signalled = false;
public synchronized void waitForSignal() throws InterruptedException {
while (!signalled) wait();
signalled = false; // consume it, if it is a one-shot signal
}
public synchronized void sendSignal() {
signalled = true;
notifyAll();
}
}
Or use a primitive that does remember: a Semaphore(0), a CountDownLatch(1), or a Go channel.
Pattern Table: Which Primitive for Which Shape
| Problem shape | Example problems | Reach for | Why it fits |
|---|---|---|---|
| Ordering (A must happen before B) | Print in Order | Semaphore(0), latch, closed channel, Event | A gate that starts closed and remembers that it was opened |
| Alternation / rotation | FooBar, Zero Even Odd, K-thread round-robin | Paired (or ring of) semaphores; one lock with a turn variable and a condition per role | Passing a single token makes "exactly one at a time, in this order" structural |
| Data-dependent dispatch | FizzBuzz, Zero Even Odd | Dispatcher thread with one semaphore per worker, or a monitor with a predicate per role | The dispatcher decides who goes next, and workers wait only for their own signal |
| Grouping / rendezvous | H2O, phased simulations | Barrier (CyclicBarrier, threading.Barrier) plus counting semaphores for the mix | The barrier forms the group, the semaphores control what goes into it |
| Bounded resources | Dining Philosophers doorman, connection pools, rate limiting | Counting semaphore, token bucket | The counter is the resource count |
| Producer-consumer | Bounded Blocking Queue | Lock + two conditions, two semaphores, BlockingQueue, buffered channel | Two predicates (not full, not empty), one per side |
| Fan-out / fan-in | Web Crawler | Fixed worker pool + pending counter, or a coordinator with channels | Bounded parallelism plus reliable termination detection |
| Shared read, exclusive write | RW lock, Traffic Light follow-up | ReentrantReadWriteLock, sync.RWMutex, lightswitch counter | Readers overlap, writers drain them first |
| One-time initialisation | Singleton | Holder idiom, sync.Once, volatile DCL | Safe publication without locking on every call |
| Multiple locks | Dining Philosophers, bank transfers | Global lock order, tryLock with back-off | Removes circular wait |
Common Mistakes
| Mistake | What goes wrong | Fix |
|---|---|---|
| Signal before wait with a bare condition variable | The signal is lost and the waiter sleeps forever | Wait on a state predicate, or use a semaphore or latch, which remember signals |
if instead of while around wait() | Spurious wake-ups, and woken threads whose condition is still false (or was stolen), carry on anyway | while (!condition) wait(); every time, or wait_for(predicate) in Python |
notify() / signal() with mixed waiters | Wakes a thread of the wrong role, which goes back to sleep, and the program hangs | notifyAll(), or one Condition per predicate |
Holding a lock while blocking (I/O, sleep, queue.put, waiting on another lock) | Throughput collapses, and if the blocked operation needs the same lock you get a deadlock | Copy what you need under the lock, release it, then do the slow work |
| Forgetting to release on exceptions | One exception leaves the lock held for ever | try/finally around lock()/unlock(), with in Python, defer mu.Unlock() in Go |
| Inconsistent lock order | Circular wait, which is a deadlock | Global order (by ID or address), or tryLock with a timeout |
| Check-then-act on a "thread-safe" collection | Lost updates, duplicate work | Atomic compound operations (merge, computeIfAbsent, putIfAbsent) |
| Busy-waiting on a flag | Burns a core, and without volatile may never see the update | Block on a primitive. If you really must spin, use volatile or atomics and Thread.onSpinWait() |
| No termination signal | Worker threads block forever after the last item (FizzBuzz, crawler) | Make "done" part of the wait predicate, or close the queue/channel |
| Unbounded thread creation | Memory exhaustion, scheduler thrashing | Fixed pool, semaphore cap, or a worker-pool pattern |
The sentence that wins concurrency rounds
Before writing a line, say: "The shared state is X. Its invariant is Y. Threads wait for predicate P, re-checked in a loop under the lock that guards X. Locks are always taken in order Z. Termination happens when Q." If you can fill in every blank, your code is very likely correct, and the interviewer knows you know why.
Further Reading
- Classic Synchronization Problems: the theory behind the problems on this page
- Mutex, Semaphore & Monitor: the primitives used here
- Race Conditions and Deadlocks: the two failure modes every solution has to rule out
- Concurrency Patterns: producer-consumer, thread pools, work stealing
- Lock-Free Programming: CAS loops, atomics, ABA
- Actor Model: sharing state by sending messages instead of locking
- Kernel Synchronization: how futexes and wait queues implement all of the above
- Java Concurrency in Practice (Goetz et al.), chapters 5, 12 and 14. The Little Book of Semaphores (Downey) for many more puzzles of this kind
Quick Quiz
1. Why can signal() replace signalAll() in the bounded blocking queue but not in a version with a single condition?
Answer
With two conditions, every waiter on notEmpty waits for the same predicate, and one enqueue satisfies exactly one of them, so waking one is enough and is always the right kind of thread. With a single condition, producers and consumers share one wait set. signal() could wake a producer after an enqueue, which re-checks, finds the queue full and sleeps again, while a consumer that could have run stays asleep. That is a lost wake-up, so you would need signalAll().
2. In the web crawler, what goes wrong if you decrement pending before scheduling the children?
Answer
The parent may take pending from 1 to 0 before calling schedule(child). The latch then fires and crawl returns, or the pool shuts down, while there is still work to do. The children are lost or rejected. Increment before submitting, and decrement only after every child has been submitted.
3. Your Java DCL singleton has no volatile. Describe the failure precisely.
Answer
The write instance = new Config() may become visible to another thread before the constructor's writes do, because of compiler or CPU reordering. Thread B's unlocked first check sees instance != null, skips the lock, and reads fields that are still at their default values (null or 0). volatile makes the write a release and the read an acquire, so B sees a fully built object.
4. In the H2O barrier solution, why release the semaphore after barrier.await() rather than right after printing?
Answer
If an H released its slot right after printing, a third H could enter and print before the current molecule's O had printed, which would give HHH in one group of three. Releasing after the barrier means the next molecule's atoms can enter only once all three atoms of this molecule have printed and met.
5. A K-thread round-robin built on one monitor and notifyAll is correct. Why would an interviewer push you towards a semaphore ring?
Answer
Every step wakes all K threads, and K−1 of them re-check and go back to sleep. That is O(K) context switches per number, a thundering herd. A semaphore per thread wakes exactly the next owner: O(1) per step, and easier to reason about.