Multi-Threaded Coding

Coding problems where several threads must take turns, share data safely or wait for each other: locks, semaphores, condition variables and barriers, and how to pick one.

Overview

What these problems test

A multi-threaded coding problem gives you two or more threads that run at the same time and interleave in any order. Your job is to make the result correct no matter how they interleave, without stopping them from running in parallel where they can. The goal is three things: no race (two threads change shared data at once), no deadlock (threads wait for each other forever), and the required order of events.

Almost every problem is one of four coordination patterns. Name the pattern first; the primitive follows from it.

The primitives

Lock (mutex) — One owner at a time — Another thread holds it — threading.Lock — synchronized, ReentrantLock
Semaphore — A count of permits — The count is 0 on acquire — threading.Semaphore — java.util.concurrent.Semaphore
Condition variable — A lock plus a waiting room — wait() until another thread notifies — threading.Condition — Object.wait and notify, or Condition
Barrier — A count of arrivals — Until all parties have arrived — threading.Barrier — CyclicBarrier
Blocking queue — Items, up to a capacity — put on full, get on empty — queue.Queue — BlockingQueue

Two facts about semaphores matter most. A semaphore may be created with a count of 0, so the first acquire blocks until someone releases; that is how one thread hands a turn to another. And the thread that releases need not be the one that acquired; Java's documentation says correct use is a matter of programming convention.

Pattern: ordering with semaphores

'Print in Order' has three methods, first, second and third, each called from its own thread in an unknown order, and the output must be first, second, third. Two semaphores that start at 0 chain the turns.

'Print FooBar Alternately' is the same idea with two semaphores handing the turn back and forth; 'FizzBuzz Multithreaded' extends it to four threads, where a shared counter under a condition variable is clearer than four semaphores.

Pattern: a race, and the lock that fixes it

The statement count += 1 is three steps: read, add, write. Two threads can both read 5, both write 6, and one increment is lost.

1 — reads 5 — 5
2 — reads 5 — 5
3 — writes 6 — 6
4 — writes 6 — 6, one update lost

A lock around the three steps makes them one step from the other thread's point of view. In CPython, the global interpreter lock (GIL) lets only one thread run Python bytecode at a time, but it does not make count += 1 atomic, because the thread can be switched out between the read and the write. Take the lock anyway; the GIL is an implementation detail, not a promise, and since Python 3.13 a build option can remove it altogether (PEP 703).

Pattern: producer and consumer with a condition variable

A bounded buffer holds at most k items. Producers wait while it is full; consumers wait while it is empty. A condition variable pairs a lock with a waiting room, and the rule that never changes is wait in a loop that re-checks the condition. Java's documentation says a waiting thread can wake without being notified, interrupted or timing out (a spurious wakeup), and Python's says the condition that prompted the notify may no longer hold by the time wait returns. Either way, an if-check is a bug.

Buffer full — waits until a consumer takes an item
Buffer empty — waits until a producer adds one
Item added — notifies waiting consumers
Item taken — notifies waiting producers

Python's Condition.wait_for(predicate) is that loop written for you. Python's queue.Queue and Java's BlockingQueue package the whole pattern, and you should offer the queue first and the condition variable when asked to build it.

Pattern: deadlock and lock ordering

'Dining Philosophers' seats five philosophers around a table with one fork between each pair. Each needs both neighboring forks to eat. If every philosopher picks up the left fork at the same moment, each holds one fork and waits forever for the other: a deadlock, which needs a cycle of waiting.

Lock ordering — Every thread takes the lower-numbered fork first; the last philosopher therefore reaches for the right fork first — None; the usual answer
Limit the diners — A semaphore of 4 permits: with at most four trying, one can always finish — Slightly less parallelism
A single lock for the table — One philosopher eats at a time — No parallelism at all

Building H2O

Threads arrive as hydrogen or oxygen and must leave in groups of two H and one O, with no group split across a boundary. A semaphore of 2 permits admits hydrogens and one of 1 permit admits oxygen; a barrier of size 3 holds each group until it is complete; after the barrier, each thread releases its own semaphore so the next group can enter.

What you will be able to do

Name the coordination pattern of a problem in the first minute.
Chain turns with semaphores that start at 0.
Protect shared state with a lock and explain the exact interleaving that goes wrong without it.
Write a bounded buffer with a condition variable, with the wait in a loop.
Explain why lock ordering removes deadlock, and offer the alternatives.

When to use it

The problem gives methods that run on different threads and requires a fixed output order
Several threads change one counter, list or map
Items are handed from producing threads to consuming threads through a bounded buffer
Each thread must hold more than one lock at once, so deadlock is possible
A fixed number of threads must meet before any of them continues (a barrier)
The problem limits how many threads may be inside a section at once (a semaphore with n permits)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio