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:
A will call foo(), whileB 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 <= 1000Problem 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.
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.
Time Complexity: O(n) because it iterates over n iterations.
Space Complexity: O(1) as it uses a fixed amount of extra space.
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.
C
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
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).
| Approach | Complexity |
|---|---|
| Using Mutex Lock or Monitor | Time Complexity: O(n) because it iterates over n iterations. |
| Using Semaphores | Time Complexity: O(n), Space Complexity: O(1). |
| Multithreading + Semaphore | — |
| 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 |
Leetcode1115. Print FooBar Alternately in C++ | Multi-Threading Part 5 • Sahil Batra • 3,287 views views
Watch 9 more video solutions →Practice Print FooBar Alternately with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor