腾讯云 — 后台开发¶

轮次： 一面 + 二面（2026-04-03）
标签： 内存序 · 无锁编程 · 进程/线程/协程 · 大数据 · LRU · 算法手撕
侧重： 并发底层原理、无锁/有锁队列、LRU Cache、树重建

一面¶

侧重： 并发底层原理（memory order、CAS、无锁队列）、系统概念、手撕三道算法

Q1. 你知道内存序吗¶

回答¶

什么是内存序（Memory Order）¶

内存序是 C++11 <atomic> 中用来 控制原子操作的可见性和重排序约束 的机制。它告诉编译器和 CPU：围绕这条原子操作，哪些读写 不能被重排。

背景：现代 CPU 和编译器会对指令进行重排序以提高性能（乱序执行、store buffer、编译优化等）。单线程下重排不影响结果，但 多线程下可能导致其他线程看到不一致的状态。

C++11 六种内存序¶

内存序	含义	开销
`memory_order_relaxed`	仅保证原子性，不保证顺序	最低
`memory_order_consume`	依赖链上的读不能重排到此 load 之前（实际几乎不用，编译器普遍提升为 acquire）	低
`memory_order_acquire`	此 load 之后的读写不能重排到此 load 之前	中
`memory_order_release`	此 store 之前的读写不能重排到此 store 之后	中
`memory_order_acq_rel`	同时具备 acquire + release 语义（用于 RMW 操作）	中
`memory_order_seq_cst`	顺序一致性，全局唯一全序，最强保证（默认值）	最高

Acquire-Release 配对¶

最核心、最高频的模型。生产者用 release 写，消费者用 acquire 读，保证生产者 store 之前的所有写入对消费者可见：

std::atomic<bool> ready{false};
int data = 0;

// 线程 1（生产者）
data = 42;                                    // ①
ready.store(true, std::memory_order_release); // ② release：①不会被重排到②之后

// 线程 2（消费者）
while (!ready.load(std::memory_order_acquire)); // ③ acquire：④不会被重排到③之前
assert(data == 42);                             // ④ 保证看到 data = 42

为什么不全用 seq_cst¶

seq_cst 在 x86 上代价不大（x86 TSO 模型天然提供较强顺序），但在 ARM / RISC-V 等弱内存模型架构 上需要插入全屏障（dmb / fence），开销显著。高性能无锁数据结构中使用 acquire/release 甚至 relaxed 可以获得可观的性能提升。

注意事项¶

面试先讲「为什么需要内存序」（重排序 + 多核可见性），再列六种，最后重点讲 acquire-release
x86 是 TSO（Total Store Order），store-store 不重排，所以 x86 上 acquire/release 几乎零开销（编译器屏障即可）；ARM 是弱序要加真正的硬件屏障
追问「happens-before」：如果 A release-store，B acquire-load 看到了 A 写的值，则 A happens-before B

细看： 并发编程

Q2. 内存序在你实现的 SPSC 队列上如何体现¶

回答¶

SPSC（Single-Producer Single-Consumer）无锁环形队列是 acquire-release 内存序的经典应用场景。

SPSC 队列核心结构¶

template <typename T, size_t Capacity>
class SPSCQueue {
    std::array<T, Capacity> buffer_;
    alignas(64) std::atomic<size_t> head_{0};  // 消费者移动
    alignas(64) std::atomic<size_t> tail_{0};  // 生产者移动
    // head_ 和 tail_ 各占一条 cache line，避免 false sharing
};

生产者 push¶

bool push(const T& value) {
    size_t tail = tail_.load(std::memory_order_relaxed);  // ① 只有自己写 tail
    size_t next = (tail + 1) % Capacity;

    if (next == head_.load(std::memory_order_acquire)) {  // ② acquire 读 head
        return false;  // 队列满
    }

    buffer_[tail] = value;                                // ③ 写数据
    tail_.store(next, std::memory_order_release);         // ④ release 写 tail
    return true;
}

消费者 pop¶

bool pop(T& value) {
    size_t head = head_.load(std::memory_order_relaxed);  // ⑤ 只有自己写 head

    if (head == tail_.load(std::memory_order_acquire)) {  // ⑥ acquire 读 tail
        return false;  // 队列空
    }

    value = buffer_[head];                                // ⑦ 读数据
    head_.store((head + 1) % Capacity, std::memory_order_release); // ⑧ release 写 head
    return true;
}

