1115. 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

The requirement:

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

 

foobarfoobarfoobar...

 

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:

 

foo_sem = 1   # foo can run first
bar_sem = 0   # bar must wait

 

Flow:

 

foo thread:print fooallow barbar thread:wait for permissionprint barallow foo

 

---

Python Implementation

 

from threading import Semaphoreclass FooBar:def __init__(self, n: int):self.n = nself.foo_sem = Semaphore(1)self.bar_sem = Semaphore(0)def foo(self, printFoo) -> None:for _ in range(self.n):self.foo_sem.acquire()printFoo()self.bar_sem.release()def bar(self, printBar) -> None:for _ in range(self.n):self.bar_sem.acquire()printBar()self.foo_sem.release()

 

---

Execution example

Initial:

 

foo_sem = 1
bar_sem = 0

 

First iteration

Foo thread:

 

acquire foo_sem↓
print foo↓
release bar_sem

 

State:

 

foo_sem = 0
bar_sem = 1

 

Bar thread:

 

acquire bar_sem↓
print bar↓
release foo_sem

 

State:

 

foo_sem = 1
bar_sem = 0

 

Repeat.

Output:

 

foo
bar
foo
bar
foo
bar

 

---

Solution 2: Use Condition

You can also solve it using Condition.

Maintain a shared variable:

 

turn = "foo"

 

Foo waits until:

 

turn == "foo"

 

Bar waits until:

 

turn == "bar"

 

---

Python Implementation

 

from threading import Conditionclass FooBar:def __init__(self, n: int):self.n = nself.condition = Condition()self.foo_turn = Truedef foo(self, printFoo) -> None:for _ in range(self.n):with self.condition:while not self.foo_turn:self.condition.wait()printFoo()self.foo_turn = Falseself.condition.notify()def bar(self, printBar) -> None:for _ in range(self.n):with self.condition:while self.foo_turn:self.condition.wait()printBar()self.foo_turn = Trueself.condition.notify()

 

---

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.

 

foo_sem = 1
bar_sem = 0

 

Very natural for alternating execution.

---

Condition solution

You are saying:

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

The state is external:

 

foo_turn = True

 

The condition only wakes threads.