Problem Description

This is a multithreading problem where you need to implement a FizzBuzz class that coordinates four different threads to print the classic FizzBuzz sequence.

The problem provides you with four printing functions:

• printFizz() - prints "fizz"
• printBuzz() - prints "buzz"
• printFizzBuzz() - prints "fizzbuzz"
• printNumber(int x) - prints the integer x

You need to implement a FizzBuzz class with four methods that will be called by four separate threads:

• Thread A calls fizz() - responsible for printing "fizz" when appropriate
• Thread B calls buzz() - responsible for printing "buzz" when appropriate
• Thread C calls fizzbuzz() - responsible for printing "fizzbuzz" when appropriate
• Thread D calls number() - responsible for printing numbers when appropriate

The class should coordinate these threads to produce the correct FizzBuzz sequence from 1 to n:

• Print "fizzbuzz" if the number is divisible by both 3 and 5
• Print "fizz" if the number is divisible by 3 but not 5
• Print "buzz" if the number is divisible by 5 but not 3
• Print the number itself if it's not divisible by either 3 or 5

For example, if n = 15, the output should be: [1, 2, "fizz", 4, "buzz", "fizz", 7, 8, "fizz", "buzz", 11, "fizz", 13, 14, "fizzbuzz"]

The key challenge is synchronizing the four threads so that:

1. Each thread only prints when it's their turn
2. The output appears in the correct sequential order from 1 to n
3. No race conditions or deadlocks occur

The solution uses semaphores to coordinate thread execution. Each type of output (fizz, buzz, fizzbuzz, number) has its own semaphore to control when that thread can execute. The number thread acts as the coordinator, determining which thread should run next based on the current number's divisibility rules.

Intuition

The core challenge here is that we have four threads that need to take turns printing in a specific order. Think of it like a relay race where only one runner can run at a time, and we need to pass the baton to the correct next runner based on the current position.

The key insight is that we need a coordination mechanism where:

1. Only one thread can execute at any given moment
2. We need to signal which specific thread should run next
3. After a thread finishes its task, it must signal the coordinator to continue

Semaphores are perfect for this because they can block threads until signaled. We can think of each semaphore as a gate that's initially closed (initialized to 0), and threads wait at their gate until it opens.

The natural approach is to have the number() thread act as the coordinator since it needs to check every number from 1 to n anyway. For each number i, it determines which output is needed:

• If i % 15 == 0 → signal the fizzbuzz thread
• If i % 3 == 0 (but not 15) → signal the fizz thread
• If i % 5 == 0 (but not 15) → signal the buzz thread
• Otherwise → print the number itself

We use four semaphores:

• nSema (initialized to 1) - controls the number thread, starts with 1 so it runs first
• fSema (initialized to 0) - controls the fizz thread
• bSema (initialized to 0) - controls the buzz thread
• fbSema (initialized to 0) - controls the fizzbuzz thread

The workflow becomes:

1. The number thread acquires nSema (consuming the permit)
2. Based on the current number, it either:
   • Releases a permit to one of the other semaphores (delegating the print job)
   • Prints the number itself and releases nSema again
3. The signaled thread acquires its semaphore, prints, then releases nSema to return control
4. This continues until all numbers from 1 to n are processed

Each specialized thread (fizz, buzz, fizzbuzz) cleverly iterates only through numbers it might need to handle (incrementing by 3, 5, or 15 respectively), making the solution more efficient than checking every single number.

Solution Approach

The solution uses semaphores as the synchronization mechanism to coordinate the four threads. Let's walk through the implementation step by step:

Data Structures

• Four Semaphores are used for thread coordination:
  • nSema = new Semaphore(1) - Controls the number thread (starts with 1 permit)
  • fSema = new Semaphore(0) - Controls the fizz thread (starts blocked)
  • bSema = new Semaphore(0) - Controls the buzz thread (starts blocked)
  • fbSema = new Semaphore(0) - Controls the fizzbuzz thread (starts blocked)

The Coordinator Thread - number()

This is the main orchestrator that runs through all numbers from 1 to n:

for (int i = 1; i <= n; i++) {
    nSema.acquire();  // Wait for permission to process number i
    if (i % 3 == 0 && i % 5 == 0) {
        fbSema.release();  // Signal fizzbuzz thread
    } else if (i % 3 == 0) {
        fSema.release();   // Signal fizz thread
    } else if (i % 5 == 0) {
        bSema.release();   // Signal buzz thread
    } else {
        printNumber.accept(i);  // Print the number directly
        nSema.release();        // Give control back to itself
    }
}

The Worker Threads

Fizz Thread:

