# Print FooBar Alternately
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/print-foobar-alternately)
Canonical: https://scaleengineer.com/dsa/problems/print-foobar-alternately
---
## Problem
Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of `FooBar` will be passed to two different threads:

* thread `A` will call `foo()`, while
* thread `B` will call `bar()`.

Modify the given program to output `"foobar"` `n` times.

**Example 1:**

**Input:** n = 1
**Output:** "foobar"
**Explanation:** There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().
"foobar" is being output 1 time.

**Example 2:**

**Input:** n = 2
**Output:** "foobarfoobar"
**Explanation:** "foobar" is being output 2 times.

**Constraints:**

* `1 <= n <= 1000`

# Approaches
## Busy-Waiting with a volatile Flag (Spinlock)
This approach uses a shared `volatile` boolean flag to control which thread's turn it is. The waiting thread continuously checks this flag in a tight loop (a "spin-wait" or "busy-wait") until it's its turn to print. This is the simplest but least efficient method.
**Time:** O(n * k), where `n` is the number of pairs to print and `k` represents the time wasted in the spin loop. This approach is very inefficient in terms of CPU usage, as the waiting thread is always active. · **Space:** O(1), as we only use a single boolean flag for synchronization.
**Pros:** Simple to implement and understand.; Very low latency in switching turns once the flag is flipped, as there is no overhead from blocking and waking up threads (context switching).
**Cons:** Extremely high CPU consumption due to the waiting thread constantly looping.; Not scalable; performance degrades significantly as the number of threads or contention increases.; Can lead to thread starvation on systems where other threads need CPU time.
### Explanation
We introduce a `volatile boolean fooTurn` initialized to `true`. The `volatile` keyword is crucial here; it ensures that any modification to this flag by one thread is immediately visible to the other thread, preventing issues caused by cached variable values.

The `foo()` method enters a loop that runs `n` times. Inside the loop, it spins in a `while` loop, waiting for `fooTurn` to be `true`. Once the condition is met, it prints "foo", sets `fooTurn` to `false` to signal the `bar` thread, and proceeds to the next iteration.

The `bar()` method does the opposite. It spins while `fooTurn` is `true`. When `fooTurn` becomes `false`, it prints "bar", sets `fooTurn` back to `true` for the `foo` thread, and continues.

This method is highly inefficient because the waiting thread consumes 100% of its allocated CPU time just checking the flag, doing no productive work.

```java
class FooBar {
    private int n;
    private volatile boolean fooTurn = true;

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (!fooTurn) {
                // Busy-wait (spin). Yielding is a hint to the scheduler.
                Thread.yield(); 
            }
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            fooTurn = false;
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            while (fooTurn) {
                // Busy-wait (spin)
                Thread.yield();
            }
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            fooTurn = true;
        }
    }
}
```
### Algorithm
- Initialize a `volatile boolean fooTurn = true`.
- In the `foo()` method's loop:
  - Continuously check if `fooTurn` is `false`. If it is, keep looping (spin). This is known as busy-waiting.
  - When `fooTurn` is `true`, exit the spin loop.
  - Print "foo".
  - Set `fooTurn = false` to allow the `bar` thread to proceed.
- In the `bar()` method's loop:
  - Continuously check if `fooTurn` is `true`. If it is, keep looping (spin).
  - When `fooTurn` is `false`, exit the spin loop.
  - Print "bar".
  - Set `fooTurn = true` to allow the `foo` thread to proceed on the next iteration.

