Building H2O
MedPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses Java's fundamental monitor-style synchronization primitives: synchronized blocks for mutual exclusion, and the wait() and notifyAll() methods for thread coordination. A shared counter, hydrogenCount, is used to track the number of hydrogen threads that have arrived at the barrier, ensuring that an oxygen thread only proceeds when two hydrogen threads are ready.
Algorithm
- Initialize an integer
hydrogenCountto 0. - In the
hydrogen()method:- Synchronize on a shared lock object.
- Use a
whileloop to check ifhydrogenCountis 2. If it is, callwait()to pause the thread and release the lock. - After the loop, call
releaseHydrogen(). - Increment
hydrogenCount. - Call
notifyAll()to wake up any waiting threads.
- In the
oxygen()method:- Synchronize on the same shared lock object.
- Use a
whileloop to check ifhydrogenCountis less than 2. If it is, callwait(). - After the loop, call
releaseOxygen(). - Reset
hydrogenCountto 0. - Call
notifyAll()to wake up waiting threads for the next molecule.
Walkthrough
A counter hydrogenCount keeps track of hydrogen threads ready to form a molecule. Both hydrogen() and oxygen() methods are synchronized on a common lock object to ensure atomic updates to this counter.
Hydrogen Thread Logic:
A hydrogen thread first checks if two hydrogen atoms are already waiting (hydrogenCount == 2). If so, it means the current group is full and is waiting for an oxygen atom. The thread calls wait(), releasing the lock and pausing its execution. If it can proceed, it calls releaseHydrogen(), increments the counter, and then calls notifyAll(). The notifyAll() call is crucial to wake up any waiting oxygen thread that might now be able to form a molecule.
Oxygen Thread Logic:
An oxygen thread checks if fewer than two hydrogen atoms are available (hydrogenCount < 2). If the condition is true, it calls wait() and pauses until it's notified and the condition is met. Once two hydrogens are available, it proceeds to call releaseOxygen(), resets hydrogenCount to 0 to prepare for the next molecule, and calls notifyAll() to wake up hydrogen threads for the next cycle.
The use of a while loop to re-check the condition after waking up is essential to handle spurious wakeups and ensure the state is correct before proceeding.
class H2O { private int hydrogenCount = 0; private final Object lock = new Object(); public H2O() {} public void hydrogen(Runnable releaseHydrogen) throws InterruptedException { synchronized (lock) { while (hydrogenCount == 2) { lock.wait(); } // releaseHydrogen.run() outputs "H". Do not change or remove this line. releaseHydrogen.run(); hydrogenCount++; lock.notifyAll(); } } public void oxygen(Runnable releaseOxygen) throws InterruptedException { synchronized (lock) { while (hydrogenCount < 2) { lock.wait(); } // releaseOxygen.run() outputs "O". Do not change or remove this line. releaseOxygen.run(); hydrogenCount = 0; lock.notifyAll(); } }}Complexity
Time
O(1) work per thread. Each thread performs a constant number of operations. The waiting time is inherent to the problem's synchronization requirements.
Space
O(1). Only a single integer counter and a lock object are used, requiring constant extra space.
Trade-offs
Pros
Uses fundamental and widely understood Java concurrency primitives.
The logic is relatively straightforward for those familiar with monitor-style synchronization.
Cons
notifyAll()is inefficient as it wakes up all waiting threads (a 'thundering herd'), including those that cannot make progress, leading to unnecessary context switches and condition re-checks.
This approach utilizes semaphores to directly manage the signaling and dependencies between the threads. Instead of a shared counter and locks, semaphores act as signals that threads can wait on or send. This method is generally more efficient than wait/notifyAll as it avoids waking up threads unnecessarily.
Algorithm
- Initialize a semaphore
hReadywith 0 permits. - Initialize a semaphore
oReadywith 0 permits. - In the
hydrogen()method:- Call
hReady.release()to signal that a hydrogen atom is available. - Call
oReady.acquire()to wait for a signal from the oxygen atom. - Once acquired, call
releaseHydrogen().
- Call
- In the
oxygen()method:- Call
hReady.acquire(2)to wait for two hydrogen atoms to become available. - Once acquired, call
releaseOxygen(). - Call
oReady.release(2)to signal the two waiting hydrogen atoms that they can proceed.
- Call
Walkthrough
We use two semaphores to orchestrate the molecule formation in a producer-consumer-like pattern.
hReady: A semaphore initialized to 0. Hydrogen threads act as producers, callingrelease()to add a permit, signaling their arrival. The oxygen thread acts as a consumer, callingacquire(2)to wait for two such signals.oReady: A semaphore initialized to 0. The oxygen thread acts as a producer, callingrelease(2)to signal that the two hydrogen threads can complete their action. The hydrogen threads act as consumers, each callingacquire()to wait for this signal.
Hydrogen Thread Logic:
A hydrogen thread first signals its availability by calling hReady.release(). It then immediately tries to acquire a permit from oReady by calling oReady.acquire(). This call will block until an oxygen thread releases a permit on oReady. Once unblocked, it knows a molecule is being formed, and it calls releaseHydrogen().
Oxygen Thread Logic:
An oxygen thread waits for two hydrogen threads by calling hReady.acquire(2). This call blocks until two separate hydrogen threads have called hReady.release(). Once it proceeds, it calls releaseOxygen() and then oReady.release(2), which unblocks the two hydrogen threads that are waiting on oReady.
import java.util.concurrent.Semaphore; class H2O { private Semaphore hReady = new Semaphore(0); private Semaphore oReady = new Semaphore(0); public H2O() {} public void hydrogen(Runnable releaseHydrogen) throws InterruptedException { hReady.release(); oReady.acquire(); // releaseHydrogen.run() outputs "H". Do not change or remove this line. releaseHydrogen.run(); } public void oxygen(Runnable releaseOxygen) throws InterruptedException { hReady.acquire(2); // releaseOxygen.run() outputs "O". Do not change or remove this line. releaseOxygen.run(); oReady.release(2); }}Complexity
Time
O(1) work per thread. Each thread performs a constant number of semaphore operations.
Space
O(1). We use two `Semaphore` objects, which is constant space.
Trade-offs
Pros
More efficient than
wait/notifyAllby avoiding the 'thundering herd' problem; threads are signaled precisely.The code directly models the dependencies: oxygen waits for two hydrogens, and each hydrogen waits for the oxygen.
Cons
The logic, while concise, might be slightly less intuitive than a barrier-based solution if one is not familiar with this specific semaphore signaling pattern.
This is arguably the most elegant and idiomatic solution, as it uses high-level concurrency utilities that directly map to the problem's description. A CyclicBarrier is used to make the group of three threads wait for each other, perfectly modeling the 'barrier' concept. Semaphores are used as gatekeepers to ensure that only the correct number of hydrogen (2) and oxygen (1) threads can attempt to enter the barrier for each molecule.
Algorithm
- Initialize a semaphore
hSemwith 2 permits. - Initialize a semaphore
oSemwith 1 permit. - Initialize a
CyclicBarrierfor 3 parties. Configure it with a barrier action (aRunnable) that resets the semaphores by callinghSem.release(2)andoSem.release(1). - In the
hydrogen()method:hSem.acquire().barrier.await().releaseHydrogen().
- In the
oxygen()method:oSem.acquire().barrier.await().releaseOxygen().
Walkthrough
This solution combines the strengths of two primitives:
- Semaphores (
hSem,oSem): These act as gates.hSemis initialized to 2 andoSemto 1. A hydrogen thread must acquire a permit fromhSem, and an oxygen thread fromoSem. This ensures that for each cycle, a maximum of two hydrogens and one oxygen can proceed towards the barrier. CyclicBarrier: This is the meeting point. It's initialized to wait for 3 threads. When a thread arrives, it callsbarrier.await()and blocks. Once the third thread callsawait(), the barrier is 'tripped', and all three waiting threads are released simultaneously to proceed.
A key feature is the barrier's reset mechanism. The CyclicBarrier is constructed with a Runnable action that executes automatically when the barrier is tripped. This action simply releases the permits back to the semaphores (hSem.release(2), oSem.release(1)), resetting the gates for the next set of threads to form the next molecule. This provides a clean, thread-safe way to manage the state between molecule formations.
import java.util.concurrent.BrokenBarrierException;import java.util.concurrent.CyclicBarrier;import java.util.concurrent.Semaphore; class H2O { private Semaphore hSem = new Semaphore(2); private Semaphore oSem = new Semaphore(1); private CyclicBarrier barrier; public H2O() { this.barrier = new CyclicBarrier(3, () -> { // This action is executed by the last thread to enter the barrier // after all threads have arrived but before they are released. // We reset the semaphores for the next molecule. hSem.release(2); oSem.release(1); }); } public void hydrogen(Runnable releaseHydrogen) throws InterruptedException { hSem.acquire(); try { barrier.await(); } catch (BrokenBarrierException e) { e.printStackTrace(); } // releaseHydrogen.run() outputs "H". Do not change or remove this line. releaseHydrogen.run(); } public void oxygen(Runnable releaseOxygen) throws InterruptedException { oSem.acquire(); try { barrier.await(); } catch (BrokenBarrierException e) { e.printStackTrace(); } // releaseOxygen.run() outputs "O". Do not change or remove this line. releaseOxygen.run(); }}Complexity
Time
O(1) work per thread. Each thread performs a constant number of synchronization operations.
Space
O(1). Uses a constant number of synchronization objects regardless of the number of threads.
Trade-offs
Pros
Highly declarative code that directly models the problem's concepts of 'grouping' and a 'barrier'.
Very efficient and robust, using modern concurrency utilities designed for this synchronization pattern.
The barrier action provides a clean and thread-safe mechanism for resetting state.
Cons
Requires understanding of two different advanced concurrency primitives (
SemaphoreandCyclicBarrier).
Solutions
Solution
class H2O { private Semaphore h = new Semaphore ( 2 ); private Semaphore o = new Semaphore ( 0 ); public H2O () { } public void hydrogen ( Runnable releaseHydrogen ) throws InterruptedException { h . acquire (); // releaseHydrogen.run() outputs "H". Do not change or remove this line. releaseHydrogen . run (); o . release (); } public void oxygen ( Runnable releaseOxygen ) throws InterruptedException { o . acquire ( 2 ); // releaseOxygen.run() outputs "O". Do not change or remove this line. releaseOxygen . run (); h . release ( 2 ); } }#include <semaphore.h> class H2O { private: sem_t h , o ; int st ; public: H2O () { sem_init ( & h , 0 , 2 ); sem_init ( & o , 0 , 0 ); st = 0 ; } void hydrogen ( function < void () > releaseHydrogen ) { sem_wait ( & h ); // releaseHydrogen() outputs "H". Do not change or remove this line. releaseHydrogen (); ++ st ; if ( st == 2 ) { sem_post ( & o ); } } void oxygen ( function < void () > releaseOxygen ) { sem_wait ( & o ); // releaseOxygen() outputs "O". Do not change or remove this line. releaseOxygen (); st = 0 ; sem_post ( & h ); sem_post ( & h ); } };from threading import Semaphore class H2O : def __init__ ( self ): self . h = Semaphore ( 2 ) self . o = Semaphore ( 0 ) def hydrogen ( self , releaseHydrogen : "Callable[[], None]" ) -> None : self . h . acquire () # releaseHydrogen() outputs "H". Do not change or remove this line. releaseHydrogen () if self . h . _value == 0 : # semaphore value checker api self . o . release () def oxygen ( self , releaseOxygen : "Callable[[], None]" ) -> None : self . o . acquire () # releaseOxygen() outputs "O". Do not change or remove this line. releaseOxygen () self . h . release ( 2 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.