We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Building H2O

Number: 1186

Difficulty: Medium

Paid? No

Companies: Tesla, LinkedIn, Google

Problem Description

There are two types of threads – oxygen and hydrogen – that need to be synchronized so that they can form water molecules (H2O). For every water molecule, two hydrogen threads and one oxygen thread must work together. Threads that arrive at the barrier must wait until a complete set (2 hydrogens and 1 oxygen) is available, ensuring that threads from one molecule bond before any others join to form the next molecule.

Key Insights

  • Use synchronization primitives to control the order in which threads pass the barrier.
  • A barrier (or cyclic barrier) that waits until three threads (2 hydrogens and 1 oxygen) are ready can help form a water molecule.
  • Counting semaphores can limit the number of hydrogen and oxygen threads participating in each molecule.
  • Once a full group is available, all threads can proceed together before allowing the next group to start bonding.

Space and Time Complexity

Time Complexity: O(n) for processing n molecules. Space Complexity: O(1) extra space aside from synchronization primitives used.

Solution

We solve the problem by using a barrier to ensure that exactly three threads (two hydrogens and one oxygen) proceed together. In addition, we use semaphores to restrict the number of hydrogen and oxygen threads that can concurrently attempt to form a molecule.

The approach is summarized as follows:

  1. Create a barrier that waits for 3 threads.
  2. Create a hydrogen semaphore initialized with a count of 2 and an oxygen semaphore with a count of 1.
  3. For a hydrogen thread:
    • Acquire the hydrogen semaphore.
    • Wait at the barrier until two hydrogen threads and one oxygen thread have arrived.
    • Call releaseHydrogen.
    • Release the hydrogen semaphore.
  4. For an oxygen thread:
    • Acquire the oxygen semaphore.
    • Wait at the barrier until the group is complete.
    • Call releaseOxygen.
    • Release the oxygen semaphore.

This guarantees that exactly one oxygen and two hydrogen threads bond together before starting the next water molecule.

Code Solutions

Below are the code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

import threading

# Initialize a barrier that waits for 3 threads to form one water molecule.
barrier = threading.Barrier(3)
# Semaphore for hydrogen allows up to 2 threads.
hydrogenSemaphore = threading.Semaphore(2)
# Semaphore for oxygen allows 1 thread.
oxygenSemaphore = threading.Semaphore(1)

class H2O:
    def __init__(self):
        pass

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        # Wait for a hydrogen permit.
        hydrogenSemaphore.acquire()
        # Wait at the barrier until 3 threads are ready.
        barrier.wait()
        # Call the function to simulate releasing hydrogen.
        releaseHydrogen()
        # Release the semaphore slot for the next hydrogen.
        hydrogenSemaphore.release()

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        # Wait for an oxygen permit.
        oxygenSemaphore.acquire()
        # Wait at the barrier until 3 threads are ready.
        barrier.wait()
        # Call the function to simulate releasing oxygen.
        releaseOxygen()
        # Release the semaphore slot for the next oxygen.
        oxygenSemaphore.release()
← Back to All Questions