AlgoInsight

Free lesson · Concurrency Interview Mastery

Fizz Buzz Multithreaded

Hard10 min readconcurrencymultithreadinginterview-prep

"Print Zero Even Odd" routed turns between two number-threads by parity. "FizzBuzz Multithreaded" scales the same idea to four threads with routing by divisibility - and introduces a cleaner way to express multi-way routing: instead of one coordinator signaling specific threads, every worker waits on a shared predicate and the one whose condition matches the current number acts. Four threads collaborate to print the FizzBuzz sequence for 1..n: one prints "fizz" (for multiples of 3), one "buzz" (multiples of 5), one "fizzbuzz" (multiples of 15), and one prints the number itself (everything else). They must produce the single correct FizzBuzz sequence in order. This is the four-way generalization of the coordinator problem, and the predicate-on-shared-state technique it showcases - multiple workers each gated by a condition over shared state - is a pattern you'll reuse for any "several threads, each handles certain cases" coordination.

The problem

Four threads share an instance with four methods, driven for i = 1 to n:

For each i from 1 to n, exactly one of the four threads prints the appropriate token, and the integers advance in order. For n = 15: 1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz. The challenge: four concurrent threads must coordinate so that for each i, only the correct one prints, and they advance through i strictly in order.

The routing rule is divisibility, and order of checking matters: 15 must be tested before 3 or 5, because a multiple of 15 is also a multiple of both 3 and 5 - if you checked i % 3 == 0 first, every multiple of 15 would wrongly trigger fizz. The correct precedence is: divisible by 15 → fizzbuzz; else by 3 → fizz; else by 5 → buzz; else number.

The core idea: predicate-gated workers on a shared counter

The elegant solution uses a mutex + condition variable + a shared counter current, where all four threads loop, each waiting until current is theirs (matches its divisibility rule), printing, advancing current, and notifying the rest:

lock = Lock(); cond = Condition(lock)
current = 1                       # the number being processed now

function fizz():
    while true:
        lock.acquire()
        while current <= n and not (current%3==0 and current%5!=0):
            cond.wait()           # not my turn -> wait
        if current > n: cond.notify_all(); lock.release(); return
        print("fizz")
        current += 1
        cond.notify_all()         # wake everyone to re-check the new current
        lock.release()

// buzz(): predicate current%5==0 and current%3!=0
// fizzbuzz(): predicate current%15==0
// number(): predicate current%3!=0 and current%5!=0

The mechanism: a single shared current counter holds the number being processed. Every thread, when it acquires the lock, checks in a while loop whether current satisfies its condition; if not, it waits. When a thread finds current matches its rule, it prints, increments current to the next number, and notify_alls - waking all threads to re-check against the new current. Exactly one thread's predicate will match each value of current, so exactly one prints it; the others re-wait. The counter advances one at a time under the lock, so the sequence is strictly ordered. This is the predicate-gated worker pattern: rather than a coordinator explicitly signaling a chosen thread, the shared state (current) plus each worker's predicate self-selects which thread acts - a more declarative way to express multi-way routing than per-thread signals.

flowchart TD
    C["shared current (1..n)"] --> Q{which predicate matches current?}
    Q -->|current % 15 == 0| FB["fizzbuzz() prints 'fizzbuzz'"]
    Q -->|div by 3 only| F["fizz() prints 'fizz'"]
    Q -->|div by 5 only| B["buzz() prints 'buzz'"]
    Q -->|div by neither| N["number() prints current"]
    FB --> I["current += 1; notify_all"]
    F --> I
    B --> I
    N --> I
    I --> C
    note["Check 15 BEFORE 3 or 5.<br/>Each worker waits in a while-loop on its predicate."]

This flowchart shows the FizzBuzz multithreaded coordination. A shared counter called current holds the number being processed, from 1 to n. At each step, the question is which thread's predicate matches the current value. If current is divisible by 15, the fizzbuzz thread prints fizzbuzz. If divisible by 3 only, the fizz thread prints fizz. If divisible by 5 only, the buzz thread prints buzz. If divisible by neither, the number thread prints the value. Whichever thread acts then increments current by one and notifies all the others to re-check against the new value. Crucially, the divisibility by 15 must be checked before 3 or 5, because a multiple of 15 is also a multiple of both. Each worker waits in a while-loop on its own predicate, so exactly one thread handles each number and they advance in order.

