LeetCode 1114: Print in Order (Semaphore / Condition Synchronization)
LeetCode 1114ConcurrencySynchronizationToday we solve LeetCode 1114 - Print in Order.
Source: https://leetcode.com/problems/print-in-order/
English
Problem Summary
Three threads call first(), second(), and third() in arbitrary order. We must guarantee output order is always first → second → third.
Key Insight
We do not need mutual exclusion for shared data complexity; we only need ordering gates. Create two signals: one released after first() finishes, another released after second() finishes. Then second() waits on signal1, and third() waits on signal2.
Brute Force and Limitations
Busy-waiting with shared flags (looping until a flag changes) works conceptually but wastes CPU and is fragile without memory visibility guarantees. Proper synchronization primitives (semaphore/condition/event/promise) are cleaner and safe.
Optimal Algorithm Steps
1) Initialize gate1 and gate2 to blocked state.
2) In first(): print then open gate1.
3) In second(): wait gate1, print, then open gate2.
4) In third(): wait gate2 then print.
Complexity Analysis
Time: O(1) work per method (excluding scheduler waiting).
Space: O(1).
Common Pitfalls
- Using plain booleans without synchronization (data race / visibility issue).
- Releasing signal before printing, which can break required order.
- Forgetting to initialize gates as blocked.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.concurrent.Semaphore;
class Foo {
private final Semaphore secondGate = new Semaphore(0);
private final Semaphore thirdGate = new Semaphore(0);
public Foo() {}
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
secondGate.release();
}
public void second(Runnable printSecond) throws InterruptedException {
secondGate.acquire();
printSecond.run();
thirdGate.release();
}
public void third(Runnable printThird) throws InterruptedException {
thirdGate.acquire();
printThird.run();
}
}type Foo struct {
secondGate chan struct{}
thirdGate chan struct{}
}
func Constructor() Foo {
return Foo{
secondGate: make(chan struct{}, 1),
thirdGate: make(chan struct{}, 1),
}
}
func (f *Foo) First(printFirst func()) {
printFirst()
f.secondGate <- struct{}{}
}
func (f *Foo) Second(printSecond func()) {
<-f.secondGate
printSecond()
f.thirdGate <- struct{}{}
}
func (f *Foo) Third(printThird func()) {
<-f.thirdGate
printThird()
}#include <functional>
#include <mutex>
#include <condition_variable>
using namespace std;
class Foo {
private:
mutex mtx;
condition_variable cv;
int state = 0; // 0: none, 1: first done, 2: second done
public:
Foo() {}
void first(function<void()> printFirst) {
{
lock_guard<mutex> lock(mtx);
printFirst();
state = 1;
}
cv.notify_all();
}
void second(function<void()> printSecond) {
{
unique_lock<mutex> lock(mtx);
cv.wait(lock, [&] { return state >= 1; });
printSecond();
state = 2;
}
cv.notify_all();
}
void third(function<void()> printThird) {
unique_lock<mutex> lock(mtx);
cv.wait(lock, [&] { return state >= 2; });
printThird();
}
};from threading import Semaphore
class Foo:
def __init__(self):
self.second_gate = Semaphore(0)
self.third_gate = Semaphore(0)
def first(self, printFirst: 'Callable[[], None]') -> None:
printFirst()
self.second_gate.release()
def second(self, printSecond: 'Callable[[], None]') -> None:
self.second_gate.acquire()
printSecond()
self.third_gate.release()
def third(self, printThird: 'Callable[[], None]') -> None:
self.third_gate.acquire()
printThird()class Gate {
constructor() {
this.opened = false;
this.waiters = [];
}
async wait() {
if (this.opened) return;
await new Promise(resolve => this.waiters.push(resolve));
}
open() {
if (this.opened) return;
this.opened = true;
for (const resolve of this.waiters) resolve();
this.waiters = [];
}
}
var Foo = function() {
this.secondGate = new Gate();
this.thirdGate = new Gate();
};
Foo.prototype.first = async function(printFirst) {
printFirst();
this.secondGate.open();
};
Foo.prototype.second = async function(printSecond) {
await this.secondGate.wait();
printSecond();
this.thirdGate.open();
};
Foo.prototype.third = async function(printThird) {
await this.thirdGate.wait();
printThird();
};中文
题目概述
有三个线程会乱序调用 first()、second()、third()。要求最终输出顺序始终是 first → second → third。
核心思路
这是典型“顺序约束”问题，不是复杂共享数据竞争问题。设置两个“闸门”信号：first() 完成后放行 second()，second() 完成后放行 third()，即可保证顺序。
暴力解法与不足
若用自旋（不断轮询布尔标记），虽然逻辑上可行，但会浪费 CPU，而且若缺少正确同步语义还会出现可见性问题。使用信号量/条件变量/事件更稳健。
最优算法步骤
1）初始化 gate1、gate2 为阻塞状态。
2）first()：打印后释放 gate1。
3）second()：等待 gate1，打印后释放 gate2。
4）third()：等待 gate2，再打印。
复杂度分析
每个方法的计算复杂度为 O(1)（不计线程调度等待）。
额外空间复杂度 O(1)。
常见陷阱
- 只用普通变量做标记，未加同步原语，可能出现竞态与可见性问题。
- 先放行再打印，导致顺序被打乱。
- 闸门初始值设错（应初始阻塞）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.concurrent.Semaphore;
class Foo {
private final Semaphore secondGate = new Semaphore(0);
private final Semaphore thirdGate = new Semaphore(0);
public Foo() {}
public void first(Runnable printFirst) throws InterruptedException {
printFirst.run();
secondGate.release();
}
public void second(Runnable printSecond) throws InterruptedException {
secondGate.acquire();
printSecond.run();
thirdGate.release();
}
public void third(Runnable printThird) throws InterruptedException {
thirdGate.acquire();
printThird.run();
}
}type Foo struct {
secondGate chan struct{}
thirdGate chan struct{}
}
func Constructor() Foo {
return Foo{
secondGate: make(chan struct{}, 1),
thirdGate: make(chan struct{}, 1),
}
}
func (f *Foo) First(printFirst func()) {
printFirst()
f.secondGate <- struct{}{}
}
func (f *Foo) Second(printSecond func()) {
<-f.secondGate
printSecond()
f.thirdGate <- struct{}{}
}
func (f *Foo) Third(printThird func()) {
<-f.thirdGate
printThird()
}#include <functional>
#include <mutex>
#include <condition_variable>
using namespace std;
class Foo {
private:
mutex mtx;
condition_variable cv;
int state = 0; // 0: none, 1: first done, 2: second done
public:
Foo() {}
void first(function<void()> printFirst) {
{
lock_guard<mutex> lock(mtx);
printFirst();
state = 1;
}
cv.notify_all();
}
void second(function<void()> printSecond) {
{
unique_lock<mutex> lock(mtx);
cv.wait(lock, [&] { return state >= 1; });
printSecond();
state = 2;
}
cv.notify_all();
}
void third(function<void()> printThird) {
unique_lock<mutex> lock(mtx);
cv.wait(lock, [&] { return state >= 2; });
printThird();
}
};from threading import Semaphore
class Foo:
def __init__(self):
self.second_gate = Semaphore(0)
self.third_gate = Semaphore(0)
def first(self, printFirst: 'Callable[[], None]') -> None:
printFirst()
self.second_gate.release()
def second(self, printSecond: 'Callable[[], None]') -> None:
self.second_gate.acquire()
printSecond()
self.third_gate.release()
def third(self, printThird: 'Callable[[], None]') -> None:
self.third_gate.acquire()
printThird()class Gate {
constructor() {
this.opened = false;
this.waiters = [];
}
async wait() {
if (this.opened) return;
await new Promise(resolve => this.waiters.push(resolve));
}
open() {
if (this.opened) return;
this.opened = true;
for (const resolve of this.waiters) resolve();
this.waiters = [];
}
}
var Foo = function() {
this.secondGate = new Gate();
this.thirdGate = new Gate();
};
Foo.prototype.first = async function(printFirst) {
printFirst();
this.secondGate.open();
};
Foo.prototype.second = async function(printSecond) {
await this.secondGate.wait();
printSecond();
this.thirdGate.open();
};
Foo.prototype.third = async function(printThird) {
await this.thirdGate.wait();
printThird();
};
Comments