1115. Print FooBar Alternately
Description
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 callfoo()
, while - thread
B
will callbar()
.
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
Solutions
Solution 1: Multithreading + Semaphore
We use two semaphores $f$ and $b$ to control the execution order of the two threads, where $f$ is initially set to $1$ and $b$ is set to $0$, indicating that thread $A$ executes first.
When thread $A$ executes, it first performs the $acquire$ operation on $f$, which changes the value of $f$ to $0$. Thread $A$ then gains the right to use $f$ and can execute the $foo$ function. After that, it performs the $release$ operation on $b$, changing the value of $b$ to $1$. This allows thread $B$ to gain the right to use $b$ and execute the $bar$ function.
When thread $B$ executes, it first performs the $acquire$ operation on $b$, which changes the value of $b$ to $0$. Thread $B$ then gains the right to use $b$ and can execute the $bar$ function. After that, it performs the $release$ operation on $f$, changing the value of $f$ to $1$. This allows thread $A$ to gain the right to use $f$ and execute the $foo$ function.
Therefore, we only need to loop $n$ times, each time executing the $foo$ and $bar$ functions, first performing the $acquire$ operation, and then the $release$ operation.
The time complexity is $O(n)$, and the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|