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)

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
    
    

All Problems

All Solutions