Fizz Buzz Multithreaded - Leetcode Solution

Problem Statement:

You have to write a multithreaded program that outputs the numbers from 1 to n. But:

• For multiples of three, output Fizz instead of the number.
• For multiples of five, output Buzz instead of the number.
• For multiples of both three and five, output FizzBuzz instead of the number.

Solution:

To solve this problem, we will create four threads:

• Three threads for handling Fizz, Buzz, and FizzBuzz cases.
• One thread for handling the non-multiple cases.

Each thread will have a range to work with, and they will notify the next thread when their work is done using condition variables.

The non-multiple thread will start first and print the numbers that are not multiples of 3 or 5.

The Fizz and Buzz threads will take care of the multiples of 3 and 5 and notify FizzBuzz thread when their work is done.

The FizzBuzz thread will print "FizzBuzz" for the multiples of both 3 and 5.

We will use a mutex to synchronize access to the shared resource, which is the counter.

Here's the code for the multithreaded FizzBuzz problem:

class FizzBuzz {
private:
    int n;
    int cur;
    mutex m;
    condition_variable cv;

public:
    FizzBuzz(int n) {
        this->n = n;
        this->cur = 1;
    }

    void fizz(function<void()> printFizz) {
        while (true) {
            unique_lock<mutex> lk(m);
            cv.wait(lk, [&](){return !(cur % 3) && (cur % 5);});

            if (cur > n) {
                break;
            }

            printFizz();
            cur++;
            cv.notify_all();
        }
    }

    void buzz(function<void()> printBuzz) {
        while (true) {
            unique_lock<mutex> lk(m);
            cv.wait(lk, [&](){return !(cur % 5) && (cur % 3);});

            if (cur > n) {
                break;
            }

            printBuzz();
            cur++;
            cv.notify_all();
        }
    }

    void fizzbuzz(function<void()> printFizzBuzz) {
        while (true) {
            unique_lock<mutex> lk(m);
            cv.wait(lk, [&](){return !(cur % 15);});

            if (cur > n) {
                break;
            }

            printFizzBuzz();
            cur++;
            cv.notify_all();
        }
    }

    void number(function<void(int)> printNumber) {
        while (true) {
            unique_lock<mutex> lk(m);
            cv.wait(lk, [&](){return cur % 3 && cur % 5;});

            if (cur > n) {
                break;
            }

            printNumber(cur);
            cur++;
            cv.notify_all();
        }
    }
};

Explanation:

The constructor initializes the instance variables to their default values.

TheprintFizz, printBuzz, and printFizzBuzz methods are called from their respective threads after the conditions are satisfied.

The number method prints the number when it’s not a multiple of 3 or 5.

Each thread waits for its turn using the cv condition variable. When it’s their turn, they check if they have more work to do, print the answer, and notify the next thread using cv.notify_all().

The cv.wait() function can get interrupted while waiting. For example, the printFizz thread might wake up while it’s not its turn. In such cases, we use a lambda function to check whether the condition is still valid before printing the answer.

Finally, the threads will exit their infinite loops when the cur variable exceeds n.

This implementation doesn't use busy-waiting (an unnecessary use of the CPU time) as we are using condition variables to efficiently coordinate between the threads.

1