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.

• Java
• Python
• C++

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

All Problems

All Solutions