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 <= 1000#1115 Print FooBar Alternately is a classic concurrency problem where two threads must coordinate to print "foo" and "bar" alternately for n iterations. The key challenge is ensuring that one thread waits until the other finishes its turn, maintaining strict ordering.
A common strategy is to use synchronization primitives such as semaphores, mutex locks with condition variables, or atomic flags. For example, two semaphores can control execution: one allowing the foo thread to start while the other blocks the bar thread until foo finishes. After printing, each thread signals the other, enforcing the alternating pattern.
This approach ensures predictable ordering without busy waiting. Since each thread performs a constant amount of work per iteration, the total time complexity is O(n). Only a few synchronization primitives are required, giving a space complexity of O(1). The main focus is designing correct thread coordination rather than complex data structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Semaphore / Lock-based Thread Coordination | O(n) | O(1) |
| Condition Variables with Mutex | O(n) | O(1) |
Coding Interview Prep
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, concurrency problems like Print FooBar Alternately are occasionally asked in interviews at companies such as Google, Amazon, and Meta. They test a candidate's understanding of thread coordination, synchronization primitives, and race condition prevention.
The optimal approach uses synchronization primitives such as semaphores, locks, or condition variables to coordinate two threads. These mechanisms ensure that one thread prints "foo" and then signals the other thread to print "bar", maintaining strict alternation for n iterations.
You should understand basic multithreading concepts such as thread synchronization, mutual exclusion, and signaling. Familiarity with semaphores, locks, and condition variables in languages like Java, C++, or Python will help you implement the solution correctly.
Instead of traditional data structures, this problem relies on concurrency tools like semaphores, mutexes, and condition variables. Semaphores are particularly popular because they make it easy to control which thread is allowed to run at a given time.