Print FooBar Alternately

Med

#1053Time: 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.

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class FooBar {2    private int n;3    private volatile boolean fooTurn = true;4 5    public FooBar(int n) {6        this.n = n;7    }8 9    public void foo(Runnable printFoo) throws InterruptedException {10        for (int i = 0; i < n; i++) {11            while (!fooTurn) {12                // Busy-wait (spin). Yielding is a hint to the scheduler.13                Thread.yield(); 14            }15            // printFoo.run() outputs "foo". Do not change or remove this line.16            printFoo.run();17            fooTurn = false;18        }19    }20 21    public void bar(Runnable printBar) throws InterruptedException {22        for (int i = 0; i < n; i++) {23            while (fooTurn) {24                // Busy-wait (spin)25                Thread.yield();26            }27            // printBar.run() outputs "bar". Do not change or remove this line.28            printBar.run();29            fooTurn = true;30        }31    }32}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class FooBar {2    private int n;3    private boolean fooTurn = true;4    private final Object lock = new Object();5 6    public FooBar(int n) {7        this.n = n;8    }9 10    public void foo(Runnable printFoo) throws InterruptedException {11        for (int i = 0; i < n; i++) {12            synchronized (lock) {13                while (!fooTurn) {14                    lock.wait();15                }16                // printFoo.run() outputs "foo". Do not change or remove this line.17                printFoo.run();18                fooTurn = false;19                lock.notifyAll();20            }21        }22    }23 24    public void bar(Runnable printBar) throws InterruptedException {25        for (int i = 0; i < n; i++) {26            synchronized (lock) {27                while (fooTurn) {28                    lock.wait();29                }30                // printBar.run() outputs "bar". Do not change or remove this line.31                printBar.run();32                fooTurn = true;33                lock.notifyAll();34            }35        }36    }37}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

A semaphore is a synchronization primitive that maintains a set of permits. We initialize two semaphores from java.util.concurrent.Semaphore:

fooSem is initialized with 1 permit: new Semaphore(1).
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.

1import java.util.concurrent.Semaphore;2 3class FooBar {4    private int n;5    private Semaphore fooSem = new Semaphore(1);6    private Semaphore barSem = new Semaphore(0);7 8    public FooBar(int n) {9        this.n = n;10    }11 12    public void foo(Runnable printFoo) throws InterruptedException {13        for (int i = 0; i < n; i++) {14            fooSem.acquire();15            // printFoo.run() outputs "foo". Do not change or remove this line.16            printFoo.run();17            barSem.release();18        }19    }20 21    public void bar(Runnable printBar) throws InterruptedException {22        for (int i = 0; i < n; i++) {23            barSem.acquire();24            // printBar.run() outputs "bar". Do not change or remove this line.25            printBar.run();26            fooSem.release();27        }28    }29}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class 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 ); } } }

1#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 ); } } };

1from 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 ()

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class 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 ); } } }

1#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 ); } } };

1from 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 ()

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.