Fizz Buzz Multithreaded - Solution & Explanation

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.