Free lesson · Concurrency Interview Mastery
Building H2O
Every problem so far has been about sequencing - making threads take turns in some order. "Building H2O" introduces a fundamentally different coordination need: grouping, or assembling a fixed set of threads before any of them may proceed. Threads represent hydrogen and oxygen atoms, and they must bond into water molecules - exactly two hydrogens and one oxygen per molecule. The constraint is that atoms can only proceed once a complete molecule's worth has gathered: two H threads and one O thread must rendezvous, bond together, and only then move on, after which the next molecule assembles from the next available atoms. No atom may race ahead and bond into a half-formed or wrongly-proportioned molecule. This requires two new tools working together: counting semaphores to enforce the 2:1 ratio, and a barrier to make the three atoms of a molecule synchronize before proceeding. The barrier - "wait until N threads have arrived, then release them together" - is the key new primitive, and it recurs in any "assemble a group, then go" coordination.
The problem
Threads call one of two methods: hydrogen() (each represents one H atom) or oxygen() (each one O atom). Each method, when its atom is ready to bond, calls a releaseHydrogen or releaseOxygen action (printing "H" or "O"). The requirements:
- Atoms must group into complete water molecules: every group that bonds consists of exactly 2 H and 1 O.
- The bonding of one molecule must complete before the next molecule's atoms bond - outputs must form valid molecules (e.g.,
"HHO","HOH","OHH"- some permutation with 2 H and 1 O - for each group of three releases), never something like"HHH"or"HHHO"that would imply a malformed molecule. - There may be arbitrarily many H and O threads arriving in any order and at any time; the solution must pair them up correctly regardless of arrival order.
So if 4 H threads and 2 O threads are present, they must form two molecules (2H+1O each), with each molecule's three atoms bonding together before the next molecule's do. The coordination must (a) let exactly 2 H and 1 O through per molecule, and (b) make those three synchronize - all three present - before any of them completes the bond and moves on.
The core idea: counting semaphores plus a barrier
The clean solution combines two counting semaphores (to enforce the 2:1 ratio) with a barrier of 3 (to assemble each molecule before release):
hydrogenSem = Semaphore(2) # allow 2 H per molecule
oxygenSem = Semaphore(1) # allow 1 O per molecule
barrier = Barrier(3) # 3 atoms (2H+1O) must rendezvous
function hydrogen():
hydrogenSem.acquire() # at most 2 H proceed before reset
barrier.await() # wait for the full molecule (2H + 1O) to gather
releaseHydrogen() # print "H" - bond
hydrogenSem.release() # free a slot for the NEXT molecule's H
function oxygen():
oxygenSem.acquire() # at most 1 O proceeds before reset
barrier.await() # wait for the full molecule to gather
releaseOxygen() # print "O" - bond
oxygenSem.release() # free the slot for the next molecule's O
Two mechanisms work together. The counting semaphores meter the ratio: hydrogenSem starts at 2, so at most two H threads pass acquire before it's exhausted; oxygenSem starts at 1, so only one O passes. This guarantees that the atoms gathering at the barrier are exactly 2 H and 1 O - never 3 H or 2 O. The barrier of 3 then enforces the rendezvous: barrier.await() blocks each arriving atom until all three (the 2 H and the 1 O the semaphores let through) have arrived, at which point the barrier releases all three together. Only after the barrier do they call release...() to bond and print. After bonding, each releases its semaphore, restoring hydrogenSem to 2 and oxygenSem to 1 for the next molecule. The barrier (being cyclic) automatically resets for the next group. So each molecule: 2 H and 1 O are admitted by the semaphores, they rendezvous at the barrier, bond together, then free their slots for the next molecule.
flowchart TD
H1["H atom"] --> HS{"hydrogenSem<br/>(2 slots)"}
H2["H atom"] --> HS
O1["O atom"] --> OS{"oxygenSem<br/>(1 slot)"}
HS -->|2 H pass| BAR
OS -->|1 O passes| BAR["Barrier(3):<br/>wait for all 2H+1O"]
BAR -->|all 3 arrived -> release together| BOND["bond: print H,H,O<br/>then release semaphores"]
BOND -->|reset for next molecule| H1
note["Semaphores enforce the 2:1 RATIO;<br/>the barrier ASSEMBLES the group before bonding."]
This flowchart shows the H2O coordination. Hydrogen atoms pass through a hydrogen semaphore that has two slots, so at most two hydrogens proceed per molecule. Oxygen atoms pass through an oxygen semaphore with one slot, so exactly one oxygen proceeds. These semaphores enforce the two-to-one ratio. The two hydrogens and one oxygen that pass then arrive at a barrier set for three threads. The barrier makes each atom wait until all three have arrived, then releases them together. Only then do they bond and print their H, H, and O outputs. After bonding, each atom releases its semaphore, restoring two hydrogen slots and one oxygen slot for the next molecule, and the cyclic barrier resets. So the semaphores control the ratio and the barrier assembles the complete group before any atom bonds.
Why both mechanisms are needed
The insight is that two separate requirements need two separate mechanisms, and neither alone suffices:
- The semaphores alone (without the barrier) would meter the ratio - 2 H and 1 O per cycle - but wouldn't synchronize them. An H that acquired its slot could call
releaseHydrogen()and finish before the O even arrived, producing outputs that don't correspond to complete molecules forming together (e.g., two H's bond and leave before the O shows up). The ratio would be right over time, but the grouping - three atoms bonding as a unit - wouldn't hold. - The barrier alone (without the semaphores) would synchronize threads in groups of 3, but wouldn't enforce the composition of each group - three H threads could arrive and trip a barrier of 3, bonding as "HHH," which is not water. The barrier ensures three atoms rendezvous but not which three.
Together they're correct: the semaphores ensure the three atoms admitted per cycle are exactly 2 H + 1 O (right composition), and the barrier ensures those three actually rendezvous and bond as a unit before the next molecule starts (right grouping). This decomposition - meter the composition with semaphores, assemble the group with a barrier - is the template for any "form groups of a specific makeup" coordination. The two concerns (how many of each type, and synchronize-the-group) are orthogonal and each gets its own primitive.
Important: "Building H2O" is a grouping/rendezvous problem: assemble exactly 2 H + 1 O, bond them together, then form the next molecule. It needs two mechanisms for two requirements: counting semaphores (
hydrogenSem=2,oxygenSem=1) enforce the 2:1 ratio (composition), and a barrier of 3 enforces the rendezvous (the three atoms synchronize before any bonds). Neither alone works - semaphores meter the ratio but don't synchronize; a barrier synchronizes three but doesn't control which three. After bonding, atoms release their semaphores to admit the next molecule, and the cyclic barrier resets. The barrier ("wait until N arrive, then release together") is the key new primitive. The decomposition - meter composition with semaphores, assemble the group with a barrier - generalizes to any fixed-makeup grouping problem.
The barrier primitive
The barrier deserves a closer look, since it's the new tool. A barrier (or cyclic barrier) is a synchronization point where threads wait until a specified number have arrived, then all proceed together - a rendezvous. It's the inverse of the signaling we've seen: rather than one thread releasing another, every thread blocks at await() until the count is met, then all release simultaneously. A cyclic barrier automatically resets after each release, so it can be reused for successive groups (essential here - each molecule reuses the barrier). Barriers appear throughout parallel computing: in fork-join-style phased computations (all workers finish phase 1 before any starts phase 2), in parallel simulations (all cells update before the next timestep), and here in grouping atoms. If your language lacks a barrier primitive, you can build one from a mutex, a counter, and a condition variable: each arriving thread increments the counter; if it's the last to arrive, it wakes everyone; otherwise it waits - with care taken to reset correctly for reuse (the classic "turnstile" two-phase barrier handles the reset cleanly). Recognizing when a problem needs a barrier (assemble a group, then go) versus a signal (one thread releases another) versus a mutex (one at a time) is exactly the primitive-selection skill this module builds.
A worked scenario: atoms arriving out of order
The solution's robustness to arbitrary arrival order is worth seeing. Suppose threads arrive in this order: H, H, H, O, O, H (three H's, then two O's, then one more H). Trace the semaphores (hydrogenSem=2, oxygenSem=1, barrier=3):
arrive H1: hydrogenSem 2->1, waits at barrier (1/3)
arrive H2: hydrogenSem 1->0, waits at barrier (2/3)
arrive H3: hydrogenSem is 0 -> BLOCKS on acquire (can't join this molecule)
arrive O1: oxygenSem 1->0, waits at barrier (3/3) -> BARRIER TRIPS
-> H1, H2, O1 bond ("HHO"), release their semaphores
-> hydrogenSem 0->2 (both H slots back... but H3 was waiting)
-> actually: H1.release ->1, H2.release ->2 ; oxygenSem ->1
arrive O2 / resume H3: H3 (was blocked) acquires (hydrogenSem 2->1), waits at barrier
a 2nd H still needed; the next arriving H + O2 complete molecule 2
The mechanism handles any order gracefully: the semaphores act as gates that admit only 2 H and 1 O at a time, so excess atoms of either type simply block on acquire until a slot frees up (after the current molecule bonds and releases). H3 arriving while both H slots are taken just waits - it can't jump into the current molecule - and joins the next one once a slot reopens. The barrier only trips when a full 2H+1O set has gathered, so partial sets wait. No matter the interleaving, atoms are admitted in the right proportions and bond in complete groups. This is the elegance of the gate-plus-rendezvous design: it's self-regulating under any arrival pattern, because the semaphores throttle admission and the barrier enforces completeness, with no explicit arrival-order logic needed.
An alternative: mutex, counters, and a condition variable
If you don't have a barrier primitive (or an interviewer asks you to avoid one), you can build the equivalent with a mutex, counters of waiting H and O, and a condition variable:
lock = Lock(); cond = Condition(lock)
waitingH = 0; waitingO = 0
function hydrogen():
lock.acquire()
waitingH += 1
while not (waitingH >= 2 and waitingO >= 1): # can a molecule form?
cond.wait()
# a molecule is available; this H is part of it
... (one thread, on forming, decrements counts by 2H+1O and releases the trio) ...
cond.notify_all()
lock.release()
releaseHydrogen()
The idea: each atom registers itself (increments waitingH/waitingO) and waits until a full molecule's worth is present (waitingH >= 2 and waitingO >= 1); when that condition holds, the atoms forming the molecule decrement the counters and proceed to bond. This reproduces the semaphore-plus-barrier behavior using explicit shared counts and a predicate - it's the same "meter composition, assemble group" logic, but with the composition check and the grouping both expressed through the condition-variable predicate over the counters. It's more error-prone than the semaphore-plus-barrier version (you must carefully decrement exactly 2H+1O per molecule and avoid double-counting, which is fiddly), which is why the barrier-based solution is preferred when a barrier is available - it cleanly separates the two concerns into two purpose-built primitives. But knowing the counter-and-condition-variable construction matters: it shows the barrier isn't magic (it's a counter + condition variable underneath), and it's the fallback when you must build the rendezvous by hand. The comparison reinforces the lesson - purpose-built primitives (semaphore, barrier) make the solution clearer than hand-rolled counter logic, even though both express the same coordination.
Note: The barrier introduced here is one of the four or five truly fundamental coordination primitives, and it's worth fixing its distinct character firmly. A mutex enforces "one at a time." A signal (semaphore release / condition notify) enforces "this thread may now proceed because that thread said so." A barrier enforces something neither can: "none of you proceed until all of you have arrived." It's a collective synchronization - symmetric across the participants, with no one thread releasing another; instead the last to arrive releases everyone. This collective rendezvous is exactly what grouping problems need, and it appears constantly in parallel computing beyond this puzzle: phased algorithms where every worker must finish phase k before any starts phase k+1 (bulk-synchronous parallel computation), parallel simulations stepping through time (all cells compute the new state before any advances), and map-reduce-style stages (all mappers finish before reducers begin). Whenever you see "everyone must reach this point before anyone continues," that's a barrier - and recognizing it, rather than trying to contort signals or mutexes into doing the job, is the primitive-selection skill that makes coordination problems tractable. H2O is the gentle introduction; the pattern scales to the largest parallel systems.
The interview angle
Interview: "Building H2O" (LeetCode 1117) is a popular grouping/synchronization question. The expected answer: counting semaphores (
hydrogenSem=2,oxygenSem=1) for the 2:1 ratio plus a barrier of 3 for the rendezvous, releasing the semaphores after bonding to enable the next molecule. Distinguishing details: (1) recognizing it needs two mechanisms for two requirements (ratio vs. grouping) and that neither alone suffices - the clearest depth signal; (2) why the barrier is essential (semaphores meter the ratio but don't synchronize the group); (3) why the semaphores are essential (a bare barrier of 3 could group "HHH"); (4) the reset for the next molecule (release semaphores, cyclic barrier resets). Knowing what a barrier is, and being able to build one from mutex + counter + condition variable if asked, rounds out a strong answer. The "two requirements, two mechanisms" decomposition is what interviewers most want to hear.
Quick reference
BUILDING H2O (LeetCode 1117): bond atoms into water - exactly 2 H + 1 O per molecule
= a GROUPING / RENDEZVOUS problem (assemble a fixed-makeup group, then proceed)
SOLUTION = TWO mechanisms for TWO requirements:
COUNTING SEMAPHORES (composition / ratio):
hydrogenSem=2 -> at most 2 H per molecule
oxygenSem=1 -> at most 1 O per molecule
BARRIER(3) (rendezvous / grouping):
all 3 atoms (2H+1O) await() -> released together -> then bond
hydrogen(): hydrogenSem.acquire(); barrier.await(); releaseH(); hydrogenSem.release()
oxygen(): oxygenSem.acquire(); barrier.await(); releaseO(); oxygenSem.release()
-> release semaphores after bonding -> next molecule; cyclic barrier auto-resets
WHY BOTH (neither alone works):
semaphores ALONE -> right ratio but atoms don't synchronize (H bonds before O arrives)
barrier ALONE -> groups of 3 but wrong composition (could be "HHH")
BARRIER primitive: wait until N threads arrive, then release ALL together (a rendezvous)
cyclic = auto-resets for reuse; buildable from mutex + counter + cond var
(vs SIGNAL = one releases another; vs MUTEX = one at a time)
TEMPLATE: meter COMPOSITION with semaphores, ASSEMBLE the group with a barrier
H2O introduced grouping and the barrier. The next two problems return to access control - coordinating many threads around shared resources with category rules: the Readers-Writers problem (concurrent readers, exclusive writers) and the Unisex Bathroom (a vivid variant with switching and starvation concerns).