内存序分析¶

操作	内存序	为什么
① 生产者读自己的 tail	`relaxed`	只有生产者写 tail，不需要同步
② 生产者读 head	`acquire`	确保看到消费者 pop 后的最新 head，并且消费者对 buffer 的读操作已完成
③ 写 buffer	普通写	被 ④ 的 release 保护
④ 生产者写 tail	`release`	保证 ③ 的数据写入在 tail 更新之前完成，消费者 acquire 读到新 tail 时一定能看到完整数据
⑥ 消费者读 tail	`acquire`	与生产者 ④ 的 release 配对，保证看到数据
⑧ 消费者写 head	`release`	与生产者 ② 的 acquire 配对，保证 buffer 读完后再更新 head

关键： release-store 与 acquire-load 构成 同步关系（synchronizes-with），确保数据写入对另一端可见。

注意事项¶

head_ 和 tail_ 用 alignas(64) 分开 cache line，避免 false sharing
SPSC 不需要 CAS——只有一个生产者和一个消费者，各自只写自己的游标
追问「MPMC 怎么办」：需要 CAS 竞争游标 → 引出 Q4

细看： 并发编程 · STL 容器深入

Q4. CAS 在无锁队列上是如何应用的¶

回答¶

什么是 CAS¶

CAS（Compare-And-Swap）是 CPU 提供的原子指令，语义为：

bool CAS(addr, expected, desired):
    if (*addr == expected):
        *addr = desired
        return true
    else:
        expected = *addr   // 更新 expected 为当前值
        return false

C++ 中对应 std::atomic<T>::compare_exchange_weak/strong。

CAS 在 MPMC 无锁队列中的应用¶

多生产者多消费者场景下，多个线程可能同时尝试推进同一个游标，需要 CAS 竞争：

// 多生产者 push（简化示意）
bool push(const T& value) {
    size_t tail = tail_.load(std::memory_order_relaxed);

    while (true) {
        size_t next = (tail + 1) % Capacity;

        if (next == head_.load(std::memory_order_acquire)) {
            return false;  // 满
        }

        // CAS 尝试占用 tail 位置
        if (tail_.compare_exchange_weak(tail, next,
                std::memory_order_acq_rel,
                std::memory_order_relaxed)) {
            buffer_[tail] = value;  // 成功，写入数据
            return true;
        }
        // 失败：tail 已被其他线程更新，compare_exchange_weak 自动载入新值到 tail，重试
    }
}

CAS 循环（CAS loop / spin）的核心思路¶

读取当前状态（relaxed 即可）
计算期望的新状态
CAS 尝试原子更新：成功则完成，失败则说明有并发修改，回到步骤 1 重试

weak vs strong¶

版本	区别
`compare_exchange_weak`	允许 spurious failure（即使值匹配也可能失败），适合放在循环中使用，某些架构上更快
`compare_exchange_strong`	不会 spurious failure，适合单次判断

ABA 问题¶

CAS 的经典陷阱：

线程 1 读到值为 A → 被抢占 → 其他线程把值改成 B 再改回 A → 线程 1 CAS 成功，但中间状态已经变化过

解决方案：

Tagged pointer：将版本号打包进指针（利用高位或对齐的低位），每次修改递增版本号
std::atomic<std::pair<T, uint64_t>>（需要 128-bit CAS，即 cmpxchg16b）
使用 hazard pointer 或 epoch-based reclamation 管理内存回收

注意事项¶

面试线：CAS 原理 → 无锁队列应用 → ABA 问题 → 解决方案
无锁 ≠ 无等待（lock-free ≠ wait-free）：lock-free 保证至少一个线程能推进，wait-free 保证每个线程都能在有限步内完成
高竞争场景下 CAS 自旋可能比锁更慢（过多重试）

细看： 并发编程

Q5. 进程、线程、协程分别是什么，分别能使用哪里的内存¶

回答¶

核心对比¶

维度	进程	线程	协程
定义	OS 资源分配的基本单位	OS 调度的基本单位	用户态的轻量执行单元
调度者	内核	内核	用户态调度器（库/语言运行时）
创建开销	最大（需复制页表等）	中等（共享地址空间）	最小（仅保存寄存器 + 栈）
上下文切换	~μs 级（需切换页表、TLB 刷新）	~μs 级（无需切页表，但需内核态切换）	~ns 级（纯用户态，无系统调用）
隔离性	独立地址空间，强隔离	共享地址空间，弱隔离	共享线程地址空间
通信	IPC（管道、共享内存、socket 等）	直接读写共享内存（需同步）	直接读写（同一线程内无需同步）

