Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build the H2O Molecule Barrier

Build the H2O Molecule Barrier

Hydrogen and oxygen threads keep arriving and need to bond into water — but "bond" here means something stricter than most producer/consumer problems: exactly two H's and one O must assemble together, and none of the three may proceed until all three are present. That's not a queue problem, it's a grouped rendezvous — the same shape as a batching flush, a quorum ack, or a distributed transaction's participant gather. It's a recurring Meta/Google-tier concurrency interview question precisely because the obvious fix (just count atoms and let three through) is subtly wrong: it gets the total ratio right while letting the wrong composition of three through at any given instant. This lab makes you build it, break it on the exact axis interviewers probe, and fix it for real, in Java and Go.

1. The trap

Model each atom as its own thread. A hydrogen thread calls hydrogen(releaseHydrogen), an oxygen thread calls oxygen(releaseOxygen), and each callback should only fire once that atom is part of a genuine, fully-assembled H2O molecule. The "obvious" first draft: don't coordinate at all, just call the callback immediately.

final class Naive {
    // hydrogen thread
    void hydrogen(Runnable releaseHydrogen) {
        releaseHydrogen.run();   // just... run it
    }

    // oxygen thread
    void oxygen(Runnable releaseOxygen) {
        releaseOxygen.run();
    }

    public static void main(String[] args) throws InterruptedException {
        Naive n = new Naive();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) new Thread(() -> n.hydrogen(() -> { synchronized (sb) { sb.append("H"); } })).start();
        for (int i = 0; i < 3; i++) new Thread(() -> n.oxygen(() -> { synchronized (sb) { sb.append("O"); } })).start();
        Thread.sleep(200);
        System.out.println(sb);
    }
}

Spin up 6 hydrogen threads and 3 oxygen threads and watch the output:

HHHOOOHHH   ← three H's bonded before any O even started

Nothing here is a molecule. There's no grouping, no ordering guarantee, and no relationship at all between when an H thread's callback fires and when an O thread's does — the scheduler interleaves them however it wants. This is worse than the classic producer/consumer failure modes (OOM, busy-wait) because it doesn't even look broken in casual testing — on a lightly loaded box the OS might happen to interleave threads roughly fairly and produce something that eyeballs okay. The bug is invisible until you specifically check composition in groups of three, which is exactly what this lab's tests do from the first line.

2. Scope it like a senior

Before reaching for a primitive, pin the contract down. A candidate who jumps straight to "I'll use a semaphore" without asking these is guessing:

3. Reason to the design

Attempt 0 — no coordination. Movement 1's trap. Root cause: there is no shared state at all connecting an H thread's decision to proceed with an O thread's. You need some shared coordination point.

Attempt 1 — a single counter behind a mutex. Track how many atoms have bonded total; let a thread through once totalBonded % 3 lines up. This sounds plausible but it's checking the wrong thing: a counter tracks quantity, not composition. Three hydrogen threads can each grab the lock, see the counter is "due" for progress, increment it, and release — nothing about a raw counter distinguishes "2 H + 1 O arrived" from "3 H arrived." You can get a perfectly incrementing counter and a molecule of three hydrogens. Counting isn't the mechanism; capping who can proceed, by type, is.

Attempt 2 — a barrier alone. This looks like the fix: a CyclicBarrier(3) (Java) or hand-rolled equivalent (Go) that blocks every thread — H or O — until exactly 3 have called await(), then releases all 3 together and resets for the next trio. It solves the "release together" requirement... but it still says nothing about which 3. If hydrogen threads simply outnumber or outrace oxygen threads to the barrier — a completely realistic scenario, not an edge case — three hydrogens can be the first three arrivals and trip the barrier together. You get a synchronized, atomically-released, wrong molecule. This is subtle enough that it's the exact bug Movement 5 reproduces on purpose: "I added a barrier, so I'm safe" is the wrong conclusion.

Attempt 3 — cap admission by type, THEN rendezvous (the design). The fix is two counting semaphores, one per atom type, that bound how many of each may even approach the barrier concurrently: hydrogenSem with 2 permits, oxygenSem with 1 permit. A thread must acquire its type's permit before calling the barrier, and only release that permit after it has bonded. This is the key inequality that makes it work:

  1. The permits sum to the barrier's party count. 2 (H permits) + 1 (O permit) = 3 (barrier parties). At most 3 threads can ever be "admitted" toward the barrier at any moment — exactly enough to trip it, never more.
  2. The permit ratio matches the stoichiometric ratio. 2 H-permits : 1 O-permit is exactly water's 2:1 ratio. A 4th hydrogen thread physically cannot acquire a permit — there are only 2 — so it blocks on acquire() until a permit is released, which only happens after the current trio has fully bonded. That's what prevents an HHH trio: the 3rd hydrogen can get in (there are 2 H permits... wait, no — exactly 2 H permits means at most 2 hydrogens can ever be admitted at once, so a 3rd hydrogen is physically blocked until an oxygen shows up to complete the current trio and free a permit).

