Concurrency

Three threads call three methods; force them to run first, second, third.

Trigger

Any wording of the form 'guarantee this order between threads'.

Approach

1. State the problem: the OS gives no ordering guarantee, so I have to impose one.
2. Two signals — an Event or a Semaphore starting at zero for each dependency.
3. first() runs, then releases signal A. second() waits on A, runs, releases B.
4. third() waits on B. No busy-waiting, no sleeps.

Target complexity

O(1) per call. Each thread blocks at most once.

Pitfall

Using a shared flag plus a spin loop. It burns CPU and is not a synchronisation primitive.

Say it out loud

“There's no ordering guarantee between threads by default, so I need explicit signalling. I'll use two semaphores initialised to zero — each method waits on its predecessor's semaphore and releases its own. That's a happens-before edge, and it costs no polling.”

Solve on LeetCode

Threads representing hydrogen and oxygen must group into complete molecules before releasing.

Trigger

'Assemble groups of N before anyone proceeds' — a barrier with counts.

Approach

1. Two counted semaphores: hydrogen with 2 permits, oxygen with 1.
2. A Barrier of 3 makes the molecule complete before any of the three returns.
3. After the barrier, release the permits back so the next molecule can form.

Target complexity

O(1) per thread. The barrier costs one context switch per participant.

Pitfall

Releasing the permits before the barrier. Then a fourth hydrogen slips into the next molecule and you emit an invalid grouping.

Say it out loud

“This is a barrier with capacity constraints. The semaphores cap how many of each atom can be in flight; the barrier is what makes the grouping atomic. The subtle part is releasing the permits after the barrier, not before.”

Solve on LeetCode

Four threads split the FizzBuzz output, each responsible for one case.

Trigger

Several threads, one shared counter, and a condition that selects who acts.

Approach

1. One Condition guarding a shared counter i.
2. Each thread loops: acquire, `while` the counter is not mine and i <= n, wait.
3. Act, increment, notify_all, release.

Target complexity

O(n) time. Each increment wakes every waiter, so it is O(n) wakeups in the worst case.

Pitfall

`notify()` instead of `notify_all()`. With four threads waiting on different conditions, you can wake the wrong one and the system stalls.

Say it out loud

“Because the four threads wait on different predicates on the same condition variable, I have to use notify_all — notify could wake a thread whose predicate is still false and nobody would make progress.”

Solve on LeetCode

Two threads must alternate strictly, printing foo then bar, n times.

Trigger

'Alternate', 'take turns', 'strictly interleave'.

Approach

1. Two semaphores: one starts at 1 (foo may go), the other at 0.
2. foo acquires its own, prints, releases bar's. bar does the mirror image.
3. The invariant: exactly one semaphore has a permit at any moment.

Target complexity

O(n) total, O(1) space. Each thread blocks n times.

Pitfall

One lock plus a boolean and an `if`: the thread can wake, find it is not its turn, and either spin or deadlock. Use a `while`, or use two semaphores.

Say it out loud

“Alternation is a ping-pong of permits. I'll start one semaphore at one and the other at zero, so the invariant is that exactly one permit exists — that makes strict alternation structural rather than something I have to check.”

Solve on LeetCode

Three threads cooperate to print 0102030405…, one owning zero, one even, one odd.

Trigger

Three or more threads with a repeating cyclic pattern.

Approach

1. Three semaphores; zero starts at 1, the other two at 0.
2. zero() runs every iteration and hands the permit to odd or even based on the parity of i.
3. The parity decision lives in one place — the zero thread — so there is no shared mutable state.

Target complexity

O(n) time, O(1) space.

Pitfall

Putting the parity logic in every thread. Then two threads read a shared counter and you have a race on top of a synchronisation problem.

Say it out loud

“I'll centralise the decision: the zero thread is the scheduler and hands the turn to odd or even. That way the parity check happens in exactly one place, and the other two threads never read shared state.”

Solve on LeetCode

Five philosophers share five forks; each needs both neighbours' forks to eat.

Trigger

Multiple resources needed together, held by different actors — the deadlock question.

Approach

1. Name the deadlock first: if everyone picks up their left fork, all four Coffman conditions hold.
2. Break circular wait: impose a global ordering — every philosopher takes the lower-numbered fork first.
3. Alternatives worth naming: a semaphore limiting four diners at once, or asymmetry (odd philosophers reverse their order).

Target complexity

O(1) per meal. The lock ordering costs nothing at runtime.

Pitfall

Adding a timeout and retry as the 'fix'. That converts deadlock into livelock unless you add randomised backoff.

Say it out loud

“The naive solution deadlocks: everyone grabs their left fork and the wait graph has a cycle. I'll break circular wait with a global lock ordering — always acquire the lower-numbered fork first. That's cheap, it's local, and it doesn't change the program's semantics.”

Solve on LeetCode