Print Zero Even Odd

Medium

Asked by:

4 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Print Zero Even Odd

Medium

Asked by:

4 views

Topics:

Bit Manipulation

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input integer 'n'? Can 'n' be zero or negative?
What synchronization primitives are available (e.g., Semaphores, Locks, Condition Variables)? Should I assume a specific implementation?
Is there a requirement for fairness in the scheduling of the threads (e.g., must 'printOdd' and 'printEven' alternate predictably if both are ready)?
What should happen if the threads encounter an exception or error during execution? Is error handling required?
Are we optimizing for any specific thread scheduling behavior or priorities? Should I avoid busy-waiting, for example?

Brute Force Solution

Approach

We want to print numbers in a specific order: first zero, then even, then odd, using multiple threads. The brute force method isn't typically the right fit here, but we can imagine it as exhaustively managing turns for each thread.

Here's how the algorithm would work step-by-step:

Imagine each number (zero, even, odd) has a thread dedicated to printing it.
To ensure the correct order, we could give one thread permission to print at a time based on a rigid schedule: Zero thread goes first.
Then, the even number thread gets a chance to print. It must print an even number.
Next, the odd number thread prints an odd number.
We keep repeating this sequence (Zero, Even, Odd), granting permission to each thread in turn.
Before each thread prints, it would check if it's its turn. If not, it waits. After it prints, it signals the next thread in line.
This forces a very controlled and predictable order, ensuring we always see a zero, then an even number, then an odd number, and so on.

Code Implementation

import threading

class ZeroEvenOdd:
    def __init__(self, maximum_number):
        self.maximum_number = maximum_number
        self.current_number = 1
        self.turn = 0  # 0: zero, 1: even, 2: odd
        self.lock = threading.Lock()
        self.zero_event = threading.Event()
        self.even_event = threading.Event()
        self.odd_event = threading.Event()

    def zero(self, print_number):
        for _ in range(self.maximum_number):
            with self.lock:
                self.zero_event.wait()
                print_number(0)
                if self.current_number % 2 == 0:
                    self.turn = 1  # Next turn: even
                    self.even_event.set()
                else:
                    self.turn = 2  # Next turn: odd
                    self.odd_event.set()
                self.zero_event.clear()

    def even(self, print_number):
        while self.current_number <= self.maximum_number:
            with self.lock:
                self.even_event.wait()
                # Ensure that we have not exceeded max_number
                if self.current_number > self.maximum_number:
                    self.even_event.clear()
                    break

                print_number(self.current_number)
                self.current_number += 1
                self.turn = 0  # Next turn: zero
                self.zero_event.set()
                self.even_event.clear()

    def odd(self, print_number):
        while self.current_number <= self.maximum_number:
            with self.lock:
                self.odd_event.wait()
                # Ensure that we have not exceeded max_number
                if self.current_number > self.maximum_number:
                    self.odd_event.clear()
                    break

                print_number(self.current_number)
                self.current_number += 1
                self.turn = 0  # Next turn: zero
                self.zero_event.set()
                self.odd_event.clear()

    def start(self):
        self.zero_event.set()

if __name__ == "__main__":
    number = 5
    zero_even_odd_instance = ZeroEvenOdd(number)

    def print_number(number):
        print(number, end="")

    zero_thread = threading.Thread(target=zero_even_odd_instance.zero, args=(print_number,))
    even_thread = threading.Thread(target=zero_even_odd_instance.even, args=(print_number,))
    odd_thread = threading.Thread(target=zero_even_odd_instance.odd, args=(print_number,))

    zero_thread.start()
    even_thread.start()
    odd_thread.start()

    zero_even_odd_instance.start()

    zero_thread.join()
    even_thread.join()
    odd_thread.join()

Big(O) Analysis

Time Complexity

O(n) – The code iterates to print 'n' numbers (zero, even, or odd). Each thread essentially waits its turn to print, and once it's its turn, it prints a single number in O(1) time. The sequence of zero, even, odd repeats until 'n' numbers are printed. Thus, the time complexity is directly proportional to the number of integers 'n' to be printed, resulting in O(n).

Space Complexity

