Suppose we have a class:
public class Foo {
public void first() { print("first"); }
public void second() { print("second"); }
public void third() { print("third"); }
}
The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().
Note:
We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.
Example 1:
Input: nums = [1,2,3] Output: "firstsecondthird" Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.
Example 2:
Input: nums = [1,3,2] Output: "firstsecondthird" Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.
Constraints:
nums is a permutation of [1, 2, 3].The key challenge in #1114 Print in Order is coordinating multiple threads so that three functions execute in the strict order: first(), second(), and third(). Since threads may start at unpredictable times, the solution requires a synchronization mechanism to enforce ordering.
A common approach is to use primitives such as semaphores, mutex locks with condition variables, or atomic flags. The idea is to allow the first() function to run immediately, while the other functions wait until the previous step signals completion. For example, once first() finishes, it releases a signal that allows second() to proceed. Similarly, second() signals when third() can run.
This design ensures deterministic ordering even in a concurrent environment. Since the operations involve only signaling and minimal state tracking, the runtime overhead remains constant and memory usage is minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Synchronization using Semaphores / Locks | O(1) | O(1) |
NeetCode
This approach employs semaphores to control the execution order of methods. Since semaphores are synchronization constructs that can be used to control access to a common resource in a concurrent system, we can use them to gate the execution of 'second' and 'third' methods until 'first' and 'second' have completed, respectively. The semaphore for 'second' starts at 0 and is incremented by 'first', allowing 'second' to run. Similarly, 'third' can proceed only after 'second' increments its semaphore.
Time Complexity: O(1) for each method call. Space Complexity: O(1).
1from threading import Semaphore
2
3class Foo:
4 def __init__(self):
5 self.second_semaphore = Semaphore(0)
6 self.third_semaphore = Semaphore(0)
7
8 def first(self, printFirst: 'Callable[[], None]') -> None:
9 printFirst()
10 self.second_semaphore.release()
11
12 def second(self, printSecond: 'Callable[[], None]') -> None:
13 self.second_semaphore.acquire()
14 printSecond()
15 self.third_semaphore.release()
16
17 def third(self, printThird: 'Callable[[], None]') -> None:
18 self.third_semaphore.acquire()
19 printThird()In Python, we utilize the Semaphore class from the threading module. We initiate two semaphores, each initialized to 0. The first method prints 'first' and then releases the semaphore for second. The second method waits (acquires) on the semaphore before printing 'second' and then releases the semaphore for third. The third method waits (acquires) on its semaphore before printing 'third'.
This approach leverages locks and condition variables to achieve the desired execution order. By associating each method with a condition variable, the appropriate method waits (and releases lock) until the previous condition is signaled, facilitating the required sequence.
Time Complexity: O(1) for each method call. Space Complexity: O(1).
1from threading import Lock, Condition
2
3class Foo
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, concurrency problems like Print in Order are occasionally asked in interviews at large tech companies. They test understanding of thread coordination, synchronization primitives, and race condition prevention.
The optimal approach uses synchronization primitives such as semaphores, mutexes with condition variables, or atomic flags. These mechanisms ensure that each function waits until the previous one signals completion, guaranteeing the correct execution order.
The logic is straightforward once you understand basic thread synchronization. The problem mainly checks whether you can enforce execution order using simple signaling techniques rather than complex algorithms.
Concurrency primitives like semaphores or locks are most suitable for this problem. They provide controlled signaling between threads so that one function can safely wait for another to finish before continuing.
In Python, we use a lock with condition variables to ensure proper sequencing. The first method sets a flag and notifies other methods once it completes. Second waits until the first_done is True and proceeds similarly for third, which waits for second_done.