Semaphore admission control plus barrier rendezvous, composed: the semaphores enforce correct composition, the barrier enforces simultaneous release. Neither alone is sufficient; together they're exactly the mechanism inside a correct H2O solution, and it generalizes directly — swap the ratio to 1:2 and permits {1,2} with a barrier of 3 and you've built CO2.

4. Build it — milestones

Attempt each milestone yourself before reading the reference implementation — it's positioned after the tests on purpose.

Reference implementation — Java (two Semaphores + CyclicBarrier)

Two counting semaphores cap admission by atom type; a 3-party CyclicBarrier makes the admitted trio release together. The permit–party arithmetic from Movement 3 is called out right in the class comment because it's the whole mechanism, not incidental detail.

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Semaphore;

/**
 * Correct H2O molecule builder: two counting semaphores cap how many H / O
 * threads may be "in flight" toward the bonding station, and a CyclicBarrier
 * of exactly 3 parties makes every trio assemble and release together.
 *
 * The key invariant: hydrogenSem permits (2) + oxygenSem permits (1) ==
 * barrier parties (3) == the molecule's stoichiometry (2 H : 1 O). That
 * equality is not a coincidence -- it's the whole design.
 */
public final class H2OBuilder {
    private final Semaphore hydrogenSem = new Semaphore(2); // at most 2 H "at the door"
    private final Semaphore oxygenSem = new Semaphore(1);   // at most 1 O "at the door"
    private final CyclicBarrier barrier = new CyclicBarrier(3);
    private final List<String> bondLog = Collections.synchronizedList(new ArrayList<>());

    /** Call when a hydrogen thread wants to bond; releaseHydrogen emits the atom. */
    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hydrogenSem.acquire();
        try {
            awaitBarrier();
            releaseHydrogen.run();
            bondLog.add("H");
        } finally {
            hydrogenSem.release(); // only freed AFTER this atom has bonded
        }
    }

    /** Call when an oxygen thread wants to bond; releaseOxygen emits the atom. */
    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oxygenSem.acquire();
        try {
            awaitBarrier();
            releaseOxygen.run();
            bondLog.add("O");
        } finally {
            oxygenSem.release();
        }
    }

    private void awaitBarrier() {
        try {
            barrier.await();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new RuntimeException(e);
        } catch (BrokenBarrierException e) {
            throw new RuntimeException(e);
        }
    }

    public List<String> bondLog() {
        return bondLog;
    }
}

Notice the finally: a permit is released only after releaseHydrogen.run()/releaseOxygen.run() has actually executed — i.e. after this atom's trio is fully bonded — not merely after this thread passed the barrier. That ordering is what stops a 4th atom from sneaking into a molecule that's still "in progress."

Reference implementation — Go (buffered channels as semaphores + a hand-rolled cyclic barrier)

Go's standard library has no CyclicBarrier, so we hand-roll a reusable one with a generation counter (the same spurious-wakeup/lost-wakeup guard as any correctly-built condition-variable wait — a waiter from generation N must never be released by generation N+1's trip):

// Package h2o implements the H2O molecule-building kata: a grouped
// rendezvous where exactly 2 hydrogen + 1 oxygen goroutine must assemble
// before any of them proceeds, and the assembled trio releases together.
package h2o

import "sync"

// Barrier is a reusable (cyclic) rendezvous point for exactly `parties`
// goroutines -- Go's standard library has no CyclicBarrier, so this is the
// hand-rolled equivalent: a generation counter guards against the lost-wakeup
// you'd get from a naive "count then broadcast" without one (a goroutine
// waiting in generation N must never be released by generation N+1's trip).
type Barrier struct {
	mu         sync.Mutex
	cond       *sync.Cond
	parties    int
	count      int
	generation int
}

// NewBarrier builds a barrier that trips once `parties` goroutines call Await.
func NewBarrier(parties int) *Barrier {
	b := &Barrier{parties: parties}
	b.cond = sync.NewCond(&b.mu)
	return b
}

