Print Zero Even Odd

MEDIUM

Description

You have a function printNumber that can be called with an integer parameter and prints it to the console.

For example, calling printNumber(7) prints 7 to the console.

You are given an instance of the class ZeroEvenOdd that has three functions: zero, even, and odd. The same instance of ZeroEvenOdd will be passed to three different threads:

Thread A: calls zero() that should only output 0's.
Thread B: calls even() that should only output even numbers.
Thread C: calls odd() that should only output odd numbers.

Modify the given class to output the series "010203040506..." where the length of the series must be 2n.

Implement the ZeroEvenOdd class:

ZeroEvenOdd(int n) Initializes the object with the number n that represents the numbers that should be printed.
void zero(printNumber) Calls printNumber to output one zero.
void even(printNumber) Calls printNumber to output one even number.
void odd(printNumber) Calls printNumber to output one odd number.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously.
One of them calls zero(), the other calls even(), and the last one calls odd().
"0102" is the correct output.

Example 2:

Input: n = 5
Output: "0102030405"

Constraints:

1 <= n <= 1000

Approaches

Checkout 3 different approaches to solve Print Zero Even Odd. Click on different approaches to view the approach and algorithm in detail.

Using `synchronized`, `wait()`, and `notifyAll()`

This approach uses Java's fundamental concurrency primitives: synchronized blocks and the wait()/notifyAll() methods. A shared state variable is used to coordinate the three threads, ensuring they print in the correct 0, 1, 0, 2, 0, 3, ... sequence.

Algorithm

A shared integer variable, turn, is used to track the current state (0 for zero, 1 for odd, 2 for even).
All three methods (zero, even, odd) are declared synchronized, using the object's intrinsic lock for mutual exclusion.
Inside each method, a thread waits in a while loop, calling wait() until the turn variable matches its required state. The loop is necessary to guard against spurious wakeups.
After printing its number, a thread updates the turn variable to signal which thread should run next.
It then calls notifyAll() to wake up all other waiting threads. The awakened threads re-check the turn variable, and the correct one proceeds.

In this method, we rely on the object's monitor lock. A state variable, turn, dictates which thread is allowed to execute. The zero thread starts first as turn is initialized to 0. It prints a zero, then decides whether the odd or even thread should run next based on the current iteration number, updates turn accordingly, and calls notifyAll(). The odd and even threads wait for their respective turn value. Once awakened and their condition is met, they print their number, set turn back to 0 for the zero thread, and also call notifyAll(). Using synchronized on the methods ensures that only one thread can modify the shared state at a time.

Complexity Analysis

Time Complexity: O(n) - Each number in the sequence is printed once. The total time is proportional to `n`, though with some overhead from thread context switching.Space Complexity: O(1) - Constant extra space is used for the state variable.

Pros and Cons

Pros:

Uses basic, built-in Java synchronization, making it a fundamental concept to understand.
The logic is contained within the methods without needing external lock objects.

Cons:

The use of notifyAll() is inefficient. It wakes up all waiting threads, even those that cannot proceed. This leads to unnecessary context switches and lock contention, a phenomenon known as the 'thundering herd' problem.

Code Solutions

Checking out 3 solutions in different languages for Print Zero Even Odd. Click on different languages to view the code.

class ZeroEvenOdd { private int n ; private Semaphore z = new Semaphore ( 1 ); private Semaphore e = new Semaphore ( 0 ); private Semaphore o = new Semaphore ( 0 ); public ZeroEvenOdd ( int n ) { this . n = n ; } // printNumber.accept(x) outputs "x", where x is an integer. public void zero ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 0 ; i < n ; ++ i ) { z . acquire ( 1 ); printNumber . accept ( 0 ); if ( i % 2 == 0 ) { o . release ( 1 ); } else { e . release ( 1 ); } } } public void even ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 2 ; i <= n ; i += 2 ) { e . acquire ( 1 ); printNumber . accept ( i ); z . release ( 1 ); } } public void odd ( IntConsumer printNumber ) throws InterruptedException { for ( int i = 1 ; i <= n ; i += 2 ) { o . acquire ( 1 ); printNumber . accept ( i ); z . release ( 1 ); } } }

Video Solution

Watch the video walkthrough for Print Zero Even Odd

Tags:

No tags found.