{x}
blog image

Building H2O

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.

Solution Explanation

This problem involves concurrent programming and requires synchronization to ensure that water molecules (H₂O) are formed correctly. The solution uses semaphores to control the access of hydrogen and oxygen threads to a shared resource (the formation of a water molecule).

Core Idea:

The solution utilizes two semaphores:

  • h: A semaphore initialized to 2. This represents the available slots for hydrogen atoms in a water molecule. When a hydrogen thread arrives, it acquires this semaphore, signifying it's part of the molecule. Once both hydrogen slots are filled, the semaphore count becomes 0.
  • o: A semaphore initialized to 0. This represents the availability of an oxygen atom. It's only released after both hydrogen threads have acquired their slots (h count becomes 0). When an oxygen thread arrives, it acquires this semaphore, signifying it's bonded with the two hydrogen atoms. After the oxygen thread completes, it releases the h semaphore, making it available for the next water molecule.

Code Walkthrough (Python3 Example):

  1. __init__: Initializes the semaphores h to 2 and o to 0.

  2. hydrogen:

    • self.h.acquire(): A hydrogen thread attempts to acquire a slot. This will succeed as long as there are available slots (the initial value of h is 2 and decrements as hydrogen threads acquire the semaphore).
    • releaseHydrogen(): The hydrogen atom is released (simulated by the function call).
    • if self.h._value == 0:: Checks if both hydrogen slots are filled. If so (h becomes 0), it releases the oxygen semaphore (self.o.release()), allowing an oxygen thread to proceed.

  3. oxygen:

    • self.o.acquire(): The oxygen thread waits until the o semaphore is released (which happens only after two hydrogen atoms have been released).
    • releaseOxygen(): The oxygen atom is released (simulated by the function call).
    • self.h.release(2): Releases both hydrogen slots back to the pool, making them available for the next water molecule formation.

Complexity Analysis:

  • Time Complexity: The time complexity is highly dependent on the number of threads and the order in which they arrive. In the worst case, if all hydrogen threads arrive before any oxygen threads, each hydrogen thread might have to wait until an oxygen thread and another hydrogen thread are available. However, assuming a relatively balanced arrival of hydrogen and oxygen threads, the time complexity remains O(n), where n is the number of water molecules to be formed. This is because each molecule formation involves a constant number of semaphore operations.

  • Space Complexity: The space complexity is O(1), as it only involves a constant number of semaphores regardless of the number of threads.

Other Language Implementations:

The Java and C++ implementations follow the same logic but use their respective concurrency primitives (Semaphores in Java and sem_t in C++). The key concepts of acquiring and releasing semaphores remain the same across all implementations.