1195. Fizz Buzz Multithreaded

MediumConcurrency
Leetcode Link

Problem Description

This problem is a multi-threading challenge that simulates a classic programming task known as "FizzBuzz". The task is to print a sequence of numbers from 1 to n but for multiples of 3, print "fizz" instead of the number, for multiples of 5 print "buzz", for numbers which are multiples of both 3 and 5 print "fizzbuzz", and for all other numbers, print the number itself.

However, the twist here is that there are four separate threads, each responsible for printing a specific part of the sequence - one for "fizz", one for "buzz", one for "fizzbuzz", and one for the numeric values that don't meet the other criteria.

The class FizzBuzz has four methods that correspond to the output they should produce: fizz(), buzz(), fizzbuzz(), and number(). Each of these methods is meant to be called by a different thread. The methods take a Runnable or IntConsumer as an argument, which are functional interfaces provided by Java; these should be executed to perform the actual printing.

The problem is to implement the FizzBuzz class such that each thread correctly outputs its part of the sequence, respecting the order of the numbers in the sequence from 1 to n.

Intuition

The intuition behind the provided solution is to use concurrency mechanisms to coordinate the work of the four threads. Since each thread is responsible for a unique part of the FizzBuzz pattern, we need to ensure they execute in the correct order and only when it is their turn to produce output. To achieve this, we use semaphores, which are synchronization aids that can control access to shared resources.

Semaphores work like counters that can be increased (release) or decreased (acquire). A semaphore with a count of 0 blocks any thread that tries to acquire it until another thread release it and increases its count.

In this solution, we're using a semaphore for each of the fizz, buzz, fizzbuzz, and number actions. The semaphore for numbers (nSema) is initially available (with a count of 1), allowing the number thread to proceed. The other semaphores start with a count of 0 (unavailable), preventing the fizz, buzz, and fizzbuzz threads from proceeding until they are allowed to do so by the logic in the number method.

The number method controls the flow of the program by acquiring the nSema semaphore to begin its operation. Whenever it encounters a number that requires the action of another thread, it releases the corresponding semaphore (fSema, bSema, or fbSema), thus allowing the correct thread to print its output. Once that thread has executed its print operation, the number thread is allowed to continue by releasing the nSema semaphore again.

The fizz, buzz, and fizzbuzz methods work in a loop that only considers numbers they are responsible for. They wait (acquire) for their respective semaphore to be available to print their output, and once they have done so, they signal (release) the number method to continue.

By carefully coordinating the release and acquisition of these semaphores, each thread does its job in the correct sequence, and the overall sequence of "fizz", "buzz", "fizzbuzz", and the respective numbers is maintained.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Solution Approach

The solution approach utilizes Java's concurrency tools to manage the synchronization of multiple threads. Let's walk through the implementation and the patterns used:

  1. Semaphores: To coordinate the execution between the four threads, the code uses four semaphores. Semaphores are initialized with a number of permits that threads can acquire, which acts as a counter indicating how many times an action can be performed without blocking. In this case, the nSema starts with a permit count of 1, because the number thread should run first. The semaphores for fizz, buzz, and fizzbuzz start off with 0 permits because these actions are conditionally based on the value of i.

  2. Initialization: The FizzBuzz class is initialized with an integer n which represents the length of the sequence that should be printed.

  3. Looping and Conditions: Each method responsible for outputting "fizz", "buzz", "fizzbuzz", or numbers implements a loop that iterates through the range of values from 1 to n. However, each loop has its own specific conditions:

    • fizz: Increments i by 3, only enters the block if i is not divisible by 5.
    • buzz: Increments i by 5, only enters the block if i is not divisible by 3.
    • fizzbuzz: Increments i by 15, enters the block for numbers divisible by both 3 and 5.
    • number: Increments i by 1, handles all numbers, applying the correct action based on divisibility rules.

  4. Synchronization: Each method must wait for the correct time to perform its action. They use acquire to wait for the semaphore's permit:

    • fizz: Waits for the fSema semaphore before printing.
    • buzz: Waits for the bSema semaphore before printing.
    • fizzbuzz: Waits for the fbSema semaphore before printing.
    • number: Always tries to acquire the nSema semaphore since it runs first, then releases the appropriate semaphore for the next action based on the divisibility of i.

