Code Implementation

from threading import Event

class Foo:
    def __init__(self):
        self.first_done = Event()
        self.second_done = Event()

    def first(self, printFirst: 'Callable[[], None]') -> None:
        printFirst()
        self.first_done.set()

    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.first_done.wait()
        printSecond()
        self.second_done.set()

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

#include <mutex>
#include <condition_variable>

class Foo {
private:
    std::mutex mtx;
    std::condition_variable cv;
    int state;

public:
    Foo() : state(0) {}

    void first(function<void()> printFirst) {
        std::unique_lock<std::mutex> lock(mtx);
        printFirst();
        state = 1;
        cv.notify_all();
    }

    void second(function<void()> printSecond) {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, [this]{ return state == 1; });
        printSecond();
        state = 2;
        cv.notify_all();
    }

    void third(function<void()> printThird) {
        std::unique_lock<std::mutex> lock(mtx);
        cv.wait(lock, [this]{ return state == 2; });
        printThird();
    }
};
      

import java.util.concurrent.CountDownLatch;

class Foo {
    private CountDownLatch firstDone = new CountDownLatch(1);
    private CountDownLatch secondDone = new CountDownLatch(1);

    public Foo() {}

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        firstDone.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        firstDone.await();
        printSecond.run();
        secondDone.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
        secondDone.await();
        printThird.run();
    }
}
      

class Foo {
    constructor() {
        this.firstDone = new Promise(resolve => this.firstResolve = resolve);
        this.secondDone = new Promise(resolve => this.secondResolve = resolve);
    }

    first(printFirst) {
        printFirst();
        this.firstResolve();
    }

    second(printSecond) {
        this.firstDone.then(() => {
            printSecond();
            this.secondResolve();
        });
    }

    third(printThird) {
        this.secondDone.then(() => {
            printThird();
        });
    }
}
      

Problem Description

The "Print in Order" problem asks you to implement a class with three methods: first, second, and third. Each method accepts a function as an argument and is meant to be called from different threads, potentially out of order. Despite this, you must ensure that the output always appears in the correct order: "first", then "second", then "third".

Key constraints:

• Each method may be called from a separate thread, and the order of calls is not guaranteed.
• You must ensure that the function passed to first is executed before second's, and second's before third's.
• There is only one valid solution: the output must always be in order, regardless of calling order.
• Do not reuse or share the same elements between threads.

Thought Process

At first glance, this problem seems simple: just call the functions in the right order. However, because each method may be called by a different thread at unpredictable times, we cannot rely on the call order. We need a way to synchronize the threads so that each waits for its turn.

A brute-force approach might involve busy-waiting or checking a shared variable in a loop, but this is inefficient and not recommended. Instead, we look for synchronization primitives (like locks, events, latches, or promises) that allow threads to wait efficiently until they are allowed to proceed.

The main idea is to set up "signals" between the methods, so that second waits for first to finish, and third waits for second. This ensures the correct order, no matter how the threads are scheduled.

Solution Approach

The solution uses synchronization mechanisms to enforce the execution order. Here’s a step-by-step breakdown:

1. Initialization:
   • We create two synchronization objects (like Events in Python, CountDownLatch in Java, Promises in JavaScript, or a combination of mutex and condition variable in C++).
2. First Method:
   • Executes its function immediately.
   • Signals (or "notifies") that it is done, allowing the second method to proceed.
3. Second Method:
   • Waits for the signal from the first method.
   • Executes its function.
   • Signals that it is done, allowing the third method to proceed.
4. Third Method:
   • Waits for the signal from the second method.
   • Executes its function.

This approach ensures that each method waits for its predecessor, and the functions are executed in the correct order, regardless of thread scheduling.

Example Walkthrough

Suppose we have three threads that call the methods in this order: third, first, second.

1. Thread 3 calls third:
   • It waits for the signal from second, which hasn't happened yet, so it blocks.
2. Thread 1 calls first:
   • It executes printFirst() and signals that first is done.
3. Thread 2 calls second:
   • It sees that first is done, executes printSecond(), and signals that second is done.
4. Now, Thread 3 is unblocked, executes printThird(), and the sequence is completed in the correct order: first, second, third.

Time and Space Complexity

Brute-force Approach:

• If we used busy waiting (e.g., checking a flag in a loop), each method could waste CPU cycles, making the time complexity difficult to analyze and very inefficient in practice.

• Each method performs a constant amount of work: waiting for a signal, executing a function, and sending a signal.
• The time complexity is O(1) per method, since the synchronization primitives are efficient.
• The space complexity is also O(1), since we only use a fixed number of synchronization objects.

This efficiency is why using proper synchronization primitives is preferred over ad-hoc solutions.

Summary

The "Print in Order" problem is a classic synchronization exercise. The key insight is to use synchronization primitives to enforce method execution order, regardless of thread scheduling. By setting up signals between the methods, we avoid busy-waiting and ensure efficiency and correctness. This solution is elegant because it leverages well-understood concurrency tools, making the code simple, robust, and easy to reason about.