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:

  1. Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
  2. Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
  3. Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
  4. 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)

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.

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;
        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();
            }
        }
    
    
  • from threading import Semaphore
    
    class FizzBuzz: # semaphore
        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(3, self.n + 1, 3):
                if i % 5 != 0:
                    self.fizzSemaphore.acquire()
                    printFizz()
                    self.numberSemaphore.release()
    
        # printBuzz() outputs "buzz"
        def buzz(self, printBuzz: 'Callable[[], None]') -> None:
            for i in range(5, self.n + 1, 5):
                if i % 3 != 0:
                    self.buzzSemaphore.acquire()
                    printBuzz()
                    self.numberSemaphore.release()
    
        # printFizzBuzz() outputs "fizzbuzz"
        def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
            for i in range(15, self.n + 1, 15):
                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: # lock
        def __init__(self, n: int):      
            self.n = n
            self.fizz_lock = threading.Lock()
            self.buzz_lock = threading.Lock()
            self.fizzbuzz_lock = threading.Lock()
            self.fizz_lock.acquire()
            self.buzz_lock.acquire()
            self.fizzbuzz_lock.acquire()
            self.main_lock = threading.Lock()
    
        def fizz(self, printFizz: 'Callable[[], None]') -> None:
            while True:
                self.fizz_lock.acquire()
                if self.n == 0 :
                    return
                printFizz()
                self.main_lock.release()
    
        def buzz(self, printBuzz: 'Callable[[], None]') -> None:
            while True:
                self.buzz_lock.acquire()
                if self.n == 0:
                    return
                printBuzz()
                self.main_lock.release()
    
        def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
            while True:
                self.fizzbuzz_lock.acquire()
                if self.n == 0:
                    return
                printFizzBuzz()
                self.main_lock.release()
    
        def number(self, printNumber: 'Callable[[int], None]') -> None:
            for i in range(1, self.n+1):
                self.main_lock.acquire()
                if i % 15 == 0:
                    self.fizzbuzz_lock.release()
                elif i % 3 == 0:
                    self.fizz_lock.release()
                elif i % 5 == 0:
                    self.buzz_lock.release()
                else:
                    printNumber(i)
                    self.main_lock.release()
    
            self.main_lock.acquire() 
            self.n = 0
            self.fizz_lock.release()
            self.buzz_lock.release()
            self.fizzbuzz_lock.release()
            return
    
    

All Problems

All Solutions