Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1117.html
1117. Building H2O
Level
Medium
Description
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 be able to 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 has to wait for two hydrogen threads.
- If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.
We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that bond 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.
Example 1:
Input: “HOH”
Output: “HHO”
Explanation: “HOH” and “OHH” are also valid answers.
Example 2:
Input: “OOHHHH”
Output: “HHOHHO”
Explanation: “HOHHHO”, “OHHHHO”, “HHOHOH”, “HOHHOH”, “OHHHOH”, “HHOOHH”, “HOHOHH” and “OHHOHH” are also valid answers.
Constraints:
- Total length of input string will be 3n, where 1 ≤ n ≤ 20.
- Total number of
H
will be 2n in the input string. - Total number of
O
will be n in the input string.
Solution
This problem can be solved using semaphores. In the class, create two semaphores semaphoreHydrogen
and semaphoreOxygen
for methods hydrogen()
and oxygen()
respectively. Initially, semaphoreHydrogen
has 2 permits, while semaphoreOxygen
has 0 permits.
For method hydrogen
, acquire a permit from semaphoreHydrogen
, call releaseHydrogen.run()
and release a permit back to semaphoreOxygen
.
For method oxygen
, adquire two permits from semaphoreOxygen
, call releaseOxygen.run()
and release two permits back to semaphoreHydrogen
.
-
import java.util.concurrent.Semaphore; public class Building_H2O { class H2O { Semaphore h, o; public H2O() { // fair {@code true} if this semaphore will guarantee first-in first-out h = new Semaphore(2, true); o = new Semaphore(0, true); } public void hydrogen(Runnable releaseHydrogen) throws InterruptedException { h.acquire(); releaseHydrogen.run(); o.release(); // can release multiple o-semaphore } public void oxygen(Runnable releaseOxygen) throws InterruptedException { o.acquire(2); // met only when hydrogen generated 2 times releaseOxygen.run(); h.release(2); } } } ############ class H2O { private Semaphore h = new Semaphore(2); private Semaphore o = new Semaphore(0); public H2O() { } public void hydrogen(Runnable releaseHydrogen) throws InterruptedException { // releaseHydrogen.run() outputs "H". Do not change or remove this line. h.acquire(); releaseHydrogen.run(); o.release(); } public void oxygen(Runnable releaseOxygen) throws InterruptedException { // releaseOxygen.run() outputs "O". Do not change or remove this line. o.acquire(2); releaseOxygen.run(); h.release(2); } }
-
class H2O { private: int n_h; mutex m_h, m_o; public: H2O() { m_o.lock(); n_h = 2; } void hydrogen(function<void()> releaseHydrogen) { m_h.lock(); releaseHydrogen(); n_h--; if (n_h > 0) m_h.unlock(); else m_o.unlock(); } void oxygen(function<void()> releaseOxygen) { m_o.lock(); releaseOxygen(); n_h = 2; m_h.unlock(); } };
-
from threading import Semaphore class H2O: def __init__(self): self.h = Semaphore(2) self.o = Semaphore(0) def hydrogen(self, releaseHydrogen: "Callable[[], None]") -> None: self.h.acquire() # releaseHydrogen() outputs "H". Do not change or remove this line. releaseHydrogen() if self.h._value == 0: self.o.release() def oxygen(self, releaseOxygen: "Callable[[], None]") -> None: self.o.acquire() # releaseOxygen() outputs "O". Do not change or remove this line. releaseOxygen() self.h.release(2)