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
Fooclass. - Three threads: A, B, and C, each calling one of the methods (
first(),second(), orthird()).
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
- Synchronization Mechanism: Use two boolean flags (
firstDoneandsecondDone) to track the completion offirst()andsecond(), respectively. - Synchronized Methods: Make each method synchronized to ensure that only one thread can execute it at a time.
- Condition Checking:
- In
second(), wait untilfirstDoneis true. - In
third(), wait untilsecondDoneis true.
- In
- Notification: After completing
first()andsecond(), 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.