各自能使用的内存¶

┌─────────── 进程 ───────────┐
│  代码段 (Text)    只读共享   │
│  数据段 (Data/BSS) 全局变量  │
│  堆 (Heap)        动态分配   │
│  mmap 区          共享库/映射 │
│  ┌──── 线程 1 ────┐         │
│  │  栈 (独立)      │         │
│  │  TLS (线程本地)  │         │
│  │  ┌─ 协程 A ──┐  │         │
│  │  │ 协程栈(KB) │  │         │
│  │  └───────────┘  │         │
│  │  ┌─ 协程 B ──┐  │         │
│  │  │ 协程栈(KB) │  │         │
│  │  └───────────┘  │         │
│  └─────────────────┘         │
│  ┌──── 线程 2 ────┐         │
│  │  栈 (独立)      │         │
│  │  TLS (线程本地)  │         │
│  └─────────────────┘         │
└─────────────────────────────┘

执行单元	可访问的内存
进程	拥有独立虚拟地址空间：代码段、数据段、堆、栈、mmap 区。进程间默认隔离，需 IPC 通信
线程	共享进程的堆、全局/静态数据、代码段、mmap 区；拥有独立栈（默认 8MB）和 TLS（线程本地存储）
协程	与所属线程共享一切内存；拥有独立的协程栈（通常很小，几 KB ~ 几十 KB），由用户态调度器在堆上分配

协程的栈¶

有栈协程（如 Boost.Context、libco）：在堆上预分配一块内存作为协程栈，切换时直接切 sp 寄存器
无栈协程（如 C++20 coroutines）：编译器将局部变量打包成一个 coroutine frame 对象（堆分配），没有真正的栈切换

注意事项¶

面试先快速给出三者定义和调度者区别，再展开内存部分
协程不是并行，是并发——同一时刻仍然只有一个协程在跑（单线程内）
追问「用过什么协程」：C++20 co_await/co_yield、Boost.Asio 协程、Go goroutine（M:N 调度）

细看： 进程 · 线程 · 内存 · 并发编程

Q6. 用过 Hadoop、Flink 吗，知道 exactly-once 吗¶

回答¶

Hadoop vs Flink 简要对比¶

维度	Hadoop (MapReduce)	Flink
计算模型	批处理	流处理（也支持批）
延迟	高（分钟级）	低（毫秒~秒级）
状态管理	无原生状态	内置有状态计算 + checkpoint
容错	任务级重试	分布式快照（Chandy-Lamport）

三种语义保证¶

语义	含义	说明
At-most-once	每条消息最多处理一次	可能丢数据，不重试
At-least-once	每条消息至少处理一次	故障时重发，可能重复处理
Exactly-once	每条消息恰好处理一次	最强保证，最难实现

Flink 的 Exactly-Once 实现¶

Flink 通过 分布式快照（Checkpoint）+ 两阶段提交（2PC） 实现端到端 exactly-once：

Checkpoint（基于 Chandy-Lamport 算法）
JobManager 定期注入 barrier（屏障标记）到数据流
算子收到所有输入通道的 barrier 后，将自身状态持久化到远端存储（如 HDFS/S3）
故障恢复时从最近的 checkpoint 恢复状态，重放 barrier 之后的数据
Two-Phase Commit Sink（两阶段提交）
对于外部系统（如 Kafka、数据库），pre-commit → checkpoint 成功后 commit
如果 checkpoint 失败，abort 回滚
Source 端
需要支持 offset 回退（如 Kafka 可以 seek 到指定 offset），这样恢复时能精确重放

注意： Exactly-once 的本质是「故障时通过 replay + 去重/幂等达到效果上的恰好一次」，而非物理上只处理一次。

Kafka 的 Exactly-Once¶

Kafka 0.11+ 通过 幂等生产者 + 事务 实现： - 幂等生产者：给每条消息分配 sequence number，broker 端去重 - 事务：跨分区原子写入，consumer 配合 read_committed 隔离级别

注意事项¶

C++ 后端面试问这个通常是 了解广度，不需要深入源码
核心要讲清楚 exactly-once 的原理：checkpoint + 可重放 source + 幂等/事务 sink
如果没用过可以坦诚说，但展示对概念的理解

