Print Zero Even Odd
MedPrompt
You have a function printNumber that can be called with an integer parameter and prints it to the console.
- For example, calling
printNumber(7)prints7to 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 output0'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 numbernthat represents the numbers that should be printed.void zero(printNumber)CallsprintNumberto output one zero.void even(printNumber)CallsprintNumberto output one even number.void odd(printNumber)CallsprintNumberto 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
3 approaches with complexity analysis and trade-offs.
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 forzero, 1 forodd, 2 foreven). - All three methods (
zero,even,odd) are declaredsynchronized, using the object's intrinsic lock for mutual exclusion. - Inside each method, a thread waits in a
whileloop, callingwait()until theturnvariable matches its required state. The loop is necessary to guard against spurious wakeups. - After printing its number, a thread updates the
turnvariable to signal which thread should run next. - It then calls
notifyAll()to wake up all other waiting threads. The awakened threads re-check theturnvariable, and the correct one proceeds.
Walkthrough
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
Time
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
O(1) - Constant extra space is used for the state variable.
Trade-offs
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.
This approach enhances synchronization by using ReentrantLock and Condition objects from the java.util.concurrent.locks package. It provides more fine-grained control over thread signaling, which is more efficient than the notifyAll()-based method.
Algorithm
- An explicit
ReentrantLockis used for mutual exclusion instead of an intrinsic lock. - Three
Conditionobjects (zeroTurn,evenTurn,oddTurn) are created from the lock, one for each thread's waiting condition. - A shared
turnvariable (0, 1, or 2) still tracks the state. - Each thread acquires the
lock, then waits on its specificConditionobject (e.g.,eventhread callsevenTurn.await()) until its turn arrives. - After printing, a thread updates the
turnstate and callssignal()on theConditionobject of the next thread in the sequence. - The lock is released in a
finallyblock to ensure it's always unlocked.
Walkthrough
By using separate Condition objects, we can create distinct waiting queues for each thread. When the zero thread finishes, it doesn't just wake up a random thread; it specifically signals the condition for the next thread in the sequence (oddTurn or evenTurn). This targeted signaling (signal()) is a major improvement over notifyAll(), as it wakes up only one relevant thread, avoiding the thundering herd problem. This reduces unnecessary wake-ups, context switches, and lock contention, leading to better performance.
Complexity
Time
O(n) - The overall complexity is linear, but it's generally faster than the `notifyAll()` approach due to more efficient thread management.
Space
O(1) - Constant extra space is used for the lock, condition objects, and state variable.
Trade-offs
Pros
More efficient than
notifyAll()becausesignal()wakes up only one specific thread, preventing the 'thundering herd' problem.ReentrantLockoffers more features than intrinsic locks, such as timed waits and interruptible lock acquisition.
Cons
The code is more verbose than the
synchronizedversion due to the need for explicitlock()andunlock()calls, typically within atry...finallyblock.
This is a highly elegant and efficient solution that uses semaphores to manage the execution order. Semaphores act as permits that threads must acquire to proceed, providing a clean and direct way to control the sequence of operations.
Algorithm
- Three
Semaphoreobjects are used:semZero,semEven, andsemOdd. semZerois initialized with 1 permit, allowing thezerothread to run first.semEvenandsemOddare initialized with 0 permits, forcing them to block initially.- Each thread's main loop starts by calling
acquire()on its corresponding semaphore. This blocks the thread until a permit is available. - The
zerothread, after printing 0, callsrelease()on eithersemOddorsemEvento grant a permit to the next thread. - The
oddandeventhreads, after printing their numbers, callrelease()onsemZeroto pass control back to thezerothread.
Walkthrough
This approach models the problem as a hand-off of a single execution permit. The semZero starts with the permit. The zero thread acquires it, does its work, and then releases a permit to the appropriate next semaphore (semOdd or semEven). The corresponding thread then acquires that permit, does its work, and releases a permit back to semZero. This cycle continues until all numbers are printed. This method is very clean because it doesn't require an explicit shared state variable like turn or explicit locking. The state is implicitly managed by which semaphore currently holds a permit.
Complexity
Time
O(n) - A very performant linear time solution due to the efficiency of semaphores.
Space
O(1) - Constant extra space is used for the three semaphore objects.
Trade-offs
Pros
The code is very concise and directly reflects the turn-based nature of the problem.
Highly efficient, as semaphore operations are typically implemented with low-level, optimized system calls.
Avoids explicit state variables and locking, which can reduce code complexity and potential for errors.
Cons
The concept of semaphores might be less familiar to some developers compared to intrinsic locks.
Solutions
Solution
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 ); } } }#include <semaphore.h> class ZeroEvenOdd { private: int n ; sem_t z , e , o ; public: ZeroEvenOdd ( int n ) { this -> n = n ; sem_init ( & z , 0 , 1 ); sem_init ( & e , 0 , 0 ); sem_init ( & o , 0 , 0 ); } // printNumber(x) outputs "x", where x is an integer. void zero ( function < void ( int ) > printNumber ) { for ( int i = 0 ; i < n ; ++ i ) { sem_wait ( & z ); printNumber ( 0 ); if ( i % 2 == 0 ) { sem_post ( & o ); } else { sem_post ( & e ); } } } void even ( function < void ( int ) > printNumber ) { for ( int i = 2 ; i <= n ; i += 2 ) { sem_wait ( & e ); printNumber ( i ); sem_post ( & z ); } } void odd ( function < void ( int ) > printNumber ) { for ( int i = 1 ; i <= n ; i += 2 ) { sem_wait ( & o ); printNumber ( i ); sem_post ( & z ); } } };from threading import Semaphore class ZeroEvenOdd : def __init__ ( self , n ): self . n = n self . z = Semaphore ( 1 ) self . e = Semaphore ( 0 ) self . o = Semaphore ( 0 ) # printNumber(x) outputs "x", where x is an integer. def zero ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( self . n ): self . z . acquire () printNumber ( 0 ) if i % 2 == 0 : # 'i%2==1' will have wrong answer "0201" self . o . release () else : self . e . release () def even ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 2 , self . n + 1 , 2 ): self . e . acquire () printNumber ( i ) self . z . release () def odd ( self , printNumber : 'Callable[[int], None]' ) -> None : for i in range ( 1 , self . n + 1 , 2 ): self . o . acquire () printNumber ( i ) self . z . 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.