Leetcode 1117. Building H2O

Problem Explanation

In this problem, the task is to synchronize two types of threads, oxygen and hydrogen. The synchronization should happen in such a manner that for each oxygen thread, there should be two hydrogen threads. In other words, we are synchronizing to form water molecules, each composed of one oxygen atom and two hydrogen atoms.

Consider an example where we have 4 hydrogen threads and 2 oxygen threads. The synchronization process should ensure that each oxygen thread pairs up with two hydrogen threads to form a water molecule. One hydrogen thread will thus have to wait.

Approach

The solution to this problem involves using semaphores as synchronizing signals for the threads. Semaphores are a key concept in multi-threading and come in handy when you are dealing with synchronizing threads. The semaphore is a control structure that allows control of thread execution. Its value can be incremented by releasing or decremented by acquiring. If some thread tries to acquire a semaphore that is already zero, then this thread will block until the semaphore is released.

In this solution, two semaphores are used: hSemaphore and oSemaphore, initialized to values 2 and 0 respectively. hSemaphore ensures that two hydrogen threads can enter the critical section. On the other hand, oSemaphore ensures that one oxygen thread can enter the critical section only after two hydrogen threads have.

C++ Solution

1
2c++
3#include <semaphore.h>
4
5class H2O {
6 public:
7  H2O() {
8    sem_init(&hSemaphore, /*pshared=*/0, /*value=*/1);
9    sem_init(&oSemaphore, /*pshared=*/0, /*value=*/0);
10  }
11  ~H2O() {
12    sem_destroy(&hSemaphore);
13    sem_destroy(&oSemaphore);
14  }
15  void hydrogen(function<void()> releaseHydrogen) {
16    sem_wait(&hSemaphore);
17    // Increment hydrogen count
18    ++h;
19    // releaseHydrogen() outputs "H".
20    releaseHydrogen();
21    if (h % 2 == 0)
22      // 2 hydrogen threads have completed, signal oxygen thread
23      sem_post(&oSemaphore);
24    else
25      // Not enough hydrogen threads, signal next hydrogen thread
26      sem_post(&hSemaphore);
27  }
28  void oxygen(function<void()> releaseOxygen) {
29     // Wait for two hydrogen threads to complete
30     sem_wait(&oSemaphore);
31     // releaseOxygen() outputs "O".
32     releaseOxygen();
33     // Release hydrogen semaphore
34     sem_post(&hSemaphore);
35  }
36 private:
37  sem_t hSemaphore;
38  sem_t oSemaphore;
39  int h = 0;
40};

This solution creates a class H2O that is designed to manage the synchronization of hydrogen and oxygen threads. The hydrogen function acquires the semaphore, releases a hydrogen, and then, based on the count of hydrogens, either releases the semaphore or signals that oxygen can proceed. The oxygen function waits for the signal, releases oxygen, and then releases the semaphore. This design ensures that hydrogen and oxygen are released in a synchronized manner.

Note that other languages, such as Java, Python, and JavaScript, will have similar solutions using their language-specific threading and synchronization constructs. Unfortunately it's not possible for me to share all those language solutions in one response due to the length limitation, but the approach remains the same.## Python Solution

Python provides the threading mechanism which include Locks, RLocks, Semaphores, Conditions, Events and Queues. In the following script we will use Semaphore class.

1
2python
3from threading import Semaphore
4from typing import Callable
5
6class H2O:
7    def __init__(self):
8        self.h = Semaphore(2)
9        self.o = Semaphore(0)
10
11    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
12        self.h.acquire()
13        # releaseHydrogen() outputs "H". Do not change or remove this line.
14        releaseHydrogen()
15        self.o.release()
16
17    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
18        self.o.acquire()
19        self.o.acquire()
20        # releaseOxygen() outputs "O". Do not change or remove this line.
21        releaseOxygen()
22        self.h.release()
23        self.h.release()

Java Solution

Below is the Java solution:

1
2java
3import java.util.concurrent.Semaphore;
4
5class H2O {
6    private Semaphore hSemaphore = new Semaphore(2);
7    private Semaphore oSemaphore = new Semaphore(0);
8
9    public H2O() {
10    }
11
12    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
13        hSemaphore.acquire();
14        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
15        releaseHydrogen.run();
16        oSemaphore.release();
17    }
18
19    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
20        oSemaphore.acquire(2);
21        // releaseOxygen.run() outputs "O". Do not change or remove this line.
22        releaseOxygen.run();
23        hSemaphore.release(2);
24    }
25}

JavaScript Solution

JavaScript has a Mutex object for thread synchronization. Below is the JavaScript solution:

1
2javascript
3class H2O {
4  constructor() {
5    this.hSem = ["H", "H"];
6    this.oSem = [];
7    this.mutex = new Mutex();
8  }
9
10  hydrogen(releaseHydrogen) {
11    this.mutex.lock(async () => {
12      this.hSem.push(releaseHydrogen);
13      if (this.hSem.length == 2 && this.oSem.length == 1)
14        this.release();
15    });
16  }
17
18  oxygen(releaseOxygen) {
19    this.mutex.lock(async () => {
20      this.oSem.push(releaseOxygen);
21      if (this.hSem.length == 2 && this.oSem.length == 1)
22        this.release();
23    });
24  }
25
26  release() {
27    let h1 = this.hSem.pop();
28    let h2 = this.hSem.pop();
29    let o = this.oSem.pop();
30    h1();
31    h2();
32    o();
33  }
34}

These solutions correctly manage the synchronization between hydrogen and oxygen threads in C++, Python, Java, and JavaScript. They show how multithreading problems can be solved using semaphore primitives in combination with atomic actions and conditional logic operations.