AlgoInsight

Free lesson · Concurrency Interview Mastery

Print Zero Even Odd

Hard10 min readconcurrencymultithreadinginterview-prep

"Print FooBar Alternately" coordinated two threads. "Print Zero Even Odd" extends turn-taking to three threads with a more interesting cycle, and introduces a key idea: a coordinator thread that decides who goes next. Three threads share a counter. One prints 0, one prints even numbers, one prints odd numbers, and together they must produce 0102030405... - a 0 before every number, with the numbers ascending and alternating odd, even, odd, even. So the sequence is 0 (zero), 1 (odd), 0 (zero), 2 (even), 0 (zero), 3 (odd)... The zero thread runs before every number, then hands off to either odd or even depending on what the next number should be. That conditional hand-off - one thread routing the turn to one of two others based on state - is the new technique, and it generalizes the ping-pong into a small state machine.

The problem

Three threads share an instance with three methods, each called in a loop:

The required output interleaves them as 0, then 1, then 0, then 2, then 0, then 3... - i.e. a 0 precedes each integer, and the integers ascend 1, 2, 3, ..., n. For n = 5 the output is "0102030405". The constraint: zero must print before each number, and the numbers must come from odd and even in the right order (odd for 1, even for 2, odd for 3...). Three threads, one strict global sequence.

The structure is a repeating cycle: zero → odd → zero → even → zero → odd → .... Notice zero appears every other step, and the number-printers alternate, with odd going first (since 1 is odd). The zero thread is effectively the metronome that runs every beat, and after each 0 it must wake the correct number-thread.

The core idea: a coordinator with three semaphores

The clean solution uses three semaphores - zeroSem (starts at 1, so zero goes first), oddSem (starts at 0), and evenSem (starts at 0) - with the zero thread acting as coordinator: after printing 0, it decides whether the next number is odd or even (from the current count) and signals that thread. The number-threads, after printing, signal zero back:

zeroSem = Semaphore(1)   # zero goes first
oddSem  = Semaphore(0)
evenSem = Semaphore(0)

function zero():
    for i in 1..n:
        zeroSem.acquire()
        print(0)
        if i is odd:  oddSem.release()    # next number (i) is odd -> wake odd
        else:         evenSem.release()    # next number (i) is even -> wake even

function odd():
    for i in 1,3,5,... up to n:
        oddSem.acquire()
        print(i)
        zeroSem.release()                  # hand back to zero

function even():
    for i in 2,4,6,... up to n:
        evenSem.acquire()
        print(i)
        zeroSem.release()                  # hand back to zero

The coordination: zero runs first (its semaphore starts at 1), prints 0, and then - crucially - routes the turn to either odd or even based on whether the number about to be printed (the i-th number) is odd or even. The chosen number-thread wakes, prints its number, and signals zeroSem to give the turn back to zero. So zero is the hub: every number is preceded by a 0, and zero's conditional signal (if i is odd → oddSem else → evenSem) is what sequences odd and even correctly. The number-threads are passive - they wait, print, and return control to the coordinator. This hub-and-spoke turn-taking, with the hub choosing the next spoke, is the pattern.

stateDiagram-v2
    [*] --> Zero
    Zero --> Odd: after 0, if next # is odd
    Zero --> Even: after 0, if next # is even
    Odd --> Zero: signal zeroSem
    Even --> Zero: signal zeroSem
    note right of Zero
        zero() is the COORDINATOR:
        prints 0 every step, then routes
        the turn to odd or even by parity
    end note

This state diagram shows the three-thread coordination for printing zero, even, and odd. The zero thread is the coordinator and runs first. From the Zero state, after printing a zero, it transitions to either Odd or Even depending on whether the next number to print is odd or even - it routes the turn by parity. The chosen number thread, Odd or Even, prints its number and then transitions back to Zero by signaling the zero semaphore. So the cycle is zero, then odd, then zero, then even, then zero, then odd, and so on. The zero thread acts as a hub that prints a zero every step and decides which of the two number threads goes next.

Why the coordinator pattern

The key design decision is making zero the coordinator that decides the next thread, rather than having the number-threads coordinate among themselves. This is clean because zero already runs every step (a 0 precedes every number), so it's naturally positioned to route the turn - it has to run anyway, so let it also decide. The alternative - having odd and even figure out whose turn is next and signal each other, with zero somehow interleaved - is more tangled, because the alternation logic would be split across two threads instead of centralized in one. Centralizing the "who goes next" decision in a single coordinator thread is a recurring technique for multi-party sequencing: one thread owns the sequence state and dispatches turns, while the others are simple wait-print-return workers. It keeps the coordination logic in one place and the workers trivial.