// Await blocks the calling goroutine until `parties` goroutines have all
// called Await, then releases all of them together and resets for reuse.
func (b *Barrier) Await() {
	b.mu.Lock()
	defer b.mu.Unlock()
	gen := b.generation
	b.count++
	if b.count == b.parties {
		// Last party to arrive: trip the barrier, start a new generation,
		// wake everyone waiting on the OLD generation.
		b.count = 0
		b.generation++
		b.cond.Broadcast()
		return
	}
	for gen == b.generation { // for, not if -- guard against spurious wakeups
		b.cond.Wait()
	}
}

And the builder itself, where two buffered channels of capacity 2 and 1 play the exact role of Java's semaphores — a send blocks when the channel is full, which is the admission cap:

package h2o

import "sync"

// Builder is the correct H2O molecule builder: two buffered channels act as
// counting semaphores (capacity 2 for hydrogen, capacity 1 for oxygen) that
// cap how many goroutines of each kind may approach the barrier at once.
// Channel capacity + barrier parties must satisfy: 2 (H) + 1 (O) == 3 (barrier
// parties) == the molecule's 2:1 stoichiometry. That equality is the design.
type Builder struct {
	hSem    chan struct{} // capacity 2 -- at most 2 H "at the door"
	oSem    chan struct{} // capacity 1 -- at most 1 O "at the door"
	barrier *Barrier

	mu      sync.Mutex
	bondLog []string
}

func NewBuilder() *Builder {
	return &Builder{
		hSem:    make(chan struct{}, 2),
		oSem:    make(chan struct{}, 1),
		barrier: NewBarrier(3),
	}
}

// Hydrogen is called by a goroutine that wants to bond as a hydrogen atom.
// releaseHydrogen is invoked only once this atom's trio has assembled.
func (b *Builder) Hydrogen(releaseHydrogen func()) {
	b.hSem <- struct{}{} // acquire one of 2 permits
	defer func() { <-b.hSem }() // freed only AFTER this atom has bonded
	b.barrier.Await()
	releaseHydrogen()
	b.record("H")
}

// Oxygen is called by a goroutine that wants to bond as an oxygen atom.
func (b *Builder) Oxygen(releaseOxygen func()) {
	b.oSem <- struct{}{}
	defer func() { <-b.oSem }()
	b.barrier.Await()
	releaseOxygen()
	b.record("O")
}

func (b *Builder) record(atom string) {
	b.mu.Lock()
	defer b.mu.Unlock()
	b.bondLog = append(b.bondLog, atom)
}

func (b *Builder) BondLog() []string {
	b.mu.Lock()
	defer b.mu.Unlock()
	out := make([]string, len(b.bondLog))
	copy(out, b.bondLog)
	return out
}

Both compile clean under go build ./... and go vet ./..., and both were exercised end to end — including under go test -race, which reports zero data races — before writing this page.

5. Break it — the test that fails

Delete exactly the two semaphore acquire/release calls, keep the barrier. Everything else stays identical:

import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;

/**
 * BUGGY builder: only the CyclicBarrier(3), no semaphores capping who may
 * approach it. The barrier guarantees "3 parties arrived" -- it says NOTHING
 * about which 3. If hydrogen threads outnumber and outrace oxygen threads to
 * the barrier, three hydrogens can trip it together: an H-H-H "molecule"
 * with zero oxygen. Wrong stoichiometry, and it reproduces every run when
 * hydrogens are given a head start.
 */
public final class BuggyH2OBuilder {
    private final CyclicBarrier barrier = new CyclicBarrier(3);
    private final List<String> bondLog = Collections.synchronizedList(new ArrayList<>());

    // Java -- BuggyH2OBuilder: only the CyclicBarrier(3), no semaphore caps.
    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        awaitBarrier();          // BUG: no cap on concurrent H arrivals
        releaseHydrogen.run();
        bondLog.add("H");
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        awaitBarrier();          // BUG: no cap on concurrent O arrivals
        releaseOxygen.run();
        bondLog.add("O");
    }

    private void awaitBarrier() {
        try {
            barrier.await();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
            throw new RuntimeException(e);
        } catch (BrokenBarrierException e) {
            throw new RuntimeException(e);
        }
    }

    public List<String> bondLog() {
        return bondLog;
    }
}

Run it (6 hydrogen threads started immediately, 3 oxygen threads started after a short delay so hydrogens reliably win the race to the barrier — counts stay at the correct 6:3 total so nobody is left stranded on a trip that never fills; the bug under test is wrong grouping, not a hang):

=== Scenario B: BuggyH2OBuilder (barrier only, no semaphores) ===
  molecule 1 = HHH   (H=3, O=0)  WRONG STOICHIOMETRY
  molecule 2 = HHH   (H=3, O=0)  WRONG STOICHIOMETRY
  molecule 3 = OOO   (H=0, O=3)  WRONG STOICHIOMETRY
