Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build Print in Order

Build Print in Order

Every startup sequence, migration pipeline, and multi-step Terraform apply you'll ever ship has the same shape as LeetCode 1114 wearing a disguise: three (or three hundred) independent threads must each do their part, but the relative order across threads is non-negotiable — the cache must warm before traffic routes, step 2 waits on step 1, task C needs both A and B done. It's a five-line interview question precisely because it can't be faked: either you know that "the order I call start() in" has nothing to do with "the order things run in," or your code jumbles the output the first time the grader's machine is busy. This lab makes you build ordered thread hand-off from an empty file, in Java and Go, break the un-synchronized version until it visibly fails, then fix it for real. See also the existing Problem 9: Print in Order using multithreading walkthrough and the Semaphore concept page — do this lab first, those will read like a victory lap.

1. The trap

The LeetCode 1114 contract: you're given a class with three methods, first(), second(), third(). A driver you don't control creates three threads and calls one method on each — but it's allowed to call t1.start(), t2.start(), t3.start() in any order. Your job: guarantee first()'s body runs, in full, before second()'s body starts, before third()'s body starts — no matter what order the driver started the threads in. The naive first draft ignores that and just writes the methods straight:

class Foo {
    public void first(Runnable printFirst)  { printFirst.run();  }
    public void second(Runnable printSecond) { printSecond.run(); }
    public void third(Runnable printThird)  { printThird.run();  }
}

This compiles, and on your laptop, run once, it might even print firstsecondthird — which is exactly the trap. A single lucky run tells you nothing, because:

The fix isn't "add a sleep" (that just makes the failure rarer, not impossible — a classic trap of its own). You need a real signal: a mechanism where second()'s thread genuinely cannot proceed past a certain line until first() has provably finished. That's the entire lab.

2. Scope it like a senior

Before reaching for a primitive, pin the contract down. A candidate who starts coding immediately on "print in order" usually builds a version that only handles the 3-stage, run-once case — and then flails when the interviewer generalizes. Ask:

Answering these up front is what "senior" looks like: you're pinning the contract, not guessing at the smallest version that happens to pass the first test.

3. Reason to the design

Attempt 0 — a shared boolean flag, polled. Have first() set firstDone = true; have second() spin: while (!firstDone) {}. Two problems, and interviewers expect you to name both without hinting: it busy-waits (burns a full core spinning on nothing, same failure as the naive producer-consumer buffer), and worse — without volatile/atomics, there is no memory-visibility guarantee at all that the JIT-compiled loop on thread 2 ever re-reads the field from main memory; it can legally spin forever on a cached stale value. This "obvious" fix is actually unsound.

Attempt 1 — one lock, one condition, a turn counter. Guard a plain int turn with a ReentrantLock/Condition: each stage waits while (turn != mine) condition.await(), then runs, then turn++; condition.signalAll(). This is correct (verified below) and it's the general-purpose tool — it's exactly the condition-variable wait/notify pattern with a turn counter standing in for "whose turn is it." The while, not if, matters for the identical reason it does in any condition-variable design: a stale wake-up must be re-checked.

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.locks.Condition;

// verified working -- one lock + one condition + a turn counter
class TurnGate {
    private final Lock lock = new ReentrantLock();
    private final Condition turnChanged = lock.newCondition();
    private int turn = 0; // 0=first's turn, 1=second's, 2=third's
    private void runTurn(int mine, Runnable body) throws InterruptedException {
        lock.lock();
        try {
            while (turn != mine) turnChanged.await();  // recheck after every wake
            body.run();
            turn++;
            turnChanged.signalAll();                    // wake ALL waiters; only one proceeds
        } finally { lock.unlock(); }
    }
}

