How do you approach Building H2O?

Track waiting counts. A molecule forms when waitingH >= 2 and waitingO >= 1.

What is the time complexity of Building H2O?

Time complexity: O(n). Space complexity: O(1) extra.

What are common mistakes on Building H2O?

Re-checking a condition with if instead of while after waiting. Spurious wakeups are real. Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock. Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

Sitelet https://gitgood.dev/coding/building-h2o

gitGood.dev

← Back to problems

Building H2O

HardOperating Systems

Description

Concurrency design problem (paper-only). Threading primitives are not available in the gitGood sandbox; the auto-grader validates a simulation of the barrier protocol. The interview-grade answer uses two semaphores plus a barrier or a monitor.

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 (one oxygen + two hydrogens). 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.

For the auto-grader: given a string arrivals of 'H' and 'O' characters representing arrival order at the barrier, return the molecule release order as a string. Each molecule is encoded as the three letters that crossed the barrier together, in their barrier-release order (always two H followed by one O - "HHO"). If the input doesn't form complete molecules, only return completed ones.

Example 1

Input: arrivals = "HOH"

Output: "HHO"

Explanation: Two H's and one O combine. Release order is the two H's then the O.

Example 2

Input: arrivals = "OOHHHH"

Output: "HHOHHO"

Explanation: Two molecules form: the first O pairs with the first two H's; the second O pairs with the next two H's.

Constraints

- 0 <= arrivals.length <= 3000 - arrivals consists only of 'H' and 'O' - Total H's and O's may not pair up perfectly; ignore the leftover.

Building H2O: approach, complexity and pitfalls

A hard concurrency problem, graded against 6 test cases (3 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

If you are stuck

Show the 3-step hint ladder

Track waiting counts. A molecule forms when waitingH >= 2 and waitingO >= 1.
When that condition fires, emit 'HHO' and decrement counts by 2 and 1.
Process arrivals in order; emit eagerly each time the molecule condition is met.

The optimal approach

Show the approach: Real concurrent design

```

hSem = Semaphore(2) # at most 2 H past the gate at once

oSem = Semaphore(1) # at most 1 O past the gate

barrier = CyclicBarrier(3)

hydrogen():

hSem.acquire()

barrier.await() # the H prints inside this section

print('H')

hSem.release()

oxygen():

oSem.acquire()

barrier.await()

print('O')

oSem.release()

```

The barrier guarantees three threads meet before any of them prints; the per-element semaphores cap how many of each species can sit at the barrier so the next molecule can't start forming until the previous one releases.

Simulation logic for the grader

Walk the arrival string in order, accumulating counts. Whenever `countH >= 2` and `countO >= 1`, emit "HHO" and decrement `countH -= 2; countO -= 1`. The leftover at the end represents threads still blocked at the barrier.

Time: O(n)
Space: O(1) extra

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.