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