1117. Building H2O

MediumConcurrency
Leetcode Link

Problem Description

The problem provides a scenario that simulates the formation of water molecules (H2O) using threads. These threads represent the elements hydrogen (H) and oxygen (O). The objective is to ensure that two hydrogen threads (H) and one oxygen thread (O) can proceed to form a water molecule by passing a barrier, but they must do so in groups of three (two H and one O). The problem statement specifies the following constraints:

  • An oxygen thread has to wait at the barrier until two hydrogen threads are available so they can all proceed together.
  • Similarly, a hydrogen thread must wait for another hydrogen thread and an oxygen thread before proceeding.

The threads themselves do not need to be aware of their specific pairings; the key is to allow them to pass the barrier in complete sets that form water molecules. The code needs to enforce these synchronization constraints to ensure that no thread is allowed through the barrier until its corresponding set is complete.

Intuition

The solution uses the concept of semaphores which are synchronization tools to control access to a common resource by multiple threads in a concurrent system. In the context of this problem, semaphores are used to manage the passage of hydrogen and oxygen threads through the barrier.

Here is the intuition behind the solution:

  • Semaphore for Hydrogen (self.h): This semaphore starts with a count of 2, allowing two hydrogen threads to acquire it and, once acquired, proceed to release a hydrogen molecule by calling releaseHydrogen(). The semaphore's count decrements with each acquire. When it reaches 0, it means two hydrogen threads have passed, and an oxygen thread can now be allowed to pass by calling self.o.release().

  • Semaphore for Oxygen (self.o): This semaphore starts with a count of 0, ensuring that no oxygen thread can proceed until it's allowed by hydrogen threads. When the semaphore for hydrogen reaches a count of 0 (meaning two hydrogens have been acquired), then self.o.release() is called to increase the count to 1, allowing one oxygen thread to acquire it and proceed to release an oxygen molecule by calling releaseOxygen(). After this, it resets the count of the hydrogen semaphore to 2 by calling self.h.release(2), allowing the next group of hydrogen threads to acquire and start the process again.

Through this mechanism, we ensure that the barrier passes threads in sets of three with the correct combination to form water molecules, complying with the problem's constraints.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Solution Approach

The implementation of the solution revolves around the use of semaphores, which are counted locks that indicate the status of a resource. In the context of the problem, they are used to control the number of hydrogen and oxygen threads that can pass the barrier to form a water molecule.

Here's the breakdown of the solution approach step by step:

  • Initialization of Semaphores:

    • self.h: A semaphore representing the hydrogen atoms. It is initialized with a count of 2, indicating that at the start, two hydrogen threads can proceed.
    • self.o: A semaphore representing the oxygen atom. It is initialized with a count of 0 since we need two hydrogen atoms to be ready before an oxygen atom can proceed.

  • Hydrogen Method:

    • self.h.acquire(): Each hydrogen thread calls this method to decrement the semaphore's count. If two hydrogen threads call it, the count will become 0 and no more hydrogen threads can proceed until it's reset.
    • releaseHydrogen(): A callback function provided to the hydrogen method which, when invoked, signifies the passing of a hydrogen thread.
    • After releasing hydrogen, the code checks if the value of the semaphore self.h is 0, which means two hydrogen threads have acquired the lock and passed. It then calls self.o.release() to increment the oxygen semaphore, signaling that an oxygen thread can proceed.

  • Oxygen Method:

    • self.o.acquire(): The oxygen thread calls this to wait until its count is greater than 0. This can only happen after two hydrogen threads have passed and called self.o.release().
    • releaseOxygen(): A callback function provided to the oxygen method which, when invoked, signifies the passing of an oxygen thread.
    • self.h.release(2): After an oxygen thread has passed, the hydrogen semaphore is reset back to a count of 2 by releasing it twice. This allows the next pair of hydrogen threads to proceed and restart the cycle.

By coordinating the actions via semaphores, the solution can ensure that at any point in time, if three threads pass through the barrier, they will always be in the H-H-O combination, hence forming a water molecule. It establishes a pattern where exactly two hydrogen threads must pass before an oxygen thread can, and this cycle repeats for each water molecule produced. The algorithm guarantees that these conditions are met, allowing the correct formation of water molecules without any explicit matching between threads.

The use of semaphores is a classic synchronization mechanism for enforcing limits on access to resources in concurrent programming, and this solution uses them effectively to solve the given problem.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's step through a small example to illustrate the solution approach using semaphores to enforce the synchronization constraints required for the formation of water molecules:

