Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1195.html
Level
Medium
Description
Write a program that outputs the string representation of numbers from 1 to n, however:
- If the number is divisible by 3, output “fizz”.
- If the number is divisible by 5, output “buzz”.
- If the number is divisible by both 3 and 5, output “fizzbuzz”.
For example, for n = 15
, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz
.
Suppose you are given the following code:
class FizzBuzz {
public FizzBuzz(int n) { ... } // constructor
public void fizz(printFizz) { ... } // only output "fizz"
public void buzz(printBuzz) { ... } // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... } // only output "fizzbuzz"
public void number(printNumber) { ... } // only output the numbers
}
Implement a multithreaded version of FizzBuzz
with four threads. The same instance of FizzBuzz
will be passed to four different threads:
- Thread A will call
fizz()
to check for divisibility of 3 and outputsfizz
. - Thread B will call
buzz()
to check for divisibility of 5 and outputsbuzz
. - Thread C will call
fizzbuzz()
to check for divisibility of 3 and 5 and outputsfizzbuzz
. - Thread D will call
number()
which should only output the numbers.
Algorithm - synchronized keyword, or semaphores
Use keyword for block code acceess control synchronized (this)
Code
-
import java.util.function.IntConsumer; public class Fizz_Buzz_Multithreaded { class FizzBuzz { private int n; private int count; public FizzBuzz(int n) { this.n = n; this.count = 1; } // printFizz.run() outputs "fizz". public void fizz(Runnable printFizz) throws InterruptedException { while (count <= n) { synchronized (this) { while (count <= n && (count % 3 != 0 || count % 5 == 0)) { // only 3 will break while() wait(); } if (count <= n) { // get yes only when it's 3 printFizz.run(); } count++; notifyAll(); } } } // printBuzz.run() outputs "buzz". public void buzz(Runnable printBuzz) throws InterruptedException { while (count <= n) { synchronized (this) { while (count <= n && (count % 5 != 0 || count % 3 == 0)) { // only 5 will break while() wait(); } if (count <= n) { // get yes only when it's 5 printBuzz.run(); } count++; notifyAll(); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { while (count <= n) { synchronized (this) { while (count <= n && (count % 5 != 0 || count % 3 != 0)) { // only 15 will break while() wait(); } if (count <= n) { printFizzBuzz.run(); } count++; notifyAll(); } } } // printNumber.accept(x) outputs "x", where x is an integer. public void number(IntConsumer printNumber) throws InterruptedException { while (count <= n) { synchronized (this) { while (count <= n && (count % 5 == 0 || count % 3 == 0)) { wait(); } if (count <= n) { printNumber.accept(count); } count++; notifyAll(); } } } } } ############ class FizzBuzz { private int n; public FizzBuzz(int n) { this.n = n; } private Semaphore fSema = new Semaphore(0); private Semaphore bSema = new Semaphore(0); private Semaphore fbSema = new Semaphore(0); private Semaphore nSema = new Semaphore(1); // printFizz.run() outputs "fizz". public void fizz(Runnable printFizz) throws InterruptedException { for (int i = 3; i <= n; i = i + 3) { if (i % 5 != 0) { fSema.acquire(); printFizz.run(); nSema.release(); } } } // printBuzz.run() outputs "buzz". public void buzz(Runnable printBuzz) throws InterruptedException { for (int i = 5; i <= n; i = i + 5) { if (i % 3 != 0) { bSema.acquire(); printBuzz.run(); nSema.release(); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { for (int i = 15; i <= n; i = i + 15) { fbSema.acquire(); printFizzBuzz.run(); nSema.release(); } } // printNumber.accept(x) outputs "x", where x is an integer. public void number(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { nSema.acquire(); if (i % 3 == 0 && i % 5 == 0) { fbSema.release(); } else if (i % 3 == 0) { fSema.release(); } else if (i % 5 == 0) { bSema.release(); } else { printNumber.accept(i); nSema.release(); } } } }
Or, this problem can be solved using semaphores. In the class, create one semaphore. Also maintain an integer i
with keyword volatile
.
For the constructor, initialize i = 1
, and initialize the semaphore to have 1 permit.
For each method, create a loop. In the loop, first acquire a permit from the semaphore. If i > n
, break the loop. Otherwise, if i
meets the current condition, output the corresponding string or number and increase i
by 1. Then release a permit back to the semaphore. Use try-finally
block to avoid waiting infinitely.
-
class FizzBuzz { private int n; private volatile int i; private Semaphore semaphore; public FizzBuzz(int n) { this.n = n; this.i = 1; semaphore = new Semaphore(1); } // printFizz.run() outputs "fizz". public void fizz(Runnable printFizz) throws InterruptedException { while (i <= n) { semaphore.acquire(); try { if (i > n) break; if (i % 3 == 0 && i % 5 != 0) { printFizz.run(); i++; } } finally { semaphore.release(); } } } // printBuzz.run() outputs "buzz". public void buzz(Runnable printBuzz) throws InterruptedException { while (i <= n) { semaphore.acquire(); try { if (i > n) break; if (i % 3 != 0 && i % 5 == 0) { printBuzz.run(); i++; } } finally { semaphore.release(); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { while (i <= n) { semaphore.acquire(); try { if (i > n) break; if (i % 3 == 0 && i % 5 == 0) { printFizzBuzz.run(); i++; } } finally { semaphore.release(); } } } // printNumber.accept(x) outputs "x", where x is an integer. public void number(IntConsumer printNumber) throws InterruptedException { while (i <= n) { semaphore.acquire(); try { if (i > n) break; if (i % 3 != 0 && i % 5 != 0) { printNumber.accept(i); i++; } } finally { semaphore.release(); } } } } ############ class FizzBuzz { private int n; public FizzBuzz(int n) { this.n = n; } private Semaphore fSema = new Semaphore(0); private Semaphore bSema = new Semaphore(0); private Semaphore fbSema = new Semaphore(0); private Semaphore nSema = new Semaphore(1); // printFizz.run() outputs "fizz". public void fizz(Runnable printFizz) throws InterruptedException { for (int i = 3; i <= n; i = i + 3) { if (i % 5 != 0) { fSema.acquire(); printFizz.run(); nSema.release(); } } } // printBuzz.run() outputs "buzz". public void buzz(Runnable printBuzz) throws InterruptedException { for (int i = 5; i <= n; i = i + 5) { if (i % 3 != 0) { bSema.acquire(); printBuzz.run(); nSema.release(); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { for (int i = 15; i <= n; i = i + 15) { fbSema.acquire(); printFizzBuzz.run(); nSema.release(); } } // printNumber.accept(x) outputs "x", where x is an integer. public void number(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { nSema.acquire(); if (i % 3 == 0 && i % 5 == 0) { fbSema.release(); } else if (i % 3 == 0) { fSema.release(); } else if (i % 5 == 0) { bSema.release(); } else { printNumber.accept(i); nSema.release(); } } } }
-
private: int n; int count; mutex m; condition_variable cv; public: FizzBuzz(int n) { this->n = n; this->count = 1; } void fizz(function<void()> printFizz) { while (true) { unique_lock<mutex> lock(m); while (count <= n && (count % 3 != 0 || count % 5 == 0)) cv.wait(lock); if (count > n) return; printFizz(); ++count; cv.notify_all(); } } void buzz(function<void()> printBuzz) { while (true) { unique_lock<mutex> lock(m); while (count <= n && (count % 5 != 0 || count % 3 == 0)) cv.wait(lock); if (count > n) return; printBuzz(); ++count; cv.notify_all(); } } void fizzbuzz(function<void()> printFizzBuzz) { while (true) { unique_lock<mutex> lock(m); while (count <= n && (count % 5 != 0 || count % 3 != 0)) cv.wait(lock); if (count > n) return; printFizzBuzz(); ++count; cv.notify_all(); } } void number(function<void(int)> printNumber) { while (true) { unique_lock<mutex> lock(m); while (count <= n && (count % 5 == 0 || count % 3 == 0)) cv.wait(lock); if (count > n) return; printNumber(count++); cv.notify_all(); } }
-
# semaphore from threading import Semaphore class FizzBuzz: def __init__(self, n: int): self.n = n self.fizzSemaphore = Semaphore(0) self.buzzSemaphore = Semaphore(0) self.fizzbuzzSemaphore = Semaphore(0) self.numberSemaphore = Semaphore(1) # printFizz() outputs "fizz" def fizz(self, printFizz: 'Callable[[], None]') -> None: for i in range(1, self.n + 1): if i % 3 == 0 and i % 15 != 0: self.fizzSemaphore.acquire() printFizz() self.numberSemaphore.release() # printBuzz() outputs "buzz" def buzz(self, printBuzz: 'Callable[[], None]') -> None: for i in range(1, self.n + 1): if i % 5 == 0 and i % 15 != 0: self.buzzSemaphore.acquire() printBuzz() self.numberSemaphore.release() # printFizzBuzz() outputs "fizzbuzz" def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None: for i in range(1, self.n + 1): if i % 15 == 0: self.fizzbuzzSemaphore.acquire() printFizzBuzz() self.numberSemaphore.release() # printNumber(x) outputs "x", where x is an integer. def number(self, printNumber: 'Callable[[int], None]') -> None: for i in range(1, self.n + 1): self.numberSemaphore.acquire() if i % 15 == 0: self.fizzbuzzSemaphore.release() elif i % 3 == 0: self.fizzSemaphore.release() elif i % 5 == 0: self.buzzSemaphore.release() else: printNumber(i) self.numberSemaphore.release() ########## # ref: https://leetcode.com/problems/fizz-buzz-multithreaded/discuss/542960/python-greater99.28-a-standard-Lock()-based-solution-with-detailed-explanation import threading class FizzBuzz: def __init__(self, n: int): self.n = n self.f = threading.Lock() self.b = threading.Lock() self.fb = threading.Lock() self.f.acquire() self.b.acquire() self.fb.acquire() self.main = threading.Lock() # printFizz() outputs "fizz" def fizz(self, printFizz: 'Callable[[], None]') -> None: while True: self.f.acquire() if self.n == 0 : return printFizz() self.main.release() # printBuzz() outputs "buzz" def buzz(self, printBuzz: 'Callable[[], None]') -> None: while True: self.b.acquire() if self.n == 0: return printBuzz() self.main.release() # printFizzBuzz() outputs "fizzbuzz" def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None: while True: self.fb.acquire() if self.n == 0: return printFizzBuzz() self.main.release() # printNumber(x) outputs "x", where x is an integer. def number(self, printNumber: 'Callable[[int], None]') -> None: for i in range(1, self.n+1): #print("number:",i) self.main.acquire() if i % 15 == 0: self.fb.release() elif i % 3 == 0: self.f.release() elif i % 5 == 0: self.b.release() else: printNumber(i) self.main.release() self.main.acquire() self.n = 0 self.f.release() self.b.release() self.fb.release() return