{"id":5354,"date":"2019-07-25T09:34:24","date_gmt":"2019-07-25T16:34:24","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5354"},"modified":"2019-07-25T09:34:32","modified_gmt":"2019-07-25T16:34:32","slug":"leetcode-1117-building-h2o","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/concurrent\/leetcode-1117-building-h2o\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1117. Building H2O"},"content":{"rendered":"\n<p>There are two kinds of threads,&nbsp;<code>oxygen<\/code>&nbsp;and&nbsp;<code>hydrogen<\/code>. Your goal is to group these threads to form water molecules.&nbsp;There is a barrier where each thread has to&nbsp;wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given a&nbsp;<code>releaseHydrogen<\/code>&nbsp;and&nbsp;<code>releaseOxygen<\/code>&nbsp;method respectfully, 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.&nbsp;You must guarantee that all the threads from one molecule bond&nbsp;<em>before<\/em>&nbsp;any other threads from the next molecule do.<\/p>\n\n\n\n<p>In other words:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.<\/li><li>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.<\/li><\/ul>\n\n\n\n<p>We don\u2019t 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.<\/p>\n\n\n\n<p>Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input: <\/strong>\"HOH\"\n<strong>Output: <\/strong>\"HHO\"\n<strong>Explanation:<\/strong> \"HOH\" and \"OHH\" are also valid answers.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted; crayon:false\"><strong>Input: <\/strong>\"OOHHHH\"\n<strong>Output: <\/strong>\"HHOHHO\"\n<strong>Explanation:<\/strong> \"HOHHHO\", \"OHHHHO\", \"HHOHOH\", \"HOHHOH\", \"OHHHOH\", \"HHOOHH\", \"HOHOHH\" and \"OHHOHH\" are also valid answers.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Total length of input string will be 3<em>n<\/em>, where 1 \u2264&nbsp;<em>n<\/em>&nbsp;\u2264 30.<\/li><li>Total number of&nbsp;<code>H<\/code>&nbsp;will be 2<em>n<\/em>&nbsp;in the input string.<\/li><li>Total number of&nbsp;<code>O<\/code>&nbsp;will&nbsp;be&nbsp;<em>n<\/em>&nbsp;in the input&nbsp;string.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Semaphore<\/strong><\/h2>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Semaphore {\npublic:\n    Semaphore(int s) : s_(s) {}\n\n    void P(int d = 1) {\n      unique_lock<mutex> lock(m_);\n      while (s_ < d) {\n        cv_.wait(lock);\n      }\n      s_ -= d;\n    }\n  \n    void V(int d = 1) {      \n      unique_lock<mutex> lock(m_);\n      s_ += d;      \n      cv_.notify_all();\n    }\nprivate:\n  mutex m_;\n  condition_variable cv_;\n  int s_;\n};\n\nclass H2O {\npublic:\n    H2O():s_h_(2), s_o_(2) {  }\n\n    void hydrogen(function<void()> releaseHydrogen) {      \n      s_h_.P();\n      releaseHydrogen();\n      s_o_.V();\n    }\n\n    void oxygen(function<void()> releaseOxygen) {\n      s_o_.P(2);      \n      releaseOxygen();\n      s_h_.V(2);\n    }\nprivate:\n  Semaphore s_h_;\n  Semaphore s_o_;\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are two kinds of threads,&nbsp;oxygen&nbsp;and&nbsp;hydrogen. Your goal is to group these threads to form water molecules.&nbsp;There is a barrier where each thread has to&nbsp;wait&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[478],"tags":[479,217,485,486],"class_list":["post-5354","post","type-post","status-publish","format-standard","hentry","category-concurrent","tag-concurrent","tag-hard","tag-semaphore","tag-thread","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5354","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5354"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5354\/revisions"}],"predecessor-version":[{"id":5356,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5354\/revisions\/5356"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}