## Using synchronized, wait(), and notifyAll()
This is a classic and efficient approach using Java's built-in monitor locks. Instead of busy-waiting, threads use `wait()` to block themselves, releasing the CPU until they are notified by another thread using `notifyAll()`. This avoids wasting CPU cycles.
**Time:** O(n). Each print operation involves some overhead for locking, waiting, and notifying, but the threads do not consume CPU while waiting. The total execution time is proportional to `n`. · **Space:** O(1). We only use a boolean flag and a lock object.
**Pros:** CPU-efficient as waiting threads are blocked by the operating system and do not consume CPU cycles.; A standard and widely understood concurrency pattern in Java.
**Cons:** Can be slightly more complex to write correctly (e.g., must use a `while` loop for `wait()` to guard against spurious wakeups, must `synchronize` on the same object).; `notifyAll()` can be less efficient than targeted notification if many threads are waiting, as it wakes all of them up, leading to contention (though not an issue here with only two threads).
### Explanation
We use a boolean flag, `fooTurn`, to track whose turn it is, and a shared `Object` instance as a lock. The flag does not need to be `volatile` because all access to it is protected by a `synchronized` block, which guarantees memory visibility between threads.

Both `foo()` and `bar()` methods synchronize on the common lock object. The `foo()` method acquires the lock and checks if it's not its turn (`!fooTurn`). If so, it calls `lock.wait()`. This action atomically releases the lock and puts the thread into a waiting state, consuming no CPU. The `bar()` method, after printing "bar", will set `fooTurn = true` and call `lock.notifyAll()`. This wakes up any threads waiting on the lock (the `foo` thread in this case).

The awakened `foo` thread re-acquires the lock and must re-check the condition in a `while` loop (this is a mandatory pattern to guard against spurious wakeups). Now that the condition is false, it proceeds to print "foo", sets `fooTurn = false`, and calls `notifyAll()` to wake up the `bar` thread. This cycle repeats `n` times.

```java
class FooBar {
    private int n;
    private boolean fooTurn = true;
    private final Object lock = new Object();

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (lock) {
                while (!fooTurn) {
                    lock.wait();
                }
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                fooTurn = false;
                lock.notifyAll();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            synchronized (lock) {
                while (fooTurn) {
                    lock.wait();
                }
                // printBar.run() outputs "bar". Do not change or remove this line.
                printBar.run();
                fooTurn = true;
                lock.notifyAll();
            }
        }
    }
}
```
### Algorithm
- Initialize a boolean flag `fooTurn = true` and a shared lock object.
- In the `foo()` method's loop:
  - Acquire the lock using a `synchronized` block.
  - Use a `while` loop to check if it's not foo's turn (`!fooTurn`). If so, call `lock.wait()` to block the thread and release the lock.
  - Once awakened and the condition is met, print "foo".
  - Set `fooTurn = false`.
  - Call `lock.notifyAll()` to wake up the waiting `bar` thread.
- The `bar()` method follows a symmetric logic, waiting for `fooTurn` to be `false` and notifying the `foo` thread after printing.

## Using Semaphores
This approach uses two semaphores to create a "ping-pong" mechanism between the two threads. One semaphore (`fooSem`) controls the execution of `foo()`, and the other (`barSem`) controls the execution of `bar()`. This is a very clean and efficient way to enforce a strict sequence of operations between threads.
**Time:** O(n). Similar to the `wait/notify` approach, the threads are efficiently blocked by the OS while waiting for a permit. The overhead of semaphore operations is very low. · **Space:** O(1). We only use two `Semaphore` objects, which have a constant size.
**Pros:** Very clean and expressive solution for this type of turn-based problem.; The logic directly models the hand-off between threads without needing an explicit state flag.; Highly efficient, relying on OS-level thread blocking and scheduling.
**Cons:** The concept of semaphores might be less familiar to some developers compared to intrinsic locks (`synchronized`).
### Explanation
A semaphore is a synchronization primitive that maintains a set of permits. We initialize two semaphores from `java.util.concurrent.Semaphore`:
1.  `fooSem` is initialized with 1 permit: `new Semaphore(1)`.
2.  `barSem` is initialized with 0 permits: `new Semaphore(0)`.

The `fooSem(1)` initialization allows the `foo()` method to acquire a permit and run first. The `barSem(0)` initialization forces the `bar()` method to wait initially.

