1195. Fizz Buzz Multithreaded
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.
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:
-
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 thenumber
thread should run first. The semaphores forfizz
,buzz
, andfizzbuzz
start off with 0 permits because these actions are conditionally based on the value ofi
. -
Initialization: The
FizzBuzz
class is initialized with an integern
which represents the length of the sequence that should be printed. -
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
: Incrementsi
by 3, only enters the block ifi
is not divisible by 5.buzz
: Incrementsi
by 5, only enters the block ifi
is not divisible by 3.fizzbuzz
: Incrementsi
by 15, enters the block for numbers divisible by both 3 and 5.number
: Incrementsi
by 1, handles all numbers, applying the correct action based on divisibility rules.
-
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 thefSema
semaphore before printing.buzz
: Waits for thebSema
semaphore before printing.fizzbuzz
: Waits for thefbSema
semaphore before printing.number
: Always tries to acquire thenSema
semaphore since it runs first, then releases the appropriate semaphore for the next action based on the divisibility ofi
.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 thenumber
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:
-
Number Thread: Starts and is the first to run because
nSema
has 1 permit. It acquires the permit and starts processing numbers. Sincei = 1
is not divisible by 3 or 5, it prints1
and releasesnSema
permit, allowing itself to proceed to the next number. -
Number Thread: Now with
i = 2
, the same process occurs: prints2
, then releases thenSema
permit. -
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 thefSema
permit and waits. -
Fizz Thread: The
fizz
thread has been blocked, waiting for thefSema
semaphore. Now it acquires the permit, prints "fizz" for number 3, and then releases thenSema
permit, signaling thenumber
thread to continue. -
Number Thread: Moves to
i = 4
, prints4
as it is not divisible by 3 or 5, releases thenSema
permit to proceed with the next number. -
Number Thread: At
i = 5
, the thread identifies it as a multiple of 5. It releasesbSema
for thebuzz
thread and waits. -
Buzz Thread: The
buzz
thread was waiting forbSema
. It acquires the permit, prints “buzz” for number 5, and releases thenSema
permit for thenumber
thread to continue with the sequence. -
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
Time and Space Complexity
Time Complexity:
The time complexity of the FizzBuzz
class methods depends on the value of n
.
-
The
number()
method is calledn
times. -
The
fizz()
method is called at mostn/3
times because every third number is potentially divisible by 3. But it checksi % 5 != 0
in its loop, meaning not alln/3
calls will result in execution of theprintFizz()
method. It will only execute when the number is not divisible by 5, essentiallyn/3 - n/15
times. -
The
buzz()
method is called at mostn/5
times because every fifth number is potentially divisible by 5, but same asfizz()
, it will only execute when the number is not divisible by 3, son/5 - n/15
times. -
The
fizzbuzz()
method is called at mostn/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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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 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 Monster Assistant anything you don't understand.
Still not clear? Submit the part you don't understand to our editors. Or join our Discord and ask the community.