1117.Building_H20(Medium).md

1117. Building H2O (Medium)

Date and Time: Feb 21, 2025, 00:22 (EST)

Link: https://leetcode.com/problems/building-h2o

Question:

There are two kinds of threads: oxygen and hydrogen. Your goal is to group these threads to form water molecules.

There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given releaseHydrogen and releaseOxygen methods respectively, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

In other words:

• If an oxygen thread arrives at the barrier when no hydrogen threads are present, it must wait for two hydrogen threads.

• If a hydrogen thread arrives at the barrier when no other threads are present, it must wait for an oxygen thread and another hydrogen thread.

We do not have to worry about matching the threads up explicitly; the threads do not necessarily know which other threads they are paired up with. The key is that threads pass the barriers in complete sets; thus, if we examine the sequence of threads that bind and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Example 1:

Input: water = "HOH"
Output: "HHO"
Explanation: "HOH" and "OHH" are also valid answers.

Example 2:

Input: water = "OOHHHH"
Output: "HHOHHO"
Explanation: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" and "OHHOHH" are also valid answers.

Constraints:

• 3 * n == water.length

• 1 <= n <= 20

• water[i] is either 'H' or 'O'.

• There will be exactly 2 * n 'H' in water.

• There will be exactly n 'O' in water.

Walk-through:

1. Use two semaphores to restrict the access of hydrogen and oxygen. We need to allow two hydrogens can be accessed at the same time, so we initialize sem_h with value 2.

2. Notice that we first lock either sem_h or sem_o. If sem_h is locked, we can allow two threads with this resource at a time, and we use counter to record when we have 2 hydrogen. Then, we can signal/release sem_o, after we have oxygen, we can reset count = 0 and release two sem_h again.
   
   If sem_o is locked first, we signal/release on two sem_h.

C++ Solution:

class H2O {
protected:
    sem_t sem_hydro;
    sem_t sem_oxy;
    int count;

public:
    H2O() {
        sem_init(&sem_hydro, 0, 2);     // Allow 2 threads at a time
        sem_init(&sem_oxy, 0, 0);
        count = 0;
    }

    void hydrogen(function<void()> releaseHydrogen) {
        sem_wait(&sem_hydro);
        count++;
        // releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen();
        // Release sem_oxygen when we have 2 hydrogens
        if (count == 2) {
            sem_post(&sem_oxy);
        }
    }

    void oxygen(function<void()> releaseOxygen) {
        sem_wait(&sem_oxy);
        // releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen();
        // Reset count to 0, and release sem_hydro
        count = 0;
        sem_post(&sem_hydro);
        sem_post(&sem_hydro);
    }
};