Problem 41.2 · Concurrency-Aware Data StructuresMedium

Fizz Buzz Multithreaded

What it teaches: Turn-taking among several threads with a shared counter, wait() in a while loop and notifyAll().

Practise it on judges as “Fizz Buzz Multithreaded”.

In plain words

Four friends share one notebook and count from 1 to n. One may only write numbers, one only "fizz" (multiples of 3), one only "buzz" (multiples of 5), and one only "fizzbuzz" (multiples of 15). Only one can hold the notebook at a time. Whoever holds it checks the current number: if it isn't their turn they put it down and wait; if it is, they write, move to the next number and wake everyone up.

Return the sequence. Example: n = 5 → [1, 2, fizz, 4, buzz].

The problem

Four threads produce the FizzBuzz sequence for 1..n together: one writes "fizz", one "buzz", one "fizzbuzz", one the numbers. Each value must be written by the correct thread, in order. Return the sequence.

Example 1

Input: n = 5
Output: [1, 2, fizz, 4, buzz]

Constraints

1 ≤ n ≤ 50

Pattern clues in the wording

→ Several threads take turns on shared state

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

Solution · starter

import java.util.*;

class Solution {
    public List<String> fizzBuzz(int n) throws InterruptedException {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	n = 5	["1","2","fizz","4","buzz"]
2	n = 15	["1","2","fizz","4","buzz","fizz","7","8","fizz","buzz","11","fizz","13","14","fizzbuzz"]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Monitor with wait/notifyAll · O(n)

Monitor with wait/notifyAll

Time O(n) Space O(n) output

One shared counter guarded by synchronized(this). Each thread loops: while it's not its turn and i ≤ n, wait; if i > n, exit; else write and notifyAll.

▶ Dry run: One lock, a shared counter, wait/notifyAlln = 5

threads(map)

fizzbuzz: waitingfizz: waitingbuzz: waitingnumber: writes 1, 2

state(vars)

i: 3

out(list)

Step 1/4i = 1 and 2 only match the number thread's test. The others call wait(), which releases the lock. The number thread writes 1, then 2, calling notifyAll after each.

Approach 1

import java.util.*;
import java.util.function.IntFunction;
import java.util.function.IntPredicate;

class Solution {
    private int i = 1, n;
    private final List<String> out = new ArrayList<>();

    public List<String> fizzBuzz(int n) throws InterruptedException {
        this.n = n;
        Thread[] threads = {
            new Thread(() -> run(x -> x % 15 == 0, x -> "fizzbuzz")),
            new Thread(() -> run(x -> x % 3 == 0 && x % 5 != 0, x -> "fizz")),
            new Thread(() -> run(x -> x % 5 == 0 && x % 3 != 0, x -> "buzz")),
            new Thread(() -> run(x -> x % 3 != 0 && x % 5 != 0, String::valueOf)),
        };
        for (Thread t : threads) t.start();
        for (Thread t : threads) t.join();
        return out;
    }

    private void run(IntPredicate mine, IntFunction<String> text) {
        synchronized (this) {
            while (true) {
                while (i <= n && !mine.test(i)) {
                    try { wait(); } catch (InterruptedException e) { return; }
                }
                if (i > n) { notifyAll(); return; }
                out.add(text.apply(i));
                i++;
                notifyAll();
            }
        }
    }
}

Verdict: notifyAll is needed: four different conditions share one monitor.

Before you submit

Edge cases and common mistakes

Test these inputs

n < 3 (only numbers)
n = 15 (ends with fizzbuzz)

Mistakes people make

Using notify() (may wake a thread whose turn it isn't, and everyone sleeps).

Interview

Follow-up questions

How would semaphores do it?

Command Palette

The problem

Approaches

Monitor with wait/notifyAll

Edge cases and common mistakes

Follow-up questions