Assume we have a sequence of threads representing hydrogen and oxygen atoms ready to form water molecules, like so: HHOHHO.

  • Step 1: Initialize semaphores self.h (count = 2) and self.o (count = 0).
  • Step 2: The first hydrogen thread H1 arrives and calls self.h.acquire(), decrementing the semaphore self.h count to 1.
  • Step 3: The second hydrogen thread H2 arrives and also calls self.h.acquire(), decrementing self.h's count to 0. Now, with 2 hydrogens ready, the code allows for an oxygen thread to proceed by calling self.o.release(), setting the semaphore self.o count to 1.
  • Step 4: The oxygen thread O1 arrives and calls self.o.acquire(), decrementing self.o's count back to 0. Now, H1 and H2 release their hydrogen atoms by invoking releaseHydrogen(), and O1 releases its oxygen atom by invoking releaseOxygen().
  • Step 5: After O1 releases the oxygen atom, self.h.release(2) is called, which resets self.h's count back to 2, allowing the next two hydrogen threads to proceed.
  • Step 6: Now the self.h count is back at 2, another pair of hydrogen threads H3 and H4 arrive and each calls self.h.acquire(), reducing the semaphore self.h count back to 0.
  • Step 7: Similar to step 3, since self.h's count is 0, self.o.release() is called again, incrementing self.o's count to 1 and allowing the next oxygen thread O2 to proceed.
  • Step 8: O2 then calls self.o.acquire(), decreasing its count to 0, and this enables H3, H4, and O2 to release their atoms by invoking releaseHydrogen() and releaseOxygen(), respectively.
  • Step 9: The cycle repeats with self.h.release(2) resetting the hydrogen semaphore count after each oxygen atom is released, ensuring the proper ratio for water molecule formation.

Throughout this example, the semaphore mechanisms enforce the correct arrival order and combination for the threads, closely emulating the constraints of water molecule formation and demonstrating the effectiveness of semaphores for synchronization in concurrent programming.

Solution Implementation

