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.

• Java
• C++
• Python

• 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();
      }
  }
  ############
  
  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();
          }
      }
  }
  
  

• 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 Semaphore
  
  class Foo:
      def __init__(self):
          self.semaphore1 = Semaphore(1)
          self.semaphore2 = Semaphore(0)
          self.semaphore3 = Semaphore(0)
  
      def first(self, printFirst: 'Callable[[], None]') -> None:
          self.semaphore1.acquire()
          # printFirst() outputs "first". Do not change or remove this line.
          printFirst()
          self.semaphore2.release()
  
      def second(self, printSecond: 'Callable[[], None]') -> None:
          self.semaphore2.acquire()
          # printSecond() outputs "second". Do not change or remove this line.
          printSecond()
          self.semaphore3.release()
  
      def third(self, printThird: 'Callable[[], None]') -> None:
          self.semaphore3.acquire()
          # printThird() outputs "third". Do not change or remove this line.
          printThird()
          self.semaphore1.release()
  
  #############
  
  '''
  A Barrier is a synchronization primitive that allows multiple threads 
  to wait until all threads have reached a certain point of execution before continuing.
  '''
  from threading import Barrier
  
  class Foo:
      def __init__(self):
          self.first_barrier = Barrier(2)
          self.second_barrier = Barrier(2)
  
      '''
      first() self.first_barrier.wait(),  waits at self.first_barrier, 
      blocking until another thread also reaches that point. 
      Once both threads have reached the barrier, 
      they are released, and execution continues.
      '''
      def first(self, printFirst):
          printFirst()
          self.first_barrier.wait()
  
      '''
      The second method is similar. 
      It takes a function printSecond as a parameter. 
      
      It first waits at self.first_barrier, ensuring that the first method has completed. 
      Then, it calls printSecond to print the "second" output. 
      
      Finally, it waits at self.second_barrier, 
      blocking until the third method reaches the same point.
      '''
      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()
  
  

All Problems

All Solutions