Building H2O
Building H2O - Video Solution
Watch 8 video solutions for Building H2O, a medium level problem involving Concurrency. This walkthrough by Suraj Mehta has 2,028 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.length1 <= n <= 20water[i]is either'H'or'O'.- There will be exactly
2 * n'H'inwater. - There will be exactly
n'O'inwater.
Approach Overview
Problem Overview: You are given multiple threads representing hydrogen and oxygen atoms. The goal is to synchronize them so exactly two hydrogen threads and one oxygen thread print in the correct grouping to form a water molecule (H2O). The challenge is not computation but coordination—threads must wait until the right combination is available before proceeding.
Approach 1: Semaphore Synchronization (O(n) time, O(1) space)
This approach uses concurrency primitives called semaphores to control how many hydrogen and oxygen threads can proceed at a time. Initialize a hydrogen semaphore with value 2 and an oxygen semaphore with value 1. Each hydrogen thread acquires the hydrogen semaphore before printing H, and each oxygen thread acquires the oxygen semaphore before printing O. After three atoms participate, the semaphores reset so the next molecule can form. The key idea is limiting the number of threads entering the critical section so only two hydrogen and one oxygen are allowed per cycle. Each thread performs constant-time synchronization operations (acquire, release), giving overall O(n) time across all threads and O(1) auxiliary space.
Approach 2: Monitor Synchronization Using Mutex and Condition Variables (O(n) time, O(1) space)
This solution models the problem using a monitor with a mutex lock and condition variables. Shared counters track how many hydrogen and oxygen threads are currently ready. When a thread arrives, it locks the mutex and checks whether adding itself would violate the 2H + 1O constraint. If the molecule is incomplete or too many of one atom have arrived, the thread waits on a condition variable. Once exactly two hydrogen and one oxygen threads are available, all three are signaled to proceed and print their characters. After printing, the counters reset for the next molecule. The monitor guarantees mutual exclusion and correct grouping, while condition variables handle waiting and signaling efficiently.
Recommended for interviews: Semaphore synchronization is usually the expected answer. It demonstrates strong understanding of thread coordination and resource limiting using simple primitives. The monitor approach is also valid and shows deeper familiarity with classic synchronization patterns like mutex locks and condition variables. Showing both indicates you understand how low-level thread coordination works beyond basic locking.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Semaphore Synchronization | O(n) | O(1) | Preferred approach for interview settings and systems using semaphore primitives for thread coordination. |
| Monitor (Mutex + Condition Variables) | O(n) | O(1) | Useful when implementing synchronization using locks and condition variables instead of semaphores. |