On this page

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:

  1. Problem — restated in plain words.
  2. What makes it tricky — the trap most first attempts fall into.
  3. Key idea — the single sentence you should say out loud before writing code.
  4. Solutions — complete, runnable code in three languages. Java usually shows two approaches, because interviewers like to ask "now do it without semaphores".
  5. Why it is correct — the argument you would make at the whiteboard.
  6. 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.

ToolJavaPythonGo
Mutexsynchronized, ReentrantLockthreading.Locksync.Mutex
Condition variablewait/notifyAll, Condition.await/signalAllthreading.Conditionsync.Cond
Counting semaphorejava.util.concurrent.Semaphorethreading.Semaphorebuffered chan struct{}
One-shot gateCountDownLatchthreading.Eventclose(ch)
BarrierCyclicBarrier, Phaserthreading.Barrierhand-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. second cannot pass acquire() until first has called release(), and that call comes after printFirst.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 checks stage before sleeping, so a notifyAll that 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 while and not if around wait()? Spurious wake-ups are allowed by the JVM spec, and notifyAll wakes threads whose condition is still false (the third thread 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 calling close twice panics, so you would guard it with sync.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 <= 1 at all times, so at most one thread is ever between its acquire and its release. Each release targets the other semaphore, which forces strict alternation.
  • Foo starts: only fooTurn has a permit at the beginning.
  • Termination: both loops run exactly n times. The last fooTurn.release() from bar leaves 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() (not signalAll) is safe here because only one thread can ever be waiting on each condition. With more threads per role you would need signalAll or 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. Use notifyAll(), or use two Conditions 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 AtomicInteger turn counter with Thread.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: zero at iteration i sends the token to the thread that owns i. That thread's own loop counter is also at i, because it has printed every earlier number it owns.
  • Termination: zero does n iterations, odd does ⌈n/2⌉, even does ⌊n/2⌋. The number of releases into each semaphore matches the number of acquires, so no thread waits for a permit that never comes. When n = 1, even runs zero iterations and returns at once, which is correct.
  • Monitor version: the predicate zeroTurn || next != i is evaluated under the lock, and notifyAll is required because three threads share a single wait set.

Follow-ups.

  • Why is notify() wrong in the monitor version? After zero prints, notify() might wake even when odd is the one that should run. even goes 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 count before 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 for count to 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 given i.
  • Monitor termination: the thread that prints n increments i to n + 1 and calls notifyAll. Every waiter wakes, sees i > n, and returns. Without the i <= 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 number releases its semaphore (count the multiples), so every acquire is 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 Condition per role with a single ReentrantLock, and after each step signal only the condition of the next owner, which you can compute from i + 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/finally in Java, with in Python and defer in Go release the forks even if eat throws. 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? ReentrantLock and sync.Mutex are 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 tryLock instead? Lock left, then tryLock right; 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:

  1. 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.
  2. Bounded parallelism. One thread per URL falls over on a site with 100,000 pages. You need a fixed pool.
  3. 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 sees true schedules the URL. In Python and Go only the coordinator ever touches visited, 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. So pending cannot 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 the nil-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.Context down to the fetch. In Java use Future.get(timeout) or CompletableFuture.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 items happens under the lock (or through a thread-safe deque in the semaphore version), and the size invariant 0 <= size <= capacity is checked under the same lock that changes it.
  • No lost wake-ups: a waiter re-checks the predicate in a while loop under the lock, so a signal sent before it started waiting doesn't matter, because the predicate is already true.
  • Why signal() and not signalAll() 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 need signalAll().
  • Semaphore version: freeSlots + filledSlots + (operations in progress) == capacity. A dequeuer who has acquired filledSlots is guaranteed that an item has already been added (the add happens before the release), so pollFirst() never returns null.

Follow-ups.

  • Add offer(x, timeout)? Use notFull.awaitNanos(remaining) in the loop and return false when the time runs out. In Go use select with time.After.
  • Is a single lock a bottleneck? LinkedBlockingQueue uses two locks (a putLock and a takeLock) and an atomic count, so producers and consumers don't block each other. ArrayBlockingQueue uses one lock, as above.
  • Support closing the queue? Add a closed flag. Waiters check while (empty && !closed), and close() calls signalAll on both conditions. In Go, close(ch) plus v, 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 turnGreen is only called when the colour is actually wrong. An if is right here (not a while) because the thread never waits. It just fixes the state and goes on.
  • Concurrent version: crossing counts the cars inside the intersection. A car from the red road waits until crossing == 0, so the light flips only when the intersection is empty. Once it flips, any newly arriving car from the old road sees greenRoad != roadId && crossing > 0 and 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.

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 shapeExample problemsReach forWhy it fits
Ordering (A must happen before B)Print in OrderSemaphore(0), latch, closed channel, EventA gate that starts closed and remembers that it was opened
Alternation / rotationFooBar, Zero Even Odd, K-thread round-robinPaired (or ring of) semaphores; one lock with a turn variable and a condition per rolePassing a single token makes "exactly one at a time, in this order" structural
Data-dependent dispatchFizzBuzz, Zero Even OddDispatcher thread with one semaphore per worker, or a monitor with a predicate per roleThe dispatcher decides who goes next, and workers wait only for their own signal
Grouping / rendezvousH2O, phased simulationsBarrier (CyclicBarrier, threading.Barrier) plus counting semaphores for the mixThe barrier forms the group, the semaphores control what goes into it
Bounded resourcesDining Philosophers doorman, connection pools, rate limitingCounting semaphore, token bucketThe counter is the resource count
Producer-consumerBounded Blocking QueueLock + two conditions, two semaphores, BlockingQueue, buffered channelTwo predicates (not full, not empty), one per side
Fan-out / fan-inWeb CrawlerFixed worker pool + pending counter, or a coordinator with channelsBounded parallelism plus reliable termination detection
Shared read, exclusive writeRW lock, Traffic Light follow-upReentrantReadWriteLock, sync.RWMutex, lightswitch counterReaders overlap, writers drain them first
One-time initialisationSingletonHolder idiom, sync.Once, volatile DCLSafe publication without locking on every call
Multiple locksDining Philosophers, bank transfersGlobal lock order, tryLock with back-offRemoves circular wait

Common Mistakes

MistakeWhat goes wrongFix
Signal before wait with a bare condition variableThe signal is lost and the waiter sleeps foreverWait 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 anywaywhile (!condition) wait(); every time, or wait_for(predicate) in Python
notify() / signal() with mixed waitersWakes a thread of the wrong role, which goes back to sleep, and the program hangsnotifyAll(), 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 deadlockCopy what you need under the lock, release it, then do the slow work
Forgetting to release on exceptionsOne exception leaves the lock held for evertry/finally around lock()/unlock(), with in Python, defer mu.Unlock() in Go
Inconsistent lock orderCircular wait, which is a deadlockGlobal order (by ID or address), or tryLock with a timeout
Check-then-act on a "thread-safe" collectionLost updates, duplicate workAtomic compound operations (merge, computeIfAbsent, putIfAbsent)
Busy-waiting on a flagBurns a core, and without volatile may never see the updateBlock on a primitive. If you really must spin, use volatile or atomics and Thread.onSpinWait()
No termination signalWorker threads block forever after the last item (FizzBuzz, crawler)Make "done" part of the wait predicate, or close the queue/channel
Unbounded thread creationMemory exhaustion, scheduler thrashingFixed 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


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.