for (int i = 3; i <= n; i = i + 3) {  // Only check multiples of 3
    if (i % 5 != 0) {  // Skip multiples of 15 (handled by fizzbuzz)
        fSema.acquire();     // Wait for signal
        printFizz.run();     // Print "fizz"
        nSema.release();     // Return control to number thread
    }
}

Buzz Thread:

for (int i = 5; i <= n; i = i + 5) {  // Only check multiples of 5
    if (i % 3 != 0) {  // Skip multiples of 15 (handled by fizzbuzz)
        bSema.acquire();     // Wait for signal
        printBuzz.run();     // Print "buzz"
        nSema.release();     // Return control to number thread
    }
}

FizzBuzz Thread:

for (int i = 15; i <= n; i = i + 15) {  // Only check multiples of 15
    fbSema.acquire();        // Wait for signal
    printFizzBuzz.run();     // Print "fizzbuzz"
    nSema.release();         // Return control to number thread
}

Execution Flow Example (n = 5)

1. i = 1: number thread prints 1, releases nSema
2. i = 2: number thread prints 2, releases nSema
3. i = 3: number thread releases fSema → fizz thread prints "fizz", releases nSema
4. i = 4: number thread prints 4, releases nSema
5. i = 5: number thread releases bSema → buzz thread prints "buzz", releases nSema

Key Patterns Used

1. Producer-Consumer Pattern: The number thread produces signals for other threads to consume
2. Token Passing: The nSema acts like a token that gets passed between threads
3. Optimization: Each worker thread only iterates through relevant numbers (multiples of 3, 5, or 15) rather than checking all numbers, reducing unnecessary iterations

The beauty of this solution is that it guarantees mutual exclusion (only one thread prints at a time) and maintains the correct order without any explicit locks or complex synchronization logic.

Example Walkthrough

Let's walk through a small example with n = 6 to illustrate how the threads coordinate:

Initial State:

• nSema = 1 (number thread can start)
• fSema = 0 (fizz thread blocked)
• bSema = 0 (buzz thread blocked)
• fbSema = 0 (fizzbuzz thread blocked)

Thread Starting Positions:

• Number thread: ready to process i = 1
• Fizz thread: waiting at i = 3 (first multiple of 3)
• Buzz thread: waiting at i = 5 (first multiple of 5)
• FizzBuzz thread: waiting at i = 15 (no iterations for n=6)

Step-by-step Execution:

Step 1: i = 1

• Number thread acquires nSema (now nSema = 0)
• 1 is not divisible by 3 or 5
• Number thread prints "1"
• Number thread releases nSema (now nSema = 1)

Step 2: i = 2

• Number thread acquires nSema (now nSema = 0)
• 2 is not divisible by 3 or 5
• Number thread prints "2"
• Number thread releases nSema (now nSema = 1)

Step 3: i = 3

• Number thread acquires nSema (now nSema = 0)
• 3 is divisible by 3 but not 5
• Number thread releases fSema (now fSema = 1)
• Fizz thread (waiting at i=3) acquires fSema (now fSema = 0)
• Fizz thread prints "fizz"
• Fizz thread releases nSema (now nSema = 1)
• Fizz thread moves to next iteration (i=6)

Step 4: i = 4

• Number thread acquires nSema (now nSema = 0)
• 4 is not divisible by 3 or 5
• Number thread prints "4"
• Number thread releases nSema (now nSema = 1)

Step 5: i = 5

• Number thread acquires nSema (now nSema = 0)
• 5 is divisible by 5 but not 3
• Number thread releases bSema (now bSema = 1)
• Buzz thread (waiting at i=5) acquires bSema (now bSema = 0)
• Buzz thread prints "buzz"
• Buzz thread releases nSema (now nSema = 1)
• Buzz thread moves to next iteration (i=10, exits loop since 10 > 6)

Step 6: i = 6

• Number thread acquires nSema (now nSema = 0)
• 6 is divisible by 3 but not 5
• Number thread releases fSema (now fSema = 1)
• Fizz thread (waiting at i=6) acquires fSema (now fSema = 0)
• Fizz thread prints "fizz"
• Fizz thread releases nSema (now nSema = 1)
• Fizz thread moves to next iteration (i=9, exits loop since 9 > 6)

Final Output: [1, 2, "fizz", 4, "buzz", "fizz"]

The key insight is that the number thread acts as a dispatcher, examining each number and signaling the appropriate worker thread. The semaphores ensure only one thread executes at a time, maintaining the correct sequential order.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The time complexity is determined by analyzing each method's execution:

