Fizz Buzz Multithreaded solution and explanation
Google
3 more videos on this problem
1195. Fizz Buzz Multithreaded (Leetcode Concurrency Section)EverydayLeetcode · 12:00 · 4K views
Fizz Buzz Multithreaded, Medium, LeetCode 1195H William Polenz · 11:50 · 511 views
No Sound Leetcode 1195: Fizz Buzz MultithreadedExtremeProgrammer · 4:05 · 36 views
Leetcode 1195. Fizz Buzz MultithreadedTechForGrowth · 25:10 · 17 views
The problem
You have the four functions:
printFizzthat prints the word"fizz"to the console,printBuzzthat prints the word"buzz"to the console,printFizzBuzzthat prints the word"fizzbuzz"to the console, andprintNumberthat prints a given integer to the console.
You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:
- Thread A: calls
fizz()that should output the word"fizz". - Thread B: calls
buzz()that should output the word"buzz". - Thread C: calls
fizzbuzz()that should output the word"fizzbuzz". - Thread D: calls
number()that should only output the integers.
Modify the given class to output the series [1, 2, "fizz", 4, "buzz", ...] where the ith token (1-indexed) of the series is:
"fizzbuzz"ifiis divisible by3and5,"fizz"ifiis divisible by3and not5,"buzz"ifiis divisible by5and not3, oriifiis not divisible by3or5.
Implement the FizzBuzz class:
FizzBuzz(int n)Initializes the object with the numbernthat represents the length of the sequence that should be printed.void fizz(printFizz)CallsprintFizzto output"fizz".void buzz(printBuzz)CallsprintBuzzto output"buzz".void fizzbuzz(printFizzBuzz)CallsprintFizzBuzzto output"fizzbuzz".void number(printNumber)Callsprintnumberto output the numbers.
Example 1:
Input: n = 15 Output: [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]
Example 2:
Input: n = 5 Output: [1,2,"fizz",4,"buzz"]
Constraints:
1 <= n <= 50
Approach overview
Problem Overview: Four threads must cooperatively print numbers from 1 to n. One thread prints fizz for multiples of 3, another prints buzz for multiples of 5, another prints fizzbuzz for multiples of both, and the last prints the number itself. The challenge is coordinating these threads so output appears in the correct order without race conditions.
This is a classic concurrency control problem. Multiple workers want to act on the same sequence of integers. Without synchronization, threads can interleave unpredictably and produce incorrect output. The goal is to enforce ordering while keeping the logic simple and efficient.
Approach 1: Synchronize with Locks (Time: O(n), Space: O(1))
A shared counter tracks the current number from 1 to n. Each thread repeatedly acquires a mutual exclusion lock, checks whether the current number satisfies its condition, prints if appropriate, and increments the counter. If the condition does not match, the thread releases the lock so another worker can check. The lock guarantees that only one thread evaluates and updates the shared state at a time, preventing race conditions. This pattern is common in multithreading problems where threads coordinate through a shared variable.
The key idea is that the condition check and counter increment must be atomic. The lock ensures ordering and correctness, though threads may repeatedly wake and check the condition until it matches. The algorithm processes each number exactly once, so total work is O(n) with constant auxiliary memory.
Approach 2: Semaphore for Synchronization (Time: O(n), Space: O(1))
A more structured solution uses semaphores to explicitly control which thread runs next. A main semaphore handles the number-checking thread. Depending on the value of the current number, it releases one of three semaphores: fizz, buzz, or fizzbuzz. The corresponding worker prints its output and signals back so the next number can be processed.
This design avoids busy checking because each thread sleeps until its semaphore is released. The number thread determines which worker should run, ensuring the correct order and condition handling. Each integer triggers exactly one worker action, so time complexity remains O(n) and memory usage stays constant.
Semaphore-based coordination is common in interview problems involving ordered thread execution. It clearly separates responsibilities between threads and avoids repeated condition polling.
Recommended for interviews: The semaphore approach is usually preferred. It demonstrates clear reasoning about thread coordination and avoids inefficient lock polling. The lock-based method still shows you understand mutual exclusion and shared state protection, but semaphores communicate intent more directly in concurrency design.
Approach 1: Synchronize with Locks
One way to solve this challenge is by using locks or mutexes. We can lock each section of code until the appropriate printing function is executed. Here, Java's intrinsic locking via `synchronized` blocks, C#'s `lock` statement, Python's `threading.Lock`, or C++'s `std::mutex` (similarly in C with Pthreads) can be utilized. The key is to ensure only one block of code runs at a time, corresponding to the appropriate thread (fizz, buzz, fizzbuzz, number). By doing this, threads can access shared data (current number) but only when it's their turn to do so based on the divisibility rules.
from threading import Lock
class FizzBuzz:
def __init__(self, n):
self.n = n
self.current = 1
self.lock = Lock()
def fizz(self, printFizz):
while True:
with self.lock:
if self.current > self.n:
return
if self.current % 3 == 0 and self.current % 5 != 0:
printFizz()
self.current += 1
def buzz(self, printBuzz):
while True:
with self.lock:
if self.current > self.n:
return
if self.current % 5 == 0 and self.current % 3 != 0:
printBuzz()
self.current += 1
def fizzbuzz(self, printFizzBuzz):
while True:
with self.lock:
if self.current > self.n:
return
if self.current % 15 == 0:
printFizzBuzz()
self.current += 1
def number(self, printNumber):
while True:
with self.lock:
if self.current > self.n:
return
if self.current % 3 != 0 and self.current % 5 != 0:
printNumber(self.current)
self.current += 1import java.util.concurrent.locks.*;
class FizzBuzz {
private int n;
private int current = 1;
private final Lock lock = new ReentrantLock();
public FizzBuzz(int n) {
this.n = n;
}
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
lock.lock();
try {
if (current > n) return;
if (current % 3 == 0 && current % 5 != 0) {
printFizz.run();
current++;
}
} finally {
lock.unlock();
}
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
lock.lock();
try {
if (current > n) return;
if (current % 5 == 0 && current % 3 != 0) {
printBuzz.run();
current++;
}
} finally {
lock.unlock();
}
}
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
lock.lock();
try {
if (current > n) return;
if (current % 15 == 0) {
printFizzBuzz.run();
current++;
}
} finally {
lock.unlock();
}
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
while (true) {
lock.lock();
try {
if (current > n) return;
if (current % 3 != 0 && current % 5 != 0) {
printNumber.accept(current);
current++;
}
} finally {
lock.unlock();
}
}
}
}This implementation uses the `threading.Lock()` in Python to synchronize access to the current number being evaluated. Each method (fizz, buzz, fizzbuzz, number) acquires the lock, checks if the shared counter needs to be accessed, performs its operation, and then releases the lock. This ensures only one thread can modify the shared state at a time and only under correct conditions.
Time Complexity: O(n) – each number from 1 to n is checked once.
Space Complexity: O(1) – constant space is used aside from input n.
Approach 2: Semaphore for Synchronization
Another approach is to use semaphore mechanisms. Semaphores control access based on counters, which can track how many threads can access a particular resource or section of code. Here, using three semaphores for fizz, buzz, and fizzbuzz allows fine-grained control over which function gets executed when. Depending on the number being evaluated, relevant semaphores are released or acquired.
from threading import Semaphore
class FizzBuzz:
def __init__(self, n):
self.n = n
self.current = 1
self.fizz_sem = Semaphore(0)
self.buzz_sem = Semaphore(0)
self.fizzbuzz_sem = Semaphore(0)
self.number_sem = Semaphore(1)
def fizz(self, printFizz):
while True:
self.fizz_sem.acquire()
if self.current > self.n:
return
printFizz()
self.current += 1
self._release_next()
def buzz(self, printBuzz):
while True:
self.buzz_sem.acquire()
if self.current > self.n:
return
printBuzz()
self.current += 1
self._release_next()
def fizzbuzz(self, printFizzBuzz):
while True:
self.fizzbuzz_sem.acquire()
if self.current > self.n:
return
printFizzBuzz()
self.current += 1
self._release_next()
def number(self, printNumber):
while True:
self.number_sem.acquire()
if self.current > self.n:
return
if self.current % 3 != 0 and self.current % 5 != 0:
printNumber(self.current)
self.current += 1
self._release_next()
def _release_next(self):
if self.current % 15 == 0:
self.fizzbuzz_sem.release()
elif self.current % 3 == 0:
self.fizz_sem.release()
elif self.current % 5 == 0:
self.buzz_sem.release()
else:
self.number_sem.release()import java.util.concurrent.Semaphore;
class FizzBuzz {
private int n;
private int current = 1;
private Semaphore fizzSem = new Semaphore(0);
private Semaphore buzzSem = new Semaphore(0);
private Semaphore fizzbuzzSem = new Semaphore(0);
private Semaphore numberSem = new Semaphore(1);
public FizzBuzz(int n) {
this.n = n;
}
public void fizz(Runnable printFizz) throws InterruptedException {
while (true) {
fizzSem.acquire();
if (current > n) return;
printFizz.run();
current++;
releaseNext();
}
}
public void buzz(Runnable printBuzz) throws InterruptedException {
while (true) {
buzzSem.acquire();
if (current > n) return;
printBuzz.run();
current++;
releaseNext();
}
}
public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
while (true) {
fizzbuzzSem.acquire();
if (current > n) return;
printFizzBuzz.run();
current++;
releaseNext();
}
}
public void number(IntConsumer printNumber) throws InterruptedException {
while (true) {
numberSem.acquire();
if (current > n) return;
if (current % 3 != 0 && current % 5 != 0) {
printNumber.accept(current);
}
current++;
releaseNext();
}
}
private void releaseNext() {
if (current > n) return;
if (current % 15 == 0) {
fizzbuzzSem.release();
} else if (current % 3 == 0) {
fizzSem.release();
} else if (current % 5 == 0) {
buzzSem.release();
} else {
numberSem.release();
}
}
}This Python solution uses `threading.Semaphore` to enable or block the execution of tasks. The `number_sem` initially allows number processing but each operation concludes with determining the next permissible operation and releasing the respective semaphore. This controls thread execution order and access to shared data.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
class FizzBuzz {
private:
std::mutex mtx;
atomic<int> index;
int n;
// 这里主要运用到了C++11中的RAII锁(lock_guard)的知识。
// 需要强调的一点是，在进入循环后，要时刻不忘加入index <= n的逻辑
public:
FizzBuzz(int n) {
this->n = n;
index = 1;
}
void fizz(function<void()> printFizz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 3 && 0 != index % 5 && index <= n) {
printFizz();
index++;
}
}
}
void buzz(function<void()> printBuzz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 5 && 0 != index % 3 && index <= n) {
printBuzz();
index++;
}
}
}
void fizzbuzz(function<void()> printFizzBuzz) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 == index % 15 && index <= n) {
printFizzBuzz();
index++;
}
}
}
void number(function<void(int)> printNumber) {
while (index <= n) {
std::lock_guard<std::mutex> lk(mtx);
if (0 != index % 3 && 0 != index % 5 && index <= n) {
printNumber(index);
index++;
}
}
}
};Complexity comparison
| Approach | Complexity |
|---|---|
| Synchronize with Locks | Time Complexity: O(n) – each number from 1 to n is checked once. |
| Semaphore for Synchronization | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Synchronize with Locks | O(n) | O(1) | When coordinating threads using a shared counter with mutual exclusion |
| Semaphore for Synchronization | O(n) | O(1) | Preferred when explicit thread signaling is needed to control execution order |
Frequently asked questions
Is Fizz Buzz Multithreaded easy or hard?
Fizz Buzz Multithreaded is rated Medium because the logic of Fizz Buzz is simple but thread coordination introduces complexity. The difficulty comes from preventing race conditions and ensuring correct ordering across multiple threads using synchronization primitives.
How to solve Fizz Buzz Multithreaded in O(n)?
Maintain a shared counter from 1 to n and synchronize threads using locks or semaphores. For each number, determine whether it is divisible by 3, 5, or both, then allow the corresponding thread to print. Each integer triggers one action, so the total work is linear in n.
Fizz Buzz Multithreaded Python or Java solution?
Both Python and Java solutions typically rely on threading primitives provided by their standard libraries. Python implementations often use threading.Lock or threading.Semaphore, while Java uses synchronized blocks, ReentrantLock, or Semaphore classes. The logic remains O(n) with constant extra memory.
What is the best approach for Fizz Buzz Multithreaded?
Semaphore-based synchronization is generally the best approach. A controlling thread checks each number and signals the appropriate worker thread (fizz, buzz, or fizzbuzz) using semaphores. This avoids repeated lock polling and provides clear thread coordination. The algorithm runs in O(n) time and O(1) space.
What data structure is used in Fizz Buzz Multithreaded?
The problem does not rely on complex data structures. It mainly uses concurrency primitives such as mutex locks, semaphores, or condition variables. A shared integer counter is the only state needed to coordinate the four threads.
What is the time complexity of Fizz Buzz Multithreaded?
The time complexity is O(n) because each number from 1 to n is processed exactly once. For every integer, one thread prints either fizz, buzz, fizzbuzz, or the number itself. Synchronization primitives like locks or semaphores add constant overhead but do not change the overall complexity.
Is Fizz Buzz Multithreaded asked at Google, Amazon, or Meta?
Fizz Buzz Multithreaded appears in interview preparation sets for companies that test concurrency concepts. Variants have been reported in interviews at large tech companies including Google, Amazon, and Meta, especially for roles requiring knowledge of multithreading or systems programming.