细看： 分布式 · 负载均衡 · 高可用

Q7. 手撕三道算法¶

7.1 二叉树层序遍历（LeetCode 102）¶

思路¶

BFS + 队列，每层开始前记录当前队列大小，即为该层节点数。

代码¶

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();  // 当前层的节点数
            vector<int> level;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left)  q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(std::move(level));
        }
        return result;
    }
};

复杂度： 时间 \(O(n)\)，空间 \(O(n)\)

注意事项¶

size 必须在循环开始前取，不能在 for 条件里用 q.size()（循环体中会变）
追问变体：锯齿形层序（偶数层反转）、右视图（每层最后一个节点）

7.2 最大子数组之和（LeetCode 53）¶

思路¶

Kadane 算法：维护以当前元素结尾的最大子数组和 cur，遇到 cur < 0 就丢弃前面的部分重新开始。

\[\text{cur}[i] = \max(\text{nums}[i],\ \text{cur}[i-1] + \text{nums}[i])\]

代码¶

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int cur = nums[0];
        int result = nums[0];
        for (int i = 1; i < (int)nums.size(); ++i) {
            cur = std::max(nums[i], cur + nums[i]);
            result = std::max(result, cur);
        }
        return result;
    }
};

复杂度： 时间 \(O(n)\)，空间 \(O(1)\)

注意事项¶

初始化 cur = nums[0]，不要初始化为 0（全负数数组会出错）
追问分治法：\(O(n \log n)\)，将数组一分为二，答案在左半、右半或跨中间
追问「返回子数组区间」：额外记录 start 和 end 索引

7.3 数组中能被 3 整除的最大子集和¶

思路¶

这是 LeetCode 1262 — Greatest Sum Divisible by Three 的变体。

DP 思路： 维护 3 个状态，分别表示当前子集和 mod 3 余数为 0、1、2 时的最大和。

\[dp[j] = \max(dp[j],\ dp[(j - \text{nums}[i] \% 3 + 3) \% 3] + \text{nums}[i])\]

代码¶

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        // dp[j] = 子集和 mod 3 == j 时的最大和
        vector<long long> dp(3, 0);
        dp[1] = dp[2] = LLONG_MIN;  // 初始只有空集（和为 0，mod 3 == 0）

        for (int num : nums) {
            auto prev = dp;  // 拷贝上一轮状态
            for (int j = 0; j < 3; ++j) {
                int nj = (j + num % 3) % 3;
                dp[nj] = std::max(dp[nj], prev[j] + num);
            }
        }
        return (int)dp[0];
    }
};

复杂度： 时间 \(O(n)\)，空间 \(O(1)\)

推导示例¶

以 nums = [3, 6, 5, 1, 8] 为例：

初始:       dp = [0, -∞, -∞]
处理 3(r=0): dp = [3, -∞, -∞]
处理 6(r=0): dp = [9, -∞, -∞]
处理 5(r=2): dp = [9, -∞, 14]
处理 1(r=1): dp = [15, 10, 14]
处理 8(r=2): dp = [18, 22, 17]
dp[0] = 18 → 选 [3, 6, 1, 8]，和 = 18，18 % 3 == 0 ✓

注意事项¶

初始化 dp[1] = dp[2] = LLONG_MIN（负无穷），表示当前不存在余数为 1 或 2 的合法子集
每轮用 上一轮的状态 更新（所以需要拷贝 prev），否则同一个元素可能被重复计算
如果题目要求「子数组」而非「子集」，则需要不同的 DP 状态定义
面试时先确认是「子集」还是「子数组」，题意不同解法差很大

一面总结¶

#	知识域	核心考点
Q1	并发	六种内存序、acquire-release、happens-before
Q2	并发	SPSC 无锁队列中的 release-store / acquire-load 配对
Q4	并发	CAS 原子操作、无锁队列 MPMC、ABA 问题
Q5	OS	进程/线程/协程定义与内存分布
Q6	大数据	Flink exactly-once = checkpoint + 2PC
Q7.1	算法	BFS 层序遍历
Q7.2	算法	Kadane 最大子数组和
Q7.3	算法	DP mod 3 分组，最大可整除子集和

二面（2026-04-03）¶

侧重： 有锁/无锁队列实现对比、LRU Cache 设计、二叉树重建与复杂度分析