Two ways to route: coordinator vs predicate-gated

It's worth contrasting this with the Zero-Even-Odd coordinator. There, one thread (zero) ran every step and actively signaled the specific next thread. Here, there's no central coordinator - instead, all four workers passively wait on a shared predicate, and the shared current value determines which one proceeds. Both solve multi-way routing, but differently:

You could solve FizzBuzz with an explicit coordinator (a driver loop signaling one of four semaphores by divisibility) and you could solve Zero-Even-Odd with predicate-gated workers; they're interchangeable in principle. The predicate-gated style shines for FizzBuzz because the routing is a tidy divisibility function and the four workers are symmetric - each just waits for "its kind" of number. Recognizing both styles, and that they're two expressions of the same multi-way-routing need, is the conceptual takeaway.

Important: "FizzBuzz Multithreaded" is four-way turn-taking routed by divisibility. The clean solution: a mutex + condition variable + shared current counter, where all four threads loop, each waiting in a while loop until current matches its divisibility predicate, then printing, incrementing current, and notify_alling. This is the predicate-gated worker pattern - workers self-select via a predicate over shared state instead of being explicitly signaled by a coordinator. The routing precedence matters: test divisible-by-15 before 3 or 5 (a multiple of 15 is a multiple of both). Contrast with Zero-Even-Odd's explicit coordinator: both route multi-way, but predicate-gated workers suit clean state-functions with symmetric workers, while a coordinator suits a natural every-step driver. notify_all (not notify) and the while-loop predicate are essential. The predicate-gated technique generalizes to any "several threads, each handling certain cases" problem.

Common pitfalls

The unifying discipline: shared state under a lock, each worker gated by a while-loop predicate, notify_all after each advance, mutually-exclusive predicates with correct precedence, and a clean termination path.

A worked trace and a targeted-signaling variant

Tracing the first few values of current shows the self-selection in action:

// n = 15; threads: fizz, buzz, fizzbuzz, number
current=1  -> number's predicate matches (1%3!=0 and 1%5!=0) -> prints "1",  current=2
current=2  -> number matches -> "2",  current=3
current=3  -> fizz matches (3%3==0, 3%5!=0) -> "fizz", current=4
current=4  -> number -> "4", current=5
current=5  -> buzz matches (5%5==0, 5%3!=0) -> "buzz", current=6
current=6  -> fizz -> "fizz", current=7
...
current=15 -> fizzbuzz matches (15%15==0) -> "fizzbuzz", current=16 (> n, all exit)

At each value, all four threads are woken by the previous notify_all, all re-check their predicate, exactly one finds current is its kind and proceeds, and the other three wait again. The shared counter self-selects the actor; no thread needs to know about the others. The mutually-exclusive predicates guarantee exactly one match per value, and the lock-protected increment guarantees ordered advancement.

The single-condition-variable design is simple but slightly wasteful: every notify_all wakes all four threads, three of which immediately re-wait (a small thundering-herd, Module 6). A targeted-signaling variant uses four separate condition variables (or semaphores), one per thread, plus the shared current. A tiny coordinator - or the acting thread itself - computes which thread should handle the next value and signals only that one's condition variable. This wakes exactly the right thread, eliminating the wasted wakeups, at the cost of more bookkeeping (the routing logic must live somewhere, and you're back toward the explicit-coordinator style of Zero-Even-Odd). For four threads the difference is negligible, but the trade-off generalizes: broadcast-and-self-select (notify_all on one CV) is simpler and fine for small worker counts, while targeted signaling (per-worker CVs/semaphores) is more efficient when there are many workers and the wasted wakeups would add up. Knowing both - and that they're the same predicate-gated idea with different wakeup efficiency - is the rounded understanding.

The generalization: declarative multi-way routing

The predicate-gated pattern is worth abstracting because it recurs far beyond FizzBuzz. The general shape is: several worker threads share some state; each worker has a predicate over that state defining "the cases I handle"; whenever the state changes, workers re-evaluate, and the one whose predicate matches acts. This is a declarative approach to multi-way routing - you specify what each worker handles (its predicate) rather than writing imperative logic to dispatch to it. The benefits: it's easy to extend (add a worker with a new predicate without touching the others), the routing is local to each worker (no central dispatcher to keep in sync), and as long as the predicates partition the state space (mutually exclusive and exhaustive), correctness is straightforward - exactly one worker acts per state.

