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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Print in Order

Number: 1203

Difficulty: Easy

Paid? No

Companies: Nvidia, Microsoft, Google

Problem Description

Design a mechanism so that when three separate threads invoke the methods first(), second(), and third() concurrently, the output always prints "firstsecondthird". Even though the threads may be scheduled in any order, the method calls must be executed in the order: first() → second() → third().

Key Insights

  • Threads can be scheduled in an unpredictable manner, so explicit synchronization is required.
  • Use of synchronization primitives such as semaphores, locks, events, or countdown latches can enforce the required order.
  • The key is to block the execution of second() until first() has finished, and similarly block third() until second() is done.

Space and Time Complexity

Time Complexity: O(1) per method call. Space Complexity: O(1) for the synchronization primitives.

Solution

We enforce the ordering by using synchronization primitives. In our solution, we use two signaling mechanisms:

  1. After executing first(), signal that second() is allowed to run.
  2. After executing second(), signal that third() is allowed to run. For example, in Python we might use threading.Event objects; in Java we can use CountDownLatch; in C++ we can use condition variables with mutexes; and in JavaScript we can simulate the behavior using promises. These structures ensure that each thread is blocked until the previous task has completed.

Code Solutions

import threading

class Foo:
    def __init__(self):
        # Create events to signal completion of first and second tasks.
        self.first_done = threading.Event()
        self.second_done = threading.Event()

    def first(self):
        # Print "first" and then signal that first is done.
        print("first", end="")
        self.first_done.set()

    def second(self):
        # Wait until first() has been executed.
        self.first_done.wait()
        # Print "second" and then signal that second is done.
        print("second", end="")
        self.second_done.set()

    def third(self):
        # Wait until second() has been executed.
        self.second_done.wait()
        # Print "third".
        print("third", end="")

# Example usage:
# foo = Foo()
# threading.Thread(target=foo.first).start()
# threading.Thread(target=foo.second).start()
# threading.Thread(target=foo.third).start()
← Back to All Questions