Strict Alternating Output
Two threads must alternate strictly, A then B then A then B, n times. The canonical solution uses a Semaphore pair, with thread A holding the 'A's turn' permit and signaling B's after each step. Same pattern with wait/notify, asyncio.Event, or Go channels.
The problem
LeetCode 1115: Print FooBar Alternately, call printFoo() and printBar() alternately, n times each, output foobarfoobar.... Two threads run concurrently; they must coordinate so neither runs twice in a row.
What's actually being tested
The interviewer wants to see the candidate reach for the right primitive. Reaching for a synchronized block + volatile boolean works but is verbose; semaphores expose the alternation as a clean token-passing protocol.
How to think about it
Two threads share one invariant: exactly one of them is allowed to print at any moment, and they must take turns. That's two questions: mutual exclusion (only one prints) AND ordering (turns alternate).
The semaphore-pair pattern Given N states with an explicit "next" relation, give each state a semaphore. State i acquires sem[i] before doing its work, then releases sem[next(i)]. Initial permits set so exactly one state is ready. This generalizes to round-robin, conditional turns, and the dining philosophers' partial-ordering solutions.
Why this question gets asked
The variant questions (Print Zero Even Odd, FizzBuzz Multithreaded, Print in Order) are all the same coordination pattern with different turn rules. Solving this one cleanly solves the family. Walking interviewers through the pattern, then noting "this generalizes to N-thread round-robin via an array of semaphores," is the senior signal.
Edge cases that bite candidates
- Forgetting
try/finallyaround the semaphore release, Java throws on interrupt, leaks the permit forever. - Using
notify()instead ofnotifyAll()in the wait/notify version, works for 2 threads, breaks for >2. - Using
ifinstead ofwhilearoundawait(), spurious wakeups corrupt the turn flag.
Implementations
fooSem starts with 1 permit; barSem starts with 0. foo() acquires fooSem, prints, releases barSem. bar() does the reverse. Strict alternation, neither thread can run twice in a row.
1 import java.util.concurrent.Semaphore;
2
3 class FooBar {
4 private final int n;
5 private final Semaphore fooSem = new Semaphore(1);
6 private final Semaphore barSem = new Semaphore(0);
7
8 public FooBar(int n) { this.n = n; }
9
10 public void foo(Runnable printFoo) throws InterruptedException {
11 for (int i = 0; i < n; i++) {
12 fooSem.acquire(); // wait my turn
13 printFoo.run();
14 barSem.release(); // hand off to bar
15 }
16 }
17
18 public void bar(Runnable printBar) throws InterruptedException {
19 for (int i = 0; i < n; i++) {
20 barSem.acquire();
21 printBar.run();
22 fooSem.release();
23 }
24 }
25 }Same idea, lower-level primitive. The turn flag tracks whose turn it is; each thread waits while it's not its turn. notifyAll wakes the other thread.
1 class FooBar {
2 private final int n;
3 private final Object lock = new Object();
4 private boolean fooTurn = true;
5
6 public FooBar(int n) { this.n = n; }
7
8 public void foo(Runnable printFoo) throws InterruptedException {
9 for (int i = 0; i < n; i++) {
10 synchronized (lock) {
11 while (!fooTurn) lock.wait();
12 printFoo.run();
13 fooTurn = false;
14 lock.notifyAll();
15 }
16 }
17 }
18 public void bar(Runnable printBar) throws InterruptedException {
19 for (int i = 0; i < n; i++) {
20 synchronized (lock) {
21 while (fooTurn) lock.wait();
22 printBar.run();
23 fooTurn = true;
24 lock.notifyAll();
25 }
26 }
27 }
28 }Key points
- •Two semaphores, started with permits 1 and 0 respectively → enforces order
- •Each thread acquires its semaphore, prints, then releases the OTHER's semaphore
- •Equivalent patterns: wait/notify pair, two condition variables, two channels
- •Generalizes to N-thread round-robin (next lesson)