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:
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.length1 <= n <= 20water[i] is either 'H' or 'O'.2 * n 'H' in water.n 'O' in water.#1117 Building H2O is a classic concurrency coordination problem where multiple hydrogen and oxygen threads must combine in the correct ratio (2H + 1O) to form water molecules. The key challenge is ensuring that exactly two hydrogen threads and one oxygen thread proceed together before printing or releasing their respective outputs.
A common strategy uses semaphores to control how many hydrogen and oxygen threads can proceed at a time. For example, a semaphore can limit hydrogen threads to two and oxygen threads to one. Once the required threads are ready, a barrier or synchronization mechanism ensures all three threads complete their actions together before allowing the next molecule to form.
This approach prevents race conditions and guarantees the correct formation order while keeping the synchronization lightweight. Since each thread performs constant work with simple synchronization primitives, the solution maintains O(1) time and O(1) extra space per operation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Semaphore + Barrier Synchronization | O(1) per thread | O(1) |
| Mutex + Counters with Condition Variables | O(1) per thread | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, concurrency problems like Building H2O are occasionally asked in advanced interviews at companies such as Google, Amazon, and Meta. They test understanding of thread coordination, synchronization primitives, and race condition handling.
The optimal approach uses semaphores to limit how many hydrogen and oxygen threads can proceed and a barrier to synchronize them. This ensures exactly two hydrogen threads and one oxygen thread form a molecule together without race conditions.
Without synchronization, hydrogen and oxygen threads could execute in the wrong ratio, producing invalid combinations. Synchronization guarantees that two hydrogen threads and one oxygen thread coordinate correctly before proceeding.
Concurrency primitives such as semaphores, mutexes, and condition variables are commonly used. Semaphores are especially effective because they naturally limit the number of threads allowed to proceed at a time.