Attempt 2 — two semaphores initialized to 0 (what we ship). A Semaphore is a lock+condition already assembled for exactly this "counting readiness signal" use case — think of it as a bucket of permits: acquire() blocks until a permit exists then takes one, release() drops a permit in. Initialize two semaphores to zero permits (no turn is "ready" yet): secondReady and thirdReady. first() runs, then calls secondReady.release() — handing exactly one permit forward. second() calls secondReady.acquire() first thing, which blocks until that permit exists. Same idea as the turn counter, but there's no shared mutable int to protect and no explicit lock to remember to release — the semaphore is the state. This is strictly more than "looks synchronized": the JVM's Semaphore gives a real happens-before edge — everything before a release() is guaranteed visible to the thread whose matching acquire() returns. That's Attempt 0's missing piece, provided for free.

Generalizing the chain: 3 stages need 2 semaphores (N stages need N−1) — each one gates exactly the next stage. That single idea (a chain of N−1 zero-initialized permits) is the whole mechanism; Movement 4's M2 is just sizing it to N instead of hardcoding 3.

4. Build it — milestones

Attempt each milestone yourself before reading the reference implementation below — the reveal is positioned after the tests on purpose.

Reference implementation — Java (two Semaphores initialized to 0)

M1, the exact LeetCode 1114 contract. Compiled and executed with javac/java before publishing — three threads started in the scrambled order third→first→second, twenty rounds, one instance per round, zero violations.

import java.util.concurrent.Semaphore;

/** M1 reference: two semaphores initialized to 0, chained as a hand-off. */
public class Foo {
    private final Semaphore secondReady = new Semaphore(0);
    private final Semaphore thirdReady  = new Semaphore(0);

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        secondReady.release();      // unblock second() -- the hand-off
    }

    public void second(Runnable printSecond) throws InterruptedException {
        secondReady.acquire();      // block until first() has run
        printSecond.run();
        thirdReady.release();       // unblock third()
    }

    public void third(Runnable printThird) throws InterruptedException {
        thirdReady.acquire();       // block until second() has run
        printThird.run();
    }
}

M2, generalized to N stages — an array of N−1 semaphores instead of two named fields. Verified with N=8, ten rounds, start order shuffled independently every round, zero violations:

import java.util.concurrent.Semaphore;

public class OrderedStages {
    private final Semaphore[] gate; // gate[i] releases stage i+1

    public OrderedStages(int n) {
        gate = new Semaphore[n - 1];
        for (int i = 0; i < gate.length; i++) gate[i] = new Semaphore(0);
    }

    public void run(int stage, Runnable body) throws InterruptedException {
        if (stage > 0) gate[stage - 1].acquire();       // wait for predecessor
        body.run();
        if (stage < gate.length) gate[stage].release();  // unblock successor
    }
}

Output from the verification run (start order scrambled every round, all 8 stages joined before checking):

run 0: start-order=[2, 1, 6, 0, 3, 4, 7, 5] printed=01234567  OK
run 1: start-order=[7, 0, 1, 3, 6, 2, 4, 5] printed=01234567  OK
...
violations = 0 / 10 (N=8 stages)

Reference implementation — Go (channels, close-to-signal)

Go's idiom for this is a chan struct{} that gets closed, not sent on: a receive from a closed channel never blocks, so a late-arriving receiver is handled automatically — no separate "did I miss the signal?" check needed, unlike a condition variable.

package main

// Foo chains two "release" channels: each stage closes its channel to
// unblock the next. Closing (not sending) means it is safe even if the
// waiter checks late -- a receive on a closed channel never blocks.
type Foo struct {
    secondReady chan struct{}
    thirdReady  chan struct{}
}

func NewFoo() *Foo {
    return &Foo{
        secondReady: make(chan struct{}),
        thirdReady:  make(chan struct{}),
    }
}

func (f *Foo) First(printFirst func()) {
    printFirst()
    close(f.secondReady) // hand off to Second
}

func (f *Foo) Second(printSecond func()) {
    <-f.secondReady // block until First has run
    printSecond()
    close(f.thirdReady) // hand off to Third
}

