Fizz Buzz Multithreaded

Medium

Asked by:

8 views

Topics:

Arrays

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 i^th 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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of numbers I should handle for the FizzBuzz sequence (i.e., the upper limit)?
How many threads should I use to implement the multithreaded FizzBuzz solution?
Should each thread be responsible for printing a specific word (Fizz, Buzz, FizzBuzz, Number) or should threads coordinate to process the entire range?
Is the printing order (Fizz, Buzz, FizzBuzz, Number) strictly enforced, and if so, how should I ensure synchronization across threads?
What output mechanism should I use (e.g., print to console, store in a list, etc.)?

Brute Force Solution

Approach

The Fizz Buzz Multithreaded challenge requires printing numbers, 'Fizz', 'Buzz', or 'FizzBuzz' based on divisibility, but with multiple workers. The brute force approach involves assigning each worker a range of numbers and having them independently check each number within their range. Finally, print them in the correct order.

Here's how the algorithm would work step-by-step:

Divide the total range of numbers to be processed into smaller, equally sized chunks.
Give each chunk to a different worker to handle separately.
Each worker takes its assigned numbers and checks each one individually.
For each number, the worker checks if it's divisible by 3, 5, or both and prints 'Fizz', 'Buzz', 'FizzBuzz', or the number itself accordingly.
The workers proceed independently and may finish at different times.
After all workers are done, combine the output from each worker, maintaining the original order of numbers to produce the final result.

Code Implementation

import threading

def fizz_buzz_worker(start_number, end_number, results):
    for number in range(start_number, end_number + 1):
        if number % 3 == 0 and number % 5 == 0:
            results[number - 1] = "FizzBuzz"
        elif number % 3 == 0:
            results[number - 1] = "Fizz"
        elif number % 5 == 0:
            results[number - 1] = "Buzz"
        else:
            results[number - 1] = str(number)

def fizz_buzz_multithreaded(number_limit, number_of_workers):
    results = [None] * number_limit
    threads = []
    chunk_size = number_limit // number_of_workers

    # Divide the work into chunks for each thread
    for worker_id in range(number_of_workers):
        start_number = worker_id * chunk_size + 1
        end_number = (worker_id + 1) * chunk_size

        # Adjust the end_number for the last worker
        if worker_id == number_of_workers - 1:
            end_number = number_limit

        thread = threading.Thread(target=fizz_buzz_worker, args=(start_number, end_number, results))
        threads.append(thread)
        thread.start()

    # Wait for all threads to complete
    for thread in threads:
        thread.join()

    # Combine the results from each worker into a single list
    return results

Big(O) Analysis

Time Complexity

O(n) – The input size is 'n', representing the total range of numbers to be processed. The brute force approach involves dividing this range into chunks and assigning each chunk to a worker. Each worker iterates through its assigned numbers, performing constant-time divisibility checks for each number. Since each number is processed only once across all workers, the overall time complexity is directly proportional to the number of input values n, resulting in O(n).

Space Complexity

O(N) – The dominant space usage comes from storing the output of each worker before combining them. Each worker processes a chunk of the input range, and the combined output from all workers constitutes the final result, storing potentially N elements, where N is the total range of numbers. Specifically, each worker constructs an intermediate data structure to hold its computed results. This necessitates auxiliary space proportional to the total number of processed elements. Therefore, the space complexity is O(N).

Optimal Solution

Approach

This problem uses multiple workers to print numbers, 'Fizz', 'Buzz', and 'FizzBuzz' based on divisibility rules. The key is to coordinate these workers efficiently using a shared signaling mechanism to ensure they print in the correct order and avoid conflicts.

Here's how the algorithm would work step-by-step:

Create separate worker routines, one for printing numbers divisible by 3 ('Fizz'), one for numbers divisible by 5 ('Buzz'), one for numbers divisible by both 3 and 5 ('FizzBuzz'), and one for printing the remaining numbers.
Establish a shared counter to track the current number being processed.
Implement a signaling mechanism (like channels or semaphores) to control which worker can print at any given time.
Each worker waits for a signal indicating it's its turn to print.
The main program increments the shared counter and signals the appropriate worker based on the divisibility rules.
Workers print their assigned value and signal the main program (or the next appropriate worker) to continue the sequence.
The main program terminates all workers after the counter reaches the desired limit, ensuring everything is printed in the right sequence.

Code Implementation

import threading