O(1) – The described solution uses a fixed number of synchronization primitives (e.g., semaphores, locks, or condition variables) and potentially a shared counter or turn indicator, irrespective of the value of N (the number up to which we are printing). These synchronization objects and the counter occupy a constant amount of extra memory. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to coordinate multiple threads to print numbers in a specific order: zero, even, then odd. We achieve this by using synchronization mechanisms that allow each thread to wait for its turn and signal the next thread in the sequence.

Here's how the algorithm would work step-by-step:

Create three separate processes for printing: one for zeros, one for even numbers, and one for odd numbers.
Use signaling objects like semaphores or locks to control the sequence. Initially, give the 'zero' process permission to print.
The 'zero' process prints a zero, then signals the 'even' or 'odd' process depending on whether the current number is even or odd.
The appropriate 'even' or 'odd' process waits for the signal, prints its number, then signals back to the 'zero' process.
Repeat the process until all numbers have been printed. Ensure that each process properly releases its lock or semaphore, allowing the next process to proceed in the correct order.

Code Implementation

import threading

class ZeroEvenOdd:
    def __init__(self, n):
        self.number = n
        self.zero_turn = True
        self.even_turn = False
        self.odd_turn = False
        self.lock = threading.Lock()
        self.condition = threading.Condition(self.lock)

    def zero(self, printNumber):
        for i in range(self.number):
            with self.condition:
                while not self.zero_turn:
                    self.condition.wait()

                printNumber(0)

                self.zero_turn = False

                # Alternate between even and odd turn
                if (i + 1) % 2 == 0:
                    self.even_turn = True
                else:
                    self.odd_turn = True

                self.condition.notify_all()

    def even(self, printNumber):
        for i in range(2, self.number + 1, 2):
            with self.condition:
                while not self.even_turn:
                    self.condition.wait()

                printNumber(i)
                self.even_turn = False

                # After printing even, give zero turn
                self.zero_turn = True

                self.condition.notify_all()

    def odd(self, printNumber):
        for i in range(1, self.number + 1, 2):
            with self.condition:
                while not self.odd_turn:
                    self.condition.wait()

                printNumber(i)
                self.odd_turn = False

                # After printing odd, give zero turn
                self.zero_turn = True

                self.condition.notify_all()

# Example usage (can't be run without a printNumber function)
# def print_number(x):
#     print(x, end='')
#
# n = 5
# zero_even_odd = ZeroEvenOdd(n)
#
# zero_thread = threading.Thread(target=zero_even_odd.zero, args=(print_number,))
# even_thread = threading.Thread(target=zero_even_odd.even, args=(print_number,))
# odd_thread = threading.Thread(target=zero_even_odd.odd, args=(print_number,))
#
# zero_thread.start()
# even_thread.start()
# odd_thread.start()
#
# zero_thread.join()
# even_thread.join()
# odd_thread.join()

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates 'n' times, where 'n' is the number of integers to be printed. Each of the three threads (zero, even, odd) waits for its turn and then performs a constant amount of work: printing a number and signaling the next thread. The number of iterations is directly proportional to 'n', thus the time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily uses semaphores or locks to coordinate the threads. These synchronization primitives occupy a fixed amount of memory regardless of how many numbers are printed (represented by N). The number of threads is constant (three: zero, even, and odd printers). Therefore, the space complexity is independent of the input size N, resulting in constant auxiliary space.

Edge Cases

Case	How to Handle
n is zero	The program should print only '0' once and then terminate gracefully without entering the loop.
n is one	The program should print '01' and then terminate.
n is negative	Treat n as zero, printing only '0' once and returning, or throw an IllegalArgumentException.
Large n leading to potential integer overflow when calculating even/odd numbers	Use a data type (like long) that can accommodate the range of numbers or implement overflow checks.
Thread starvation of one of the threads	Use proper synchronization mechanisms (e.g., Semaphores, Locks, Condition Variables) to ensure fair thread execution and prevent indefinite waiting.
Spurious wakeups affecting synchronization	Use while loops with condition variable checks to handle spurious wakeups correctly.
n is a very large number and printing becomes slow	Consider using a thread pool to print multiple numbers in parallel if output speed is critical for very large n.
Interrupting the threads while they are waiting	Handle InterruptedExceptions gracefully, allowing the threads to exit cleanly and stop the printing process.