1from threading import Semaphore
2from typing import Callable
3
4class H2O:
5    def __init__(self):
6        # Initialize two semaphores for hydrogen and oxygen.
7        # Semaphore for hydrogen starts at 2 since we need two hydrogen atoms.
8        self.sem_hydrogen = Semaphore(2)
9        # Semaphore for oxygen starts at 0 - it is released when we have two hydrogen atoms.
10        self.sem_oxygen = Semaphore(0)
11
12    def hydrogen(self, releaseHydrogen: Callable[[], None]) -> None:
13        # Acquire the hydrogen semaphore.
14        self.sem_hydrogen.acquire()
15      
16        # When this function is called, we output the hydrogen atom.
17        # This simulates the release of a hydrogen atom.
18        releaseHydrogen()  # Outputs "H"
19      
20        # If there are no more hydrogen permits available, it means we have two hydrogens.
21        # Now we can release oxygen to balance and make an H2O molecule.
22        if self.sem_hydrogen._value == 0:
23            self.sem_oxygen.release()
24
25    def oxygen(self, releaseOxygen: Callable[[], None]) -> None:
26        # Acquire the oxygen semaphore.
27        self.sem_oxygen.acquire()
28
29        # When this function is called, we output the oxygen atom.
30        # This simulates the release of an oxygen atom.
31        releaseOxygen()  # Outputs "O"
32      
33        # After releasing an oxygen, we reset the hydrogen semaphore to 2.
34        # This allows two new hydrogen atoms to be processed, starting the cycle over.
35        self.sem_hydrogen.release(2)
36
1class H2O {
2  
3    // Semaphores to control the release of hydrogen and oxygen atoms.
4    private Semaphore semaphoreHydrogen = new Semaphore(2); // hydrogen semaphore initialized to 2 permits, since we need 2 H for every O
5    private Semaphore semaphoreOxygen = new Semaphore(0); // oxygen semaphore initialized with 0 permits, will be released by hydrogen
6
7    public H2O() {
8        // Constructor for H2O, nothing needed here since semaphores are initialized above
9    }
10
11    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
12        // Acquire a permit for releasing a hydrogen atom
13        semaphoreHydrogen.acquire();
14        // releaseHydrogen.run() outputs "H"
15        releaseHydrogen.run();
16        // Release a permit for oxygen, signaling that one H has been released
17        semaphoreOxygen.release();
18    }
19
20    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
21        // Acquire two permits for releasing an oxygen atom as we need two hydrogen atoms before releasing one oxygen atom
22        semaphoreOxygen.acquire(2);
23        // releaseOxygen.run() outputs "O"
24        releaseOxygen.run();
25        // Release two permits for hydrogen, allowing the release of two hydrogen atoms
26        semaphoreHydrogen.release(2);
27    }
28}
29
1#include <semaphore.h>
2#include <functional>
3
4class H2O {
5private:
6    sem_t semH; // Semaphore for hydrogen
7    sem_t semO; // Semaphore for oxygen
8    int hydrogenCount; // Count the number of hydrogens produced
9
10public:
11    H2O() : hydrogenCount(0) {
12        sem_init(&semH, 0, 2); // Initialize the semaphore for hydrogen to 2, allowing 2 hydrogens to be produced
13        sem_init(&semO, 0, 0); // Initialize the semaphore for oxygen to 0, blocking oxygen production until hydrogen is available
14    }
15
16    void hydrogen(std::function<void()> releaseHydrogen) {
17        sem_wait(&semH); // Decrement the semaphore for hydrogen, blocking if unavailable
18        // releaseHydrogen() outputs "H". Do not change or remove this line.
19        releaseHydrogen();
20        ++hydrogenCount; // Increment the count of produced hydrogen atoms
21        if (hydrogenCount == 2) { // If 2 hydrogens are produced, an oxygen may be produced
22            sem_post(&semO); // Increment the semaphore for oxygen, allowing an oxygen to be produced
23        }
24    }
25
26    void oxygen(std::function<void()> releaseOxygen) {
27        sem_wait(&semO); // Decrement the semaphore for oxygen, blocking if unavailable
28        // releaseOxygen() outputs "O". Do not change or remove this line.
29        releaseOxygen();
30        hydrogenCount = 0; // Reset the count of produced hydrogen atoms
31        sem_post(&semH); // Increment the semaphore for hydrogen, allowing another hydrogen to be produced
32        sem_post(&semH); // Allow the second hydrogen to be produced
33    }
34};
35
1// Importing necessary libraries for semaphore functionality
2const { Semaphore } = require('await-semaphore'); // Node.js library for semaphores, use 'npm install await-semaphore' to install
3
4// Creating semaphores for hydrogen and oxygen
5let semH: Semaphore = new Semaphore(2); // Semaphore for hydrogen, starts at 2 to allow 2 hydrogens
6let semO: Semaphore = new Semaphore(0); // Semaphore for oxygen starts at 0
7let hydrogenCount: number = 0;  // Counter for the number of hydrogen atoms produced
8
9// Function to simulate the release of a hydrogen atom
10async function hydrogen(releaseHydrogen: () => void): Promise<void> {
11    await semH.acquire(); // Acquire a hydrogen semaphore permit (decrement)
12    // releaseHydrogen() outputs "H". Do not change or remove this line.
13    releaseHydrogen();
14    hydrogenCount++; // Increment the hydrogen count
15
16    if (hydrogenCount === 2) {
17        // After 2 hydrogens, allow the release of an oxygen
18        semO.release(); // Release an oxygen semaphore permit (increment)
19    }
20}
21
22// Function to simulate the release of an oxygen atom
23async function oxygen(releaseOxygen: () => void): Promise<void> {
24    await semO.acquire(); // Acquire an oxygen semaphore permit (decrement)
25    // releaseOxygen() outputs "O". Do not change or remove this line.
26    releaseOxygen();
27    hydrogenCount = 0; // Reset the hydrogen counter
28
29    // Release two hydrogen semaphore permits (increment twice)
30    semH.release(); 
31    semH.release();
32}
33
34// Export the functions if this is being used as a module
35module.exports = { hydrogen, oxygen };
36
Not Sure What to Study? Take the 2-min Quiz：

Depth first search can be used to find whether two components in a graph are connected.

Time and Space Complexity

Time Complexity

The time complexity of both hydrogen and oxygen methods in the H2O class can be described as O(1). These methods involve a fixed number of operations: a semaphore acquire operation and a semaphore release operation. The semaphore operations themselves have a constant time complexity since they are essentially atomic operations that manage an internal counter.

Space Complexity

The space complexity of the H2O class is O(1). This is because the class maintains a constant number of semaphores with fixed space usage regardless of the number of invocations of the hydrogen and oxygen methods. No additional space that scales with the input size or the number of method calls is utilized.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