Leetcode 1116. Print Zero Even Odd

Problem Explanation:

In this problem, we are given a class called ZeroEvenOdd. We are supposed to modify this class so that when it's instance is passed into three threads, these three threads output a specific pattern based on the logic defined within the functions that they call.

The first thread calls zero() which outputs only '0's. The second thread calls even() which outputs only even numbers. The third thread calls odd() which outputs only odd numbers.

The goal is to ensure that these functions work together in a way that the numbers outputted by them form a sequence in the pattern '010203040506...' and so on, for a length of 2n.

We need to ensure the correct order and synchronization of outputs of these three threads.

If we are given n = 2, the desired output sequence is "0102".

Solution Explanation:

The tricky part in this problem is ensuring the correct order of printing and synchronization among multiple threads. For accomplishing this, we can use Semaphores. Semaphores are used to handle synchronization in multi-threading scenarios. They can allow or block thread execution based on whether the semaphore is available or not.

We will use three semaphores in this problem: zeroSemaphore, evenSemaphore, oddSemaphore. The zeroSemaphore will help us in printing '0' and ensuring that '0' is printed before an even or odd number is printed. The evenSemaphore and oddSemaphore will help in controlling the order of printing for even and odd numbers respectively.

1
2text
3If n = 3; 
4
5(1) zeroSemaphore gets the control and prints '0'. 
6(2) It then passes the control to oddSemaphore (because 1 % 2 = 1).
7(3) oddSemaphore prints '1' and passes control back to zeroSemaphore.
8(4) zeroSemaphore prints '0' and passes control to evenSemaphore (because 2 % 2 = 0).
9(5) evenSemaphore prints '2' and passes control back to zeroSemaphore.
10(6) Steps (1) to (5) are repeated untill no more numbers are left to print.

C++ Solution:

1
2cpp
3#include <semaphore.h>
4
5class ZeroEvenOdd {
6 private:
7  const int n;
8  sem_t zeroSemaphore;
9  sem_t evenSemaphore;
10  sem_t oddSemaphore;
11 public:
12  ZeroEvenOdd(int n) : n(n) {
13    sem_init(&zeroSemaphore, /*pshared=*/0, /*value=*/1);
14    sem_init(&evenSemaphore, /*pshared=*/0, /*value=*/0);
15    sem_init(&oddSemaphore, /*pshared=*/0, /*value=*/0);
16  }
17  ~ZeroEvenOdd() {
18    sem_destroy(&zeroSemaphore);
19    sem_destroy(&evenSemaphore);
20    sem_destroy(&oddSemaphore);
21  }
22  void zero(function<void(int)> printNumber) {
23    for (int i = 0; i < n; ++i) {
24      sem_wait(&zeroSemaphore);
25      printNumber(0);
26      sem_post(&(i % 2 == 0 ? oddSemaphore : evenSemaphore));
27    }
28  }
29  void even(function<void(int)> printNumber) {
30    for (int i = 2; i <= n; i += 2) {
31      sem_wait(&evenSemaphore);
32      printNumber(i);
33      sem_post(&zeroSemaphore);
34    }
35  }
36  void odd(function<void(int)> printNumber) {
37    for (int i = 1; i <= n; i += 2) {
38      sem_wait(&oddSemaphore);
39      printNumber(i);
40      sem_post(&zeroSemaphore);
41    }
42  }
43};

Python Solution

Python supports multithreading through the threading module. However, the Global Interpreter Lock (GIL) reduces the utility of threads in Python for many tasks. Fortunately, the GIL is not a concern for this problem because no thread executes Python byte-code when it is not printing a number, meaning that print calls from different threads can overlap.

The semaphore construct in Python is available through the threading.Semaphore() object.

1
2python
3import threading
4
5class ZeroEvenOdd:
6    def __init__(self, n):
7        self.n = n
8        self.zeroSem = threading.Semaphore(1)
9        self.evenSem = threading.Semaphore(0)
10        self.oddSem = threading.Semaphore(0)
11
12    def zero(self, printNumber: 'Callable[[int], None]') -> None:
13        for i in range(self.n):
14            self.zeroSem.acquire()
15            printNumber(0)
16            if i % 2: self.evenSem.release()
17            else: self.oddSem.release()
18
19    def even(self, printNumber: 'Callable[[int], None]') -> None:
20        for i in range(2, self.n+1, 2):
21            self.evenSem.acquire()
22            printNumber(i)
23            self.zeroSem.release()
24
25    def odd(self, printNumber: 'Callable[[int], None]') -> None:
26        for i in range(1, self.n+1, 2):
27            self.oddSem.acquire()
28            printNumber(i)
29            self.zeroSem.release()

JavaScript Solution

JavaScript supports semaphore-like logic with promise-based barriers, which is a suitable way of solving the problem.

1
2javascript
3class ZeroEvenOdd {
4	constructor(n) {
5		this.n = n;
6		this.zeroP = Promise.resolve();
7		this.oddP = new Promise(()=>{})
8		this.evenP = new Promise(()=>{})
9	}
10	async zero(printNumber) {
11		for (let i = 1; i <= this.n; i++) {
12			await this.zeroP;
13			printNumber(0);
14			this.zeroP = new Promise((r) => (this.zeroR = r));
15			if (i % 2) this.oddR();
16			else this.evenR();
17		}
18	}
19	async even(printNumber) {
20		for (let i = 2; i <= this.n; i += 2) {
21			await this.evenP;
22			printNumber(i);
23			this.evenP = new Promise((r) => (this.evenR = r));
24			this.zeroR();
25		}
26	}
27	async odd(printNumber) {
28		for (let i = 1; i <= this.n; i += 2) {
29			await this.oddP;
30			printNumber(i);
31			this.oddP = new Promise((r) => (this.oddR = r));
32			this.zeroR();
33		}
34	}
35}

Java Solution

In Java, we can use java.util.concurrent.Semaphore for implementing the semaphore construct.

1
2java
3import java.util.concurrent.*;
4
5class ZeroEvenOdd {
6    private int n;
7    Semaphore zeroSemaphore, evenSemaphore, oddSemaphore;
8
9    public ZeroEvenOdd(int n) {
10        this.n = n;
11        zeroSemaphore = new Semaphore(1);
12        evenSemaphore = new Semaphore(0);
13        oddSemaphore = new Semaphore(0);
14    }
15
16    public void zero(IntConsumer printNumber) throws InterruptedException {
17        for (int i = 1; i <= n; i++) {
18            zeroSemaphore.acquire();
19            printNumber.accept(0);
20            if (i % 2 == 0) evenSemaphore.release();
21            else oddSemaphore.release();
22        }
23    }
24
25    public void even(IntConsumer printNumber) throws InterruptedException {
26        for (int i = 2; i <= n; i+=2) {
27            evenSemaphore.acquire();
28            printNumber.accept(i);
29            zeroSemaphore.release();
30        }
31    }
32
33    public void odd(IntConsumer printNumber) throws InterruptedException {
34        for (int i = 1; i <= n; i+=2) {
35            oddSemaphore.acquire();
36            printNumber.accept(i);
37            zeroSemaphore.release();
38        }
39    }
40}

In this problem, the thread synchronization is achieved via the use of semaphores. This approach can be generalized to a large number of similar multithreading synchronization problems.