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

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();
                }
            }
        }
    }
}

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();
            }
        }
    }
}

All Problems

All Solutions