Concurrency Coding Problems

The classic multithreaded interview problems (print in order, alternating output, FizzBuzz with four threads, H2O, dining philosophers, a traffic light, a crawler), each solved with the primitive that fits and tested with real threads.

Overview

Concurrency coding problems give you a class whose methods are called from several threads at once, and ask you to add synchronization so the output is always correct, whatever order the threads run in. They are short, but they test whether you can name the constraint and pick the primitive that enforces it, rather than sprinkling locks around.

Most of them are one of three shapes: an order between threads (A before B, or A and B taking turns), a group that must form before anyone proceeds, or shared resources that must not deadlock. LeetCode's Concurrency list has nine problems: Print in Order, Print FooBar Alternately, Print Zero Even Odd, Building H2O, Design Bounded Blocking Queue, Fizz Buzz Multithreaded, The Dining Philosophers, Web Crawler Multithreaded and Traffic Light Controlled Intersection.

Picking the primitive

Ask three questions in order: what state is shared, what ordering is required, and which primitive states that ordering most directly.

Event (a one-way flag) — 'This has happened' — Print in Order
Semaphore — 'N may pass', or a turn handed from one thread to another — FooBar, H2O, bounded pools
Lock + condition variable — 'Wait until this shared state is true' — FizzBuzz, Zero Even Odd, bounded queue
Barrier — 'All of us have arrived' — H2O
Lock ordering — 'Locks are always taken in the same order' — Dining Philosophers
Lock + set — 'Check and add is one step' — Web Crawler

Every solution below starts its threads in a scrambled order and asserts on the whole output, which is how you should test these in an interview too.

Print in Order

Three threads call first(), second() and third() in an unknown order; the output must always be first, second, third. Each step waits for the one before it, once, so an event per boundary is all it takes.

Taking turns: FooBar

One thread prints foo n times and another prints bar n times; the output must alternate, foo first. A semaphore per side hands the turn over: foo's starts at 1 (it may go), bar's at 0. Each thread takes its own permit and gives one to the other.

Shared counter: FizzBuzz with four threads

Four threads print a FizzBuzz sequence from 1 to n: one prints fizz, one buzz, one fizzbuzz and one the plain numbers, and the combined output must be in order. The state is a single counter; each thread waits until the counter is on a number it owns (or past n), prints, advances and wakes everyone, because the next number may belong to any of the other three. Zero Even Odd is the same pattern with three threads.

notify_all is required here: with notify, the one thread woken might not own the next number, and it would go back to sleep while the owner never wakes.

Forming a group: Building H2O

Threads arrive as hydrogen or oxygen atoms in any order; they must leave in groups of exactly two hydrogens and one oxygen. Two semaphores cap how many of each kind can be in the group being formed, and a barrier of 3 holds them until the group is complete. A thread releases its slot only after the barrier, so the next group cannot start early.

Deadlock: the Dining Philosophers

Dijkstra's classic setting: five philosophers at a round table, one fork between each pair, and each needs both neighboring forks to eat. If everyone picks up the left fork first, all five hold one fork and wait forever for the second. The program forces that worst case (with a timeout instead of a hang) and then applies the standard fix, taking the lower-numbered fork first.

A deadlock needs all four of these conditions at once, so removing any one prevents it.

Mutual exclusion — A fork is held by one philosopher — Usually cannot be removed
Hold and wait — Holding the left fork while waiting for the right — Take both forks at once under one lock, or not at all
No preemption — Nobody can take a held fork away — Try the second fork with a timeout, and put the first back on failure
Circular wait — 0 waits for 1, 1 for 2, ..., 4 for 0 — Global order: always take the lower-numbered fork first

What you will be able to do

Turn a problem statement into a constraint and pick the primitive that states it.
Solve Print in Order, FooBar, FizzBuzz, H2O and Dining Philosophers from memory.
Explain why a solution cannot deadlock and why it never loses a wakeup.
Test concurrent code by scrambling thread start order and asserting on the whole output.

Interview questions

What are the most common concurrency coding problems, and what does each test?
How do you avoid deadlock in the Dining Philosophers problem? Compare the options.
How do you solve the producer-consumer problem?
Design a multithreaded web crawler that visits each page on one host exactly once.
Implement the traffic light for a two-road intersection.
How do you test concurrent code so a pass means something?