# Fizz Buzz Multithreaded **Difficulty:** MEDIUM [External](https://leetcode.com/problems/fizz-buzz-multithreaded) Canonical: https://scaleengineer.com/dsa/problems/fizz-buzz-multithreaded --- ## Problem You have the four functions: * `printFizz` that prints the word `"fizz"` to the console, * `printBuzz` that prints the word `"buzz"` to the console, * `printFizzBuzz` that prints the word `"fizzbuzz"` to the console, and * `printNumber` that 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"` if `i` is divisible by `3` and `5`, * `"fizz"` if `i` is divisible by `3` and not `5`, * `"buzz"` if `i` is divisible by `5` and not `3`, or * `i` if `i` is not divisible by `3` or `5`. Implement the `FizzBuzz` class: * `FizzBuzz(int n)` Initializes the object with the number `n` that represents the length of the sequence that should be printed. * `void fizz(printFizz)` Calls `printFizz` to output `"fizz"`. * `void buzz(printBuzz)` Calls `printBuzz` to output `"buzz"`. * `void fizzbuzz(printFizzBuzz)` Calls `printFizzBuzz` to output `"fizzbuzz"`. * `void number(printNumber)` Calls `printnumber` to 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` # Approaches ## Busy-Waiting with AtomicInteger This approach uses a shared `java.util.concurrent.atomic.AtomicInteger` to track the current number in the sequence. Each of the four threads runs in a loop, continuously checking the value of this atomic integer. This is known as "busy-waiting" or a "spinlock". When a thread finds that the current number matches its condition (e.g., for the `fizz` thread, `i % 3 == 0 && i % 5 != 0`), it performs its print action and then atomically increments the counter. **Time:** O(N * C) where N is the input number and C is the number of threads (4). Each thread spins until `current` is incremented. In the worst case, for each number from 1 to N, all 4 threads will spin, checking the condition. The total number of checks is very high. · **Space:** O(1) as we only use a few shared variables. **Pros:** Conceptually simple to understand.; It's a lock-free approach, which avoids potential deadlocks that can occur with explicit locks. **Cons:** Extremely inefficient in terms of CPU usage. Threads that are not printing are stuck in a tight loop (spinlock), consuming 100% of their allocated CPU core time. This is wasteful and can significantly degrade system performance.; Can lead to livelock situations where threads are active but not making progress.; The order of execution is not guaranteed and relies on the thread scheduler, which might lead to fairness issues. ### Explanation We initialize an `AtomicInteger` `current` to 1. Each of the four methods (`fizz`, `buzz`, `fizzbuzz`, `number`) enters a `while` loop that continues as long as `current.get() <= n`. Inside the loop, each thread constantly checks if it's its turn. For example, the `fizz` thread checks `if (current.get() % 3 == 0 && current.get() % 5 != 0)`. If it is its turn, it calls the appropriate print function and then increments the `current` counter using `current.getAndIncrement()`. If it's not its turn, the loop continues, effectively "spinning" and consuming CPU cycles without doing useful work. This continues until the condition is met or the entire sequence is printed (`current > n`). ```java import java.util.concurrent.atomic.AtomicInteger; import java.util.function.IntConsumer; class FizzBuzz { private int n; private AtomicInteger current = new AtomicInteger(1); public FizzBuzz(int n) { this.n = n; } // printFizz.run() outputs "fizz". public void fizz(Runnable printFizz) throws InterruptedException { while (current.get() <= n) { if (current.get() % 3 == 0 && current.get() % 5 != 0) { printFizz.run(); current.getAndIncrement(); } } } // printBuzz.run() outputs "buzz". public void buzz(Runnable printBuzz) throws InterruptedException { while (current.get() <= n) { if (current.get() % 3 != 0 && current.get() % 5 == 0) { printBuzz.run(); current.getAndIncrement(); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { while (current.get() <= n) { if (current.get() % 15 == 0) { printFizzBuzz.run(); current.getAndIncrement(); } } } // printNumber.accept(x) outputs "x", where x is an integer. public void number(IntConsumer printNumber) throws InterruptedException { while (current.get() <= n) { if (current.get() % 3 != 0 && current.get() % 5 != 0) { printNumber.accept(current.get()); current.getAndIncrement(); } } } } ``` ### Algorithm - Initialize a shared `AtomicInteger current` to 1. - Start four threads, each calling one of the methods: `fizz`, `buzz`, `fizzbuzz`, `number`. - Each thread enters a loop that runs as long as `current <= n`. - Inside the loop, each thread continuously checks if the value of `current` satisfies its specific condition. - If the condition is met, the thread prints its output and increments `current`. - If the condition is not met, the thread does nothing and continues to the next iteration of its loop, re-checking the condition. ## synchronized with wait() and notifyAll() This approach uses Java's built-in monitor locks (`synchronized` blocks) to coordinate the threads. A shared counter tracks the current number. When a thread's turn comes, it prints and increments the counter. If it's not a thread's turn, it calls `wait()` on a shared lock object, which causes it to sleep and release the lock, avoiding busy-waiting. After a thread finishes its work, it calls `notifyAll()` to wake up all other waiting threads, so they can re-check if it's their turn. **Time:** O(N). Each number from 1 to N is processed once. The overhead is in the context switches and lock contention caused by `notifyAll()`, but it's significantly better than spinning. · **Space:** O(1). No extra space proportional to `N` is used. **Pros:** Much more efficient than busy-waiting. Waiting threads are blocked by the OS and do not consume CPU cycles.; A standard and well-understood pattern for thread coordination in Java. **Cons:** The use of `notifyAll()` can be inefficient. It wakes up all waiting threads, leading to contention for the lock. Only one thread will actually be able to proceed, while the others will check their condition, find it false, and go back to waiting. This is known as the "thundering herd" problem. ### Explanation We use a standard `int` counter, `i`, initialized to 1. This counter is a shared resource. All four methods are `synchronized` on the `FizzBuzz` instance itself (`this`), ensuring that only one thread can execute its logic at any given time. Each method has a loop that iterates as long as `i <= n`. Inside the loop, a thread checks if it's its turn. If not, it calls `wait()`. The `wait()` call is placed inside a `while` loop to guard against spurious wakeups (where a thread wakes up without being notified). If it is the thread's turn, it prints its output, increments `i`, and then calls `notifyAll()`. `notifyAll()` wakes up every thread that is currently waiting on the lock. Each woken thread will then re-acquire the lock and check the condition again. ```java import java.util.function.IntConsumer; class FizzBuzz { private int n; private int i = 1; public FizzBuzz(int n) { this.n = n; } public synchronized void fizz(Runnable printFizz) throws InterruptedException { while (i <= n) { while (i <= n && (i % 3 != 0 || i % 5 == 0)) { wait(); } if (i <= n) { printFizz.run(); i++; notifyAll(); } } } public synchronized void buzz(Runnable printBuzz) throws InterruptedException { while (i <= n) { while (i <= n && (i % 5 != 0 || i % 3 == 0)) { wait(); } if (i <= n) { printBuzz.run(); i++; notifyAll(); } } } public synchronized void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { while (i <= n) { while (i <= n && (i % 15 != 0)) { wait(); } if (i <= n) { printFizzBuzz.run(); i++; notifyAll(); } } } public synchronized void number(IntConsumer printNumber) throws InterruptedException { while (i <= n) { while (i <= n && (i % 3 == 0 || i % 5 == 0)) { wait(); } if (i <= n) { printNumber.accept(i); i++; notifyAll(); } } } } ``` ### Algorithm - Initialize a shared integer `i` to 1. - Each of the four methods is synchronized on the same lock object. - Each thread enters a main loop that continues as long as `i <= n`. - Inside the loop, it enters another `while` loop to check if it's its turn. If not (`condition == false`), it calls `wait()`, releasing the lock and going to sleep. - When woken up, it re-checks the condition (to handle spurious wakeups). - If it is its turn (`condition == true`), it exits the inner loop, prints its output, increments `i`, and calls `notifyAll()`. - `notifyAll()` wakes up all other waiting threads. One of them will acquire the lock and proceed. ## Targeted Notification with Semaphores This is the most efficient approach. It uses `java.util.concurrent.Semaphore` to pass control directly from one thread to the next, in a "token passing" or "baton passing" style. We use four semaphores, one for each thread type (`fizz`, `buzz`, `fizzbuzz`, `number`). Each semaphore is initialized with zero permits, except for the `number` semaphore, which gets one permit because the sequence starts with a number. The thread that is currently allowed to run acquires its semaphore, prints, and then determines which thread should run next and `release()`s that specific semaphore. **Time:** O(N). Each number is processed once. The overhead per number is minimal, involving just one `acquire` and one `release` operation, which is very efficient. This is the most performant solution. · **Space:** O(1). The space used by the semaphores is constant. **Pros:** Highly efficient. It avoids both busy-waiting and the "thundering herd" problem of `notifyAll()`.; Control is passed directly to the thread that needs to run next, minimizing unnecessary context switches and lock contention.; Provides a clean and scalable solution for such turn-based coordination problems. **Cons:** The logic can be slightly more complex to set up compared to the `synchronized` approach, especially the termination logic which requires releasing all semaphores. ### Explanation We create four `Semaphore` instances, one for each condition. `numberSem` is initialized with `new Semaphore(1)` and the others with `new Semaphore(0)`. A shared `volatile int i` tracks the current number. Each thread's method contains a loop. Inside the loop, it first tries to `acquire()` its specific semaphore. This will block until another thread releases a permit for it. Once the semaphore is acquired, the thread checks if the sequence is complete (`i > n`). If so, it releases all semaphores to allow the other waiting threads to terminate gracefully and then breaks its loop. If the sequence is not complete, it prints its output and increments `i`. Crucially, it then checks the condition for the *new* value of `i` and releases the corresponding semaphore for the thread that should run next. This directly signals the correct thread without waking up the others. ```java import java.util.concurrent.Semaphore; import java.util.function.IntConsumer; class FizzBuzz { private int n; private volatile int i = 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 (i > n) break; printFizz.run(); i++; releaseNext(); } } public void buzz(Runnable printBuzz) throws InterruptedException { while (true) { buzzSem.acquire(); if (i > n) break; printBuzz.run(); i++; releaseNext(); } } public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException { while (true) { fizzbuzzSem.acquire(); if (i > n) break; printFizzBuzz.run(); i++; releaseNext(); } } public void number(IntConsumer printNumber) throws InterruptedException { while (true) { numberSem.acquire(); if (i > n) break; printNumber.accept(i); i++; releaseNext(); } } private void releaseNext() { if (i > n) { // Release all to allow threads to terminate fizzSem.release(); buzzSem.release(); fizzbuzzSem.release(); numberSem.release(); return; } if (i % 15 == 0) { fizzbuzzSem.release(); } else if (i % 3 == 0) { fizzSem.release(); } else if (i % 5 == 0) { buzzSem.release(); } else { numberSem.release(); } } } ``` ### Algorithm - Initialize four semaphores: `numberSem` with 1 permit, and `fizzSem`, `buzzSem`, `fizzbuzzSem` with 0 permits. - Initialize a shared volatile integer `i` to 1. - Each thread enters an infinite loop. - At the start of the loop, each thread calls `acquire()` on its respective semaphore, blocking until a permit is available. - Once unblocked, it checks if `i > n`. If true, it means the sequence is finished. It releases all semaphores to unblock any other waiting threads and then breaks the loop to terminate. - If `i <= n`, it performs its print action. - It then increments `i`. - Finally, it determines which thread should run for the new `i` and calls `release()` on that thread's semaphore, passing control directly. # Solutions ### Java ```java class FizzBuzz { private int n ; public FizzBuzz ( int n ) { this . n = n ; } private Semaphore fSema = new Semaphore ( 0 ); private Semaphore bSema = new Semaphore ( 0 ); private Semaphore fbSema = new Semaphore ( 0 ); private Semaphore nSema = new Semaphore ( 1 ); // printFizz.run() outputs "fizz". public void fizz ( Runnable printFizz ) throws InterruptedException { for ( int i = 3 ; i <= n ; i = i + 3 ) { if ( i % 5 != 0 ) { fSema . acquire (); printFizz . run (); nSema . release (); } } } // printBuzz.run() outputs "buzz". public void buzz ( Runnable printBuzz ) throws InterruptedException { for ( int i = 5 ; i <= n ; i = i + 5 ) { if ( i % 3 != 0 ) { bSema . acquire (); printBuzz . run (); nSema . release (); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz ( Runnable printFizzBuzz ) throws InterruptedException { for ( int i = 15 ; i <= n ; i = i + 15 ) { fbSema . acquire (); printFizzBuzz . run (); nSema . release (); } } // printNumber.accept(x) outputs "x", where x is an integer. public void number ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 1 ; i <= n ; i ++) { nSema . acquire (); if ( i % 3 == 0 && i % 5 == 0 ) { fbSema . release (); } else if ( i % 3 == 0 ) { fSema . release (); } else if ( i % 5 == 0 ) { bSema . release (); } else { printNumber . accept ( i ); nSema . release (); } } } } ``` ### Python ```python from threading import Semaphore class FizzBuzz : # semaphore def __init__ ( self , n : int ): self . n = n self . fizzSemaphore = Semaphore ( 0 ) self . buzzSemaphore = Semaphore ( 0 ) self . fizzbuzzSemaphore = Semaphore ( 0 ) self . numberSemaphore = Semaphore ( 1 ) # printFizz() outputs "fizz" def fizz ( self , printFizz : 'Callable[[], None]' ) -> None : for i in range ( 3 , self . n + 1 , 3 ): if i % 5 != 0 : self . fizzSemaphore . acquire () printFizz () self . numberSemaphore . release () # printBuzz() outputs "buzz" def buzz ( self , printBuzz : 'Callable[[], None]' ) -> None : for i in range ( 5 , self . n + 1 , 5 ): if i % 3 != 0 : self . buzzSemaphore . acquire () printBuzz () self . numberSemaphore . release () # printFizzBuzz() outputs "fizzbuzz" def fizzbuzz ( self , printFizzBuzz : 'Callable[[], None]' ) -> None : for i in range ( 15 , self . n + 1 , 15 ): self . fizzbuzzSemaphore . acquire () printFizzBuzz () self . numberSemaphore . release () # printNumber(x) outputs "x", where x is an integer. def number ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 1 , self . n + 1 ): self . numberSemaphore . acquire () if i % 15 == 0 : self . fizzbuzzSemaphore . release () elif i % 3 == 0 : self . fizzSemaphore . release () elif i % 5 == 0 : self . buzzSemaphore . release () else : printNumber ( i ) self . numberSemaphore . release () ########## # ref: https://leetcode.com/problems/fizz-buzz-multithreaded/discuss/542960/python-greater99.28-a-standard-Lock()-based-solution-with-detailed-explanation import threading class FizzBuzz : # lock def __init__ ( self , n : int ): self . n = n self . fizz_lock = threading . Lock () self . buzz_lock = threading . Lock () self . fizzbuzz_lock = threading . Lock () self . fizz_lock . acquire () self . buzz_lock . acquire () self . fizzbuzz_lock . acquire () self . main_lock = threading . Lock () def fizz ( self , printFizz : 'Callable[[], None]' ) -> None : while True : self . fizz_lock . acquire () if self . n == 0 : return printFizz () self . main_lock . release () def buzz ( self , printBuzz : 'Callable[[], None]' ) -> None : while True : self . buzz_lock . acquire () if self . n == 0 : return printBuzz () self . main_lock . release () def fizzbuzz ( self , printFizzBuzz : 'Callable[[], None]' ) -> None : while True : self . fizzbuzz_lock . acquire () if self . n == 0 : return printFizzBuzz () self . main_lock . release () def number ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 1 , self . n + 1 ): self . main_lock . acquire () if i % 15 == 0 : self . fizzbuzz_lock . release () elif i % 3 == 0 : self . fizz_lock . release () elif i % 5 == 0 : self . buzz_lock . release () else : printNumber ( i ) self . main_lock . release () self . main_lock . acquire () self . n = 0 self . fizz_lock . release () self . buzz_lock . release () self . fizzbuzz_lock . release () return ``` ### CPP ```cpp 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 ++ ; } } } }; ```