In the `foo()` method's loop, it first calls `fooSem.acquire()`. This succeeds immediately on the first iteration. After printing "foo", it calls `barSem.release()`, which increments the permit count of `barSem` to 1, effectively signaling the `bar` thread.

In the `bar()` method's loop, it first calls `barSem.acquire()`. This will block until `foo()` has released a permit. Once it acquires the permit, it prints "bar" and then calls `fooSem.release()`, giving a permit back to the `foo` thread for the next iteration. This creates a perfect, efficient hand-off between the two threads.

```java
import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    private Semaphore fooSem = new Semaphore(1);
    private Semaphore barSem = new Semaphore(0);

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSem.acquire();
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            barSem.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSem.acquire();
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            fooSem.release();
        }
    }
}
```
### Algorithm
- Initialize a semaphore `fooSem` with 1 permit.
- Initialize a semaphore `barSem` with 0 permits.
- In the `foo()` method's loop:
  - Acquire a permit from `fooSem` by calling `fooSem.acquire()`. This will block if no permits are available.
  - Print "foo".
  - Release a permit to `barSem` by calling `barSem.release()`, allowing the `bar` thread to proceed.
- In the `bar()` method's loop:
  - Acquire a permit from `barSem` by calling `barSem.acquire()`. This will block until the `foo` thread releases a permit.
  - Print "bar".
  - Release a permit to `fooSem` by calling `fooSem.release()`, allowing the `foo` thread to proceed on the next iteration.

# Solutions
### Java

```java
class FooBar { private int n ; private Semaphore f = new Semaphore ( 1 ); private Semaphore b = new Semaphore ( 0 ); public FooBar ( int n ) { this . n = n ; } public void foo ( Runnable printFoo ) throws InterruptedException { for ( int i = 0 ; i < n ; i ++) { f . acquire ( 1 ); // printFoo.run() outputs "foo". Do not change or remove this line. printFoo . run (); b . release ( 1 ); } } public void bar ( Runnable printBar ) throws InterruptedException { for ( int i = 0 ; i < n ; i ++) { b . acquire ( 1 ); // printBar.run() outputs "bar". Do not change or remove this line. printBar . run (); f . release ( 1 ); } } }
```

### CPP

```cpp
#include <semaphore.h> class FooBar { private: int n ; sem_t f , b ; public: FooBar ( int n ) { this -> n = n ; sem_init ( & f , 0 , 1 ); sem_init ( & b , 0 , 0 ); } void foo ( function < void () > printFoo ) { for ( int i = 0 ; i < n ; i ++ ) { sem_wait ( & f ); // printFoo() outputs "foo". Do not change or remove this line. printFoo (); sem_post ( & b ); } } void bar ( function < void () > printBar ) { for ( int i = 0 ; i < n ; i ++ ) { sem_wait ( & b ); // printBar() outputs "bar". Do not change or remove this line. printBar (); sem_post ( & f ); } } };
```

### Python

```python
from threading import Semaphore class FooBar : def __init__ ( self , n ): self . n = n self . f = Semaphore ( 1 ) self . b = Semaphore ( 0 ) def foo ( self , printFoo : "Callable[[], None]" ) -> None : for _ in range ( self . n ): self . f . acquire () # printFoo() outputs "foo". Do not change or remove this line. printFoo () self . b . release () def bar ( self , printBar : "Callable[[], None]" ) -> None : for _ in range ( self . n ): self . b . acquire () # printBar() outputs "bar". Do not change or remove this line. printBar () self . f . release () ############# class FooBar : def __init__ ( self , n ): self . n = n self . fooLock = threading . Lock () self . barLock = threading . Lock () self . barLock . acquire () def foo ( self , printFoo : 'Callable[[], None]' ) -> None : for i in range ( self . n ): self . fooLock . acquire () printFoo () self . barLock . release () def bar ( self , printBar : 'Callable[[], None]' ) -> None : for i in range ( self . n ): self . barLock . acquire () printBar () self . fooLock . release ()
```