You have a function printNumber that can be called with an integer parameter and prints it to the console.
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:
zero() that should only output 0's.even() that should only output even numbers.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 <= 1000Problem Overview: You control three threads: one prints 0, one prints even numbers, and one prints odd numbers. The output must follow the pattern 0 1 0 2 0 3 ... 0 n. The challenge is coordinating thread execution so the correct thread prints at the correct time without race conditions.
Approach 1: Using Mutex and Condition Variables (O(n) time, O(1) space)
This approach coordinates threads using a shared mutex and condition variables. A shared state variable determines which thread should run next: zero, odd, or even. Each thread acquires the mutex, checks the state, and waits on a condition variable if it is not its turn. When the correct thread prints its value, it updates the state and signals the next waiting thread using notify or signal. The zero thread runs before every number, alternating between odd and even threads depending on the current value. The complexity is O(n) because each number is printed once, and the synchronization overhead is constant. Space complexity is O(1) since only a few shared variables are maintained.
This technique relies on primitives from concurrency such as mutex locks and condition variables. It provides fine-grained control and avoids busy waiting. Systems programming interviews sometimes prefer this method because it demonstrates understanding of thread coordination and lock-based synchronization.
Approach 2: Using Semaphores (O(n) time, O(1) space)
Semaphores simplify the coordination logic by directly controlling which thread is allowed to proceed. Three semaphores are used: one for the zero thread, one for odd numbers, and one for even numbers. The zero semaphore starts with value 1 so the zero thread prints first. After printing 0, the zero thread releases either the odd or even semaphore depending on the next number. The corresponding thread prints its value and then releases the zero semaphore to continue the sequence.
This pattern ensures only one thread runs at a time while preserving the required order. Every print operation corresponds to one semaphore acquire and release, giving O(n) total operations. Space usage remains O(1). Semaphores are a classic tool in concurrency control and often appear in interview problems involving ordered thread execution. If you are comfortable with semaphores, this implementation is typically shorter and easier to reason about than condition variables.
Recommended for interviews: The semaphore solution is usually the cleanest and easiest to explain under time pressure. It clearly expresses which thread runs next using semaphore permits. The mutex + condition variable approach is also valid and demonstrates deeper knowledge of synchronization primitives. Showing the ability to model thread states and prevent race conditions is what interviewers typically look for in concurrency problems.
This approach uses mutexes and condition variables to synchronize the threads. The zero function signals either the odd or even function after printing a zero. The even and odd functions wait for their respective conditions to be signaled to proceed. This ensures that the numbers are printed in the correct order.
Here, we initialize three Lock objects: zero_lock, even_lock, and odd_lock. At the start, we acquire zero_lock to ensure Thread A (zero) is the one beginning the sequence. The even_lock and odd_lock are also acquired initially, meaning the even and odd threads will be waiting. The zero method prints 0 and releases the lock for either odd or even methods based on the sequence. This ensures the correct sequence is maintained.
Time Complexity: O(n), since we loop through n iterations for each function.
Space Complexity: O(1), as we use a fixed amount of additional memory for lock objects.
Semaphores are used to manage access to shared resources by multiple threads in a concurrent system. In this solution, semaphores manage the permit distribution so that no two threads execute their print function simultaneously. This controls the order of function executions.
This Java solution utilizes the Semaphore class for synchronization. Initially, the zeroSemaphore permits one thread to print '0'. Subsequent odd or even semaphore releases permit specific threads to print their respective numbers. By carefully releasing and acquiring these semaphores, the correct order is maintained.
Java
JavaScript
Time Complexity: O(n), each thread iterates through a portion of n values.
Space Complexity: O(1), as semaphore footprint is constant regardless of n.
We use three semaphores z, e, and o to control the execution order of the three threads, where z is initially set to 1, and e and o are set to 0.
z controls the execution of the zero function. When the value of semaphore z is 1, the zero function can be executed. After execution, the value of semaphore z is set to 0, and the value of semaphore e or o is set to 1, depending on whether the even function or the odd function needs to be executed next.e controls the execution of the even function. When the value of semaphore e is 1, the even function can be executed. After execution, the value of semaphore z is set to 1, and the value of semaphore e is set to 0.o controls the execution of the odd function. When the value of semaphore o is 1, the odd function can be executed. After execution, the value of semaphore z is set to 1, and the value of semaphore o is set to 0.The time complexity is O(n), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Using Mutex and Condition Variables | Time Complexity: O(n), since we loop through n iterations for each function. |
| Approach 2: Using Semaphores | Time Complexity: O(n), each thread iterates through a portion of n values. |
| Multithreading + Semaphore | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mutex and Condition Variables | O(n) | O(1) | When demonstrating low-level thread coordination and lock-based synchronization |
| Semaphores | O(n) | O(1) | Preferred for clarity and simpler ordered thread execution logic |
Leetcode 1116 Print Zero Even Odd (Java Concurrency) • TheAnalyticGuy • 2,093 views views
Watch 6 more video solutions →Practice Print Zero Even Odd with our built-in code editor and test cases.
Practice on FleetCode