AlgoInsight

Free lesson · Concurrency Interview Mastery

Print Foo Bar Alternately

Hard10 min readconcurrencymultithreadinginterview-prep

Welcome to the classic synchronization problems - the canonical puzzles that have been used for decades to teach coordination, and that show up directly in interviews and on LeetCode's concurrency section. Everything in the earlier modules was groundwork; this module is where you apply the primitives, patterns, and pitfalls to concrete problems. We start with the simplest coordination there is: making two threads strictly take turns. In "Print FooBar Alternately," one thread prints foo and another prints bar, n times each, and the output must alternate perfectly - foobarfoobar... - never foofoo or barbar. It sounds trivial, but it's the cleanest possible introduction to the ping-pong coordination that underlies all turn-taking, and the technique here - paired signals where one starts available and the other starts blocked - recurs throughout the rest of the module. Master this and you have the template for two-thread alternation.

The problem

Two threads share an object with two methods. One thread repeatedly calls foo(), which prints "foo"; the other repeatedly calls bar(), which prints "bar". Each is called n times. The required output is foo and bar strictly alternating, starting with foo: for n = 3, exactly foobarfoobar foobar → "foobarfoobarfoobar". The challenge is that the two threads run concurrently with no inherent ordering, so without coordination you'd get an arbitrary interleaving - foofoobarbar, barfoo..., anything. You must force the exact sequence: foo, then bar, then foo, then bar, and so on, with each thread waiting its turn.

The essential requirements: foo must go first; after each foo, the next print must be bar; after each bar, the next must be foo (until both have run n times). This is strict alternation between two threads - neither may run twice in a row.

The core idea: ping-pong with two semaphores

The cleanest solution uses two binary semaphores that pass a single "permission to print" back and forth - a ping-pong. One semaphore (fooSem) starts available (value 1), the other (barSem) starts blocked (value 0). Each thread waits on its semaphore before printing and signals the other's semaphore after printing, handing the turn across:

fooSem = Semaphore(1)    # starts AVAILABLE -> foo goes first
barSem = Semaphore(0)    # starts BLOCKED   -> bar waits

function foo():
    for i in 1..n:
        fooSem.acquire()     # wait for my turn
        print("foo")
        barSem.release()     # hand the turn to bar

function bar():
    for i in 1..n:
        barSem.acquire()     # wait for my turn
        print("bar")
        fooSem.release()     # hand the turn back to foo

The mechanism is a tight hand-off. Initially only fooSem is available, so foo proceeds while bar blocks on its acquire. After foo prints, it releases barSem, which unblocks bar; meanwhile foo loops back and blocks on fooSem (now 0). bar prints and releases fooSem, unblocking foo again. The single unit of permission ping-pongs between the two semaphores, and because each thread blocks on its own semaphore until the other hands it over, strict alternation is guaranteed - neither can run twice because after printing it must wait for the other to release it again. The asymmetric initial values (1 and 0) are what make foo go first; that's the whole trick to "who starts."

sequenceDiagram
    participant F as foo thread
    participant FS as fooSem (1)
    participant BS as barSem (0)
    participant B as bar thread
    F->>FS: acquire (gets it, =0)
    F->>F: print "foo"
    F->>BS: release (=1)
    B->>BS: acquire (gets it, =0)
    B->>B: print "bar"
    B->>FS: release (=1)
    Note over F,B: turn ping-pongs back to foo; repeat n times

This sequence diagram shows the ping-pong between two threads using two semaphores. The foo semaphore starts at one (available) and the bar semaphore starts at zero (blocked), so foo goes first. The foo thread acquires the foo semaphore, bringing it to zero, prints foo, then releases the bar semaphore, bringing it to one. Now the bar thread, which was blocked, acquires the bar semaphore, prints bar, and releases the foo semaphore. The single unit of permission ping-pongs back and forth between the two semaphores, so the threads strictly alternate: foo, bar, foo, bar, repeated n times. The asymmetric starting values - one and zero - are what make foo go first.

An alternative: lock plus condition variable

The same alternation can be built with a mutex, a condition variable, and a shared turn flag - the monitor style from Module 3:

lock = Lock()
cond = Condition(lock)
turn = "foo"          # whose turn it is