• The number method iterates from 1 to n, executing exactly n iterations: O(n)
• The fizz method iterates through multiples of 3 up to n, executing approximately n/3 iterations, but only processes numbers where i % 5 != 0, which is approximately n/3 * 4/5 = 4n/15 iterations: O(n)
• The buzz method iterates through multiples of 5 up to n, executing approximately n/5 iterations, but only processes numbers where i % 3 != 0, which is approximately n/5 * 2/3 = 2n/15 iterations: O(n)
• The fizzbuzz method iterates through multiples of 15 up to n, executing approximately n/15 iterations: O(n)

Since these methods run concurrently in separate threads and coordinate through semaphores, the overall time complexity remains O(n) as the number method drives the progression through all values from 1 to n.

Space Complexity: O(1)

The space complexity analysis:

• The class uses 4 semaphore objects (fSema, bSema, fbSema, nSema), each requiring constant space: O(1)
• One integer instance variable n is stored: O(1)
• Each method uses a constant amount of local variables (loop counter i): O(1)
• No additional data structures that grow with input size are used

The total space complexity is O(1) as the memory usage remains constant regardless of the value of n.

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

Common Pitfalls

1. Busy Waiting and CPU Waste

The provided Python solution suffers from a severe performance issue: all four threads are continuously spinning in tight while loops, constantly acquiring and releasing the lock even when it's not their turn to print. This leads to:

• High CPU usage: Threads are constantly checking conditions that will fail most of the time
• Lock contention: Threads repeatedly compete for the lock unnecessarily
• Poor scalability: Performance degrades significantly as n increases

Example of the problem: When processing number 7, all four threads will:

• Acquire the lock
• Check their condition (3 threads will fail)
• Release the lock
• Immediately try again

This happens thousands of times for each number!

2. Improved Solution Using Condition Variables

Here's a better approach that eliminates busy waiting:

import threading

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.current = 1
        self.lock = threading.Lock()
        # Use a condition variable to avoid busy waiting
        self.cv = threading.Condition(self.lock)
  
    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        for i in range(3, self.n + 1, 3):  # Only iterate through multiples of 3
            if i % 5 != 0:  # Skip multiples of 15
                with self.cv:
                    # Wait until it's our turn (current reaches i)
                    while self.current != i:
                        self.cv.wait()
                    printFizz()
                    self.current += 1
                    self.cv.notify_all()  # Wake up all waiting threads
  
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        for i in range(5, self.n + 1, 5):  # Only iterate through multiples of 5
            if i % 3 != 0:  # Skip multiples of 15
                with self.cv:
                    while self.current != i:
                        self.cv.wait()
                    printBuzz()
                    self.current += 1
                    self.cv.notify_all()
  
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        for i in range(15, self.n + 1, 15):  # Only iterate through multiples of 15
            with self.cv:
                while self.current != i:
                    self.cv.wait()
                printFizzBuzz()
                self.current += 1
                self.cv.notify_all()
  
    def number(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            if i % 3 != 0 and i % 5 != 0:  # Only handle non-fizzbuzz numbers
                with self.cv:
                    while self.current != i:
                        self.cv.wait()
                    printNumber(i)
                    self.current += 1
                    self.cv.notify_all()

3. Alternative Solution Using Semaphores (Matching the Java Approach)

For consistency with the Java solution described earlier:

import threading

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.nSema = threading.Semaphore(1)  # Number thread starts
        self.fSema = threading.Semaphore(0)  # Fizz thread blocked
        self.bSema = threading.Semaphore(0)  # Buzz thread blocked
        self.fbSema = threading.Semaphore(0) # FizzBuzz thread blocked
  
    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        for i in range(3, self.n + 1, 3):
            if i % 5 != 0:
                self.fSema.acquire()
                printFizz()
                self.nSema.release()
  
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        for i in range(5, self.n + 1, 5):
            if i % 3 != 0:
                self.bSema.acquire()
                printBuzz()
                self.nSema.release()
  
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        for i in range(15, self.n + 1, 15):
            self.fbSema.acquire()
            printFizzBuzz()
            self.nSema.release()
  
    def number(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1, self.n + 1):
            self.nSema.acquire()
            if i % 15 == 0:
                self.fbSema.release()
            elif i % 3 == 0:
                self.fSema.release()
            elif i % 5 == 0:
                self.bSema.release()
            else:
                printNumber(i)
                self.nSema.release()

Key Improvements:

1. No busy waiting: Threads sleep when it's not their turn
2. Predictable iteration: Each thread knows exactly which numbers it handles
3. Better CPU utilization: No wasted cycles checking conditions repeatedly
4. Cleaner logic: Each thread has a clear responsibility