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.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.
This approach leverages semaphores to synchronize the hydrogen and oxygen threads. The idea is to have semaphores interrupt the thread execution until the necessary conditions (2 hydrogen threads and 1 oxygen thread) are met to form a water molecule.
This C program creates hydrogen and oxygen threads using the pthread library and controls their synchronization using semaphores. The semaphores ensure that exactly two hydrogen and one oxygen thread proceed at a time to release their respective elements according to the formation of water.
Time Complexity: O(1) for each thread operation as the semaphore operations are constant time.
Space Complexity: O(1), excluding thread stack space.
This alternative approach uses a monitor-style synchronization, generally with mutex and condition variables, to control the sequence in which hydrogen and oxygen threads are executed to form molecules.
This C solution implements monitor-based synchronization using pthread_mutex and pthread_cond constructs to effectively manage access to shared resources. The condition signals ensure that threads are only released when they can successfully form a water molecule.
Time Complexity: O(1) per lock, unlock, and condition operations, being constant time.
Space Complexity: O(1) excluding thread stack space.
| Approach | Complexity |
|---|---|
| Semaphore Synchronization | Time Complexity: O(1) for each thread operation as the semaphore operations are constant time. |
| Monitor Synchronization Using Mutex and Condition Variables | Time Complexity: O(1) per lock, unlock, and condition operations, being constant time. |
| Default Approach | — |
| 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. |
Building H2O • Suraj Mehta • 2,019 views views
Watch 5 more video solutions →Practice Building H2O with our built-in code editor and test cases.
Practice on FleetCode