Building H2O

Building H2O

What is this problem about?

The "Building H2O interview question" is a classic concurrency and synchronization problem. You are given two types of threads: Hydrogen and Oxygen. These threads call methods hydrogen() and oxygen() respectively. Your goal is to synchronize these threads such that for every three threads, exactly two hydrogen threads and one oxygen thread proceed to form a water molecule ($H_2O$). The molecules must be formed one at a time.

Why is this asked in interviews?

Top firms like Tesla and LinkedIn use the "Building H2O coding problem" to test a candidate's knowledge of Concurrency. It evaluates your ability to use synchronization primitives like Semaphores, Barriers, or Condition Variables. It’s a test of how you handle race conditions and ensure that a specific ratio of actions is maintained in a multi-threaded environment.

Algorithmic pattern used

The most common pattern used is Semaphores or Locks with Condition Variables.

1. Ratio Control: Use two semaphores or counters to track the number of available H and O slots.
2. Release Logic:
   • The Hydrogen thread waits for an H-slot, performs its action, and then signals that it is done.
   • The Oxygen thread waits for an O-slot, performs its action, and signals.
3. Barrier/Cyclic Synchronization: Use a barrier to ensure that all three threads (2H and 1O) complete their current molecule before any thread starts the next one.

Example explanation

• 4 Hydrogen threads and 2 Oxygen threads arrive.
• Molecule 1: Two H threads and one O thread are allowed to pass through.
• Molecule 2: The remaining two H threads and one O thread are allowed to pass.
• If an O thread arrives before any H threads, it must wait until at least two H threads are available.

Common mistakes candidates make

• Deadlocks: Threads waiting indefinitely for each other because the release signal logic is flawed.
• Race Conditions: Allowing three H threads to pass because the counter wasn't properly locked.
• Incorrect Ratio: Forgetting that water needs two hydrogen atoms for every one oxygen atom.

Interview preparation tip

Practice using Semaphore and CyclicBarrier in Java or threading.Semaphore in Python. Understanding the difference between a lock (mutex) and a semaphore is crucial for "Concurrency interview pattern" questions.