What is the time complexity of the Semaphore approach?

O(1) for each method call. The semaphore approach uses blocking wait which is efficient.

What is the space complexity of all approaches?

O(1) for all approaches. We only use a constant amount of extra space for synchronization primitives.

Which approach is most efficient?

The Semaphore and Condition Variable approaches are most efficient as they use blocking wait instead of busy waiting, avoiding CPU waste.

What is the downside of busy waiting approaches?

Busy waiting wastes CPU cycles by continuously checking the condition instead of sleeping, which is inefficient for longer wait times.

Print in Order | N3mo LC

Difficulty: Easy | Acceptance: 72.90% | Paid: No Topics: Concurrency

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 to ensure that first() is called before second(), and second() is called before third().

Examples
Constraints
Approach 1: Using Semaphore
Approach 2: Using Condition Variable
Approach 3: Using Mutex with Busy Waiting
Approach 4: Using Atomic Operations
Approach 5: Using CountDownLatch

Examples

Example 1

Input: [1,2,3] Output: “firstsecondthird” Explanation: The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). “firstsecondthird” is the output of the correct execution.

Example 2

Input: [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 output of the correct execution.

Constraints

The input to the three threads will be a random permutation of [1, 2, 3].

Using Semaphore

Intuition Use semaphores to control the order of execution. Initialize semaphores such that only the first method can execute initially, then release permits for subsequent methods.

Steps

Initialize semaphore1 with 1 permit (for first)
Initialize semaphore2 and semaphore3 with 0 permits
After first() completes, release semaphore2
After second() completes, release semaphore3

python

from threading import Semaphore

class Foo:
    def __init__(self):
        self.sem1 = Semaphore(1)
        self.sem2 = Semaphore(0)
        self.sem3 = Semaphore(0)

    def first(self, printFirst: 'Callable[[], None]') -> None:
        self.sem1.acquire()
        printFirst()
        self.sem2.release()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.sem2.acquire()
        printSecond()
        self.sem3.release()

    def third(self, printThird: 'Callable[[], None]') -> None:
        self.sem3.acquire()
        printThird()

Complexity

Time: O(1) for each method call
Space: O(1)
Notes: Clean and efficient, uses blocking wait instead of busy waiting

Using Condition Variable

Intuition Use condition variables to wait for specific conditions (counter value) before executing. Threads sleep until notified, avoiding CPU waste.

Steps

Initialize a mutex and condition variable
Use a counter to track which method should execute next
Each method waits for its turn using the condition variable
After printing, increment counter and notify all waiting threads

python

from threading import Condition

class Foo:
    def __init__(self):
        self.cond = Condition()
        self.counter = 1

    def first(self, printFirst: 'Callable[[], None]') -> None:
        with self.cond:
            printFirst()
            self.counter = 2
            self.cond.notify_all()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.cond:
            while self.counter != 2:
                self.cond.wait()
            printSecond()
            self.counter = 3
            self.cond.notify_all()

    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.cond:
            while self.counter != 3:
                self.cond.wait()
            printThird()

Complexity

Time: O(1) for each method call
Space: O(1)
Notes: Efficient blocking wait, threads sleep instead of spinning

Using Mutex with Busy Waiting

Intuition Use a simple mutex to protect a counter. Threads busy-wait (spin) until it’s their turn. Simple but wastes CPU cycles.

Steps

Initialize a mutex and counter
Each method acquires the lock, checks if it’s its turn
If not its turn, release lock and retry
If it’s its turn, print and increment counter

python

from threading import Lock

class Foo:
    def __init__(self):
        self.lock = Lock()
        self.counter = 1

    def first(self, printFirst: 'Callable[[], None]') -> None:
        with self.lock:
            printFirst()
            self.counter = 2

    def second(self, printSecond: 'Callable[[], None]') -> None:
        while True:
            with self.lock:
                if self.counter == 2:
                    printSecond()
                    self.counter = 3
                    return

    def third(self, printThird: 'Callable[[], None]') -> None:
        while True:
            with self.lock:
                if self.counter == 3:
                    printThird()
                    return

Complexity

Time: O(n) where n is wait time (busy waiting)
Space: O(1)
Notes: Simple but inefficient - wastes CPU cycles during waiting

Using Atomic Operations

Intuition Use atomic variables to track the state without explicit locks. Threads spin-wait on the atomic value using lock-free operations.

Steps

Initialize an atomic counter
Each method spins until the counter reaches its expected value
After printing, increment the counter atomically

python

from threading import Lock

class Foo:
    def __init__(self):
        self.counter = 1
        self.lock = Lock()

    def first(self, printFirst: 'Callable[[], None]') -> None:
        printFirst()
        with self.lock:
            self.counter = 2

    def second(self, printSecond: 'Callable[[], None]') -> None:
        while True:
            with self.lock:
                if self.counter == 2:
                    printSecond()
                    self.counter = 3
                    return

    def third(self, printThird: 'Callable[[], None]') -> None:
        while True:
            with self.lock:
                if self.counter == 3:
                    printThird()
                    return

Complexity

Time: O(n) where n is wait time (busy waiting)
Space: O(1)
Notes: Lock-free but still busy-waits; good for very short wait times

Using CountDownLatch

Intuition Use countdown latches to signal completion of previous methods. Each latch waits for the previous method to complete before proceeding.

Steps

Initialize two countdown latches
first() counts down the first latch after printing
second() waits for first latch, then prints and counts down second latch
third() waits for second latch, then prints

python

from threading import Lock, Condition

class Foo:
    def __init__(self):
        self.cond = Condition()
        self.first_done = False
        self.second_done = False

    def first(self, printFirst: 'Callable[[], None]') -> None:
        printFirst()
        with self.cond:
            self.first_done = True
            self.cond.notify_all()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.cond:
            while not self.first_done:
                self.cond.wait()
        printSecond()
        with self.cond:
            self.second_done = True
            self.cond.notify_all()

    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.cond:
            while not self.second_done:
                self.cond.wait()
        printThird()

Complexity

Time: O(1) for each method call
Space: O(1)
Notes: Clean one-way synchronization pattern, easy to understand