Build Multithreaded FizzBuzz
Build Multithreaded FizzBuzz
Everyone knows single-threaded FizzBuzz in thirty seconds. The interview twist — four threads, one for fizz, one for buzz, one for fizzbuzz, one for plain numbers, all printing 1..n in the exact right order — is a completely different problem wearing a childish costume, and that's exactly why Meta/Google/Amazon-tier interviewers reach for it: it looks trivial, so a candidate who hasn't internalized synchronization primitives will start typing immediately and produce garbage. This lab makes you build the coordination mechanism from an empty file, in Java and Go, break it on purpose, and fix it for real. It also underpins the FizzBuzz Multithreading Problem page — do this lab first, that page will read like a victory lap.
1. The trap
The brief: 4 threads, one role each. numberThread prints every i where i%3!=0 && i%5!=0; fizzThread prints "fizz" where i%3==0 && i%5!=0; buzzThread prints "buzz" where i%5==0 && i%3!=0; fizzbuzzThread prints "fizzbuzz" where i%15==0. The "obvious" first draft: give each thread the whole range and let it filter its own numbers.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
/**
* The "obvious" first draft: four threads, each independently looping the
* FULL range 1..n and printing whenever ITS OWN condition matches. No shared
* state, no coordination -- just four uncoordinated copies of FizzBuzz logic
* racing to System.out.println. Demonstrates the trap: correct per-number
* logic is not the hard part; producing ONE interleaved in-order sequence
* from four independent threads is.
*/
public final class NaiveMain {
public static void main(String[] args) throws InterruptedException {
int n = 20;
final List<String> out = Collections.synchronizedList(new ArrayList<String>());
CountDownLatch done = new CountDownLatch(4);
// four threads, each independently scanning the FULL range 1..n
Thread tFizz = new Thread(() -> {
for (int i = 1; i <= n; i++) if (i % 3 == 0 && i % 5 != 0) out.add("fizz");
done.countDown();
});
Thread tBuzz = new Thread(() -> {
for (int i = 1; i <= n; i++) if (i % 5 == 0 && i % 3 != 0) out.add("buzz");
done.countDown();
});
// ...and so on for fizzbuzz / number
Thread tFizzBuzz = new Thread(() -> {
for (int i = 1; i <= n; i++) if (i % 15 == 0) out.add("fizzbuzz");
done.countDown();
});
Thread tNumber = new Thread(() -> {
for (int i = 1; i <= n; i++) if (i % 3 != 0 && i % 5 != 0) out.add(String.valueOf(i));
done.countDown();
});
tFizz.start(); tBuzz.start(); tFizzBuzz.start(); tNumber.start();
done.await();
String expected = "1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz,16,17,fizz,19,buzz";
String actual = String.join(",", out);
System.out.println("expected = " + expected);
System.out.println("actual = " + actual);
System.out.println(actual.equals(expected) ? "matches (would be luck)" : "TRAP CONFIRMED: right values, WRONG interleaving -- not usable output");
}
}
Run it for n = 20 with all four threads started together. Each thread's own filter logic is correct — that was never the hard part — but here's what a real run produced:
expected = 1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz,16,17,fizz,19,buzz
actual = fizz,fizz,fizz,fizz,fizz,buzz,buzz,buzz,fizzbuzz,1,2,4,7,8,11,13,14,16,17,19
TRAP CONFIRMED: right values, WRONG interleaving -- not usable output
Every value that got printed is individually correct — there really are five "fizz"s, three "buzz"es, one "fizzbuzz" in 1..20. But the OS scheduler ran each thread to completion (or close to it) before the next got real CPU time, so the output is four correct answers to four different questions, concatenated in whatever order the scheduler felt like — not the ONE interleaved, in-order stream the spec demands. Four independent loops racing to print() with zero coordination cannot produce "in order" by construction, no matter how correct each thread's own filter is. That's the trap: this isn't a bug you fix by tightening one condition, it's a missing mechanism — nothing tells thread N "wait, it isn't your turn yet."
2. Scope it like a senior
Before writing a line, pin the contract down. Ask:
- What does "in order" mean, precisely? The combined output stream, read top to bottom across all four threads, must equal the single-threaded FizzBuzz sequence for
1..n— not "each thread's own subsequence is sorted," which the naive version already satisfies and is still wrong. - Is the thread-to-role mapping fixed? Yes — one thread owns
fizz, one ownsbuzz, one ownsfizzbuzz, one owns plain numbers, for the life of the run. (Contrast with work-stealing pools where any worker can take any task — that's a different problem with a different mechanism.) - Do threads busy-poll or block? Busy-polling ("keep checking if it's my turn") burns a full core per idle thread for no work — unacceptable with only 4 threads, catastrophic if this pattern generalizes to more roles. We need real blocking: a thread that isn't up should consume zero CPU until woken.
- What if the thread that starts isn't the one whose number is first? All four threads should be startable in ANY order (this is the realistic case — you don't control OS thread scheduling) and the output must still come out correct. If your design only works when threads happen to start in role order, it's not actually correct, it's lucky.
- Fixed vs. dynamic thread count? Exactly 4 roles here, but note where the design would need to change if a 5th role (say, multiples of 7 — "buzzfizz") were added mid-design — that's a good measure of whether the mechanism is principled or hard-coded.
Answering these up front is what separates "I can write a for-loop" from "I understand what's actually being tested here" — the interviewer already knows you can FizzBuzz; they're grading how you reason about coordinating independent threads around one shared sequence.
3. Reason to the design
Attempt 0 — busy-wait polling. Give every thread a shared counter cur and have each thread spin: while (cur <= n) { if (matchesMyRole(cur)) { print(); cur++; } }. This "works" in the sense that it can produce correct output, but three of the four threads are spinning at 100% CPU at every instant they're not the active one — for 4 threads that's up to 3 wasted cores doing nothing but polling a variable. It also has a genuine race: two threads can both read cur, both see it matches nobody, or worse, both think it's their turn if the role check and the increment aren't atomic together. Not viable past a toy example.
Attempt 1 — one shared counter behind a single lock, still polling inside it. Wrapping the check-and-increment in a synchronized block fixes the correctness race but not the waste: threads still spin, just now serialized through a lock instead of raw memory reads. Worse, actually — now they're fighting over the lock too. You need a way to make a thread actually stop running until specifically notified, not a tighter spin.
Attempt 2 — the relay baton (the real mechanism). Model this as a token that visits exactly one of four "mailboxes," one per role, in the sequence dictated by cur % 15. A thread blocks on ITS OWN mailbox (no polling, no wasted CPU); whichever thread currently holds the token does its print, advances cur, and drops the token in whichever mailbox matches the new cur's category. Two implementations of "mailbox," same idea:
- Java: a semaphore per role.
semNumberstarts with 1 permit (becausecur=1is a plain number);semFizz,semBuzz,semFizzBuzzstart at 0. A thread callsacquire()on its own semaphore — if the permit isn't there, the thread genuinely sleeps (no CPU spent), handled by the OS scheduler, not your code. Whoever finishes a print releases exactly the ONE semaphore matching the nextcur. - Go: a buffered channel per role. Same idea, no lock needed at all — a buffered channel of capacity 1 IS the mailbox; a send is a release, a receive is an acquire, and Go's channel operations carry their own documented happens-before guarantee, so
curis safe to touch without a separate mutex as long as exactly one goroutine ever holds the token.
The one rule that makes or breaks this: exactly ONE mailbox may ever hold a token at a time. That's not an implementation detail, it is the correctness argument — if you can prove "at most one role is ever runnable," you've proven both no duplicate work (only the active role prints) and no missed work (someone always gets woken next, because advance() unconditionally hands the token to exactly one of the four). Movement 5 breaks this invariant on purpose so you feel why it's load-bearing.
4. Build it — milestones
Attempt each milestone yourself before reading the reference implementation — the reveal is positioned after the tests on purpose.
- Core contract: four methods (
number(IntConsumer),fizz(Runnable),buzz(Runnable),fizzbuzz(Runnable)), each meant to be run on its own dedicated thread, each taking a print callback so the mechanism is testable without touchingSystem.outdirectly. - M1 — single relay, fixed n. Build the token-passing mechanism for a hard-coded small
n(say 20) and confirm the combined output is exactly the sequential FizzBuzz sequence, regardless of which thread'sstart()call happens to run first. - M2 — prove start-order independence. Start the four threads in a deliberately "wrong" order (buzz, fizzbuzz, number, fizz) five times in a row and confirm identical, correct output every time — this is the test that actually distinguishes "I understand the mechanism" from "it happened to work once."
- M3 — generalize to a 5th role. Add a role for multiples of 7 alone (call it "buzzfizz" for fun) without touching the other four methods' logic — only
advance()'s routing table changes. If this requires rewriting the mechanism, the design was accidentally coupled to "exactly 4." - M4 — clean shutdown. Confirm all four threads actually terminate (no thread left blocked forever on an empty mailbox) once
cur > n— the "who wakes the sleepers when there's no more work" problem, same shape as the graceful-shutdown milestone in any producer/consumer design.
Reference implementation — Java (one semaphore per role)
Notice there is no if (cur % 3 == 0) check anywhere inside fizz() — the thread trusts that if its semaphore released a permit, cur IS a fizz number. The permit itself is the only "check" that exists. That's the whole mechanism in one sentence.
import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;
/**
* Correct design: one shared counter `cur`, four semaphores acting as a relay
* baton. Exactly ONE semaphore holds a permit at any instant -- whichever
* matches the category of `cur`. A thread that acquires its semaphore is
* therefore guaranteed cur is its number; no thread ever checks cur%3/%5
* itself, the permit IS the gate.
*/
public final class FizzBuzz {
private final int n;
private int cur = 1;
private final Semaphore semNumber = new Semaphore(1); // cur=1 is a plain number -- seed here
private final Semaphore semFizz = new Semaphore(0);
private final Semaphore semBuzz = new Semaphore(0);
private final Semaphore semFizzBuzz = new Semaphore(0);
public FizzBuzz(int n) { this.n = n; }
/** Advance cur and hand the baton to whichever semaphore matches the next number. */
private void advance() {
cur++;
if (cur > n) {
// Done: release everyone so blocked threads can wake, see cur > n, and exit.
semNumber.release();
semFizz.release();
semBuzz.release();
semFizzBuzz.release();
return;
}
if (cur % 15 == 0) semFizzBuzz.release();
else if (cur % 3 == 0) semFizz.release();
else if (cur % 5 == 0) semBuzz.release();
else semNumber.release();
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
semFizzBuzz.acquire();
if (cur > n) return;
printFizzBuzz.run();
advance();
}
}
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
semFizz.acquire();
if (cur > n) return;
printFizz.run();
advance();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
semBuzz.acquire();
if (cur > n) return;
printBuzz.run();
advance();
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
while (true) {
semNumber.acquire();
if (cur > n) return;
printNumber.accept(cur);
advance();
}
}
}
Driven from four threads, started in a deliberately non-role order to prove the mechanism doesn't depend on start order:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
public final class Main {
public static void main(String[] args) throws InterruptedException {
int n = 20;
final List<String> out = Collections.synchronizedList(new ArrayList<String>());
FizzBuzz fb = new FizzBuzz(n);
CountDownLatch done = new CountDownLatch(4);
Thread tFizz = new Thread(() -> {
try { fb.fizz(() -> out.add("fizz")); } catch (InterruptedException e) {}
done.countDown();
});
Thread tBuzz = new Thread(() -> {
try { fb.buzz(() -> out.add("buzz")); } catch (InterruptedException e) {}
done.countDown();
});
Thread tFizzBuzz = new Thread(() -> {
try { fb.fizzbuzz(() -> out.add("fizzbuzz")); } catch (InterruptedException e) {}
done.countDown();
});
Thread tNumber = new Thread(() -> {
try { fb.number(i -> out.add(String.valueOf(i))); } catch (InterruptedException e) {}
done.countDown();
});
// Start in a "random" order on purpose -- the design must not depend on start order.
tBuzz.start(); tFizzBuzz.start(); tNumber.start(); tFizz.start(); // order scrambled on purpose
done.await();
String expected = "1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz,16,17,fizz,19,buzz";
String actual = String.join(",", out);
System.out.println("expected = " + expected);
System.out.println("actual = " + actual);
System.out.println(actual.equals(expected) ? "PASS: in-order, correctly typed" : "FAIL");
}
}
Run five times in a row, this produced the identical, correct sequence every time:
actual = 1,2,fizz,4,buzz,fizz,7,8,fizz,buzz,11,fizz,13,14,fizzbuzz,16,17,fizz,19,buzz
PASS: in-order, correctly typed (5/5 runs identical)
Reference implementation — Go (buffered channel per role)
Same mechanism, no lock at all — a channel of capacity 1 is the mailbox, and Go's own memory model guarantees a send happens-before the matching receive completes, which is exactly the ordering guarantee this design needs on cur.
package fizzbuzzlab
// FizzBuzz is the channel-baton design: cur is shared, but only ONE
// goroutine ever holds the baton (a token on its own buffered channel) at
// a time. Whoever finishes a print decides who gets the next token based
// on cur's new value, so there is never a check-then-act race on cur --
// the token IS the lock, and the channel send/receive pair is what gives
// Go's memory model a documented happens-before edge between them.
type FizzBuzz struct {
n int
cur int
numCh, fizzCh, buzzCh, fbCh chan struct{}
}
func NewFizzBuzz(n int) *FizzBuzz {
fb := &FizzBuzz{
n: n,
cur: 1,
numCh: make(chan struct{}, 1),
fizzCh: make(chan struct{}, 1),
buzzCh: make(chan struct{}, 1),
fbCh: make(chan struct{}, 1),
}
fb.numCh <- struct{}{} // seed: cur=1 is a plain number -- ONLY this channel starts loaded
return fb
}
func (fb *FizzBuzz) advance() {
fb.cur++
if fb.cur > fb.n {
close(fb.numCh)
close(fb.fizzCh)
close(fb.buzzCh)
close(fb.fbCh)
return
}
switch {
case fb.cur%15 == 0:
fb.fbCh <- struct{}{}
case fb.cur%3 == 0:
fb.fizzCh <- struct{}{}
case fb.cur%5 == 0:
fb.buzzCh <- struct{}{}
default:
fb.numCh <- struct{}{}
}
}
func (fb *FizzBuzz) Number(print func(int)) {
for range fb.numCh {
print(fb.cur)
fb.advance()
}
}
func (fb *FizzBuzz) Fizz(print func()) {
for range fb.fizzCh {
print()
fb.advance()
}
}
func (fb *FizzBuzz) Buzz(print func()) {
for range fb.buzzCh {
print()
fb.advance()
}
}
func (fb *FizzBuzz) FizzBuzzOut(print func()) {
for range fb.fbCh {
print()
fb.advance()
}
}
Closing all four channels once cur > n is Go's version of M4: a for range over a closed, empty channel simply exits the loop, so every one of the four goroutines terminates cleanly with no explicit shutdown protocol needed — the channel close IS the shutdown signal. Verified clean:
$ go build ./...
$ go vet ./...
$ go test -race -count=3 -run TestFizzBuzzInOrder -v ./...
--- PASS: TestFizzBuzzInOrder (0.00s) (x3, identical output every time)
PASS
ok fizzbuzzlab 1.5s
5. Break it — the test that fails
Change exactly one thing: seed every semaphore/channel with a starting token instead of just the "number" one. In Java, that's new Semaphore(1) for semFizz/semBuzz/semFizzBuzz instead of new Semaphore(0). Nothing else changes — same advance(), same acquire/print/advance loop in every method.
import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;
/**
* BuggyFizzBuzz -- the ONLY change from FizzBuzz.java: every semaphore is
* seeded with 1 permit instead of only semNumber. That is the ONLY change
* from FizzBuzz.java. It destroys the gate: on the very first tick all four
* threads can acquire simultaneously, so more than one thread believes it
* owns `cur` at once.
*/
public final class BuggyFizzBuzz {
private final int n;
private int cur = 1;
private final Semaphore semNumber = new Semaphore(1);
private final Semaphore semFizz = new Semaphore(1); // BUG: should be 0
private final Semaphore semBuzz = new Semaphore(1); // BUG: should be 0
private final Semaphore semFizzBuzz = new Semaphore(1); // BUG: should be 0
public BuggyFizzBuzz(int n) { this.n = n; }
private void advance() {
cur++;
if (cur > n) {
semNumber.release();
semFizz.release();
semBuzz.release();
semFizzBuzz.release();
return;
}
if (cur % 15 == 0) semFizzBuzz.release();
else if (cur % 3 == 0) semFizz.release();
else if (cur % 5 == 0) semBuzz.release();
else semNumber.release();
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
semFizzBuzz.acquire();
if (cur > n) return;
printFizzBuzz.run();
advance();
}
}
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
semFizz.acquire();
if (cur > n) return;
printFizz.run();
advance();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
semBuzz.acquire();
if (cur > n) return;
printBuzz.run();
advance();
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
while (true) {
semNumber.acquire();
if (cur > n) return;
printNumber.accept(cur);
advance();
}
}
}
The reasoning: with all four semaphores holding a permit at start, all four threads can call acquire() successfully on tick one — before anyone has checked whether cur actually belongs to them, because no thread ever checked in the first place; the permit WAS the only check. Multiple threads now believe, simultaneously, that they own cur. Run it three times at n = 20:
run 1 actual = fizzbuzz,fizz,buzz,fizz,buzz,1,7,8,9,10,buzz,11,13,14,fizz,fizz,16,fizz,18,fizz,fizzbuzz
run 1 length = 21 (expected 20)
run 1 result = BUG REPRODUCED: wrong/jumbled/duplicated output
run 2 actual = buzz,1,3,4,fizz,fizz,fizz,8,buzz,buzz,9,fizz,13,fizz,15,16,fizzbuzz,17,19,fizzbuzz
run 2 length = 20 (expected 20)
run 2 result = BUG REPRODUCED: wrong/jumbled/duplicated output
run 3 actual = buzz,fizzbuzz,3,4,5,buzz,fizz,fizz,8,fizz,fizz,12,fizz,14,15,buzz,16,fizzbuzz,19,20
run 3 length = 20 (expected 20)
run 3 result = BUG REPRODUCED: wrong/jumbled/duplicated output
Look closely at run 2: position 3 (which should be "fizz", since 3%3==0) prints the literal number 3 instead — the "number" thread grabbed a stray permit and printed a plain number for a value that was never its own to print, while some other thread's turn silently got skipped or double-taken. cur itself gets incremented by whichever threads race through advance() concurrently — sometimes twice for one printed value, sometimes a category never gets checked at all. Every run above is deterministically wrong; only the exact shape of the wrongness varies.
The Go equivalent — seed every channel with a token instead of just numCh — is, if anything, a more dramatic demonstration, because it doesn't just corrupt output, it can deadlock or panic outright:
package fizzbuzzlab
// BuggyFizzBuzz is the SAME design with ONE change: every channel is seeded
// with a token at construction instead of only numCh. That destroys the
// baton -- all four goroutines can proceed on the very first tick.
type BuggyFizzBuzz struct {
n int
cur int
numCh, fizzCh, buzzCh, fbCh chan struct{}
}
func NewBuggyFizzBuzz(n int) *BuggyFizzBuzz {
fb := &BuggyFizzBuzz{ /* ... same fields ... */
n: n,
cur: 1,
numCh: make(chan struct{}, 1),
fizzCh: make(chan struct{}, 1),
buzzCh: make(chan struct{}, 1),
fbCh: make(chan struct{}, 1),
}
fb.numCh <- struct{}{}
fb.fizzCh <- struct{}{} // BUG: should stay empty until cur%3==0
fb.buzzCh <- struct{}{} // BUG: should stay empty until cur%5==0
fb.fbCh <- struct{}{} // BUG: should stay empty until cur%15==0
return fb
}
func (fb *BuggyFizzBuzz) advance() {
fb.cur++
if fb.cur > fb.n {
close(fb.numCh)
close(fb.fizzCh)
close(fb.buzzCh)
close(fb.fbCh)
return
}
switch {
case fb.cur%15 == 0:
fb.fbCh <- struct{}{}
case fb.cur%3 == 0:
fb.fizzCh <- struct{}{}
case fb.cur%5 == 0:
fb.buzzCh <- struct{}{}
default:
fb.numCh <- struct{}{}
}
}
func (fb *BuggyFizzBuzz) Number(print func(int)) {
for range fb.numCh {
print(fb.cur)
fb.advance()
}
}
func (fb *BuggyFizzBuzz) Fizz(print func()) {
for range fb.fizzCh {
print()
fb.advance()
}
}
func (fb *BuggyFizzBuzz) Buzz(print func()) {
for range fb.buzzCh {
print()
fb.advance()
}
}
func (fb *BuggyFizzBuzz) FizzBuzzOut(print func()) {
for range fb.fbCh {
print()
fb.advance()
}
}
$ go test -count=1 -run TestBrokenWithoutBaton -v ./...
buggy_test.go:50: actual (partial if deadlocked) = fizz,2,3,4,fizz,fizz,buzz,8,9,fizz,buzz,buzz,fizz,14,fizzbuzz,16
buggy_test.go:51: items printed = 16 (expected 20)
buggy_test.go:54: BUG REPRODUCED: deadlock -- seeding every channel let threads race for cur=1;
the loser(s) of that race are left waiting on a token nobody will ever send again.
--- PASS: TestBrokenWithoutBaton (2.00s)
$ go test -race -count=1 -run TestBrokenWithoutBaton -v ./...
==================
WARNING: DATA RACE
Read at 0x00c00011b058 by goroutine 7: ...(*BuggyFizzBuzz).advance()
Previous write at 0x00c00011b058 by goroutine 10: ...(*BuggyFizzBuzz).advance()
==================
--- FAIL: TestBrokenWithoutBaton (2.00s)
FAIL
Two independent goroutines both entered advance() "at the same time" because two channels had a token neither should have had, so both read and wrote the unguarded fb.cur field concurrently — exactly the race the Go race detector exists to catch. Depending on timing, the same bug also manifests as a flat-out deadlock (a goroutine left waiting on a channel that will never receive another send, because the token that should have gone to it was consumed by an impostor earlier) or a panic: close of closed channel (two goroutines both decide cur > n and both call close() on the same channel). Three different failure shapes, one root cause: the invariant "exactly one mailbox holds a token" was never true to begin with.
6. Optimise — with trade-offs
| Approach | Overhead | Simplicity | Generalizes to N roles? | Use when |
|---|---|---|---|---|
| Semaphore relay (this lab, Java) | Low — OS-level blocking, no spin, one acquire/release pair per tick | Moderate — you own the routing table in advance() | Yes — add a semaphore + a routing branch, nothing else changes (M3) | Default choice for a fixed, small set of cooperating roles sharing one sequence |
| Buffered channel relay (this lab, Go) | Low, comparable to semaphores | Highest of the Go options — no explicit lock, the channel op is the synchronization | Yes, same shape as Java | Any Go program with this exact "fixed roles, shared turn order" shape |
| Single lock + one shared condition variable, all four threads check their own predicate | Higher — every tick wakes ALL waiters (thundering herd), each re-checks and three go back to sleep | Lower — you must write the while(!isMyTurn(cur)) loop yourself and get the re-check right (the exact "while not if" lesson from the bounded-buffer lab) | Yes, but the routing logic lives inside every thread instead of one central place | You need threads to also observe OTHER shared state beyond just "whose turn," where a single condition is simpler to reason about than N mailboxes |
| A single coordinator thread that calls all 4 print callbacks itself, in order, no worker threads at all | None — no synchronization needed, it's sequential | Highest | Trivially — it's just an if/else chain | When the "4 threads" requirement is artificial and the real ask is just correct FizzBuzz — but this defeats the actual point of the exercise, which is to demonstrate you can coordinate independent threads, so don't offer this as your answer in an interview without naming it as the degenerate case |
Barrier-based round-robin (e.g. CyclicBarrier) | Higher — every tick, ALL 4 threads rendezvous at the barrier even though only one has real work | Moderate | Awkward — a barrier assumes every party does something every round; here 3 of 4 parties do nothing most rounds | When every role genuinely has work every tick (this problem's real shape is "1 of 4," so a barrier is the wrong tool, but it's worth naming as the pattern for turn-based problems where all parties DO act each round, e.g. a fixed-round simulation) |
The real judgment call: the relay-baton (semaphore or channel) wins here because the problem's actual shape is "exactly one of N roles is active per tick" — a mechanism that lets 3-of-4 threads sleep with zero CPU cost while the active one runs is the natural fit. A single shared condition variable is the more general tool (it generalizes to conditions a fixed set of mailboxes can't express, like "wake when 2-of-4 sub-tasks finish") but costs you the thundering-herd tax and puts the routing logic in N places instead of one. Reach for the condition-variable version when the "whose turn" question can't be answered by a static routing table; default to the relay baton when it can — which is most turn-based, round-robin coordination problems, including this one.
7. Defend under drilling
An interviewer will push on the design. These are the follow-ups that come up almost every time, with the answer a staff engineer gives — short, concrete, no hedging.
- "Why not just use one lock and have every thread check
cur % 3/% 5itself?" You can — that's the condition-variable row in the trade-off table — but then every thread carries a copy of the routing logic, and every wake-up disturbs threads that turn out not to be up. The semaphore/channel version centralizes "whose turn is it" into one function (advance()), which is both easier to audit and cheaper at runtime, because a release/send only ever wakes the ONE thread that can actually proceed. - "What if two roles could legitimately be true for the same number?" They can't here by construction (the
%15/%3/%5branches inadvance()are mutually exclusive and exhaustive), but if they could, you'd need to decide whether BOTH threads print (then the "at most one active mailbox" invariant breaks on purpose, and you need a different mechanism, like releasing two semaphores and having whichever comes second wait on a barrier) or whether one wins by priority — naming this edge case unprompted is a strong signal. - "How does this generalize to a fully general turn-based scheduler — N roles, arbitrary turn order, not just a modulo pattern?" Replace the hard-coded
if/elsechain inadvance()with a lookup: a functionroleFor(cur) -> tokenthat can encode ANY deterministic sequence, and swap the fixed semaphore fields for aMap<Role, Semaphore>. The mechanism — exactly one mailbox holds a token at a time, whoever finishes routes the next token — doesn't change at all; only the routing function does. That's the generalization to a barrier/turn-based scheduler the design was hinting at from the start. - "What if a thread crashes mid-print, holding the token?" With this design there's no lock to leak — the "token" is just a semaphore permit or a channel send that already happened. If the thread dies after
acquire()but beforeadvance(), the token is simply gone forever and every other thread deadlocks waiting on a release that will never come. That's a real gap: production code would want a watchdog/timeout (Java:tryAcquire(timeout); Go:selectwithtime.After) so a stuck role degrades to a detectable failure instead of a silent hang — worth naming even though this lab's reference implementation doesn't include it. - "What breaks at 100× the number of roles?" Nothing about correctness breaks — the mechanism doesn't care if there are 4 mailboxes or 400. What breaks is efficiency of the routing function if it's a naive if/else chain (linear scan per tick); swap it for the
Map/table lookup from the generalization question and it's back to O(1) per tick regardless of role count. The thread-per-role model itself would start to strain the OS scheduler well before 400 threads, though — that's the point where you'd escalate to a single coordinator dispatching work to a fixed-size pool instead of one OS thread per role.
8. You can now defend
- You can implement a relay-baton mechanism from scratch — a semaphore per role in Java, a buffered channel per role in Go — that lets N-1 of N cooperating threads sleep at zero CPU cost while exactly one runs, in strict, deterministic order, regardless of thread start order.
- You've broken it with a one-line change (seed every mailbox instead of just one) and watched it fail three different ways — jumbled/duplicated output, a data race the race detector catches, and a genuine deadlock/panic — all from the same root cause: the "exactly one token exists" invariant was never true.
- You can place this design on a spectrum against a shared condition variable, a barrier, and the degenerate single-coordinator solution, and argue the overhead/simplicity/generality trade-off for each, with a concrete "use when."
- You can generalize the fixed 4-role modulo pattern to an arbitrary turn-based scheduler by isolating the routing function from the mechanism — and you can name the real production gap (a crashed thread holding the only token forever) unprompted.
Re-authored/Deepened for this guide. Reference code compiled and executed (javac/java; go build, go vet, go test -race) before publishing; the break-it scenarios reproduce wrong/jumbled output (Java) and a data race plus deadlock/panic (Go) deterministically across runs. See also: the FizzBuzz Multithreading Problem.
🤖 Don't fully get this? Learn it with Claude
Stuck on Build Multithreaded FizzBuzz? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.
Build the mental picture, not memorization.
I just read a lesson on **Build Multithreaded FizzBuzz** (Hands-On Builds) and want to truly understand it. Explain Build Multithreaded FizzBuzz 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.
Socratic — adapts to where you're stuck.
Teach me **Build Multithreaded FizzBuzz** 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.
Active recall exposes what you missed.
Quiz me on **Build Multithreaded FizzBuzz** 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.
Intuition + hook + flashcards for long-term memory.
Help me remember **Build Multithreaded FizzBuzz** 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.