Skip to main content
Talentd

Print FooBar Alternately - Solution & Explanation

MediumConcurrency11 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Two threads share a class. One thread prints "foo" and the other prints "bar". Your job is to coordinate them so the output becomes foobarfoobar... exactly n times. The challenge is pure thread synchronization: both threads run concurrently but must alternate execution.

Approach 1: Using Mutex Lock or Monitor (O(n) time, O(1) space)

This approach uses a shared lock and a state variable to control which thread prints next. Both threads acquire the same mutex. The foo() thread waits while it is not its turn, prints "foo", flips the state, and notifies the other thread. The bar() thread performs the symmetric operation. Monitor primitives such as synchronized, wait(), and notify() in Java or Condition/Lock patterns in Python ensure that only one thread proceeds at a time. Each iteration performs constant work, so total runtime is O(n) and memory usage remains O(1). This technique is common when solving coordination problems in concurrency or multithreading interviews.

Approach 2: Using Semaphores (O(n) time, O(1) space)

Semaphores provide a cleaner signaling mechanism between threads. Initialize two semaphores: one allowing the foo thread to run first (value 1) and another blocking the bar thread (value 0). The foo() thread acquires its semaphore, prints "foo", then releases the bar semaphore. The bar() thread acquires its semaphore, prints "bar", then releases the foo semaphore. This creates a strict alternating schedule enforced by semaphore permits. Each acquire/release operation is constant time, so the full execution still runs in O(n) time with O(1) additional space. Semaphores are widely used for ordered execution problems in concurrency and semaphores based synchronization.

Recommended for interviews: Interviewers usually expect the semaphore solution or a monitor-based lock solution. Implementing a mutex + condition variable shows you understand thread coordination primitives. The semaphore approach is often shorter and demonstrates strong knowledge of synchronization tools used in real systems.

Approach 1: Using Mutex Lock or Monitor

This approach involves using a mutex lock or monitor to synchronize the two threads. The idea is to allow one thread to print "foo" and then signal the other thread to print "bar", ensuring they alternate correctly. This can be achieved by holding a common lock and using wait and notify mechanisms to alternate the printing.

This solution uses ReentrantLock, combined with Condition variables for synchronization. The foo() method acquires the lock, checks if it's fooTurn, prints "foo", and then signals the bar() method. The bar() method follows a similar pattern.

Code

JavaPython

Java

Python

Complexity

Time Complexity: O(n) because it iterates over n iterations.
Space Complexity: O(1) as it uses a fixed amount of extra space.

Try this approach in the editor →

Approach 2: Using Semaphores

This approach uses two semaphores to control the execution of threads alternately. The semaphore for foo() starts with 1, allowing it to run first, while the semaphore for bar() starts with 0, making it wait initially. Upon finishing execution, each thread signals the other to run.

This C solution uses POSIX semaphores, initializing foo_sem with value 1 and bar_sem with value 0. Within the foo function, it waits on foo_sem, prints "foo", and signals bar_sem to allow the bar function to run. The bar function follows the reverse process.

Code

CJavaScript

C

JavaScript

Complexity

Time Complexity: O(n), Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Multithreading + Semaphore

We use two semaphores f and b to control the execution order of the two threads, where f is initially set to 1 and b is set to 0, indicating that thread A executes first.

When thread A executes, it first performs the acquire operation on f, which changes the value of f to 0. Thread A then gains the right to use f and can execute the foo function. After that, it performs the release operation on b, changing the value of b to 1. This allows thread B to gain the right to use b and execute the bar function.

When thread B executes, it first performs the acquire operation on b, which changes the value of b to 0. Thread B then gains the right to use b and can execute the bar function. After that, it performs the release operation on f, changing the value of f to 1. This allows thread A to gain the right to use f and execute the foo function.

Therefore, we only need to loop n times, each time executing the foo and bar functions, first performing the acquire operation, and then the release operation.

The time complexity is O(n), and the space complexity is O(1).

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Mutex Lock or Monitor

Time Complexity: O(n) because it iterates over n iterations.
Space Complexity: O(1) as it uses a fixed amount of extra space.

Using Semaphores

Time Complexity: O(n), Space Complexity: O(1).

Multithreading + Semaphore—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Mutex Lock / MonitorO(n)O(1)When using built-in monitor primitives like synchronized, wait, and notify for thread coordination
SemaphoresO(n)O(1)When explicit signaling between threads is needed with cleaner alternating control

Video Solution

Leetcode1115. Print FooBar Alternately in C++ | Multi-Threading Part 5 • Sahil Batra • 4,012 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Print FooBar Alternately easy or hard?
Print FooBar Alternately is rated Medium because the logic is simple but requires correct thread synchronization. Developers familiar with concurrency primitives like locks or semaphores usually solve it quickly, while beginners may struggle with coordinating two running threads.
Print FooBar Alternately Python/Java solution
Python solutions typically use threading locks or condition variables to alternate execution between threads. Java implementations often rely on synchronized blocks with wait/notify or Semaphore from java.util.concurrent to coordinate foo and bar printing.
How to solve Print FooBar Alternately in O(n)?
Use synchronization primitives that control which thread runs next. With semaphores, initialize foo with one permit and bar with zero. The foo thread prints and releases bar; the bar thread prints and releases foo. Each iteration executes constant work, resulting in O(n) total time.
What is the best approach for Print FooBar Alternately?
The semaphore-based approach is the most straightforward. One semaphore allows the foo thread to run first while the other blocks the bar thread. After printing, each thread releases the other's semaphore, enforcing strict alternation. This solution runs in O(n) time with O(1) space and minimal shared state.
Is Print FooBar Alternately asked at Google/Amazon/Meta?
Concurrency coordination problems like Print FooBar Alternately appear in interviews at large tech companies including Google, Amazon, and Meta. They test understanding of thread synchronization, signaling, and race condition prevention rather than complex algorithms.
What data structure is used in Print FooBar Alternately?
The problem relies on synchronization primitives rather than traditional data structures. Common tools include mutex locks, condition variables, monitors, and semaphores to control execution order between threads.
What is the time complexity of Print FooBar Alternately?
Both common solutions—mutex/monitor synchronization and semaphores—run in O(n) time. Each thread performs one print and one synchronization operation per iteration. Space complexity stays O(1) because only a few synchronization primitives and counters are used.

Ready to solve this problem?

Practice Print FooBar Alternately with our built-in code editor and test cases.

Practice on FleetCode
Previous

Print in Order

Next

Print Zero Even Odd