Two different threads will call foo and bar respectively. Design a mechanism so that "foobar" is printed n times by alternating between the two threads: foo always prints first, then bar, then foo again, and so on.

Examples

Example 1:

Input: n = 1
Output: "foobar"

Example 2:

Input: n = 2
Output: "foobarfoobar"

Constraints

  • 1 <= n <= 1000

Thinking Process

This is a classic producer-consumer synchronization problem. Two threads must take strict turns:

Thread A (foo): print "foo" only when it's foo's turn
Thread B (bar): print "bar" only when it's bar's turn
foo → bar → foo → bar → ...

Synchronization Pattern

We need:

  1. Mutual exclusion – only one thread prints at a time
  2. Ordering – foo always goes before bar in each round

A mutex + condition variable + boolean flag achieves both:

  • foo_turn = true means it’s foo’s turn
  • Each thread waits until the flag matches its turn, prints, flips the flag, and notifies the other

How condition_variable::wait Works

cv.wait(lock, predicate);

This atomically:

  1. Checks predicate() – if true, proceeds immediately
  2. If false, releases the lock and sleeps
  3. On notify_all, re-acquires the lock and re-checks the predicate
  4. Repeats until predicate is true

The predicate prevents spurious wakeups – a thread only proceeds when the condition is actually met.

Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Brute force (this problem) Often O(n^2) or O(2^n) O(n) Baseline; clarifies the optimization target
Sort + scan O(n log n) O(1) Pairs, intervals, greedy ordering
Hash map / set O(n) O(n) Frequency, membership, two-sum style
Single-pass linear O(n) O(1) Two pointers, sliding window, Kadane

Solution

class FooBar {
private:
    int n;
    mutex mtx;
    condition_variable cv;
    bool foo_turn = true;

public:
    FooBar(int n) {
        this->n = n;
    }

    void foo(function<void()> printFoo) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [this]() { return foo_turn; });

            printFoo();

            foo_turn = false;
            cv.notify_all();
        }
    }

    void bar(function<void()> printBar) {
        for (int i = 0; i < n; i++) {
            unique_lock<mutex> lock(mtx);
            cv.wait(lock, [this]() { return !foo_turn; });

            printBar();

            foo_turn = true;
            cv.notify_all();
        }
    }
};

Solution Explanation

Approach: Brute force (this problem)

Key idea: This is a classic producer-consumer synchronization problem. Two threads must take strict turns:

How the code works:

  1. Mutual exclusion – only one thread prints at a time
  2. Ordering – foo always goes before bar in each round
    • foo_turn = true means it’s foo’s turn
    • Each thread waits until the flag matches its turn, prints, flips the flag, and notifies the other
  3. Checks predicate() – if true, proceeds immediately
  4. If false, releases the lock and sleeps

Walkthrough — input n = 1, expected output "foobar":

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Comparison

Approach Mechanism Complexity Notes
Mutex + CV mutex + condition_variable + flag More boilerplate Works in C++11+
Binary Semaphore binary_semaphore pair Minimal, elegant Requires C++20

Execution Trace

n = 2, foo_turn = true

foo thread:  wait(foo_turn=true) → passes → print "foo" → foo_turn=false → notify
bar thread:  wait(!foo_turn=true) → passes → print "bar" → foo_turn=true  → notify
foo thread:  wait(foo_turn=true) → passes → print "foo" → foo_turn=false → notify
bar thread:  wait(!foo_turn=true) → passes → print "bar" → foo_turn=true  → notify

Output: "foobarfoobar"

Key Components

Component Role
mutex Ensures only one thread accesses shared state at a time
condition_variable Allows threads to sleep/wake efficiently (no busy-waiting)
unique_lock RAII wrapper that locks on construction, unlocks on destruction
foo_turn Boolean flag encoding whose turn it is
notify_all Wakes the other thread to check its condition

Common Mistakes

  • Using notify_one vs notify_all – both work here (only 2 threads), but notify_all is safer in general
  • Forgetting the predicate in cv.wait – without it, spurious wakeups can cause out-of-order printing
  • Using lock_guard instead of unique_lock – condition_variable::wait requires unique_lock because it needs to temporarily release the lock

References

Key Takeaways

  • “Alternate between two threads” = mutex + condition variable + boolean flag
  • The cv.wait(lock, predicate) pattern is the idiomatic C++ way to handle conditional synchronization
  • This is the simplest form of the producer-consumer pattern with exactly two participants