Problem Description

This is a thread synchronization problem where you need to coordinate threads representing hydrogen (H) and oxygen (O) atoms to form water molecules (H₂O).

The problem requires implementing a class H2O with two methods:

• hydrogen(): Called by hydrogen threads
• oxygen(): Called by oxygen threads

Key Requirements:

1. Molecule Formation: Threads must group in sets of exactly 3 - two hydrogen threads and one oxygen thread - to form one water molecule.

2. Barrier Synchronization: Threads must wait at a barrier until a complete molecule can be formed:

   • If an oxygen thread arrives when there are fewer than 2 hydrogen threads waiting, it must wait
   • If a hydrogen thread arrives when there's no oxygen thread or only one hydrogen thread, it must wait

3. Atomic Bonding: Once three threads (2H + 1O) are available, they must all "bond" together before any threads from the next molecule can proceed. This ensures molecules form completely without mixing threads from different molecules.

4. Output Order: While the exact pairing doesn't matter, the output must always show groups of three with the pattern of 2 H's and 1 O (in any order within each group).

Example Scenarios:

• If threads arrive in order H, H, O → they can immediately form H₂O
• If threads arrive in order O, H, H → the O waits, then all three proceed together
• If threads arrive in order H, O, H → the first H waits, then all three proceed together

The solution uses semaphores to control access:

• self.h = Semaphore(2): Allows up to 2 hydrogen threads to proceed
• self.o = Semaphore(0): Initially blocks oxygen threads

The hydrogen method acquires one H permit, releases hydrogen, and when both H permits are taken (meaning 2 hydrogens are ready), it releases the oxygen semaphore. The oxygen method waits for permission, releases oxygen, then releases 2 hydrogen permits for the next molecule formation.

Intuition

The key insight is recognizing that we need to control the "capacity" of each type of thread that can proceed at any given time. Since a water molecule needs exactly 2 hydrogen atoms and 1 oxygen atom, we can think of this as having "slots" available for each type.

Initially, we should allow 2 hydrogen threads to enter because that's how many we need for one molecule. But we shouldn't let any oxygen thread proceed until we have those 2 hydrogens ready. This naturally leads us to think about semaphores - they're perfect for controlling how many threads can access a resource.

The clever part is understanding the cycle:

1. Start by allowing 2 H threads (initialize H semaphore with 2)
2. Block all O threads initially (initialize O semaphore with 0)
3. When both H slots are filled, we know we have our 2 hydrogens ready, so we can signal the oxygen to proceed
4. After the oxygen executes, it should "reset" the system for the next molecule by releasing 2 new H permits

The "handoff" mechanism is crucial: the second hydrogen thread (when self.h._value == 0) acts as the trigger to release the oxygen. This ensures we always have exactly 2 H's before any O can proceed. Then the oxygen thread, after executing, becomes responsible for enabling the next pair of hydrogens.

This creates a repeating pattern: H, H, O → H, H, O → H, H, O...

The beauty of this approach is that it doesn't matter in what order the threads arrive. The semaphores naturally queue them up and release them in valid groups of three. If an oxygen arrives first, it waits. If only one hydrogen arrives, it takes one slot and waits for another hydrogen to fill the second slot before they collectively release the oxygen.

Solution Approach

The solution uses semaphores as the primary synchronization mechanism. Let's walk through the implementation step by step:

Data Structure Initialization

def __init__(self):
    self.h = Semaphore(2)  # Allow 2 hydrogen threads initially
    self.o = Semaphore(0)  # Block all oxygen threads initially

• self.h: Controls hydrogen thread access with initial value 2 (since we need 2 H atoms per molecule)
• self.o: Controls oxygen thread access with initial value 0 (oxygen must wait for hydrogens first)

Hydrogen Thread Logic