func (f *Foo) Third(printThird func()) {
    <-f.thirdReady // block until Second has run
    printThird()
}

func main() {
    f := NewFoo()
    go f.First(func() {})
    go f.Second(func() {})
    f.Third(func() {})
}

And the M2 generalization — a slice of N−1 gate channels, one line of logic per stage regardless of N:

package main

import "sync"

// OrderedStages generalizes Foo to N stages: N-1 gate channels chain
// stage i's completion to unblock stage i+1.
type OrderedStages struct {
    gate []chan struct{} // gate[i] closes when stage i finishes, unblocking stage i+1
}

func NewOrderedStages(n int) *OrderedStages {
    gates := make([]chan struct{}, n-1)
    for i := range gates {
        gates[i] = make(chan struct{})
    }
    return &OrderedStages{gate: gates}
}

func (s *OrderedStages) Run(stage int, body func()) {
    if stage > 0 {
        <-s.gate[stage-1] // wait for predecessor
    }
    body()
    if stage < len(s.gate) {
        close(s.gate[stage]) // unblock successor
    }
}

func main() {
    n := 3
    s := NewOrderedStages(n)
    var wg sync.WaitGroup
    wg.Add(n)
    for i := 0; i < n; i++ {
        i := i
        go func() {
            defer wg.Done()
            s.Run(i, func() {})
        }()
    }
    wg.Wait()
}

Both files pass go build ./... and go vet ./... clean, and were exercised with go run -race . — 20 rounds of the 3-stage Foo (goroutines started in scrambled order) and 10 rounds of the 8-stage generalization, both 0 violations, no race reported:

=== Foo (channel-based, correctly ordered) ===
run 0: firstsecondthird  OK
...
violations = 0 / 20
CORRECT: firstsecondthird on every run, goroutine start order scrambled each time.

=== OrderedStages (generalized to N=8) ===
run 0: start-order=[3 5 0 1 7 2 6 4] printed=01234567  OK
...
violations = 0 / 10 (N=8 stages)

5. Break it — the test that fails

Delete the signalling entirely — go back to Movement 1's naive Foo, which just runs each method body with no coordination at all — and drive it properly this time: start all three threads, release them from a shared start-gate at (as close to) the same instant, add a 0–2ms random jitter per thread so the "who runs first" question is genuinely up to the scheduler, and repeat 20 times with a fresh instance each round.

// Java -- BuggyFoo: no signalling at all
public class BuggyFoo {
    public void first(Runnable printFirst)  { printFirst.run(); }
    public void second(Runnable printSecond) { printSecond.run(); }
    public void third(Runnable printThird)  { printThird.run(); }
}

Run it (three threads released together via a CountDownLatch start-gate, each with a small random jitter, 20 rounds):

run 0: thirdfirstsecond  OUT-OF-ORDER
run 1: thirdfirstsecond  OUT-OF-ORDER
run 2: firstsecondthird  ok
run 3: firstthirdsecond  OUT-OF-ORDER
run 4: thirdsecondfirst  OUT-OF-ORDER
...
run 19: firstthirdsecond  OUT-OF-ORDER
violations = 16 / 20
BUG REPRODUCED: 16/20 runs printed out of order with no signalling.

The Go version reproduces the same way — three goroutines released from a shared closed-channel start-gate, 0–2ms jitter, 20 rounds:

=== BuggyFoo (no signalling) ===
run 0: thirdfirstsecond  OUT-OF-ORDER
run 1: thirdfirstsecond  OUT-OF-ORDER
...
violations = 16 / 20
BUG REPRODUCED: 16/20 runs printed out of order with no signalling.