The parity decision deserves care. When zero is about to enable the i-th number (for i from 1 to n), it checks whether i is odd or even and signals the matching thread. odd prints 1, 3, 5, ... and even prints 2, 4, 6, ..., so the i-th number is odd exactly when i is odd - the routing is simply i's parity. Getting this index/parity mapping right is the one piece of real logic in the problem; the rest is mechanical hand-off.

Important: "Print Zero Even Odd" is three-thread turn-taking with a coordinator. Use three semaphores - zeroSem at 1 (zero first), oddSem and evenSem at 0 - and make zero the coordinator: it prints 0 every step, then routes the turn to odd or even based on the next number's parity (if i is odd → signal oddSem, else evenSem); the number-threads print and signal zeroSem back. The pattern is hub-and-spoke: one coordinator owns the sequence and dispatches turns; the workers just wait-print-return. Centralizing "who goes next" in a single coordinator (which already runs every step) is cleaner than splitting alternation logic across the workers. The one piece of real logic is the parity routing (the i-th number is odd iff i is odd). This coordinator technique generalizes the two-thread ping-pong to any number of sequenced parties.

Common pitfalls

The bugs here are about the routing logic and the hand-off direction:

The unifying idea: the coordinator (zero) must be the only thread that decides sequencing, and control must always return to it between numbers, so it can enforce both the "0 before each number" rule and the odd/even ordering. Keep the routing logic in the coordinator and make the workers always hand back, and the problem is straightforward.

A worked trace

Tracing n = 5 makes the hand-off concrete. The semaphores start zeroSem = 1, oddSem = 0, evenSem = 0, so only zero can proceed:

// n = 5; target output: 0102030405
step i=1: zero acquires zeroSem(->0), prints "0", i=1 odd -> releases oddSem(->1)
          odd acquires oddSem(->0), prints "1", releases zeroSem(->1)        => "01"
step i=2: zero acquires zeroSem(->0), prints "0", i=2 even -> releases evenSem(->1)
          even acquires evenSem(->0), prints "2", releases zeroSem(->1)      => "0102"
step i=3: zero acquires zeroSem(->0), prints "0", i=3 odd -> releases oddSem(->1)
          odd acquires oddSem(->0), prints "3", releases zeroSem(->1)        => "010203"
step i=4: zero ... prints "0", i=4 even -> evenSem; even prints "4"          => "01020304"
step i=5: zero ... prints "0", i=5 odd  -> oddSem;  odd  prints "5"          => "0102030405"

Follow the permission: at every step, zero holds it first (because the number-threads always release zeroSem back), prints 0, then routes it to odd or even by i's parity. The chosen thread prints and returns the permission to zero. The 0 appears every step because control always funnels back through the coordinator before the next number; the numbers ascend because zero enables them in i order; odd/even alternate because parity alternates with i. The trace also shows why the number-threads can use simple blocking acquires without checking anything: by the time oddSem is released, it's definitely odd's turn to print its next value - the coordinator guarantees it. All the sequencing intelligence lives in zero; the workers are dumb wait-print-return loops. That asymmetry - smart hub, dumb spokes - is the essence of the coordinator pattern and what makes it easy to reason about.

Generalizing the coordinator

The coordinator technique scales well beyond three threads, which is why it's worth understanding deeply. The general shape is: one coordinator thread owns a piece of sequence state (here, the implicit step counter and the parity decision) and, at each step, dispatches the turn to one of several worker threads based on that state; each worker does its bit and returns the turn to the coordinator. To extend Zero-Even-Odd to, say, print 0, then a number, then a letter, then a symbol in some pattern, you'd keep zero (or a dedicated coordinator) as the hub and add more worker semaphores, with the coordinator's routing logic encoding the richer sequence. The structure doesn't change - only the number of spokes and the routing rule do.