When a method receives the semaphore's permit, it performs its action (calling the appropriate print method provided) and then releases the appropriate semaphore to signal the next action:

1- After printing "fizz", "buzz", or "fizzbuzz", the corresponding method releases the `nSema` semaphore to let the `number` method proceed.
2- The `number` method decides which semaphore to release based on the divisibility logic, or if the number is not divisible by 3 or 5, it prints the number itself and then releases `nSema` again for the next number.

By using these semaphores, the program ensures that the threads run in order without overlapping and respect the sequence rules for the FizzBuzz game.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Example Walkthrough

Let's illustrate the solution approach using a small example where n is 5. This means our sequence consists of the numbers from 1 to 5. We will walk through the flow of the program using threads that are synchronized using semaphores.

Suppose we start with the following semaphore permits:

  • nSema: 1 permit because the number thread should run first.
  • fSema: 0 permits initially, for "fizz" output.
  • bSema: 0 permits initially, for "buzz" output.
  • fbSema: 0 permits initially, for "fizzbuzz" output.

Here's how the flow of the program might look like:

  1. Number Thread: Starts and is the first to run because nSema has 1 permit. It acquires the permit and starts processing numbers. Since i = 1 is not divisible by 3 or 5, it prints 1 and releases nSema permit, allowing itself to proceed to the next number.

  2. Number Thread: Now with i = 2, the same process occurs: prints 2, then releases the nSema permit.

  3. Number Thread: When i = 3, the thread recognizes that this number is a multiple of 3. It doesn't print anything itself; instead, it releases the fSema permit and waits.

  4. Fizz Thread: The fizz thread has been blocked, waiting for the fSema semaphore. Now it acquires the permit, prints "fizz" for number 3, and then releases the nSema permit, signaling the number thread to continue.

  5. Number Thread: Moves to i = 4, prints 4 as it is not divisible by 3 or 5, releases the nSema permit to proceed with the next number.

  6. Number Thread: At i = 5, the thread identifies it as a multiple of 5. It releases bSema for the buzz thread and waits.

  7. Buzz Thread: The buzz thread was waiting for bSema. It acquires the permit, prints “buzz” for number 5, and releases the nSema permit for the number thread to continue with the sequence.

  8. Number Thread: Since we have reached n = 5, there are no more numbers to process, and the program concludes the sequence.

This example demonstrates how the threads work collaboratively, ensuring the FizzBuzz rules are followed and output is printed in the correct sequence. Each thread is precisely timed by the semaphores to print its corresponding value at the right time, leading to synchronization among threads to fulfill the task.

Solution Implementation

