Building H2O

Problem

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. Hydrogen and oxygen threads will be given releaseHydrogen and releaseOxygen methods respectively, which will allow them to pass the barrier. These 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.

We do not have to worry about matching the threads up explicitly; the threads do not necessarily know which other threads they are paired up with. The key is that threads pass the barriers in complete sets; thus, if we examine the sequence of threads that bind and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Examples

Example 1

1
2
3


Input: water = "HOH"
Output: "HHO"
Explanation: "HOH" and "OHH" are also valid answers.

Example 2

1
2
3


Input: water = "OOHHHH"
Output: "HHOHHO"
Explanation: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" and "OHHOHH" are also valid answers.

Constraints

3 * n == water.length
1 <= n <= 20
water[i] is either 'H' or 'O'.
There will be exactly 2 * n 'H' in water.
There will be exactly n 'O' in water.

Solution

Method 1 – Semaphore and Barrier Synchronization

Intuition: We need to ensure that exactly two hydrogen threads and one oxygen thread bond together to form a water molecule, and that no thread from the next molecule bonds before the current molecule is complete. This can be achieved using semaphores to control the number of hydrogens and oxygens, and a barrier to synchronize the threads.

Approach:

Use two semaphores: one for hydrogen (initial value 2) and one for oxygen (initial value 1).
Each hydrogen thread acquires the hydrogen semaphore before proceeding, and each oxygen thread acquires the oxygen semaphore.
Use a barrier (cyclic barrier or countdown latch) to ensure that exactly three threads (2H + 1O) proceed together.
After bonding, release the semaphores so the next group can proceed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <semaphore.h>
#include <thread>
#include <functional>
#include <barrier>

class H2O {
    std::counting_semaphore<2> h{2};
    std::counting_semaphore<1> o{1};
    std::barrier<> barrier{3};
public:
    H2O() {}
    void hydrogen(std::function<void()> releaseHydrogen) {
        h.acquire();
        barrier.arrive_and_wait();
        releaseHydrogen();
        h.release();
    }
    void oxygen(std::function<void()> releaseOxygen) {
        o.acquire();
        barrier.arrive_and_wait();
        releaseOxygen();
        o.release();
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


import (
    "sync"
)

type H2O struct {
    h, o chan struct{}
    barrier *sync.WaitGroup
}

func NewH2O() *H2O {
    return &H2O{
        h: make(chan struct{}, 2),
        o: make(chan struct{}, 1),
        barrier: &sync.WaitGroup{},
    }
}

func (h2o *H2O) Hydrogen(releaseHydrogen func()) {
    h2o.h <- struct{}{}
    h2o.barrier.Add(1)
    if len(h2o.h) == 2 && len(h2o.o) == 1 {
        h2o.barrier.Wait()
    }
    releaseHydrogen()
    <-h2o.h
}

func (h2o *H2O) Oxygen(releaseOxygen func()) {
    h2o.o <- struct{}{}
    h2o.barrier.Add(1)
    if len(h2o.h) == 2 && len(h2o.o) == 1 {
        h2o.barrier.Wait()
    }
    releaseOxygen()
    <-h2o.o
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import java.util.concurrent.Semaphore;
import java.util.concurrent.CyclicBarrier;

class H2O {
    private Semaphore h = new Semaphore(2);
    private Semaphore o = new Semaphore(1);
    private CyclicBarrier barrier = new CyclicBarrier(3);

    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        h.acquire();
        try {
            barrier.await();
            releaseHydrogen.run();
        } catch (Exception e) {} 
        h.release();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        o.acquire();
        try {
            barrier.await();
            releaseOxygen.run();
        } catch (Exception e) {} 
        o.release();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import java.util.concurrent.Semaphore
import java.util.concurrent.CyclicBarrier

class H2O {
    private val h = Semaphore(2)
    private val o = Semaphore(1)
    private val barrier = CyclicBarrier(3)

    fun hydrogen(releaseHydrogen: () -> Unit) {
        h.acquire()
        try {
            barrier.await()
            releaseHydrogen()
        } finally {
            h.release()
        }
    }

    fun oxygen(releaseOxygen: () -> Unit) {
        o.acquire()
        try {
            barrier.await()
            releaseOxygen()
        } finally {
            o.release()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from threading import Semaphore, Barrier

class H2O:
    def __init__(self):
        self.h = Semaphore(2)
        self.o = Semaphore(1)
        self.barrier = Barrier(3)

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        self.h.acquire()
        self.barrier.wait()
        releaseHydrogen()
        self.h.release()

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        self.o.acquire()
        self.barrier.wait()
        releaseOxygen()
        self.o.release()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


use std::sync::{Arc, Barrier, Semaphore};

struct H2O {
    h: Arc<Semaphore>,
    o: Arc<Semaphore>,
    barrier: Arc<Barrier>,
}

impl H2O {
    fn new() -> Self {
        Self {
            h: Arc::new(Semaphore::new(2)),
            o: Arc::new(Semaphore::new(1)),
            barrier: Arc::new(Barrier::new(3)),
        }
    }
    fn hydrogen(&self, release_hydrogen: impl Fn()) {
        self.h.acquire();
        self.barrier.wait();
        release_hydrogen();
        self.h.release();
    }
    fn oxygen(&self, release_oxygen: impl Fn()) {
        self.o.acquire();
        self.barrier.wait();
        release_oxygen();
        self.o.release();
    }
}

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Semaphore and Barrier Synchronization#

Code#

Complexity#