Domain 1EasyCORE

Print in Order

The problem requires us to ensure that three methods (`first()`, `second()`, and `third()`) are executed in a specific order by different threads. The same instance of the `Foo` class will be passed to three different threads: Thread A calls `first()`, Thread B calls `second()`, and Thread C calls `third()`. We need to design a mechanism that guarantees the correct execution order regardless of how the operating system schedules these threads.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

1114. Print in Order

Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 67.2%


Problem Breakdown

The problem requires us to ensure that three methods (first(), second(), and third()) are executed in a specific order by different threads. The same instance of the Foo class will be passed to three different threads: Thread A calls first(), Thread B calls second(), and Thread C calls third(). We need to design a mechanism that guarantees the correct execution order regardless of how the operating system schedules these threads.

Inputs:

  • An instance of the Foo class.
  • Three threads: A, B, and C, each calling one of the methods (first(), second(), or third()).

Outputs:

  • The string “firstsecondthird” printed in order.

Implicit Constraints/Tricky Edge Cases:

  • The order in which threads are scheduled by the operating system is unknown.
  • We need a mechanism to enforce the correct execution order across threads.

Intuition

A brute-force approach might involve busy-waiting or polling, where each method checks if the previous one has completed before proceeding. However, this approach can lead to high CPU usage and poor performance due to constant checking.

The key insight is to use synchronization primitives that allow threads to wait for a condition to be met before proceeding. In Java, we can use synchronized blocks or methods along with wait() and notifyAll() to achieve this.

Approach

  1. Synchronization Mechanism: Use two boolean flags (firstDone and secondDone) to track the completion of first() and second(), respectively.
  2. Synchronized Methods: Make each method synchronized to ensure that only one thread can execute it at a time.
  3. Condition Checking:
    • In second(), wait until firstDone is true.
    • In third(), wait until secondDone is true.
  4. Notification: After completing first() and second(), notify all waiting threads to check the conditions.

Complexity Analysis

  • Time Complexity: O(1) for each method call, assuming no context switching or blocking occurs.
  • Space Complexity: O(1), as we are using a constant amount of space for the boolean flags.

Solution

import threading

class Foo:
    def __init__(self):
        self.firstDone = False
        self.secondDone = False
        self.lock = threading.Lock()

    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        with self.lock:
            printFirst()
            self.firstDone = True

    def second(self, printSecond: 'Callable[[], None]') -> None:
        with self.lock:
            while not self.firstDone:
                self.lock.wait()
            # printSecond() outputs "second". Do not change or remove this line.
            printSecond()
            self.secondDone = True
            self.lock.notify_all()

    def third(self, printThird: 'Callable[[], None]') -> None:
        with self.lock:
            while not self.secondDone:
                self.lock.wait()
            # printThird() outputs "third". Do not change or remove this line.
            printThird()

Edge Cases Handled

  • Thread Interference: The use of synchronized methods and flags ensures that threads do not interfere with each other’s execution.
  • Order Enforcement: The boolean flags and wait/notify mechanisms enforce the correct order of execution (first(), second(), third()).
  • Concurrency Issues: Synchronization primitives prevent race conditions and ensure thread safety.