Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1114.html
1114. Print in Order
Level
Easy
Description
Suppose we have a class:
public class Foo {
public void first() { print("first"); }
public void second() { print("second"); }
public void third() { print("third"); }
}
The same instance of Foo
will be passed to three different threads. Thread A will call first()
, thread B will call second()
, and thread C will call third()
. Design a mechanism and modify the program to ensure that second()
is executed after first()
, and third()
is executed after second()
.
Example 1:
Input: [1,2,3]
Output: “firstsecondthird”
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). “firstsecondthird” is the correct output.
Example 2:
Input: [1,3,2]
Output: “firstsecondthird”
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). “firstsecondthird” is the correct output.
Note:
We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.
Solution
There are several solutions to this problem. This solution uses semaphores. Create three semaphores semaphore1
, semaphore2
and semaphore3
, which are for method first()
, second()
and third()
, respectively. The three semaphores are defined in the class. Initially, semaphore1
has 1 permit, while semaphore2
and semaphore3
have 0 permits.
For each method first()
, second()
and third()
, 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.
-
class Foo { private Semaphore semaphore1 = new Semaphore(1); private Semaphore semaphore2 = new Semaphore(0); private Semaphore semaphore3 = new Semaphore(0); public Foo() { } public void first(Runnable printFirst) throws InterruptedException { semaphore1.acquire(); // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); semaphore2.release(); } public void second(Runnable printSecond) throws InterruptedException { semaphore2.acquire(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); semaphore3.release(); } public void third(Runnable printThird) throws InterruptedException { semaphore3.acquire(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); semaphore1.release(); } } ############ class Foo { private final Semaphore s2 = new Semaphore(0); private final Semaphore s3 = new Semaphore(0); public Foo() { } public void first(Runnable printFirst) throws InterruptedException { printFirst.run(); s2.release(); } public void second(Runnable printSecond) throws InterruptedException { s2.acquire(); printSecond.run(); s3.release(); } public void third(Runnable printThird) throws InterruptedException { s3.acquire(); printThird.run(); } }
-
class Foo { private: mutex m2, m3; public: Foo() { m2.lock(); m3.lock(); } void first(function<void()> printFirst) { printFirst(); m2.unlock(); } void second(function<void()> printSecond) { m2.lock(); printSecond(); m3.unlock(); } void third(function<void()> printThird) { m3.lock(); printThird(); } };
-
from threading import Barrier class Foo: def __init__(self): self.first_barrier = Barrier(2) self.second_barrier = Barrier(2) def first(self, printFirst): printFirst() self.first_barrier.wait() def second(self, printSecond): self.first_barrier.wait() printSecond() self.second_barrier.wait() def third(self, printThird): self.second_barrier.wait() printThird() ############ from threading import Event class Foo: def __init__(self): self.done = (Event(),Event()) def first(self, printFirst): printFirst() self.done[0].set() def second(self, printSecond): self.done[0].wait() printSecond() self.done[1].set() def third(self, printThird): self.done[1].wait() printThird() ############ from threading import Semaphore class Foo: def __init__(self): self.gates = (Semaphore(0),Semaphore(0)) def first(self, printFirst): printFirst() self.gates[0].release() def second(self, printSecond): with self.gates[0]: printSecond() self.gates[1].release() def third(self, printThird): with self.gates[1]: printThird() ############ from threading import Condition class Foo: def __init__(self): self.exec_condition = Condition() self.order = 0 self.first_finish = lambda: self.order == 1 self.second_finish = lambda: self.order == 2 def first(self, printFirst): with self.exec_condition: printFirst() self.order = 1 self.exec_condition.notify(2) def second(self, printSecond): with self.exec_condition: self.exec_condition.wait_for(self.first_finish) printSecond() self.order = 2 self.exec_condition.notify() def third(self, printThird): with self.exec_condition: self.exec_condition.wait_for(self.second_finish) printThird() ############ class Foo: def __init__(self): self.l2 = threading.Lock() self.l3 = threading.Lock() self.l2.acquire() self.l3.acquire() def first(self, printFirst: 'Callable[[], None]') -> None: printFirst() self.l2.release() def second(self, printSecond: 'Callable[[], None]') -> None: self.l2.acquire() printSecond() self.l3.release() def third(self, printThird: 'Callable[[], None]') -> None: self.l3.acquire() printThird()
Or, use CountDownLatch
.
-
import java.util.concurrent.CountDownLatch; public class Print_in_Order { class Foo { private final CountDownLatch countDownLatch1; private final CountDownLatch countDownLatch2; public Foo() { countDownLatch1 = new CountDownLatch(1); // count the number of times must be invoked countDownLatch2 = new CountDownLatch(1); } public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); countDownLatch1.countDown(); } public void second(Runnable printSecond) throws InterruptedException { countDownLatch1.await(); // Causes the current thread to wait until the latch has counted down to zero // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); countDownLatch2.countDown(); } public void third(Runnable printThird) throws InterruptedException { countDownLatch2.await(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } }