Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1116.html

1116. Print Zero Even Odd

Level

Medium

Description

Suppose you are given the following code:

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // constructor
  public void zero(printNumber) { ... }  // only output 0's
  public void even(printNumber) { ... }  // only output even numbers
  public void odd(printNumber) { ... }   // only output odd numbers
}

The same instance of ZeroEvenOdd will be passed to three different threads:

  1. Thread A will call zero() which should only output 0’s.
  2. Thread B will call even() which should only ouput even numbers.
  3. Thread C will call odd() which should only output odd numbers.

Each of the threads is given a printNumber method to output an integer. Modify the given program to output the series 010203040506... where the length of the series must be 2n.

Example 1:

Input: n = 2

Output: “0102”

Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). “0102” is the correct output.

Example 2:

Input: n = 5

Output: “0102030405”

Solution

This problem can be solved using semaphores. In the class, create three semaphores semaphoreZero, semaphoreOdd and semaphoreEven for methods zero(), odd() and even() respectively. Initially, semaphoreZero has 1 permit, while semaphoreOdd and semaphoreEven has 0 permits.

For each method zero(), odd() and even(), 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 printNumber.accept(x) method for the current number. The third step is to release a permit back to the next semaphore.

  • import java.util.concurrent.Semaphore;
import java.util.function.IntConsumer;

public class Print_Zero_Even_Odd {

    // co-ordinate 3 threads
    public class ZeroEvenOdd {
        private int n;
        private Semaphore even;
        private Semaphore odd;
        private Semaphore zero;

        public ZeroEvenOdd(int n) {
            this.n = n;
            even = new Semaphore(0);
            odd = new Semaphore(0);
            zero = new Semaphore(1);
        }

        // printNumber.accept(x) outputs "x", where x is an integer.
        public void zero(IntConsumer printNumber) throws InterruptedException {
            for (int i = 0; i < n; i++) {
                zero.acquire();
                printNumber.accept(0);
                if ((i & 1) == 0) {
                    odd.release();
                } else {
                    even.release();
                }
            }
        }

        public void even(IntConsumer printNumber) throws InterruptedException {
            for (int i = 2; i <= n; i += 2) {
                even.acquire();
                printNumber.accept(i);
                zero.release();
            }
        }

        public void odd(IntConsumer printNumber) throws InterruptedException {
            for (int i = 1; i <= n; i += 2) {
                odd.acquire();
                printNumber.accept(i);
                zero.release();
            }
        }
    }
}

############

class ZeroEvenOdd {

    private Semaphore zero_S;
    private Semaphore odd_S;
    private Semaphore even_S;
    private int n;

    public ZeroEvenOdd(int n) {
        this.n = n;
        this.zero_S = new Semaphore(1);
        this.odd_S = new Semaphore(0);
        this.even_S = new Semaphore(0);
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i++) {
            zero_S.acquire(1);
            printNumber.accept(0);
            if ((i & 1) == 0) {
                odd_S.release(1);
            } else {
                even_S.release(1);
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for (int i = 2; i <= n; i += 2) {
            even_S.acquire(1);
            printNumber.accept(i);
            zero_S.release(1);
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for (int i = 1; i <= n; i += 2) {
            odd_S.acquire(1);
            printNumber.accept(i);
            zero_S.release(1);
        }
    }
}

  • class ZeroEvenOdd {
private:
    int n;
    int flag;
    mutex m1, m2, m3;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        flag = 1; //奇偶判断
        m1.lock();
        m2.lock();
        m3.lock();
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        m3.unlock();
        for (int i = 0; i < n; i++) {
            m3.lock();
            printNumber(0);
            if (flag == 1)
                flag = 0, m2.unlock();
            else
                flag = 1, m1.unlock();
        }
    }

    void odd(function<void(int)> printNumber) { //输出奇数
        for (int i = 1; i <= n; i += 2) {
            m2.lock();
            printNumber(i);
            m3.unlock();
        }
    }

    void even(function<void(int)> printNumber) { //输出偶数
        for (int i = 2; i <= n; i += 2) {
            m1.lock();
            printNumber(i);
            m3.unlock();
        }
    }
};

  • from threading import Semaphore

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.z = Semaphore(1)
        self.e = Semaphore(0)
        self.o = Semaphore(0)
        
	# printNumber(x) outputs "x", where x is an integer.
    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(self.n):
            self.z.acquire()
            printNumber(0)
            if i % 2 == 0:
                self.o.release()
            else:
                self.e.release()
        
    def even(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(2, self.n + 1, 2):
            self.e.acquire()
            printNumber(i)
            self.z.release()
        
    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1, 2):
            self.o.acquire()
            printNumber(i)
            self.z.release()

All Problems

All Solutions