Scenario B: BUG REPRODUCED

Every hydrogen wins every race to the barrier because nothing throttles how many can approach it at once — so the first two trips are all-hydrogen, and the barrier, having no idea what a "type" even is, happily trips on 3-of-a-kind twice, leaving the three delayed oxygens to form a 0-hydrogen trio by elimination. This is not a rare interleaving needing -race luck to surface — giving hydrogens even a small head start reproduces it deterministically, every run, in both languages:

// Go -- go test -race -run TestBuggyBuilderReproducesWrongStoichiometry -v
    h2o_test.go:89:   molecule 1 = HHH  (H=3, O=0) good=false
    h2o_test.go:89:   molecule 2 = HHH  (H=3, O=0) good=false
    h2o_test.go:89:   molecule 3 = OOO  (H=0, O=3) good=false
    h2o_test.go:92: BUG REPRODUCED: barrier-only design let a [H H H] trio through
--- PASS: TestBuggyBuilderReproducesWrongStoichiometry (0.30s)

The fix is putting the two semaphore acquires back before awaitBarrier(). Re-running the identical scenario against the correct H2OBuilder/Builder:

=== Scenario A: correct H2OBuilder (semaphores + barrier) ===
  molecule 1 = HHO   (H=2, O=1)  ok
  molecule 2 = OHH   (H=2, O=1)  ok
  molecule 3 = OHH   (H=2, O=1)  ok
Scenario A: ALL MOLECULES CORRECT (2H:1O)

That's the entire lesson in two log blocks: a rendezvous barrier answers "did enough parties arrive?" — it has no opinion on "the right kind of parties." Composition has to be enforced separately, before the rendezvous, not folded into it.

6. Optimise — with trade-offs

ApproachGuarantees simultaneous release?ComplexityThroughputUse when
2 semaphores + barrier (this lab)Yes — the barrier is the release pointModerate — two coordinating primitives, but each has one jobGood; barrier serializes only the hand-off instant, not the whole critical sectionYou need atomic, all-or-nothing group formation — matches real "assemble N then act" systems (batch flush, quorum gather, 2PC commit)
Semaphores only, no barrier (the classic LeetCode-1117 answer)No — each atom bonds the instant its own permit is free; only the running total ratio is ever correctLowest — two semaphores, nothing elseHighest — no thread ever waits for two others specificallyYou only need the aggregate ratio correct over time, not a discrete "this molecule exists" event — e.g. a rate-limited fan-out where 2:1 pacing is the actual requirement, not grouping
Single mutex + one condition variable + countersYes, if written correctly (each waiter loops re-checking hReady==2 && oReady==1)Highest — you hand-roll the exact admission logic the semaphores gave you for free, and must get the wait-loop right (Movement 3's "while, not if" lesson from the bounded producer/consumer lab applies verbatim)Lower — a single lock serializes both admission-checking and releaseYou need a custom, non-uniform group shape (e.g. "2 of type A OR 3 of type B") that a fixed-permit semaphore can't express directly
Channels-only, single arbiter goroutine (Go idiom)Yes — one goroutine owns all state, no shared memory to race onLow to reason about (no locks at all), but the arbiter itself is a bottleneck by constructionLower under heavy fan-in — everything funnels through one goroutine's select loopYou want zero shared-memory synchronization primitives and can accept a single coordinating goroutine; idiomatic Go, easiest to audit for correctness

The real judgment call: semaphores-only is a legitimate, simpler, higher-throughput answer to the original LeetCode problem — take it if all you need is a correctly-paced ratio over time. Reach for the barrier only when something downstream genuinely needs to observe "a complete molecule now exists" as a discrete event — a distributed-transaction commit, a batch flush, a quorum ack — because that's the property a barrier buys you that raw admission control doesn't. Don't add a barrier you don't need; it's one more thing to get right (Movement 5 proved that "one more thing" is exactly where the bug lives if you get the composition side wrong).

7. Defend under drilling

An interviewer will push on the design. These are the follow-ups that come up almost every time, with the answer a staff engineer gives — short, concrete, no hedging.

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed (javac/java; go build, go vet, go test -race) before publishing; the break-it test reproduces the wrong-stoichiometry bug deterministically on every run. See also: Problem 12: Building H2O and the Barriers & Resource Coordination pattern.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build the H2O Molecule Barrier? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build the H2O Molecule Barrier** (Hands-On Builds) and want to truly understand it. Explain Build the H2O Molecule Barrier from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build the H2O Molecule Barrier** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build the H2O Molecule Barrier** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build the H2O Molecule Barrier** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build Multithreaded FizzBuzzBuild a Traffic Light Controller →