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

The requirement:

• Two threads:
  • Thread A calls foo()
  • Thread B calls bar()
• Output must be:

The key problem is: how do we make one thread wait until it is its turn?

Solution 1: Use Semaphore (Recommended)

Use two semaphores:

• foo_sem: controls when foo() can run
• bar_sem: controls when bar() can run

Initial state:

Flow:

Python Implementation

Execution example

Initial:

First iteration

Foo thread:

State:

Bar thread:

State:

Repeat.

Output:

Solution 2: Use Condition

You can also solve it using Condition.

Maintain a shared variable:

Foo waits until:

Bar waits until:

Python Implementation

Semaphore vs Condition here

Both work, but they model the problem differently.

Semaphore solution

You are saying:

"Foo has a permit to print. After printing, give the permit to Bar."

The semaphore itself stores the state.

Very natural for alternating execution.

Condition solution

You are saying:

"Threads should wait until the shared state foo_turn changes."

The state is external:

The condition only wakes threads.