1from threading import Lock
2from typing import Callable
3
4class FizzBuzz:
5    def __init__(self, n: int):
6        # Initialize the maximum number and set the current counter to 1
7        self.current = 1
8        self.max_number = n
9        self.lock = Lock()  # Initialize the lock for thread safety
10
11    def fizz(self, print_fizz: Callable[[], None]) -> None:
12        # Output "fizz" for multiples of 3 that are not multiples of 5
13        while self.current <= self.max_number:
14            with self.lock:  # Acquire the lock to ensure thread safety
15                if self.current % 3 == 0 and self.current % 5 != 0:
16                    print_fizz()
17                    self.current += 1
18
19    def buzz(self, print_buzz: Callable[[], None]) -> None:
20        # Output "buzz" for multiples of 5 that are not multiples of 3
21        while self.current <= self.max_number:
22            with self.lock:  # Acquire the lock
23                if self.current % 5 == 0 and self.current % 3 != 0:
24                    print_buzz()
25                    self.current += 1
26
27    def fizzbuzz(self, print_fizzbuzz: Callable[[], None]) -> None:
28        # Output "fizzbuzz" for numbers that are multiples of both 3 and 5
29        while self.current <= self.max_number:
30            with self.lock:  # Acquire the lock
31                if self.current % 15 == 0:
32                    print_fizzbuzz()
33                    self.current += 1
34
35    def number(self, print_number: Callable[[int], None]) -> None:
36        # Output the integer number that is neither a multiple of 3 nor 5
37        while self.current <= self.max_number:
38            with self.lock:  # Acquire the lock
39                if self.current % 3 != 0 and self.current % 5 != 0:
40                    print_number(self.current)
41                    self.current += 1
42
1import java.util.concurrent.Semaphore;
2import java.util.function.IntConsumer;
3
4class FizzBuzz {
5    private int n;
6  
7    // Semaphores to control the execution flow for each type of print operation
8    private Semaphore fizzSemaphore = new Semaphore(0);
9    private Semaphore buzzSemaphore = new Semaphore(0);
10    private Semaphore fizzBuzzSemaphore = new Semaphore(0);
11    private Semaphore numberSemaphore = new Semaphore(1);
12
13    // Constructor that sets the number up to which FizzBuzz should run
14    public FizzBuzz(int n) {
15        this.n = n;
16    }
17
18    // Method to print "fizz" for numbers divisible by 3 and not by 5
19    public void fizz(Runnable printFizz) throws InterruptedException {
20        for (int i = 3; i <= n; i += 3) {
21            if (i % 5 != 0) { // Skip multiples of 5
22                fizzSemaphore.acquire();
23                printFizz.run();
24                numberSemaphore.release();
25            }
26        }
27    }
28
29    // Method to print "buzz" for numbers divisible by 5 and not by 3
30    public void buzz(Runnable printBuzz) throws InterruptedException {
31        for (int i = 5; i <= n; i += 5) {
32            if (i % 3 != 0) { // Skip multiples of 3
33                buzzSemaphore.acquire();
34                printBuzz.run();
35                numberSemaphore.release();
36            }
37        }
38    }
39
40    // Method to print "fizzbuzz" for numbers divisible by both 3 and 5
41    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
42        for (int i = 15; i <= n; i += 15) {
43            fizzBuzzSemaphore.acquire();
44            printFizzBuzz.run();
45            numberSemaphore.release();
46        }
47    }
48
49    // Method to print the number if it's not divisible by 3 or 5
50    public void number(IntConsumer printNumber) throws InterruptedException {
51        for (int i = 1; i <= n; i++) {
52            numberSemaphore.acquire();
53            if (i % 3 == 0 && i % 5 == 0) {
54                fizzBuzzSemaphore.release();
55            } else if (i % 3 == 0) {
56                fizzSemaphore.release();
57            } else if (i % 5 == 0) {
58                buzzSemaphore.release();
59            } else {
60                printNumber.accept(i);
61                numberSemaphore.release();
62            }
63        }
64    }
65}
66
1#include <functional>
2#include <mutex>
3#include <atomic>
4
5class FizzBuzz {
6private:
7    std::mutex mtx;              // mutex for synchronizing access to shared resources
8    std::atomic<int> current;    // atomic counter to ensure operation atomicity
9    int maxNumber;               // the number up to which the game will be played
10
11public:
12    FizzBuzz(int n) : maxNumber(n), current(1) {
13        // Constructor initializes the max number and sets the current counter to 1
14    }
15
16    // printFizz() outputs "fizz" for multiples of 3 that are not multiples of 5.
17    void fizz(std::function<void()> printFizz) {
18        while (current <= maxNumber) {
19            std::lock_guard<std::mutex> lock(mtx); // Lock the mutex to ensure thread safety
20            if (current % 3 == 0 && current % 5 != 0 && current <= maxNumber) {
21                printFizz();
22                current++;
23            }
24        }
25    }
26
27    // printBuzz() outputs "buzz" for multiples of 5 that are not multiples of 3.
28    void buzz(std::function<void()> printBuzz) {
29        while (current <= maxNumber) {
30            std::lock_guard<std::mutex> lock(mtx); // Lock the mutex
31            if (current % 5 == 0 && current % 3 != 0 && current <= maxNumber) {
32                printBuzz();
33                current++;
34            }
35        }
36    }
37
38    // printFizzBuzz() outputs "fizzbuzz" for numbers that are multiples of both 3 and 5.
39    void fizzbuzz(std::function<void()> printFizzBuzz) {
40        while (current <= maxNumber) {
41            std::lock_guard<std::mutex> lock(mtx); // Lock the mutex
42            if (current % 15 == 0 && current <= maxNumber) {
43                printFizzBuzz();
44                current++;
45            }
46        }
47    }
48
49    // printNumber(x) outputs "x", where x is an integer that is neither multiple of 3 nor 5.
50    void number(std::function<void(int)> printNumber) {
51        while (current <= maxNumber) {
52            std::lock_guard<std::mutex> lock(mtx); // Lock the mutex
53            if (current % 3 != 0 && current % 5 != 0 && current <= maxNumber) {
54                printNumber(current);
55                current++;
56            }
57        }
58    }
59};
60
1// Import the required modules
2import { Mutex } from 'async-mutex';
3import { atomically } from 'atomic-fns';
4
5// Create a mutex for synchronizing access to shared resources.
6const lock = new Mutex();
7// Create an atomic counter to ensure operation atomicity.
8let current: number = 1;
9// Initialize a variable to hold the maximum number up to which the game will be played.
10let maxNumber: number;
11
12// Assign a maximum number to maxNumber and set the current counter to 1.
13const initialize = (n: number): void => {
14    maxNumber = n;
15    current = 1;
16};
17
18// Print "fizz" for multiples of 3 that are not multiples of 5.
19const fizz = async (printFizz: () => void): Promise<void> => {
20    while (current <= maxNumber) {
21        await lock.runExclusive(async () => {
22            if (current % 3 === 0 && current % 5 !== 0) {
23                printFizz();
24                current++;
25            }
26        });
27    }
28};
29
30// Print "buzz" for multiples of 5 that are not multiples of 3.
31const buzz = async (printBuzz: () => void): Promise<void> => {
32    while (current <= maxNumber) {
33        await lock.runExclusive(async () => {
34            if (current % 5 === 0 && current % 3 !== 0) {
35                printBuzz();
36                current++;
37            }
38        });
39    }
40};
41
42// Print "fizzbuzz" for numbers that are multiples of both 3 and 5.
43const fizzbuzz = async (printFizzBuzz: () => void): Promise<void> => {
44    while (current <= maxNumber) {
45        await lock.runExclusive(async () => {
46            if (current % 15 === 0) {
47                printFizzBuzz();
48                current++;
49            }
50        });
51    }
52};
53
54// Print the number itself if it's neither a multiple of 3 nor 5.
55const number = async (printNumber: (n: number) => void): Promise<void> => {
56    while (current <= maxNumber) {
57        await lock.runExclusive(async () => {
58            if (current % 3 !== 0 && current % 5 !== 0) {
59                printNumber(current);
60                current++;
61            }
62        });
63    }
64};
65
Not Sure What to Study? Take the 2-min Quiz：

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Time and Space Complexity

Time Complexity:

The time complexity of the FizzBuzz class methods depends on the value of n.

  • The number() method is called n times.

  • The fizz() method is called at most n/3 times because every third number is potentially divisible by 3. But it checks i % 5 != 0 in its loop, meaning not all n/3 calls will result in execution of the printFizz() method. It will only execute when the number is not divisible by 5, essentially n/3 - n/15 times.

  • The buzz() method is called at most n/5 times because every fifth number is potentially divisible by 5, but same as fizz(), it will only execute when the number is not divisible by 3, so n/5 - n/15 times.

  • The fizzbuzz() method is called at most n/15 times because it only executes when the number is divisible by both 3 and 5.

Since all of these method calls are dependent on n and they operate in parallel (assuming this is being run by multiple threads), the overall time complexity is O(n).

Space Complexity:

The space complexity of the FizzBuzz class is essentially O(1). This is because the space used does not scale with the value of n. It uses four semaphores (which can be considered of constant size) and integer variables for loop control. The memory footprint of the class does not depend on how large n is, assuming we are not counting the stack frames of the method calls themselves which will be hidden by the OS's threading mechanism.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