Q1. 有锁的队列怎么实现，SPSC 队列又应该怎么实现¶

回答¶

一、有锁队列¶

最直接的方式：一把互斥锁保护整个队列。

template <typename T>
class LockedQueue {
    std::queue<T> q_;
    mutable std::mutex mtx_;
    std::condition_variable cv_;

public:
    void push(const T& value) {
        {
            std::lock_guard<std::mutex> lock(mtx_);
            q_.push(value);
        }
        cv_.notify_one();  // 通知等待的消费者
    }

    T pop() {
        std::unique_lock<std::mutex> lock(mtx_);
        cv_.wait(lock, [this] { return !q_.empty(); });
        T value = std::move(q_.front());
        q_.pop();
        return value;
    }

    bool try_pop(T& value) {
        std::lock_guard<std::mutex> lock(mtx_);
        if (q_.empty()) return false;
        value = std::move(q_.front());
        q_.pop();
        return true;
    }
};

问题： 所有操作串行化（单锁），高并发下锁竞争严重。

优化方向：

优化	做法
双锁分离	head 和 tail 各一把锁，push 和 pop 可以并发进行
减小临界区	只在修改链表指针时加锁，数据拷贝在锁外完成

二、SPSC 无锁队列¶

单生产者单消费者场景 不需要锁也不需要 CAS，只需 acquire-release 内存序：

template <typename T, size_t Cap>
class SPSCQueue {
    std::array<T, Cap + 1> buf_;                       // 多留一槽区分满/空
    alignas(64) std::atomic<size_t> head_{0};          // 消费者写
    alignas(64) std::atomic<size_t> tail_{0};          // 生产者写

    size_t next(size_t i) const { return (i + 1) % (Cap + 1); }

public:
    bool push(const T& val) {
        size_t t = tail_.load(std::memory_order_relaxed);
        size_t nt = next(t);
        if (nt == head_.load(std::memory_order_acquire))  // 满
            return false;
        buf_[t] = val;
        tail_.store(nt, std::memory_order_release);       // 数据写完再更新 tail
        return true;
    }

    bool pop(T& val) {
        size_t h = head_.load(std::memory_order_relaxed);
        if (h == tail_.load(std::memory_order_acquire))   // 空
            return false;
        val = buf_[h];
        head_.store(next(h), std::memory_order_release);  // 数据读完再更新 head
        return true;
    }
};

有锁 vs SPSC 无锁对比¶

维度	有锁队列	SPSC 无锁
适用场景	MPMC 通用	严格一生产一消费
同步机制	mutex + condvar	atomic + memory order
系统调用	有（futex）	无
延迟	μs 级（锁竞争时）	ns 级
实现难度	低	中（需理解内存序）

注意事项¶

面试先写有锁版展示基本功，再写 SPSC 无锁版展示进阶能力
SPSC 无锁队列可以进一步优化：batch read/write、cache-line padding、prefetch
追问「MPMC 无锁」：需要 CAS（见一面 Q4），实现复杂度跳升一个量级

细看： 并发编程

Q2. LRU Cache 怎么实现，get 和 put 操作¶

回答¶

数据结构¶

哈希表 + 双向链表，两个操作均为 \(O(1)\)：

哈希表 unordered_map<key, list::iterator>：O(1) 查找节点
双向链表 list<pair<key, value>>：O(1) 移动/删除节点，维护使用顺序

链表头部 = 最近使用，链表尾部 = 最久未使用。

最近使用                              最久未使用
  HEAD ←→ [A] ←→ [B] ←→ [C] ←→ TAIL
                                 ↑
                           容量满时淘汰

完整代码¶

#include <list>
#include <unordered_map>

class LRUCache {
    int capacity_;
    std::list<std::pair<int, int>> lru_list_;                    // {key, value}
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map_;

public:
    LRUCache(int capacity) : capacity_(capacity) {}

