Three-Way Round-Robin Output
Three threads must produce 010203040..., Zero, then alternating Odd/Even. Three semaphores form a token-passing relay: Zero hands to Odd-or-Even based on parity; the parity thread hands back to Zero.
The problem
LeetCode 1116: Print Zero Even Odd, three threads coordinate to print 0102030405060708... for n=8. Zero, then alternating Odd/Even, separated by Zeros.
The difference from FooBar FooBar (previous lesson) was 2 threads alternating 1:1. This is 3 threads with conditional next-turn, Zero alternates between dispatching to Odd and Even based on the counter's parity. Same primitive, more interesting routing.
The pattern that scales
Token-passing relays Every "N threads in a defined sequence" problem has the same structure:
- Give each thread a semaphore (initial permit only on the first one to run).
- Each thread acquires its own semaphore, does its work, releases the next one's semaphore.
- The sequence is encoded in who releases whom.
Print-in-Order (next lesson) is N=3 strict relay. FooBar was N=2 alternating relay. This is N=3 conditional relay. Same engine, different routing logic.
What interviewers probe after the solution
- "Can this be done with one shared mutex and condition variables?" Yes, predicates on a shared counter. They want to see the candidate articulate the equivalence.
- "What if Zero, Odd, and Even threads start in any order, does this solution still work?" Yes,
zero_semstarts with 1 permit, the others with 0, so only Zero can proceed initially regardless of which thread reachedacquire()first. - "Does this solution scale to N threads?" Yes, array of semaphores, generalize the index math.
Common bug
Putting the parity check INSIDE the parity threads' loops instead of in zero(). That requires Odd and Even to each track their own progress and signal Zero correctly, works but the logic is split across three places. Centralizing the routing decision in Zero keeps the design clean.
Implementations
zero() always prints 0, then chooses to release oddSem or evenSem based on the next number's parity. The chosen thread prints, then releases zeroSem. The relay continues.
1 import java.util.concurrent.Semaphore;
2
3 class ZeroEvenOdd {
4 private final int n;
5 private final Semaphore zeroSem = new Semaphore(1);
6 private final Semaphore oddSem = new Semaphore(0);
7 private final Semaphore evenSem = new Semaphore(0);
8
9 public ZeroEvenOdd(int n) { this.n = n; }
10
11 public void zero(IntConsumer printNumber) throws InterruptedException {
12 for (int i = 1; i <= n; i++) {
13 zeroSem.acquire();
14 printNumber.accept(0);
15 if (i % 2 == 1) oddSem.release();
16 else evenSem.release();
17 }
18 }
19 public void odd(IntConsumer printNumber) throws InterruptedException {
20 for (int i = 1; i <= n; i += 2) {
21 oddSem.acquire();
22 printNumber.accept(i);
23 zeroSem.release();
24 }
25 }
26 public void even(IntConsumer printNumber) throws InterruptedException {
27 for (int i = 2; i <= n; i += 2) {
28 evenSem.acquire();
29 printNumber.accept(i);
30 zeroSem.release();
31 }
32 }
33 }Key points
- •Three semaphores: zeroSem (starts 1), oddSem (0), evenSem (0)
- •Zero always runs after every digit; parity thread alternates 'who's next' based on counter
- •Generalizes the strict-alternation pattern to conditional next-turn
- •wait/notify version: shared int + condition variables, harder to get right