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

All Problems

All Solutions