class FizzBuzz:
    def __init__(self, number):
        self.number = number
        self.current_number = 1
        self.lock = threading.Lock()
        self.fizz_event = threading.Event()
        self.buzz_event = threading.Event()
        self.fizzbuzz_event = threading.Event()
        self.number_event = threading.Event()
        self.number_event.set()

    def fizz(self, print_fizz):
        while self.current_number <= self.number:
            self.fizz_event.wait()
            if self.current_number > self.number:
                break
            print_fizz()
            with self.lock:
                self.current_number += 1
                # Signal the correct routine after printing
                if self.current_number % 5 == 0 and self.current_number % 3 == 0:
                    self.fizzbuzz_event.set()
                elif self.current_number % 5 == 0:
                    self.buzz_event.set()
                elif self.current_number % 3 == 0:
                    self.fizz_event.set()
                else:
                    self.number_event.set()
            self.fizz_event.clear()

    def buzz(self, print_buzz):
        while self.current_number <= self.number:
            self.buzz_event.wait()
            if self.current_number > self.number:
                break
            print_buzz()
            with self.lock:
                self.current_number += 1
                # Signal the correct routine after printing
                if self.current_number % 5 == 0 and self.current_number % 3 == 0:
                    self.fizzbuzz_event.set()
                elif self.current_number % 5 == 0:
                    self.buzz_event.set()
                elif self.current_number % 3 == 0:
                    self.fizz_event.set()
                else:
                    self.number_event.set()
            self.buzz_event.clear()

    def fizzbuzz(self, print_fizzbuzz):
        while self.current_number <= self.number:
            self.fizzbuzz_event.wait()
            if self.current_number > self.number:
                break
            print_fizzbuzz()
            with self.lock:
                self.current_number += 1
                # Signal the correct routine after printing
                if self.current_number % 5 == 0 and self.current_number % 3 == 0:
                    self.fizzbuzz_event.set()
                elif self.current_number % 5 == 0:
                    self.buzz_event.set()
                elif self.current_number % 3 == 0:
                    self.fizz_event.set()
                else:
                    self.number_event.set()
            self.fizzbuzz_event.clear()

    def number_printer(self, print_number):
        while self.current_number <= self.number:
            self.number_event.wait()
            if self.current_number > self.number:
                break
            print_number(self.current_number)
            with self.lock:
                self.current_number += 1
                # Signal the correct routine after printing
                if self.current_number % 5 == 0 and self.current_number % 3 == 0:
                    self.fizzbuzz_event.set()
                elif self.current_number % 5 == 0:
                    self.buzz_event.set()
                elif self.current_number % 3 == 0:
                    self.fizz_event.set()
                else:
                    self.number_event.set()
            self.number_event.clear()

if __name__ == "__main__":
    fizz_buzz_instance = FizzBuzz(15)

    def print_fizz():
        print("fizz")

    def print_buzz():
        print("buzz")

    def print_fizzbuzz():
        print("fizzbuzz")

    def print_number(number):
        print(number)

    thread_fizz = threading.Thread(target=fizz_buzz_instance.fizz, args=(print_fizz,))
    thread_buzz = threading.Thread(target=fizz_buzz_instance.buzz, args=(print_buzz,))
    thread_fizzbuzz = threading.Thread(target=fizz_buzz_instance.fizzbuzz, args=(print_fizzbuzz,))
    thread_number = threading.Thread(target=fizz_buzz_instance.number_printer, args=(print_number,))

    thread_fizz.start()
    thread_buzz.start()
    thread_fizzbuzz.start()
    thread_number.start()

    thread_fizz.join()
    thread_buzz.join()
    thread_fizzbuzz.join()
    thread_number.join()

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates from 1 to n, incrementing a shared counter. In each iteration, it checks the counter's divisibility by 3 and 5. Based on these checks, it signals the appropriate worker thread (Fizz, Buzz, FizzBuzz, or Number). Each worker also performs a constant amount of work (printing) after being signaled. Therefore, the time complexity is directly proportional to n, the number of iterations.

Space Complexity

O(1) – The algorithm primarily uses a shared counter and signaling mechanisms (channels or semaphores). The space required for these is constant and independent of N, where N is the upper limit of the numbers being processed. The worker routines themselves don't create any data structures whose size scales with N. Thus, the auxiliary space remains constant regardless of the input size.

Edge Cases

Case	How to Handle
n is zero or negative	Return an empty list or throw an IllegalArgumentException as the FizzBuzz sequence is undefined for non-positive numbers.
n is a very large number causing potential integer overflow	Use appropriate data types (long) or exception handling to prevent overflow errors during calculations and string generation.
Thread creation failure or resource exhaustion	Implement proper error handling to gracefully terminate the program or retry thread creation with backoff.
n is close to Integer.MAX_VALUE causing thread synchronization issues	Ensure proper synchronization mechanisms are in place and rigorously tested to prevent race conditions.
The input 'n' exceeds the maximum allowed value (e.g., system limits)	Validate 'n' against reasonable system limits and handle the overflow by either truncating or throwing an error.
Spurious wakeups in the thread synchronization mechanisms	Implement proper condition checks within the while loop of each thread to handle spurious wakeups correctly.
Deadlock between threads due to incorrect synchronization	Carefully design and review the synchronization logic to prevent deadlocks by ensuring proper resource ordering.
Exception during thread execution causing program halt	Implement a global exception handler to log errors, handle thread termination and prevent application crash.

n is zero or negative

How to Handle:

Return an empty list or throw an IllegalArgumentException as the FizzBuzz sequence is undefined for non-positive numbers.

n is a very large number causing potential integer overflow

How to Handle:

Use appropriate data types (long) or exception handling to prevent overflow errors during calculations and string generation.

Thread creation failure or resource exhaustion

How to Handle:

Implement proper error handling to gracefully terminate the program or retry thread creation with backoff.

n is close to Integer.MAX_VALUE causing thread synchronization issues

How to Handle:

Ensure proper synchronization mechanisms are in place and rigorously tested to prevent race conditions.

The input 'n' exceeds the maximum allowed value (e.g., system limits)

How to Handle:

Validate 'n' against reasonable system limits and handle the overflow by either truncating or throwing an error.

Spurious wakeups in the thread synchronization mechanisms

How to Handle:

Implement proper condition checks within the while loop of each thread to handle spurious wakeups correctly.

Deadlock between threads due to incorrect synchronization

How to Handle:

Carefully design and review the synchronization logic to prevent deadlocks by ensuring proper resource ordering.

Exception during thread execution causing program halt

How to Handle:

Implement a global exception handler to log errors, handle thread termination and prevent application crash.