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

All Problems

All Solutions