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

import java.util.concurrent.Semaphore;

class FooBar {
    private int n;
    private Semaphore fooSema = new Semaphore(1);
    private Semaphore barSema = new Semaphore(0);

    public FooBar(int n) {
        this.n = n;
    }

    public void foo() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            fooSema.acquire();
            System.out.print("foo");
            barSema.release();
        }
    }

    public void bar() throws InterruptedException {
        for (int i = 0; i < n; i++) {
            barSema.acquire();
            System.out.print("bar");
            fooSema.release();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        FooBar fooBar = new FooBar(5);

        Thread fooThread = new Thread(() -> {
            try {
                fooBar.foo();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        Thread barThread = new Thread(() -> {
            try {
                fooBar.bar();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        });

        fooThread.start();
        barThread.start();

        fooThread.join();
        barThread.join();
    }
}

Explanation:

1. Problem Description: The problem requires synchronizing two threads, one printing "foo" and the other printing "bar", such that the output is always "foobar" repeated n times.

2. Approach: We use Semaphores to control the order in which the threads execute. fooSema is initialized with a permit, allowing the foo thread to execute first. barSema is initialized with no permits, so the bar thread waits until foo releases a permit. After foo prints "foo", it releases a permit for bar, and after bar prints "bar", it releases a permit for foo, ensuring the "foobar" sequence.

3. Code Details:

   • FooBar class encapsulates the logic.
   • n stores the number of times "foobar" should be printed.
   • fooSema and barSema are Semaphores used for thread synchronization.
   • foo() method prints "foo" n times, acquiring fooSema before printing and releasing barSema after.
   • bar() method prints "bar" n times, acquiring barSema before printing and releasing fooSema after.

4. Example: For n = 5, the output will be "foobarfoobarfoobarfoobarfoobar".

Big(O) Analysis:

• Time Complexity: O(n)

  • The foo() and bar() methods each iterate n times, where n is the input. Each iteration involves printing a string and acquiring/releasing a semaphore, all of which are O(1) operations. Since both methods run in parallel, the overall time complexity is determined by the number of iterations, resulting in O(n).

• Space Complexity: O(1)

  • The space used by the program is constant regardless of the value of n. The variables n, fooSema, and barSema occupy a fixed amount of memory. No additional data structures are created that scale with the input size.

Edge Cases:

1. n = 1:

   • The output should be "foobar".

2. n = 0 (Invalid Input):

   • The loops in foo() and bar() would not execute, resulting in no output.
   • Error handling for invalid input (n < 1) would be required in a production environment.

3. Large n (e.g., n = 1000):

   • The program should still produce the correct output, but the execution time will increase linearly with n.
   • Memory usage remains constant regardless of n.