The teaching point interviewers actually care about: this is not a data race in the "corrupted memory" sense — the shared output buffer is protected by its own mutex in the harness, so go run -race reports nothing, and Java's -Xlint reports nothing either. There is no torn read, no invalid state. It is purely an ordering bug: nothing in the program establishes a happens-before edge between the three method bodies, so the scheduler is free to interleave them however it wants, and it does, on the large majority of runs once real contention (the jitter) is introduced. Race detectors catch memory races, not missing ordering guarantees — that distinction is exactly why "it passed -race" is not the same claim as "the ordering is correct," and a fix here is not a lock around a data structure, it's a genuine happens-before edge (Movement 3's semaphore/channel hand-off).

Re-run the identical harness against the real Foo (semaphores) or the channel version and the violation count drops to exactly 0/20, every time — the only change is that a hand-off now exists.

6. Optimise — with trade-offs

MechanismReusable across rounds (same instance)?Generalizes to N stages?Generalizes to a DAG (multiple predecessors)?Use when
Two Semaphores init to 0 (this lab)Yes — verified: a zero-initialized semaphore returns to exactly 0 permits after each release+acquire pair, so the same instance is safe for round 2 as long as rounds don't overlapYes — array of N−1 gatesPartially — a node with 2 predecessors can acquire(2) a single semaphore that both predecessors release() intoDefault choice for a fixed chain of stages, especially if the same pipeline runs many times
CountDownLatchNo — verified: once the count hits 0, every future await() returns immediately forever; it cannot be reset, so round 2 on the same latch enforces nothingYes, but needs one fresh latch per roundYes, natively — a latch's count IS "number of predecessors still pending," its intended use caseOne-shot barriers: "wait for exactly these K things to finish once" (e.g. app startup gating on K subsystems)
Lock + Condition + turn counterYes, but you must reset turn yourself between rounds and guard against a round overlapping the resetYes — compare against an array/counter instead of 0/1/2Awkward — needs a per-node predecessor-count check inside the same condition, more bookkeepingYou need one shared wait condition for several different wake-up reasons in the same object (semaphores force you to separate concerns per gate)
Go channels (close-to-signal)No as written (closed channels stay closed) — same fix as the latch: fresh channels per round, or replace with buffered channel sends for a reusable versionYes — slice of N−1 gatesYes — a sync.WaitGroup per node counting down predecessors, then closing the node's own gateIdiomatic Go; prefer over hand-rolled sync.Cond unless you need a custom wake condition (same trade-off as the producer–consumer lab)

The real judgment call: for a fixed, small chain that fires once, any of these is fine — pick the one that reads clearest (semaphores or channels, both one line per hand-off). The trade-off that actually matters shows up at scale: this whole lab is a linear special case of a DAG scheduler. Generalize "stage i waits on stage i−1" to "task T waits on tasks {P1, P2, ...}" and you've derived exactly how build systems (Make, Bazel), workflow engines (Airflow, Step Functions), and CI pipelines schedule work: give every task a countdown of its remaining unfinished predecessors (a per-task CountDownLatch/semaphore initialized to its in-degree), and have every finishing predecessor decrement/release into each of its successors. When a task's counter hits zero, it's ready — schedule it. That's Kahn's topological-sort algorithm, with the "ready queue" implemented as thread wake-ups instead of an explicit queue. The 3-stage chain here is the DAG scheduler with in-degree always exactly 1.

7. Defend under drilling

An interviewer will push past "it works." These are the follow-ups that come up almost every time, with the answer a staff engineer gives — short, concrete, no hedging.

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed (javac/java; go build, go vet, go run -race) before publishing; the break-it harness reproduces out-of-order output on 16–20 of 20 runs in both languages, and the semaphore-vs-latch reuse claim in Movement 6 was verified directly (a zero-initialized Semaphore returns to 0 permits after each round; a spent CountDownLatch never blocks again). See also: Problem 9: Print in Order using multithreading and the Semaphore concept page.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build Print in Order? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build Print in Order** (Hands-On Builds) and want to truly understand it. Explain Build Print in Order from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build Print in Order** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build Print in Order** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build Print in Order** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build a Future / PromiseBuild Multithreaded FizzBuzz →