Print FooBar Alternately solution and explanation
9 more videos on this problem
Leetcode1115. Print FooBar Alternately in C++ | Multi-Threading Part 5Sahil Batra · 7:21 · 4K views
Leetcode 1115 Print FooBar Alternately (Java Concurrency)TheAnalyticGuy · 5:14 · 1K views
LeetCode Concurrency | Print FooBar AlternatelyCppNuts · 7:14 · 1K views
1115. Print FooBar Alternately(Leetcode Concurrency Section)EverydayLeetcode · 5:43 · 879 views
1115. Print FooBar Alternately | LEETCODE MEDIUM | MULTITHREADING C++code Explainer · 10:01 · 445 views
Print FooBar Alternately LeetCode 1115 | Medium | Concurrencyleetloaf · 9:23 · 137 views
Print FooBar Alternately | LeetCode 1115 | Java & Go Concurrency Interview QuestionCoding Thor · 7:06 · 126 views
Code Review: LeetCode 1115: Print FooBar AlternatelyRoel Van de Paar · 2:43 · 56 views
Print FooBar Alternately, Medium, LeetCode 1115H William Polenz · 3:36:52 · 34 views
Leetcode 1115 Print FooBar AlternatelyAlgorithmicIQ · 13:23 · 31 views
The 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
Awill callfoo(), while - thread
Bwill callbar().
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.
from threading import Lock, Condition
class FooBar:
def __init__(self, n):
self.n = n
self.lock = Lock()
self.foo_turn = True
self.foo_cond = Condition(self.lock)
self.bar_cond = Condition(self.lock)
def foo(self):
for _ in range(self.n):
with self.lock:
while not self.foo_turn:
self.foo_cond.wait()
print("foo", end='')
self.foo_turn = False
self.bar_cond.notify()
def bar(self):
for _ in range(self.n):
with self.lock:
while self.foo_turn:
self.bar_cond.wait()
print("bar", end='')
self.foo_turn = True
self.foo_cond.notify()import java.util.concurrent.locks.*;
class FooBar {
private int n;
private Lock lock;
private Condition fooCond, barCond;
private boolean fooTurn;
public FooBar(int n) {
this.n = n;
lock = new ReentrantLock();
fooCond = lock.newCondition();
barCond = lock.newCondition();
fooTurn = true;
}
public void foo() throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (!fooTurn) {
fooCond.await();
}
System.out.print("foo");
fooTurn = false;
barCond.signal();
} finally {
lock.unlock();
}
}
}
public void bar() throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while (fooTurn) {
barCond.await();
}
System.out.print("bar");
fooTurn = true;
fooCond.signal();
} finally {
lock.unlock();
}
}
}
}This Python solution utilizes a Lock and two Condition variables.
Each method acquires the lock, checks the condition variable to see if it can print,
does the printing, and then signals the other method.
Time Complexity: O(n), Space Complexity: O(1).
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.
class Semaphore {
constructor(count = 1) {
this.count = count;
this.queue = [];
}
acquire() {
return new Promise(resolve => {
if (this.count > 0) {
this.count -= 1;
resolve();
} else {
this.queue.push(resolve);
}
});
}
release() {
if (this.queue.length > 0) {
const resolve = this.queue.shift();
resolve();
} else {
this.count += 1;
}
}
}
class FooBar {
constructor(n) {
this.n = n;
this.fooSemaphore = new Semaphore(1);
this.barSemaphore = new Semaphore(0);
}
async foo(printFoo) {
for (let i = 0; i < this.n; i++) {
await this.fooSemaphore.acquire();
printFoo();
this.barSemaphore.release();
}
}
async bar(printBar) {
for (let i = 0; i < this.n; i++) {
await this.barSemaphore.acquire();
printBar();
this.fooSemaphore.release();
}
}
}
function printFoo() {
process.stdout.write('foo');
}
function printBar() {
process.stdout.write('bar');
}
let fooBar = new FooBar(2);
Promise.all([fooBar.foo(printFoo), fooBar.bar(printBar)]);#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
sem_t foo_sem, bar_sem;
void *foo(void *arg) {
int n = *(int *)arg;
for (int i = 0; i < n; ++i) {
sem_wait(&foo_sem);
printf("foo");
sem_post(&bar_sem);
}
return NULL;
}
void *bar(void *arg) {
int n = *(int *)arg;
for (int i = 0; i < n; ++i) {
sem_wait(&bar_sem);
printf("bar");
sem_post(&foo_sem);
}
return NULL;
}
int main() {
int n = 2; // Example input
pthread_t thread1, thread2;
sem_init(&foo_sem, 0, 1);
sem_init(&bar_sem, 0, 0);
pthread_create(&thread1, NULL, foo, &n);
pthread_create(&thread2, NULL, bar, &n);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
sem_destroy(&foo_sem);
sem_destroy(&bar_sem);
return 0;
}In this JavaScript solution, a custom Semaphore class is used, starting with 1 for foo and 0 for bar. Promises are employed to await semaphore acquisition before printing, ensuring proper alternation.
Time Complexity: O(n), Space Complexity: O(1).
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).
#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);
}
}
};Complexity comparison
| Approach | Complexity |
|---|---|
| Using Mutex Lock or Monitor | Time Complexity: O(n), Space Complexity: O(1). |
| Using Semaphores | Time Complexity: O(n), Space Complexity: O(1). |
| Multithreading + Semaphore | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mutex Lock / Monitor | O(n) | O(1) | When using built-in monitor primitives like synchronized, wait, and notify for thread coordination |
| Semaphores | O(n) | O(1) | When explicit signaling between threads is needed with cleaner alternating control |
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.