function foo():
    for i in 1..n:
        lock.acquire()
        while turn != "foo":      # wait until it's foo's turn (while-loop!)
            cond.wait()
        print("foo")
        turn = "bar"              # set next turn
        cond.notify_all()         # wake the other
        lock.release()

function bar():
    for i in 1..n:
        lock.acquire()
        while turn != "bar":
            cond.wait()
        print("bar")
        turn = "foo"
        cond.notify_all()
        lock.release()

Here a shared turn variable explicitly tracks whose turn it is. Each thread waits in a while loop until turn names it (the while handling spurious and stolen wakeups, per Module 6), prints, flips turn to the other, and notifies. This is more verbose than the two-semaphore version but more general - it scales naturally to more than two parties (just more turn values) and makes the coordination state explicit. The two-semaphore version is more elegant for exactly two alternating threads; the condition-variable version generalizes better, which matters for the multi-party problems later in this module. Both are correct; knowing both, and when each is cleaner, is the goal.

Important: "Print FooBar Alternately" is the canonical two-thread strict alternation (ping-pong) problem. The cleanest solution: two binary semaphores, one starting available (1) and one blocked (0), where each thread waits on its own semaphore and signals the other's after printing - passing a single unit of permission back and forth. The asymmetric initial values (1 and 0) decide who goes first. Strict alternation is guaranteed because after printing, a thread must wait to be re-signaled by the other, so neither can run twice in a row. The alternative - mutex + condition variable + a turn flag (wait in a while loop until it's your turn, flip the flag, notify) - is more verbose but generalizes to more parties. Recognizing this as ping-pong, and the "one sem starts at 1, the other at 0" template, is the key takeaway that the rest of the module builds on.

Why this matters and common pitfalls

The ping-pong template is foundational because turn-taking is everywhere in coordination - any time two threads must alternate access to something, this is the shape. The pitfalls to avoid are instructive:

The deepest point: mutual exclusion and ordering are different problems. A mutex stops two threads from printing at the same time, but it does nothing to make them print in a particular order. This problem needs ordering, which is why it uses semaphores-as-signals or a condition variable with explicit turn state - coordination primitives that impose sequence, not just exclusion. Internalizing that distinction is the real lesson of the first classic problem.

A single-semaphore variant and the binary-flag idea

It's worth seeing that two semaphores aren't the only way - understanding the variants deepens the intuition. One compact alternative uses a single mutex/lock held across the alternation, with the threads spinning on a shared flag - but busy-waiting (Module 1) wastes CPU and is the wrong instinct here, so it's an anti-pattern to recognize rather than use. A better compact variant in some languages is a single binary semaphore plus a flag, but the two-semaphore approach is clearer precisely because it needs no shared flag: the state (whose turn it is) is encoded entirely in which semaphore currently holds the permission. That's an elegant property - the coordination state lives in the semaphores themselves, not in a separate variable you must protect. When fooSem holds the unit, it's foo's turn; when barSem holds it, it's bar's. There's no turn variable to race on because the semaphore values are the turn state.

