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

Java

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

1195 - Fizz Buzz Multithreaded

Level

Description

Algorithm - synchronized keyword, or semaphores

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Level

Description

Algorithm - synchronized keyword, or semaphores

Code

All Problems

All Solutions