The crucial discipline, as the divisibility trap shows, is that the predicates must genuinely partition the relevant states: mutually exclusive (no state matches two predicates, or you get conflicts/races over who acts) and exhaustive (every state matches some predicate, or a state is handled by no one and the system stalls). FizzBuzz's four categories partition the integers; the bug is forgetting that multiples of 15 belong solely to the fizzbuzz partition. This partition requirement is the predicate-gated pattern's version of "get the routing right," and it's where these problems are usually subtly wrong. When you reach for predicate-gated workers - and you will, any time several threads each handle certain cases of a shared state - the first check is always "do my predicates partition the space cleanly?" Get that right and the broadcast-re-check-self-select machinery handles the rest.

Note: FizzBuzz Multithreaded is a small lesson in a big idea: there are two fundamental ways to coordinate which of several threads handles a piece of work - push (a coordinator decides and dispatches to the chosen worker) and pull (workers watch shared state and self-select when their condition is met). Zero-Even-Odd is push; FizzBuzz is pull. The pull model (predicate-gated workers) is often more elegant when the routing is a clean function of observable state and the workers are symmetric, because it keeps each worker's logic self-contained and makes the system easy to extend - adding a case is adding a worker with a predicate, touching nothing else. The push model is better when there's a natural coordinator and you want central control over sequencing. Real systems use both: a thread pool pulling tasks from a queue is pull-style self-selection; a load balancer routing requests to specific workers is push-style dispatch. Recognizing which model a problem wants - and that they're duals of the same multi-way-routing need - is a design instinct that transfers well beyond these puzzle problems into how you structure work distribution in actual systems.

The interview angle

Interview: "FizzBuzz Multithreaded" (LeetCode 1195) is a popular four-thread coordination question. The expected answer: mutex + condition variable + shared current, each thread waiting in a while loop on its divisibility predicate, printing, incrementing, and notify_alling. Distinguishing details: (1) the predicate-gated worker framing - workers self-select via shared state rather than being explicitly signaled; (2) checking 15 before 3 or 5 (or mutually-exclusive predicates) - a classic correctness trap; (3) notify_all over notify for the single-CV design, and why (one CV, four waiters, only one can proceed); (4) the while-loop discipline and the termination path. A strong candidate also contrasts it with the coordinator style (Zero-Even-Odd) and notes both are valid multi-way-routing expressions. The divisibility precedence and notify_all rationale are the standout signals.

Quick reference

Four-way turn-taking routed by divisibility, showcasing the predicate-gated worker pattern - workers self-select by checking a predicate over shared state, rather than being explicitly dispatched by a coordinator. The two things to get right are mutually-exclusive predicates that partition the integers (so 15's multiples go to fizzbuzz, not fizz/buzz) and notify_all so the one matching worker is always woken among the four waiters:

FIZZBUZZ MULTITHREADED (LeetCode 1195): 4 threads print fizz/buzz/fizzbuzz/number for 1..n
  routed by DIVISIBILITY = four-way turn-taking

PREDICATE-GATED SOLUTION (mutex + cond var + shared `current`):
  every thread loops:
    lock; while current<=n and current NOT mine: cond.wait()
    if current>n: notify_all; return
    print my token; current += 1; cond.notify_all(); unlock
  predicates: fizzbuzz current%15==0 | fizz %3==0 and %5!=0 | buzz %5==0 and %3!=0
              | number %3!=0 and %5!=0

PATTERN: PREDICATE-GATED WORKERS -> workers SELF-SELECT via a predicate over shared state
  (vs Zero-Even-Odd's explicit COORDINATOR that signals the chosen worker)
  coordinator: natural every-step driver, few workers
  predicate-gated: clean state-function routing, several symmetric workers

PITFALLS:
  check %3/%5 BEFORE %15 -> fizzbuzz never fires (test 15 first / mutually-exclusive predicates)
  notify (not notify_all) -> wrong waiter woken, right one stalls (one CV, 4 waiters)
  if (not while) -> prints out of turn | missing current>n termination -> threads hang

FizzBuzz completes the sequencing problems - turn-taking routed by a rule. The next problem introduces a genuinely different kind of coordination: not "take turns" but "assemble a group before anyone proceeds" - "Building H2O," where threads must bond into molecules of exactly two hydrogens and one oxygen.

Back to Concurrency Interview Mastery