Print in Order
EasyPrompt
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:
numsis a permutation of[1, 2, 3].
Approaches
4 approaches with complexity analysis and trade-offs.
This approach utilizes java.util.concurrent.CountDownLatch, a high-level synchronization aid. A latch acts as a gate that remains closed until its internal count reaches zero. We use two latches to create a dependency chain: second() waits for the first latch, and third() waits for the second latch.
Algorithm
- Initialize two
CountDownLatchobjects,latch1andlatch2, both with a count of 1. first(): Executes its logic, then callslatch1.countDown(). This decrements the latch's count to 0, releasing any threads waiting on it.second(): First, it callslatch1.await(), which blocks the thread untillatch1's count becomes 0. After being released, it executes its logic and then callslatch2.countDown().third(): Callslatch2.await(), which blocks untilsecond()has completed and counted downlatch2. Then, it executes its logic.
Walkthrough
This approach utilizes java.util.concurrent.CountDownLatch, a high-level synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes. A latch is initialized with a given count. Threads can wait on the latch using await(), and they will block until the count is decremented to zero by other threads calling countDown(). We use two latches to create a dependency chain: second() waits for the first latch (released by first()), and third() waits for the second latch (released by second()).
- Initialize two
CountDownLatchobjects,latch1andlatch2, both with a count of 1. first(): Executes its logic, then callslatch1.countDown(). This decrements the latch's count to 0, releasing any threads waiting on it.second(): First, it callslatch1.await(), which blocks the thread untillatch1's count becomes 0. After being released, it executes its logic and then callslatch2.countDown().third(): Callslatch2.await(), which blocks untilsecond()has completed and counted downlatch2. Then, it executes its logic.
import java.util.concurrent.CountDownLatch; class Foo { private CountDownLatch latchForSecond; private CountDownLatch latchForThird; public Foo() { latchForSecond = new CountDownLatch(1); latchForThird = new CountDownLatch(1); } public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); latchForSecond.countDown(); } public void second(Runnable printSecond) throws InterruptedException { latchForSecond.await(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); latchForThird.countDown(); } public void third(Runnable printThird) throws InterruptedException { latchForThird.await(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); }}Complexity
Time
Highly efficient. Waiting threads are parked by the OS, consuming minimal resources.
Space
O(1) extra space for the two `CountDownLatch` objects.
Trade-offs
Pros
Highly efficient and uses very little CPU while waiting.
The code is clean, readable, and clearly expresses the intent of waiting for a preceding task to complete.
Less error-prone than manual locking with
wait()/notify().
Cons
A
CountDownLatchcannot be reset once its count reaches zero, making it unsuitable for problems requiring cyclical or reusable barriers (though this is not a limitation for the current problem).
This solution uses java.util.concurrent.Semaphore, another high-level concurrency utility. A semaphore maintains a set of permits. A thread must acquire a permit to proceed and can release a permit when done. By initializing semaphores with zero permits, we can force threads to wait until another thread explicitly releases a permit for them.
Algorithm
- Initialize two
Semaphoreobjects,semSecondandsemThird, both with 0 permits. first(): Executes its logic, then callssemSecond.release(). This adds one permit tosemSecond, effectively signaling that the second task can proceed.second(): CallssemSecond.acquire(). This will block until a permit is available. Once it acquires the permit, it executes its logic and then callssemThird.release()to signal the third task.third(): CallssemThird.acquire(), blocking until the second task releases a permit. Once acquired, it executes its logic.
Walkthrough
This solution uses java.util.concurrent.Semaphore, another high-level concurrency utility. A semaphore maintains a set of permits. A thread calls acquire() to get a permit (blocking if none are available) and release() to return a permit. This mechanism is perfect for signaling between threads. We use two semaphores, both initialized with zero permits, to act as gates. first() opens the gate for second(), and second() opens the gate for third().
- Initialize two
Semaphoreobjects,semSecondandsemThird, both with 0 permits. first(): Executes its logic, then callssemSecond.release(). This adds one permit tosemSecond, effectively signaling that the second task can proceed.second(): CallssemSecond.acquire(). This will block until a permit is available. Once it acquires the permit, it executes its logic and then callssemThird.release()to signal the third task.third(): CallssemThird.acquire(), blocking until the second task releases a permit. Once acquired, it executes its logic.
import java.util.concurrent.Semaphore; class Foo { private Semaphore semSecond; private Semaphore semThird; public Foo() { semSecond = new Semaphore(0); semThird = new Semaphore(0); } public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); semSecond.release(); } public void second(Runnable printSecond) throws InterruptedException { semSecond.acquire(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); semThird.release(); } public void third(Runnable printThird) throws InterruptedException { semThird.acquire(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); }}Complexity
Time
Highly efficient. Waiting threads are parked by the OS, consuming minimal resources.
Space
O(1) extra space for the two `Semaphore` objects.
Trade-offs
Pros
Very efficient, with waiting threads consuming minimal CPU.
The code is extremely concise and elegant for this 'pass the baton' style of synchronization.
Robust and less error-prone due to being a high-level abstraction.
Cons
The concept of permits might be slightly less intuitive for this specific problem than a
CountDownLatch, which directly models 'waiting for an event to happen'.
This approach uses Java's built-in monitor locks (synchronized blocks) along with the wait() and notifyAll() methods. Threads that are not ready to run call wait() to efficiently suspend themselves, releasing the CPU. When a thread completes its task, it calls notifyAll() to wake up the waiting threads so they can re-check if it's their turn.
Algorithm
- Initialize an integer counter to 1 and a shared lock object.
- All three methods are synchronized on the shared lock object.
first(): Executes its logic, increments the counter to 2, and callsnotifyAll()to wake up any waiting threads.second(): Enters awhileloop checking if the counter is not 2. If it's not its turn, it callswait(), which releases the lock and puts the thread to sleep. When woken, it re-checks the condition. If the condition is met, it executes, increments the counter to 3, and callsnotifyAll().third(): Follows the same pattern assecond(), waiting for the counter to be 3.
Walkthrough
This approach uses Java's built-in monitor locks (synchronized blocks) along with the wait() and notifyAll() methods. This is a classic and more efficient alternative to busy-waiting. Threads that are not ready to run call wait() to efficiently suspend themselves, releasing the CPU and the lock. When a thread completes its task, it changes the state and calls notifyAll() to wake up any waiting threads so they can re-check if it's their turn to proceed.
- Initialize an integer counter to 1 and a shared lock object.
- All three methods are synchronized on the shared lock object.
first(): Executes its logic, increments the counter to 2, and callsnotifyAll()to wake up any waiting threads.second(): Enters awhileloop checking if the counter is not 2. If it's not its turn, it callswait(), which releases the lock and puts the thread to sleep. When woken, it re-checks the condition. If the condition is met, it executes, increments the counter to 3, and callsnotifyAll().third(): Follows the same pattern assecond(), waiting for the counter to be 3.
class Foo { private int turn = 1; private final Object lock = new Object(); public Foo() { } public void first(Runnable printFirst) throws InterruptedException { synchronized (lock) { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); turn = 2; lock.notifyAll(); } } public void second(Runnable printSecond) throws InterruptedException { synchronized (lock) { while (turn != 2) { lock.wait(); } // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); turn = 3; lock.notifyAll(); } } public void third(Runnable printThird) throws InterruptedException { synchronized (lock) { while (turn != 3) { lock.wait(); } // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } }}Complexity
Time
Efficient in terms of CPU usage. The actual time depends on thread scheduling by the OS.
Space
O(1) extra space for the counter and the lock object.
Trade-offs
Pros
CPU efficient, as waiting threads are blocked by the OS instead of spinning.
A fundamental and widely understood concurrency pattern in Java.
Cons
More verbose and complex than higher-level concurrency utilities.
Prone to common errors like forgetting to use a
whileloop forwait()(to guard against spurious wakeups) or callingwait()/notifyAll()outside a synchronized block.notifyAll()can be inefficient as it wakes up all waiting threads, even those whose conditions are not yet met.
This approach uses a shared volatile integer to act as a flag, indicating which method's turn it is. Waiting threads continuously check this flag in a tight loop, a technique known as busy-waiting or a spinlock.
Algorithm
- Initialize a
volatile intvariable, sayturn, to 1. - The
first()method executes its logic and then setsturnto 2. - The
second()method enters awhileloop that continuously checks ifturnis equal to 2. This is known as busy-waiting or spinning. Once the condition is met, it executes its logic and setsturnto 3. - The
third()method similarly spins in awhileloop, waiting forturnto become 3 before executing its logic.
Walkthrough
This approach uses a shared volatile integer variable to act as a flag indicating which method's turn it is to execute. The volatile keyword ensures that changes to the flag are immediately visible to all threads. The second() and third() methods enter a tight loop (a spinlock) where they continuously check the value of this flag. They only proceed with their execution once the flag indicates that the preceding method has finished.
- Initialize a
volatile intvariable, sayturn, to 1. - The
first()method executes its logic and then setsturnto 2. - The
second()method enters awhileloop that continuously checks ifturnis equal to 2. This is known as busy-waiting or spinning. Once the condition is met, it executes its logic and setsturnto 3. - The
third()method similarly spins in awhileloop, waiting forturnto become 3 before executing its logic.
class Foo { private volatile int turn = 1; public Foo() { } public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". Do not change or remove this line. printFirst.run(); turn = 2; } public void second(Runnable printSecond) throws InterruptedException { while (turn != 2) { // Busy-wait, consuming CPU } // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); turn = 3; } public void third(Runnable printThird) throws InterruptedException { while (turn != 3) { // Busy-wait, consuming CPU } // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); }}Complexity
Time
The execution time is dependent on thread scheduling. The main drawback is not algorithmic complexity but the high CPU usage from busy-waiting, which is very inefficient.
Space
O(1) extra space for the volatile integer flag.
Trade-offs
Pros
Conceptually simple to understand and implement.
Cons
Extremely inefficient as it consumes CPU cycles while waiting (busy-waiting).
Does not scale well with more threads or more complex conditions.
Can lead to performance issues like priority inversion on some systems.
Solutions
Solution
class Foo { private Semaphore a = new Semaphore ( 1 ); private Semaphore b = new Semaphore ( 0 ); private Semaphore c = new Semaphore ( 0 ); public Foo () { } public void first ( Runnable printFirst ) throws InterruptedException { a . acquire ( 1 ); // printFirst.run() outputs "first". Do not change or remove this line. printFirst . run (); b . release ( 1 ); } public void second ( Runnable printSecond ) throws InterruptedException { b . acquire ( 1 ); // printSecond.run() outputs "second". Do not change or remove this line. printSecond . run (); c . release ( 1 ); } public void third ( Runnable printThird ) throws InterruptedException { c . acquire ( 1 ); // printThird.run() outputs "third". Do not change or remove this line. printThird . run (); a . release ( 1 ); } }import threading # Shared resource counter = 0 # Create a lock lock = threading . Lock () # A function to increment global counter def increment (): global counter for _ in range ( 100000 ): # Acquire the lock lock . acquire () counter += 1 # Release the lock lock . release () # Create threads thread1 = threading . Thread ( target = increment ) thread2 = threading . Thread ( target = increment ) # Start threads thread1 . start () thread2 . start () # Wait for both threads to finish thread1 . join () thread2 . join () print ( f "The final counter value is { counter } " )class Foo { private: mutex m2 , m3 ; public: Foo () { m2 . lock (); m3 . lock (); } void first ( function < void () > printFirst ) { printFirst (); m2 . unlock (); } void second ( function < void () > printSecond ) { m2 . lock (); printSecond (); m3 . unlock (); } void third ( function < void () > printThird ) { m3 . lock (); printThird (); } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.