This is a subtle but important idea that recurs in the harder problems: you can often encode coordination state in the semaphores/primitives themselves rather than in separate shared variables. Doing so eliminates a class of races (there's no shared flag to protect) and makes the solution more self-contained. The condition-variable version takes the opposite approach - explicit turn state guarded by the lock - which is more flexible but reintroduces the shared variable. Neither is universally better; the two-semaphore "state in the primitives" style is elegant for tight alternation, while the explicit-state style scales to complex sequencing. Seeing both ways to hold the same coordination state - implicitly in semaphores versus explicitly in a guarded variable - is a mental tool you'll reuse across this whole module.

Cross-language notes

The pattern translates directly across languages, with each providing the primitives:

The constant across all of them is the structure: a unit of permission passed back and forth, with asymmetric starting state deciding who goes first. Whether that unit lives in a semaphore, a condition-variable predicate, or a channel send is a language-idiom detail; the coordination shape is identical. A useful interview move is to give the semaphore solution and then mention the language-idiomatic variant (channels in Go, condition variables where semaphores aren't first-class), showing you understand the underlying pattern rather than memorizing one API.

Note: The "mutual exclusion is not ordering" distinction at the heart of this problem is one of the most important conceptual divides in all of concurrency, and it's worth fixing firmly now because every later problem in this module depends on it. A mutex answers the question "can these two threads be in the critical section at the same time?" - and its answer is always "no." But it says nothing about which thread goes first or in what order they take turns; whichever thread happens to grab the lock wins, and that's nondeterministic. Ordering is a different requirement entirely: it constrains the sequence of operations, not just their non-overlap. Semaphores used as signals (one thread releasing to unblock another) and condition variables (one thread notifying another that a predicate now holds) are ordering primitives - they let one thread cause another to proceed at a chosen moment. That's why FooBar can't be solved with a lock alone: "alternate strictly" is an ordering constraint, and you need a primitive that imposes sequence. Whenever a problem says "in order," "alternately," "before," or "after," you're facing an ordering problem and should reach for signaling primitives, not just mutual exclusion. Conversely, when a problem says "only one at a time" with no sequence requirement, a mutex suffices. Sorting every coordination requirement into "exclusion" versus "ordering" is the first analytical step for every problem ahead.

The interview angle

Interview: "Print FooBar Alternately" (LeetCode 1115) is a common warm-up concurrency interview question. The expected answer: two semaphores, one starting at 1 (foo) and one at 0 (bar), each thread waiting on its own and signaling the other's. Distinguishing details interviewers listen for: (1) why the asymmetric initial values - they make foo go first and bar wait; (2) why cross-signaling (each signals the other's semaphore) enforces alternation; (3) the condition-variable alternative with a turn flag and a while loop, and that it generalizes to more parties; (4) the key insight that a plain mutex is insufficient because this is an ordering problem, not just mutual exclusion. The strongest candidates name this as the ping-pong/turn-taking template and note it's the two-party base case of the multi-party turn-taking problems (Zero-Even-Odd, FizzBuzz) that follow.

Quick reference

The two-thread strict-alternation base case, and the cleanest demonstration that ordering is a distinct problem from mutual exclusion. The template to memorize is two binary semaphores with asymmetric initial values (one at 1, one at 0) where each thread waits on its own and signals the other's, passing a single unit of permission back and forth; the condition-variable-with-turn-flag form is the more general alternative that scales to more parties. The single most important takeaway is conceptual: a mutex gives you exclusion but never ordering, so any "alternate," "in order," or "before/after" requirement demands signaling primitives, with who-goes-first encoded in the asymmetric initial state. Get the initial values right, cross-signal the other thread rather than yourself, and re-check predicates in a while loop, and two-thread alternation is solved - a template you'll reuse directly in every turn-taking problem that follows in this module:

PRINT FOOBAR ALTERNATELY (LeetCode 1115): two threads strictly ALTERNATE -> foobarfoobar...
  = the TWO-THREAD TURN-TAKING / PING-PONG base case

TWO-SEMAPHORE SOLUTION (cleanest):
  fooSem=Semaphore(1)  # available -> foo first
  barSem=Semaphore(0)  # blocked   -> bar waits
  foo(): loop: fooSem.acquire(); print foo; barSem.release()   # wait MINE, signal OTHER
  bar(): loop: barSem.acquire(); print bar; fooSem.release()
  -> single unit of permission PING-PONGS; asymmetric 1/0 decides who starts

COND-VAR ALTERNATIVE (generalizes to >2 parties):
  shared turn flag; each thread: lock; while turn != me: wait; print; turn=other; notify_all
  (WHILE loop, not if -> spurious/stolen wakeups)

PITFALLS:
  both sems = 1 -> no alternation | both = 0 -> deadlock
  signal your OWN sem -> run twice (foofoo) ; must cross-signal the OTHER
  plain mutex alone -> NO ordering (mutex = exclusion, NOT sequence)

KEY INSIGHT: mutual EXCLUSION != ORDERING. alternation needs ordering primitives
  (signals / turn state), not just a lock.

Two-thread alternation is the base case. The next problem extends turn-taking to three threads with a specific cycle - "Print Zero Even Odd" - where one thread coordinates which of the other two goes next, introducing the coordinator technique that carries through the rest of the module.

Back to Concurrency Interview Mastery