    int get(int key) {
        auto it = map_.find(key);
        if (it == map_.end()) return -1;

        // 移到链表头部（最近使用）
        lru_list_.splice(lru_list_.begin(), lru_list_, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map_.find(key);

        if (it != map_.end()) {
            // key 已存在：更新值，移到头部
            it->second->second = value;
            lru_list_.splice(lru_list_.begin(), lru_list_, it->second);
            return;
        }

        // key 不存在：插入新节点
        if ((int)map_.size() >= capacity_) {
            // 淘汰尾部（最久未使用）
            int evict_key = lru_list_.back().first;
            map_.erase(evict_key);
            lru_list_.pop_back();
        }

        lru_list_.emplace_front(key, value);
        map_[key] = lru_list_.begin();
    }
};

关键操作图解¶

get(B)：

之前: HEAD ←→ [A] ←→ [B] ←→ [C] ←→ TAIL
之后: HEAD ←→ [B] ←→ [A] ←→ [C] ←→ TAIL
                              ↑ splice 把 B 移到头部

put(D)（容量满）：

之前: HEAD ←→ [B] ←→ [A] ←→ [C] ←→ TAIL    (cap=3)
淘汰C: HEAD ←→ [B] ←→ [A] ←→ TAIL
插入D: HEAD ←→ [D] ←→ [B] ←→ [A] ←→ TAIL

为什么用 `splice` 而不是 erase + push_front¶

std::list::splice 是 O(1) 的节点摘取和重新插入，不涉及内存分配和释放；而 erase + push_front 需要释放旧节点、分配新节点，且会使所有保存的 iterator 失效。

注意事项¶

要点	说明
哈希表存 iterator	`std::list` 的 iterator 在 splice/erase 其他节点时不会失效
淘汰时先删 map 再删 list	顺序不能反，否则 key 找不回来
线程安全版	整体加互斥锁，或分段锁（ConcurrentLRU）
LFU 变体	追问时提：LFU 需要额外维护频率计数和频率链表

细看： STL 容器深入

Q3. 手撕：前序 + 中序 → 后序（含复杂度分析与优化）¶

思路¶

前序遍历第一个元素是当前子树的根节点，在 中序遍历 中找到该根，即可划分左右子树，递归重建后输出后序。

前序: [根 | 左子树前序 | 右子树前序]
中序: [左子树中序 | 根 | 右子树中序]
后序: [左子树后序 | 右子树后序 | 根]    ← 目标

基础版代码¶

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> buildPostorder(vector<int>& preorder, vector<int>& inorder) {
        vector<int> result;
        build(preorder, 0, preorder.size() - 1,
              inorder,  0, inorder.size() - 1, result);
        return result;
    }

private:
    void build(vector<int>& pre, int preL, int preR,
               vector<int>& in,  int inL,  int inR,
               vector<int>& result) {
        if (preL > preR) return;

        int root = pre[preL];

        // 在中序中线性查找根节点位置
        int rootIdx = inL;
        while (in[rootIdx] != root) ++rootIdx;

        int leftSize = rootIdx - inL;

        // 递归左子树
        build(pre, preL + 1, preL + leftSize,
              in,  inL,      rootIdx - 1, result);
        // 递归右子树
        build(pre, preL + leftSize + 1, preR,
              in,  rootIdx + 1,          inR, result);

        // 后序：左、右、根
        result.push_back(root);
    }
};

复杂度分析¶

基础版¶

每一层递归需要在中序数组中 线性查找 根节点：

最好情况（平衡树）：每层将问题一分为二，递推 \(T(n) = 2T(n/2) + O(n)\)，由 Master 定理得 \(O(n \log n)\)
最差情况（退化链表）：每次根在中序最边上，\(T(n) = T(n-1) + O(n)\)，得 \(O(n^2)\)

类比排序算法： 与 快速排序 一模一样！平衡划分 \(O(n \log n)\)，极端不平衡 \(O(n^2)\)。

优化版：哈希表预建索引¶

用 unordered_map 预先存储中序数组中 值 → 下标 的映射，查找从 \(O(n)\) 降到 \(O(1)\)：

class Solution {
public:
    vector<int> buildPostorder(vector<int>& preorder, vector<int>& inorder) {
        // 预建哈希表：值 → 中序下标
        unordered_map<int, int> inMap;
        for (int i = 0; i < (int)inorder.size(); ++i) {
            inMap[inorder[i]] = i;
        }

        vector<int> result;
        build(preorder, 0, preorder.size() - 1,
              0, inorder.size() - 1, inMap, result);
        return result;
    }

private:
    void build(vector<int>& pre, int preL, int preR,
               int inL, int inR,
               unordered_map<int, int>& inMap,
               vector<int>& result) {
        if (preL > preR) return;

        int root = pre[preL];
        int rootIdx = inMap[root];   // O(1) 查找
        int leftSize = rootIdx - inL;

        build(pre, preL + 1, preL + leftSize,
              inL, rootIdx - 1, inMap, result);
        build(pre, preL + leftSize + 1, preR,
              rootIdx + 1, inR, inMap, result);

        result.push_back(root);
    }
};

