{"id":5579,"date":"2019-09-22T03:53:38","date_gmt":"2019-09-22T10:53:38","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5579"},"modified":"2019-09-22T03:53:48","modified_gmt":"2019-09-22T10:53:48","slug":"leetcode-1195-fizz-buzz-multithreaded","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/concurrent\/leetcode-1195-fizz-buzz-multithreaded\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1195. Fizz Buzz Multithreaded"},"content":{"rendered":"\n<p>Write a program that outputs the string representation of numbers from 1 to&nbsp;<em>n<\/em>, however:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>If the number is divisible by 3, output &#8220;fizz&#8221;.<\/li><li>If the number is divisible by 5, output&nbsp;&#8220;buzz&#8221;.<\/li><li>If the number is divisible by both 3 and 5, output&nbsp;&#8220;fizzbuzz&#8221;.<\/li><\/ul>\n\n\n\n<p>For example, for&nbsp;<code>n = 15<\/code>, we output:&nbsp;<code>1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz<\/code>.<\/p>\n\n\n\n<p>Suppose you are given the following code:<\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\">class FizzBuzz {\n&nbsp; public FizzBuzz(int n) { ... }&nbsp;              \/\/ constructor\n  public void fizz(printFizz) { ... }          \/\/ only output \"fizz\"\n  public void buzz(printBuzz) { ... }          \/\/ only output \"buzz\"\n  public void fizzbuzz(printFizzBuzz) { ... }  \/\/ only output \"fizzbuzz\"\n  public void number(printNumber) { ... }      \/\/ only output the numbers\n}<\/pre>\n\n\n\n<p>Implement a multithreaded version of&nbsp;<code>FizzBuzz<\/code>&nbsp;with&nbsp;<strong>four<\/strong>&nbsp;threads. The same instance of&nbsp;<code>FizzBuzz<\/code>&nbsp;will be passed to four different threads:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>Thread A will call&nbsp;<code>fizz()<\/code>&nbsp;to check for divisibility of 3 and outputs&nbsp;<code>fizz<\/code>.<\/li><li>Thread B will call&nbsp;<code>buzz()<\/code>&nbsp;to check for divisibility of 5 and outputs&nbsp;<code>buzz<\/code>.<\/li><li>Thread C will call&nbsp;<code>fizzbuzz()<\/code>&nbsp;to check for divisibility of 3 and 5 and outputs&nbsp;<code>fizzbuzz<\/code>.<\/li><li>Thread D will call&nbsp;<code>number()<\/code>&nbsp;which should only output the numbers.<\/li><\/ol>\n\n\n\n<p><strong>Solution:<\/strong><\/p>\n\n\n\n<p>4 Semaphores <\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Semaphore {\npublic:\n  Semaphore (int count = 0): count_(count) {}\n\n  inline void notify() {\n    unique_lock<std::mutex> lock(mtx_);\n    count_++;\n    cv_.notify_one();\n  }\n\n  inline void wait() {\n    unique_lock<std::mutex> lock(mtx_);\n    while (count_ == 0) cv_.wait(lock);\n    count_--;\n  }\n\nprivate:\n  mutex mtx_;\n  condition_variable cv_;\n  int count_;\n};\n\nclass FizzBuzz {\nprivate:\n  int n;\n  Semaphore sn;\n  Semaphore s3;\n  Semaphore s5;\n  Semaphore s15;\n  \n\npublic:\n  FizzBuzz(int n): n(n), sn(1), s3(0), s5(0), s15(0) {}\n  \n  void fizz(function<void()> printFizz) {\n    for (int i = 3; i <= n; i += 3) {\n      if (i % 5 == 0) continue;\n      s3.wait();\n      printFizz();      \n      sn.notify();\n    }\n  }\n  \n  void buzz(function<void()> printBuzz) {\n    for (int i = 5; i <= n; i += 5) {\n      if (i % 3 == 0) continue;\n      s5.wait();\n      printBuzz();      \n      sn.notify();\n    }\n  }\n  \n  void fizzbuzz(function<void()> printFizzBuzz) {\n    for (int i = 15; i <= n; i += 15) {\n      s15.wait();\n      printFizzBuzz();      \n      sn.notify();\n    }\n  }\n\n  void number(function<void(int)> printNumber) {\n    for (int i = 1; i <= n; ++i)\n      if (i % 15 == 0) { s15.notify(); sn.wait(); }\n      else if (i % 5 == 0) { s5.notify(); sn.wait(); }\n      else if (i % 3 == 0) { s3.notify(); sn.wait(); }\n      else { printNumber(i); }    \n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Write a program that outputs the string representation of numbers from 1 to&nbsp;n, however: If the number is divisible by 3, output &#8220;fizz&#8221;. If the&#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,177,481],"class_list":["post-5579","post","type-post","status-publish","format-standard","hentry","category-concurrent","tag-concurrent","tag-medium","tag-multithreading","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5579","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=5579"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5579\/revisions"}],"predecessor-version":[{"id":5581,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5579\/revisions\/5581"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5579"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5579"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5579"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}