def hydrogen(self, releaseHydrogen):
    self.h.acquire()                    # Try to get one of the 2 hydrogen permits
    releaseHydrogen()                    # Output "H"
    if self.h._value == 0:              # Check if both H permits are taken
        self.o.release()                 # Signal oxygen thread to proceed

Step-by-step execution:

1. acquire() decrements the hydrogen semaphore. If the value was > 0, the thread proceeds; otherwise it blocks
2. Once acquired, the hydrogen atom is "released" (outputs "H")
3. The critical check: if self.h._value == 0, it means both hydrogen slots are filled (2 hydrogens are ready)
4. When both hydrogens are ready, release the oxygen semaphore to allow one oxygen thread to proceed

Oxygen Thread Logic

def oxygen(self, releaseOxygen):
    self.o.acquire()                     # Wait for signal from hydrogen threads
    releaseOxygen()                      # Output "O"
    self.h.release(2)                    # Reset: allow 2 new hydrogen threads

Step-by-step execution:

1. acquire() on oxygen semaphore - this thread blocks until the second hydrogen signals it
2. Once unblocked, the oxygen atom is "released" (outputs "O")
3. release(2) on hydrogen semaphore adds 2 permits back, allowing the next pair of hydrogen threads to start forming the next molecule

The Synchronization Pattern

The implementation creates a cyclic barrier pattern:

• Phase 1: Two hydrogen threads enter (consuming both H permits)
• Phase 2: Second hydrogen signals the oxygen thread
• Phase 3: Oxygen thread executes and resets the system for the next molecule

This ensures that threads always group in sets of three (2H + 1O) before any thread from the next molecule can proceed. The semaphores naturally handle queueing - if extra threads arrive, they wait in the semaphore's internal queue until their turn comes in the next molecule formation cycle.

Example Walkthrough

Let's walk through a concrete example where 6 threads arrive in the order: H₁, O₁, H₂, O₂, H₃, H₄

Initial State:

• self.h = Semaphore(2) - can accept 2 hydrogen threads
• self.o = Semaphore(0) - blocks all oxygen threads

Step 1: H₁ arrives

• H₁ calls self.h.acquire() → succeeds (semaphore: 2→1)
• H₁ outputs "H"
• H₁ checks self.h._value == 1 (not 0) → doesn't release oxygen
• H₁ completes

Step 2: O₁ arrives

• O₁ calls self.o.acquire() → BLOCKS (semaphore value is 0)
• O₁ waits in queue...

Step 3: H₂ arrives

• H₂ calls self.h.acquire() → succeeds (semaphore: 1→0)
• H₂ outputs "H"
• H₂ checks self.h._value == 0 → YES! Both H slots filled
• H₂ calls self.o.release() → unblocks O₁
• H₂ completes

Step 4: O₁ unblocks and executes

• O₁ resumes from self.o.acquire()
• O₁ outputs "O"
• O₁ calls self.h.release(2) → resets H semaphore (0→2)
• O₁ completes
• First molecule complete: "HHO"

Step 5: O₂ arrives

• O₂ calls self.o.acquire() → BLOCKS (semaphore back to 0)
• O₂ waits in queue...

Step 6: H₃ arrives

• H₃ calls self.h.acquire() → succeeds (semaphore: 2→1)
• H₃ outputs "H"
• H₃ checks self.h._value == 1 (not 0) → doesn't release oxygen
• H₃ completes

Step 7: H₄ arrives

• H₄ calls self.h.acquire() → succeeds (semaphore: 1→0)
• H₄ outputs "H"
• H₄ checks self.h._value == 0 → YES! Both H slots filled
• H₄ calls self.o.release() → unblocks O₂
• H₄ completes

Step 8: O₂ unblocks and executes

• O₂ resumes from self.o.acquire()
• O₂ outputs "O"
• O₂ calls self.h.release(2) → resets for next molecule
• O₂ completes
• Second molecule complete: "HHO"

Final Output: "HHOHHO" (two complete water molecules)