优化后复杂度¶

每层递归只做 \(O(1)\) 的查找 + \(O(1)\) 的划分，递归函数本身每个节点恰好调用一次：

\[T(n) = T(k) + T(n-1-k) + O(1)\]

无论树的形状如何（平衡或退化），总调用次数 = 节点数 n：

时间：\(O(n)\)（每个节点恰好访问一次）
空间：\(O(n)\)（哈希表 + 递归栈，最差 \(O(n)\) 层）

面试官问「现在复杂度是多少」，答 \(O(n)\)——瓶颈从查找根节点变成了遍历所有节点本身。

完整对比¶

版本	查找根节点	最好	最差	空间
基础（线性查找）	\(O(n)\)	\(O(n \log n)\)	\(O(n^2)\)	\(O(n)\) 递归栈
优化（哈希表）	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(n)\) 哈希表 + 递归栈

注意事项¶

面试先写基础版，主动分析复杂度并类比快排，再提出优化方案——展示 完整的思考链路
前提假设：输入中 无重复元素（有重复则无法唯一确定树结构）
相关 LeetCode：105（前序+中序→构建二叉树）、106（中序+后序→构建二叉树）
追问「不建树直接输出后序」：本代码就是这样做的，递归过程中直接 push_back，不需要真正 new 节点

细看： 数据结构与算法

二面总结¶

#	知识域	核心考点
Q1	并发	有锁队列（mutex+condvar）vs SPSC 无锁队列（acquire-release）
Q2	数据结构设计	LRU Cache = 哈希表 + 双向链表，splice O(1)
Q3	算法	前序+中序→后序，复杂度类比快排，哈希优化到 O(n)

腾讯云 — 后台开发¶

一面¶

Q1. 你知道内存序吗¶

回答¶

什么是内存序（Memory Order）¶

C++11 六种内存序¶

Acquire-Release 配对¶

为什么不全用 seq_cst¶

注意事项¶

Q2. 内存序在你实现的 SPSC 队列上如何体现¶

回答¶

SPSC 队列核心结构¶

生产者 push¶

消费者 pop¶

内存序分析¶

注意事项¶

Q4. CAS 在无锁队列上是如何应用的¶

回答¶

什么是 CAS¶

CAS 在 MPMC 无锁队列中的应用¶

CAS 循环（CAS loop / spin）的核心思路¶

weak vs strong¶

ABA 问题¶

注意事项¶

Q5. 进程、线程、协程分别是什么，分别能使用哪里的内存¶

回答¶

核心对比¶

各自能使用的内存¶

协程的栈¶

注意事项¶

Q6. 用过 Hadoop、Flink 吗，知道 exactly-once 吗¶

回答¶

Hadoop vs Flink 简要对比¶

三种语义保证¶

Flink 的 Exactly-Once 实现¶

Kafka 的 Exactly-Once¶

注意事项¶

Q7. 手撕三道算法¶

7.1 二叉树层序遍历（LeetCode 102）¶

思路¶

代码¶

注意事项¶

7.2 最大子数组之和（LeetCode 53）¶

思路¶

代码¶

注意事项¶

7.3 数组中能被 3 整除的最大子集和¶

思路¶

代码¶

推导示例¶

注意事项¶

一面总结¶

二面（2026-04-03）¶

Q1. 有锁的队列怎么实现，SPSC 队列又应该怎么实现¶

回答¶

一、有锁队列¶

二、SPSC 无锁队列¶

有锁 vs SPSC 无锁 对比¶

注意事项¶

Q2. LRU Cache 怎么实现，get 和 put 操作¶

回答¶

数据结构¶

完整代码¶

关键操作图解¶

为什么用 splice 而不是 erase + push_front¶

注意事项¶

Q3. 手撕：前序 + 中序 → 后序（含复杂度分析与优化）¶

思路¶

基础版代码¶

复杂度分析¶

基础版¶

优化版：哈希表预建索引¶

优化后复杂度¶

完整对比¶

注意事项¶

二面总结¶

有锁 vs SPSC 无锁对比¶

为什么用 `splice` 而不是 erase + push_front¶