Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1115.html
1115. Print FooBar Alternately
Level
Medium
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 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.
Solution
This problem can be solved using semaphores. In the class, create two semaphores semaphoreFoo
and semaphoreBar
for methods foo()
and bar()
respectively. Initially, semaphoreFoo
has 1 permit, while semaphoreBar
has 0 permits.
For each method foo()
and bar()
, in the loop, there are three steps. The first step is to acquire a permit from the current semaphore. The second step is to call the run()
method for the Runnable
object. The third step is to release a permit back to the next semaphore.
Alternatively, use volatile
. Good reading http://tutorials.jenkov.com/java-concurrency/volatile.html
The Java volatile keyword is used to mark a Java variable as “being stored in main memory”. More precisely that means, that every read of a volatile variable will be read from the computer’s main memory, and not from the CPU cache, and that every write to a volatile variable will be written to main memory, and not just to the CPU cache.
-
public class Print_FooBar_Alternately { class FooBar_Semaphore { private int n; Semaphore s = new Semaphore(0); // `permits` the initial number of permits available. Semaphore s2 = new Semaphore(1); public FooBar_Semaphore(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { // printFoo.run() outputs "foo". Do not change or remove this line. s2.acquire(); printFoo.run(); s.release(); } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { // printBar.run() outputs "bar". Do not change or remove this line. s.acquire(); printBar.run(); s2.release(); } } } // volatile variable version class FooBar { private int n; public FooBar(int n) { this.n = n; } private volatile int state = 1; public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { while (state != 1) { Thread.yield(); } // printFoo.run() outputs "foo". Do not change or remove this line. printFoo.run(); state = 2; } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { while (state != 2) { Thread.yield(); } // printBar.run() outputs "bar". Do not change or remove this line. printBar.run(); state = 1; } } } } ############ class FooBar { private int n; private final Semaphore fooSem = new Semaphore(1); private final Semaphore barSem = new Semaphore(0); public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { fooSem.acquire(); printFoo.run(); barSem.release(); } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { barSem.acquire(); printBar.run(); fooSem.release(); } } }
-
class FooBar: def __init__(self, n): self.n = n self.fooLock = threading.Lock() self.barLock = threading.Lock() self.barLock.acquire() def foo(self, printFoo: 'Callable[[], None]') -> None: for i in range(self.n): self.fooLock.acquire() printFoo() self.barLock.release() def bar(self, printBar: 'Callable[[], None]') -> None: for i in range(self.n): self.barLock.acquire() printBar() self.fooLock.release()
-
class FooBar { private: int n; mutex fooMu, barMu; public: FooBar(int n) { this->n = n; barMu.lock(); } void foo(function<void()> printFoo) { for (int i = 0; i < n; i++) { fooMu.lock(); printFoo(); barMu.unlock(); } } void bar(function<void()> printBar) { for (int i = 0; i < n; i++) { barMu.lock(); printBar(); fooMu.unlock(); } } };