This is fundamentally different from the peer-to-peer alternation of FooBar, where the two threads signal each other directly with no central decision-maker. With two parties and simple alternation, peer-to-peer is fine (each just signals the other). But as the number of parties grows or the sequencing rule gets complex, centralizing the decision in a coordinator scales better than trying to encode a multi-way sequence as a web of peer-to-peer signals - because the sequence logic stays in one place (the coordinator) instead of being smeared across every worker. This is a genuine architectural choice you'll face in real coordination problems: peer-to-peer hand-off (simple, symmetric, few parties) versus a coordinator/dispatcher (centralized logic, scales to many parties and complex rules). Zero-Even-Odd is the gentle introduction to the coordinator side of that choice, and recognizing when to reach for a coordinator - when sequencing logic is non-trivial or parties are many - is a transferable design instinct.

Note: A useful way to see Zero-Even-Odd is as a tiny state machine driven by one thread. The coordinator holds the current state (which step, what parity), and each step is a transition: print 0, then move to either the "odd prints" state or the "even prints" state, then back to the coordinator state. Framing multi-thread coordination as a state machine - what are the states, what triggers each transition, and which thread drives them - is a powerful analytical habit that pays off enormously in the harder problems later in this module (the Cigarette Smokers and Santa Claus problems are essentially state machines with more states and more intricate transitions). When a coordination problem feels tangled, drawing its state machine and asking "who drives each transition?" often reveals that one thread should be the coordinator and the others should be workers waiting to be dispatched - exactly the structure here. The discipline of identifying states and transitions, then assigning a driver to each, turns intimidating multi-thread puzzles into mechanical implementations.

The interview angle

Interview: "Print Zero Even Odd" (LeetCode 1116) is a step up from FooBar and a common interview problem. The expected answer: three semaphores (zeroSem=1, oddSem=0, evenSem=0) with zero as the coordinator that prints 0 and signals odd or even by parity, and the number-threads signaling zero back. Distinguishing details: (1) recognizing zero should be the coordinator because it runs every step and can route the turn; (2) the parity routing logic (i-th number is odd iff i is odd); (3) that control must return to zero between numbers to preserve the "0 before each number" invariant; (4) handling the different iteration counts of the three threads. The strong framing is "hub-and-spoke turn-taking - one coordinator dispatches turns to workers," connecting it back to FooBar's ping-pong as the two-party case and forward to the multi-party problems ahead.

Quick reference

Three-thread turn-taking that introduces the coordinator technique - one thread owns the sequence and dispatches turns to workers who wait, print, and hand control back. The template is three semaphores (only the coordinator's starts available) with the coordinator routing each turn by the next number's parity; it generalizes the two-thread ping-pong to any number of sequenced parties and scales better than peer-to-peer signaling when the sequencing rule is non-trivial. The one piece of real logic is the parity routing, which is simple because the step index's parity equals the printed number's parity; everything else is mechanical wait-print-return hand-off through the coordinator. Keep the routing logic in the coordinator, make every worker return control to it between numbers, and the three-way sequence falls out cleanly and correctly:

PRINT ZERO EVEN ODD (LeetCode 1116): 3 threads -> 0102030405...
  (a 0 before every number; numbers ascend; odd/even alternate, odd first)
  = THREE-THREAD turn-taking with a COORDINATOR

THREE-SEMAPHORE SOLUTION:
  zeroSem=1 (zero first), oddSem=0, evenSem=0
  zero():  loop i=1..n: zeroSem.acquire(); print 0;
             if i odd -> oddSem.release() else evenSem.release()   # ROUTE by parity
  odd():   loop odd i:  oddSem.acquire();  print i; zeroSem.release()   # hand back to zero
  even():  loop even i: evenSem.acquire(); print i; zeroSem.release()

PATTERN: HUB-AND-SPOKE turn-taking
  - zero = COORDINATOR: runs every step, OWNS the sequence, ROUTES turn to odd/even
  - number-threads = workers: wait -> print -> return turn to coordinator
  - centralize "who goes next" in ONE coordinator (it runs every step anyway)

KEY LOGIC: i-th number is ODD iff i is ODD -> route accordingly

PITFALLS: route to wrong thread (wrong sequence) | off-by-one / mismatched loop counts
  | number-threads signal each other (breaks "0 before each #") | wrong initial sem values

The coordinator technique scales the turn-taking idea to multiple parties with centralized sequencing logic. The next problem - "FizzBuzz Multithreaded" - applies the same multi-thread sequencing to a four-way split with a richer routing rule based on divisibility.

Back to Concurrency Interview Mastery