The key observation is how the semaphores enforce the grouping: even though O₁ arrived before H₂, it had to wait until two hydrogens were ready. Similarly, O₂ waited for H₃ and H₄ to both arrive before proceeding. The pattern ensures threads always group in valid sets of three.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) per operation

Each method (hydrogen and oxygen) performs a constant number of operations:

• hydrogen: One semaphore acquire, one function call, one conditional check, and potentially one semaphore release
• oxygen: One semaphore acquire, one function call, and one semaphore release with count 2

All semaphore operations (acquire and release) are O(1) in terms of the operation itself, though threads may block waiting for synchronization. The blocking time depends on thread scheduling and arrival order, not on input size.

Space Complexity: O(1)

The space usage is constant regardless of how many times the methods are called:

• Two semaphore objects (self.h and self.o)
• Each semaphore internally maintains a counter and a queue for waiting threads
• The queue size is bounded by the number of threads that can be blocked at once (at most 2 hydrogen threads waiting)

The space does not grow with the number of method invocations, making it constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Race Condition in Hydrogen Counter Check

The Pitfall: The code shown uses a shared hydrogen_count variable that's accessed and modified by multiple hydrogen threads without proper synchronization:

self.hydrogen_count += 1
if self.hydrogen_count == 2:
    self.hydrogen_count = 0
    self.oxygen_semaphore.release()

This creates a race condition. Consider this scenario:

• Thread H1 increments counter (now 1)
• Thread H2 increments counter (now 2)
• Thread H2 checks if count == 2 (true)
• Thread H1 also checks if count == 2 (true)
• Both threads might release the oxygen semaphore, causing two oxygen threads to proceed instead of one!

The Solution: Use the semaphore's internal state directly without additional shared variables:

def hydrogen(self, releaseHydrogen):
    self.hydrogen_semaphore.acquire()
    releaseHydrogen()
  
    # Check if this is the second hydrogen (both permits taken)
    if self.hydrogen_semaphore._value == 0:
        self.oxygen_semaphore.release()

2. Incorrect Semaphore Release Order

The Pitfall: Some implementations try to release permits before outputting the atom:

def oxygen(self, releaseOxygen):
    self.oxygen_semaphore.acquire()
    self.hydrogen_semaphore.release(2)  # Wrong: releasing before output
    releaseOxygen()

This breaks the barrier synchronization - new hydrogen threads could start processing before the current molecule completes formation.

The Solution: Always output the atom first, then release permits for the next molecule:

def oxygen(self, releaseOxygen):
    self.oxygen_semaphore.acquire()
    releaseOxygen()  # Output first
    self.hydrogen_semaphore.release(2)  # Then allow next molecule

3. Using Mutex/Lock Instead of Semaphores

The Pitfall: Attempting to use a simple Lock or Mutex:

def __init__(self):
    self.lock = Lock()
    self.h_count = 0
  
def hydrogen(self, releaseHydrogen):
    with self.lock:
        while self.h_count >= 2:
            # Deadlock! Can't wait while holding the lock
            pass
        releaseHydrogen()
        self.h_count += 1

This leads to deadlock because threads can't wait for conditions while holding the lock.

The Solution: Use counting semaphores which naturally handle waiting and counting:

• Semaphores allow threads to block without holding exclusive access
• They maintain internal counters that handle the "2 hydrogens, 1 oxygen" requirement elegantly

4. Forgetting to Handle Thread Arrival Order

The Pitfall: Assuming threads will arrive in a convenient order (like H, H, O repeatedly):

def hydrogen(self, releaseHydrogen):
    releaseHydrogen()  # Just output immediately
    # Assumes oxygen will coordinate - wrong!

The Solution: The semaphore pattern handles any arrival order:

• If O arrives first, it blocks on oxygen_semaphore.acquire()
• If H arrives first, it proceeds but ensures O waits until 2 H's are ready
• The pattern self-organizes regardless of thread arrival timing