Scale Engineer

Fizz Buzz Multithreaded

Med
#1118Time: O(N * C) where N is the input number and C is the number of threads (4). Each thread spins until `current` is incremented. In the worst case, for each number from 1 to N, all 4 threads will spin, checking the condition. The total number of checks is very high.Space: O(1) as we only use a few shared variables.

Prompt

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 ith 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a shared java.util.concurrent.atomic.AtomicInteger to track the current number in the sequence. Each of the four threads runs in a loop, continuously checking the value of this atomic integer. This is known as "busy-waiting" or a "spinlock". When a thread finds that the current number matches its condition (e.g., for the fizz thread, i % 3 == 0 && i % 5 != 0), it performs its print action and then atomically increments the counter.

Algorithm

  • Initialize a shared AtomicInteger current to 1.
  • Start four threads, each calling one of the methods: fizz, buzz, fizzbuzz, number.
  • Each thread enters a loop that runs as long as current <= n.
  • Inside the loop, each thread continuously checks if the value of current satisfies its specific condition.
  • If the condition is met, the thread prints its output and increments current.
  • If the condition is not met, the thread does nothing and continues to the next iteration of its loop, re-checking the condition.

Walkthrough

We initialize an AtomicInteger current to 1. Each of the four methods (fizz, buzz, fizzbuzz, number) enters a while loop that continues as long as current.get() <= n. Inside the loop, each thread constantly checks if it's its turn. For example, the fizz thread checks if (current.get() % 3 == 0 && current.get() % 5 != 0). If it is its turn, it calls the appropriate print function and then increments the current counter using current.getAndIncrement(). If it's not its turn, the loop continues, effectively "spinning" and consuming CPU cycles without doing useful work. This continues until the condition is met or the entire sequence is printed (current > n).

import java.util.concurrent.atomic.AtomicInteger;import java.util.function.IntConsumer; class FizzBuzz {    private int n;    private AtomicInteger current = new AtomicInteger(1);     public FizzBuzz(int n) {        this.n = n;    }     // printFizz.run() outputs "fizz".    public void fizz(Runnable printFizz) throws InterruptedException {        while (current.get() <= n) {            if (current.get() % 3 == 0 && current.get() % 5 != 0) {                printFizz.run();                current.getAndIncrement();            }        }    }     // printBuzz.run() outputs "buzz".    public void buzz(Runnable printBuzz) throws InterruptedException {        while (current.get() <= n) {            if (current.get() % 3 != 0 && current.get() % 5 == 0) {                printBuzz.run();                current.getAndIncrement();            }        }    }     // printFizzBuzz.run() outputs "fizzbuzz".    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {        while (current.get() <= n) {            if (current.get() % 15 == 0) {                printFizzBuzz.run();                current.getAndIncrement();            }        }    }     // printNumber.accept(x) outputs "x", where x is an integer.    public void number(IntConsumer printNumber) throws InterruptedException {        while (current.get() <= n) {            if (current.get() % 3 != 0 && current.get() % 5 != 0) {                printNumber.accept(current.get());                current.getAndIncrement();            }        }    }}

Complexity

Time

O(N * C) where N is the input number and C is the number of threads (4). Each thread spins until `current` is incremented. In the worst case, for each number from 1 to N, all 4 threads will spin, checking the condition. The total number of checks is very high.

Space

O(1) as we only use a few shared variables.

Trade-offs

Pros

  • Conceptually simple to understand.

  • It's a lock-free approach, which avoids potential deadlocks that can occur with explicit locks.

Cons

  • Extremely inefficient in terms of CPU usage. Threads that are not printing are stuck in a tight loop (spinlock), consuming 100% of their allocated CPU core time. This is wasteful and can significantly degrade system performance.

  • Can lead to livelock situations where threads are active but not making progress.

  • The order of execution is not guaranteed and relies on the thread scheduler, which might lead to fairness issues.

Solutions

class FizzBuzz { private int n ; public FizzBuzz ( int n ) { this . n = n ; } private Semaphore fSema = new Semaphore ( 0 ); private Semaphore bSema = new Semaphore ( 0 ); private Semaphore fbSema = new Semaphore ( 0 ); private Semaphore nSema = new Semaphore ( 1 ); // printFizz.run() outputs "fizz". public void fizz ( Runnable printFizz ) throws InterruptedException { for ( int i = 3 ; i <= n ; i = i + 3 ) { if ( i % 5 != 0 ) { fSema . acquire (); printFizz . run (); nSema . release (); } } } // printBuzz.run() outputs "buzz". public void buzz ( Runnable printBuzz ) throws InterruptedException { for ( int i = 5 ; i <= n ; i = i + 5 ) { if ( i % 3 != 0 ) { bSema . acquire (); printBuzz . run (); nSema . release (); } } } // printFizzBuzz.run() outputs "fizzbuzz". public void fizzbuzz ( Runnable printFizzBuzz ) throws InterruptedException { for ( int i = 15 ; i <= n ; i = i + 15 ) { fbSema . acquire (); printFizzBuzz . run (); nSema . release (); } } // printNumber.accept(x) outputs "x", where x is an integer. public void number ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 1 ; i <= n ; i ++) { nSema . acquire (); if ( i % 3 == 0 && i % 5 == 0 ) { fbSema . release (); } else if ( i % 3 == 0 ) { fSema . release (); } else if ( i % 5 == 0 ) { bSema . release (); } else { printNumber . accept ( i ); nSema . release (); } } } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem