{x}
blog image

Print FooBar Alternately

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

Solution Explanation: Print FooBar Alternately

This problem requires printing "foo" and "bar" alternately n times using two threads. The solution employs semaphores for thread synchronization. Semaphores are signaling mechanisms that allow threads to coordinate their actions.

Approach: Using Semaphores

The core idea is to use two semaphores:

  • f: Controls access to the foo function. Initialized to 1 (allows foo to run initially).
  • b: Controls access to the bar function. Initialized to 0 (prevents bar from running initially).

The threads operate as follows:

  1. Thread A (foo):

    • Acquires the f semaphore (waits if f is 0). This ensures that foo runs only when allowed.
    • Prints "foo".
    • Releases the b semaphore. This signals that bar can now run.

  2. Thread B (bar):

    • Acquires the b semaphore (waits if b is 0). This ensures that bar runs only when allowed.
    • Prints "bar".
    • Releases the f semaphore. This signals that foo can now run again.

This alternating acquisition and release of semaphores guarantees the "foobar" sequence. The loop ensures that this sequence repeats n times.

Time and Space Complexity

  • Time Complexity: O(n). The loops run n times. The semaphore operations (acquire and release) are generally considered constant time operations.
  • Space Complexity: O(1). The space used is constant regardless of the input n. The semaphores are fixed-size.

Code Implementation (Python, Java, C++)

The code implementations below demonstrate this approach. Each language has its own semaphore mechanism:

Python

from threading import Semaphore
 
class FooBar:
    def __init__(self, n):
        self.n = n
        self.f = Semaphore(1)  # Semaphore for foo, initialized to 1
        self.b = Semaphore(0)  # Semaphore for bar, initialized to 0
 
    def foo(self, printFoo):
        for _ in range(self.n):
            self.f.acquire()  # Acquire the foo semaphore
            printFoo()        # Print "foo"
            self.b.release()  # Release the bar semaphore
 
    def bar(self, printBar):
        for _ in range(self.n):
            self.b.acquire()  # Acquire the bar semaphore
            printBar()        # Print "bar"
            self.f.release()  # Release the foo semaphore

Java

import java.util.concurrent.Semaphore;
 
class FooBar {
    private int n;
    private Semaphore f = new Semaphore(1); // Semaphore for foo, initialized to 1
    private Semaphore b = new Semaphore(0); // Semaphore for bar, initialized to 0
 
    public FooBar(int n) {
        this.n = n;
    }
 
    public void foo(Runnable printFoo) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            f.acquire();      // Acquire the foo semaphore
            printFoo.run();   // Print "foo"
            b.release();     // Release the bar semaphore
        }
    }
 
    public void bar(Runnable printBar) throws InterruptedException {
        for (int i = 0; i < n; i++) {
            b.acquire();      // Acquire the bar semaphore
            printBar.run();   // Print "bar"
            f.release();     // Release the foo semaphore
        }
    }
}

C++

#include <semaphore>
#include <functional>
 
class FooBar {
private:
    int n;
    std::binary_semaphore f{1}; // Semaphore for foo, initialized to 1
    std::binary_semaphore b{0}; // Semaphore for bar, initialized to 0
 
public:
    FooBar(int n) : n(n) {}
 
    void foo(std::function<void()> printFoo) {
        for (int i = 0; i < n; ++i) {
            f.acquire();      // Acquire the foo semaphore
            printFoo();       // Print "foo"
            b.release();     // Release the bar semaphore
        }
    }
 
    void bar(std::function<void()> printBar) {
        for (int i = 0; i < n; ++i) {
            b.acquire();      // Acquire the bar semaphore
            printBar();       // Print "bar"
            f.release();     // Release the foo semaphore
        }
    }
};

These code snippets show the essential logic for solving the problem using semaphores. Remember to handle potential exceptions (like InterruptedException in Java) in a production environment. The printFoo and printBar functions are placeholders for the actual printing logic provided by the LeetCode problem.