1115. Print FooBar Alternately

Leetcode

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.

分析

这道题目要求交替打印字符串。其实是个生产者消费者问题。解决的方法有多种。最直观的是使用wait/notify, await/signal同步。当然也可以用信号量来实现。

synchronized

class FooBar {
    private int n;
    private boolean first = true;

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        synchronized (this) {
            for (int i = 0; i < n; i++) {
                while (!first) wait();
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                first = false;
                notifyAll();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        synchronized (this) {
            for (int i = 0; i < n; i++) {
                // printBar.run() outputs "bar". Do not change or remove this line.
                if (first) wait();
                printBar.run();
                first = true;
                notifyAll();
            }
        }
    }
}

Condition

class FooBar {
    private int n;
    private ReentrantLock lock = new ReentrantLock();
    private Condition fooOk = lock.newCondition();
    private Condition barOk = lock.newCondition();
    private boolean first = true;

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        lock.lock();
        for (int i = 0; i < n; i++) {
            while (!first) fooOk.await();
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            first = false;
            barOk.signalAll();
        }
        lock.unlock();

    }

    public void bar(Runnable printBar) throws InterruptedException {
        lock.lock();
        for (int i = 0; i < n; i++) {
            // printBar.run() outputs "bar". Do not change or remove this line.
            if (first) barOk.await();
            printBar.run();
            first = true;
            fooOk.signalAll();
        }
        lock.unlock();
    }
}

Semaphore

class FooBar {
    private int n;
    private Semaphore fooOk = new Semaphore(0);
    private Semaphore barOk = new Semaphore(1);

    public FooBar(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.
               barOk.acquire();
            printFoo.run();
            fooOk.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.
               fooOk.acquire();
            printBar.run();
            barOk.release();
        }
    }
}