How do you approach FizzBuzz Multithreaded?

Each thread loops: lock, check whether the current counter value matches its role, print and advance, or wait.

What is the time complexity of FizzBuzz Multithreaded?

Time complexity: O(n) prints. Space complexity: O(1).

What are common mistakes on FizzBuzz Multithreaded?

Re-checking a condition with if instead of while after waiting. Spurious wakeups are real. Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock. Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

gitGood.dev

← Back to problems

FizzBuzz Multithreaded

HardOperating Systems

Description

**Concurrency design problem (paper-only).** Threading is not available in the sandbox; the auto-grader validates a single-threaded equivalent. You have a class `FizzBuzz` shared by four threads. Each thread is responsible for one role: - Thread 1: prints `"fizz"` for numbers divisible by 3 but not 5. - Thread 2: prints `"buzz"` for numbers divisible by 5 but not 3. - Thread 3: prints `"fizzbuzz"` for numbers divisible by both 3 and 5. - Thread 4: prints the number itself for numbers not divisible by 3 or 5. For a positive integer `n`, the threads collectively output the FizzBuzz sequence from `1` to `n`, separated by spaces. **For the auto-grader:** implement `fizzBuzzSeq(n)` returning the joined sequence. Your implementation should make explicit the role-dispatch each thread would perform - in the explanation we describe the four-thread design with a shared counter and per-role wake conditions.

Example 1

Input: n = 5

Output: "1 2 fizz 4 buzz"

Example 2

Input: n = 15

Output: "1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz"

Constraints

- 1 <= n <= 50

FizzBuzz Multithreaded: approach, complexity and pitfalls

A hard concurrency problem, graded against 5 test cases (2 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

Each thread loops: lock, check whether the current counter value matches its role, print and advance, or wait.
Use a single condition variable plus a 'current value' counter; signalAll on advance so the right role wakes up.
For the grader, just dispatch each integer to the right role and join with spaces.

The optimal approach

Show the approach: Real concurrent design

```

class FizzBuzz:

n: int

cur: int = 1

lock: Mutex

cv: ConditionVariable

def role(self, predicate, emit):

while True:

with self.lock:

while self.cur <= self.n and not predicate(self.cur):

self.cv.wait(self.lock)

if self.cur > self.n:

self.cv.notify_all()

return

emit(self.cur)

self.cur += 1

self.cv.notify_all()

fizz(): self.role(lambda x: x % 3 == 0 and x % 5 != 0, lambda x: print("fizz"))

buzz(): self.role(lambda x: x % 5 == 0 and x % 3 != 0, lambda x: print("buzz"))

fizzbuzz(): self.role(lambda x: x % 15 == 0, lambda x: print("fizzbuzz"))

number(): self.role(lambda x: x % 3 != 0 and x % 5 != 0, lambda x: print(x))

```

Each thread waits until its predicate matches the current counter, then prints and advances. The notify_all on advance wakes whichever role is responsible next.

Time: O(n) prints
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

← Back to problems

FizzBuzz Multithreaded

HardOperating Systems

Description

Example 1

Input: n = 5

Output: "1 2 fizz 4 buzz"

Example 2

Input: n = 15

Output: "1 2 fizz 4 buzz fizz 7 8 fizz buzz 11 fizz 13 14 fizzbuzz"

Constraints

- 1 <= n <= 50

FizzBuzz Multithreaded: approach, complexity and pitfalls

A hard concurrency problem, graded against 5 test cases (2 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

Each thread loops: lock, check whether the current counter value matches its role, print and advance, or wait.
Use a single condition variable plus a 'current value' counter; signalAll on advance so the right role wakes up.
For the grader, just dispatch each integer to the right role and join with spaces.

The optimal approach

Show the approach: Real concurrent design

```

class FizzBuzz:

n: int

cur: int = 1

lock: Mutex

cv: ConditionVariable

def role(self, predicate, emit):

while True:

with self.lock:

while self.cur <= self.n and not predicate(self.cur):

self.cv.wait(self.lock)

if self.cur > self.n:

self.cv.notify_all()

return

emit(self.cur)

self.cur += 1

self.cv.notify_all()

fizz(): self.role(lambda x: x % 3 == 0 and x % 5 != 0, lambda x: print("fizz"))

buzz(): self.role(lambda x: x % 5 == 0 and x % 3 != 0, lambda x: print("buzz"))

fizzbuzz(): self.role(lambda x: x % 15 == 0, lambda x: print("fizzbuzz"))

number(): self.role(lambda x: x % 3 != 0 and x % 5 != 0, lambda x: print(x))

```

Each thread waits until its predicate matches the current counter, then prints and advances. The notify_all on advance wakes whichever role is responsible next.

Time: O(n) prints
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.