We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Print Zero Even Odd

Number: 1216

Difficulty: Medium

Paid? No

Companies: Goldman Sachs

Problem Description

Design a synchronization mechanism for three threads such that one thread prints zeros, one prints even numbers, and one prints odd numbers. The goal is to output a series in the format "01020304..." with a total length of 2n, where n represents the number of non-zero numbers printed.

Key Insights

  • Use synchronization primitives (like semaphores) to control the order of execution between three threads.
  • The printing order is always a zero followed by either an odd or an even number.
  • The zero thread prints zero n times and then signals either the odd or even thread based on the current count.
  • Avoid race conditions by ensuring proper signaling between threads.

Space and Time Complexity

Time Complexity: O(n) – Each thread loops over roughly n/iterations. Space Complexity: O(1) – Only a fixed number of synchronization primitives are used.

Solution

We use semaphores to coordinate printing between the three threads. The zero thread is allowed to run first and prints a zero for each iteration. Then, depending on whether the current number is even or odd, it signals the respective thread. After the odd or even thread prints its number, it signals back to the zero thread to proceed with the next iteration. This guarantees the order of "zero, number" repeatedly until 2n characters are printed.

Data Structures/Techniques:

  • Semaphores: Used to control which thread is allowed to print.
  • Thread synchronization: Ensures that zero, odd, and even are printed in the correct order without interleaving.

Code Solutions

import threading

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n                              # Total numbers to print
        self.sem_zero = threading.Semaphore(1)  # Semaphore for zero; initially available
        self.sem_odd = threading.Semaphore(0)   # Semaphore for odd; initially blocked
        self.sem_even = threading.Semaphore(0)  # Semaphore for even; initially blocked

    def zero(self, printNumber):
        for num in range(1, self.n + 1):
            self.sem_zero.acquire()             # Wait until allowed to print zero
            printNumber(0)                      # Print zero
            # Signal the appropriate number thread based on current number's parity
            if num % 2 == 0:
                self.sem_even.release()         # If even, signal the even thread
            else:
                self.sem_odd.release()          # If odd, signal the odd thread

    def odd(self, printNumber):
        for num in range(1, self.n + 1, 2):
            self.sem_odd.acquire()              # Wait for zero thread to signal odd
            printNumber(num)                    # Print odd number
            self.sem_zero.release()             # Signal zero thread for next iteration

    def even(self, printNumber):
        for num in range(2, self.n + 1, 2):
            self.sem_even.acquire()             # Wait for zero thread to signal even
            printNumber(num)                    # Print even number
            self.sem_zero.release()             # Signal zero thread for next iteration
← Back to All Questions