Watch 10 video solutions for Print in Order, a easy level problem involving Concurrency. This walkthrough by Eugene Suleimanov has 6,243 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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].Problem Overview: Three methods first(), second(), and third() are executed by separate threads. The threads can start in any order, but the output must always be "first", then "second", then "third". The challenge is coordinating threads so later steps wait until earlier ones finish.
This problem tests basic synchronization patterns from concurrency. You must enforce ordering without relying on thread start order. The core idea: block a thread until the previous step signals completion.
Approach 1: Using Semaphores (O(1) time, O(1) space)
This solution uses two semaphores to control execution order. Initialize both semaphores with value 0. The first() method prints and then releases the first semaphore, allowing second() to proceed. The second() method waits on the first semaphore, prints, then releases the second semaphore so third() can run.
The key insight: a semaphore acts as a gate. Threads calling acquire() block until another thread calls release(). This makes it easy to chain execution order across threads. Each method performs constant operations—one acquire or release—so runtime is O(1) and extra space is O(1). This pattern is common when learning semaphores and basic thread signaling.
Approach 2: Using Locks and Conditions (O(1) time, O(1) space)
This approach uses a shared state variable protected by a lock and condition variables. Maintain an integer flag representing progress: 1 means first finished, 2 means second finished. The second() method waits on the condition until the flag indicates that first() completed. The third() method waits until the flag shows that second() completed.
The lock guarantees mutual exclusion while checking or updating the state. Condition variables allow threads to sleep efficiently instead of busy waiting. When a step finishes, it updates the flag and signals waiting threads. Each method performs a constant number of lock operations and checks, giving O(1) time and O(1) space. This pattern appears frequently in systems programming and problems involving locks and thread coordination.
Recommended for interviews: The semaphore solution is usually the clearest. It directly models dependency between steps using simple acquire/release operations. Showing the lock + condition approach demonstrates deeper understanding of thread coordination primitives. Both run in O(1) time and O(1) space, but semaphores require less boilerplate and are easier to reason about under interview pressure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Semaphores | O(1) | O(1) | Best for enforcing execution order between threads with minimal code |
| Locks and Conditions | O(1) | O(1) | Useful when managing shared state with explicit locking and condition signaling |