米哈游 C++ 技术一面回顾

面试官提问清单

项目与工程设计

1. 请简单自我介绍。
2. 最近一个项目的背景是什么，是个人项目、课程项目还是团队项目？
3. 团队规模多少？你负责哪些模块？
4. 项目中的热点检测具体解决什么问题，触发和结束条件如何定义？
5. 峰值时的输入量级或并发量级大约是多少？
6. 该项目是客户端还是服务端？
7. 多路实时输入、解码、渲染或分析时，遇到过哪些性能瓶颈？
8. CPU/GPU 解码、本地模型推理等高算力任务如何优化和取舍？
9. 扫码登录的整体流程和原理是什么？
10. 除扫码外是否支持其他登录方式？会话如何复用和失效？
11. 是否了解 OAuth 2.0 的授权流程？
12. 项目是否使用数据库、缓存或其他持久化组件？
13. 不使用数据库时，数据如何落地、查询和管理？
14. 是否接触过图形学、3D 数学或实时渲染相关知识？

数据结构与算法基础

1. 数组和链表分别有什么特点？
2. 顺序遍历数组和顺序遍历链表，哪个通常更快？为什么？
3. AVL 树和红黑树有什么区别？
4. 二者查找、插入、删除的时间复杂度分别是什么？
5. 哈希表与平衡树相比有什么特点和适用场景？
6. 堆是什么结构，通常如何实现？插入和删除堆顶如何完成？
7. Dijkstra 与 A* 分别解决什么问题，如何选择？

C++

1. const int* 与 int* const 的区别是什么？
2. 什么是右值引用，移动语义解决了什么问题？
3. 是否在实际代码中使用过右值引用或 std::move？
4. push_back 与 emplace_back 有什么区别？
5. static_cast、dynamic_cast、reinterpret_cast 分别适用于什么场景？
6. static_cast 与 dynamic_cast 的检查时机有什么区别？
7. dynamic_cast 如何在运行时判断对象类型？
8. volatile 的用途是什么？它能否用于线程同步？
9. 什么是菱形继承，会带来什么问题？
10. 菱形继承如何解决重复基类和调用歧义？
11. new/delete 与 malloc/free 的区别是什么？
12. new 和 malloc 的底层分配链路有什么关系？
13. unique_ptr、shared_ptr、weak_ptr 的所有权模型分别是什么？
14. 两个线程各自持有一个共享同一对象的 shared_ptr，并在不同时间释放，是否安全？

操作系统与网络

1. 用户态和内核态是什么，为什么需要区分？
2. 一个进程的典型虚拟地址空间由哪些区域组成？
3. 进程最多能使用多少内存，受哪些因素限制？
4. 为什么多个进程可申请的虚拟内存总量大于物理内存？
5. 物理内存不足时，页面回收、swap 和 OOM 大致如何发生？
6. 是否接触过 TCP、epoll 或网络事件循环？
7. TCP 的主要特性是什么？它如何保证可靠有序？
8. TCP 在哪些情况下会重传？
9. TIME_WAIT 在谁身上出现，为什么要等待？
10. 流量控制与拥塞控制分别保护什么，如何限制发送量？

现场编程

1. 删除有序链表中的重复元素，使每个值只保留一次；要求 O(n) 时间、O(1) 额外空间。
2. 返回整数数组中第 K 大元素；题目要求线性时间，并进一步限制不能直接使用 std::sort 或 priority_queue。

知识点回顾

项目题：按“目标—链路—约束—指标—降级”回答

实时客户端、工具或服务端项目，不应只报出“用了什么库”或“开了多少线程”。更有效的回答顺序是：

目标：要保证什么体验或功能？
链路：输入 → 处理 → 队列 → 输出的关键数据流是什么？
约束：CPU、GPU、显存、网络、磁盘和延迟上限是什么？
指标：吞吐、P95/P99 延迟、队列深度、丢帧、CPU/GPU 利用率如何测量？
降级：处理速度跟不上输入时，阻塞、限流、丢帧、降帧还是关闭非关键任务？

例如多路实时媒体管线可抽象为：

网络接收 → 解复用 → 解码 → 色彩转换 → 渲染
                     ├→ 分段存档
                     └→ 异步分析

重点不是盲目“全都上 GPU”。应先找到瓶颈：软件解码、GPU 解码会话数、GPU↔CPU 拷贝、色彩转换、渲染同步、模型推理或磁盘写入都可能先到上限。若硬件与 API 支持，可减少不必要的 GPU→CPU→GPU 往返；但必须用统一机器、输入路数、分辨率、帧率和采样时长验证优化收益。

扫码登录一般是“创建短期二维码会话 → 展示二维码 → 轮询或订阅状态 → 用户确认 → 获取会话凭据 → 安全保存和刷新”。要考虑过期、取消、轮询退避、失败重试、登出和凭据保护。OAuth 2.0 的授权码模式还应理解授权服务器、资源服务器、state、PKCE、access token 和 refresh token 的职责。

数组、链表、树、哈希和堆

顺序遍历数组与链表都是 O(n)，但数组通常更快：元素连续，CPU cache 和预取更容易生效；链表节点分散，指针追逐容易产生 cache miss。不要仅以“数组可以 O(1) 随机访问”回答遍历性能问题。

结构	核心性质	典型复杂度 / 取舍
AVL 树	高度平衡更严格	查找、插入、删除都是 O(log n)；树通常更矮，更新调整更多
红黑树	平衡较松，最长路径受黑高约束	操作都是 O(log n)；更新旋转通常较少，关联容器常用
哈希表	hash(key) 定位桶，再处理冲突	平均 O(1)，最坏 O(n)；无序，负载过高要 rehash
堆	满足堆序的完全二叉树，常用数组	top O(1)，插入/删除堆顶 O(log n)，建堆 O(n)

堆使用数组时：

parent(i) = (i - 1) / 2
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

插入在尾部放入元素后上浮；删除堆顶时用尾元素覆盖堆顶后下沉。

Dijkstra 用于非负权图的单源最短路，每次扩展当前距离 g(n) 最小的节点。A* 按 f(n) = g(n) + h(n) 扩展，h(n) 是到目标的启发函数；h = 0 时退化为 Dijkstra。面向明确目标的寻路常用 A*，而求源点到所有点距离时 Dijkstra 更合适。

C++ 速答

const 指针

const int* p1 = nullptr; // p1 可改，不能经 p1 修改 int
int* const p2 = nullptr; // p2 不可改，可经 p2 修改 int

const int* const 则同时限制指针和所指对象。

右值引用、std::move 和容器插入

右值引用支持资源转移，减少不必要的深拷贝。std::move 自身不移动资源，只把表达式转换成可匹配移动重载的值类别；真正是否移动取决于后续构造或赋值操作。移动后对象仍然有效、可析构和可重新赋值，只是内容通常未指定。

push_back 接收已有对象，传左值通常复制，传右值通常移动；emplace_back(args...) 在元素存储位置用构造参数直接构造。emplace_back 不保证总更快：若传入的本就是 T，仍可能发生复制或移动；扩容时两者都可能搬迁旧元素。

cast、RTTI、volatile 与继承

工具	正确边界
static_cast	编译期可检查的显式转换；错误向下转换不会做运行时保护
dynamic_cast	多态继承体系的运行时安全转换；指针失败返回 nullptr，引用失败抛 std::bad_cast
reinterpret_cast	低级表示重解释；对齐、别名、对象生命周期不正确时风险很高
volatile	防止编译器随意删除/合并可观察访问；适用于 MMIO 等场景，不是多线程同步

dynamic_cast 依赖 RTTI；很多实现将运行时类型元数据与虚表关联，但不能把某个编译器的虚表布局当作语言标准。

菱形继承中，两个分支普通继承同一基类会让最派生类拥有两份基类子对象，造成状态重复和歧义。虚继承可共享一份虚基类；该虚基类由最派生类构造。若两个分支都覆盖同一虚函数，最派生类还需保证唯一最终覆盖者。

内存与智能指针

对比项	new/delete	malloc/free
语义	获取存储后构造对象 / 析构后释放	获取 / 释放原始字节存储
失败	默认抛 std::bad_alloc	返回 nullptr
类型	有类型	返回 void*
配对	new/delete，new[]/delete[]	malloc/free

new 表达式通常会调用可重载的 operator new，但标准不要求它底层一定调用 malloc。工程中优先用 RAII、容器和智能指针。

• unique_ptr：独占所有权，不可复制、可移动；
• shared_ptr：控制块维护强引用计数；最后一个强引用释放时销毁对象；
• weak_ptr：不增加强引用计数，使用 lock() 安全观察对象并打破循环引用。

不同 shared_ptr 实例共享控制块时，引用计数操作可以并发；但被管理对象不自动线程安全，同一个 shared_ptr 变量也不能被无同步地并发读写。

操作系统与 TCP

用户态受限，不能直接执行特权指令或随意访问设备、内核地址；内核态负责调度、内存、文件、网络和驱动。系统调用、异常、缺页和中断都可能使 CPU 进入内核。

典型进程地址空间包括可执行文件相关的 .text/.rodata/.data/.bss，以及 heap、mmap 区域、共享库和线程栈。真实布局受 OS、ABI、ASLR、PIE 和分配器影响。

需要区分三件事：虚拟地址范围是否被保留、系统是否承诺可提供后备资源、页面是否当前驻留在物理内存。首次访问未映射的按需分配页会触发缺页，内核分配物理页并更新页表。内存压力大时可回收缓存或把不活跃匿名页换出到 swap；频繁换入换出会导致抖动，无法满足内存请求时可能发生 OOM。

TCP 可靠有序字节流依赖序列号、ACK、校验和、超时重传、快速重传、乱序重排、去重和滑动窗口。SYN 用于建立连接，不能替代数据序列号 SEQ。

• 超时重传：RTO 内未收到足够 ACK；
• 快速重传：通常收到 3 个重复 ACK 时，提前重传疑似丢失段；
• TIME_WAIT：通常由主动关闭、发送最后 ACK 的一方进入，用于可靠确认最后挥手并让旧报文消失；
• 流量控制：接收端用 rwnd 保护自身缓冲；
• 拥塞控制：发送端用 cwnd 根据网络反馈保护网络；
• 实际在途数据通常受 min(rwnd, cwnd) 限制。

现场编程复盘要点

有序链表去重

维护 current：若 current->val == current->next->val，摘除 next；否则前进。时间 O(n)、额外空间 O(1)。

ListNode* delete_duplicates(ListNode* head) {
    for (ListNode* current = head; current && current->next;) {
        if (current->val == current->next->val) {
            ListNode* duplicate = current->next;
            current->next = duplicate->next;
            delete duplicate; // 取决于题目的节点所有权约定
        } else {
            current = current->next;
        }
    }
    return head;
}

第 K 大元素

大小为 K 的小顶堆适合流式 Top K，复杂度 O(n log k)，但不满足题目明确要求 O(n) 的场景。此时应使用 Quickselect：把第 K 大转成升序下标 n-k，每轮 partition 后只进入目标所在一边，随机 pivot 时平均 O(n)、原地额外空间 O(1)。

int find_kth_largest(std::vector<int>& nums, int k) {
    const int target = static_cast<int>(nums.size()) - k;
    int left = 0;
    int right = static_cast<int>(nums.size()) - 1;

    while (left <= right) {
        const int pivot = nums[right];
        int store = left;
        for (int i = left; i < right; ++i) {
            if (nums[i] <= pivot) {
                std::swap(nums[store++], nums[i]);
            }
        }
        std::swap(nums[store], nums[right]);

        if (store == target) return nums[store];
        if (store < target) left = store + 1;
        else right = store - 1;
    }
    throw std::logic_error("unreachable");
}

固定 pivot 的最坏复杂度为 O(n²)；随机化 pivot 可获得平均 O(n)。若题目强调最坏 O(n)，需要说明 BFPRT，而不是把普通 Quickselect 说成最坏线性。

本次回答中需要改进的地方

项目与工程表达

• 问题：项目回答能给出功能流程，但主线不够集中，多个模块、性能点和细节交错出现；部分性能结论缺少测试环境、输入规模和指标口径。
• 改进：每个项目先用 60 秒讲清“目标、职责、架构、结果”，再准备热点检测、性能优化、登录/持久化三个可深挖案例。所有性能数据要能说明机器、路数、分辨率、帧率、测试时长和优化前后结果。
• 问题：扫码登录回答只覆盖请求二维码、轮询和保存凭据，未展开过期、取消、退避、刷新与安全存储。
• 改进：补齐会话状态机和 OAuth 2.0 授权码 + PKCE 的基本流程。

数据结构与算法

• 问题：AVL 与红黑树的核心取舍有所了解，但把红黑树插入复杂度误说成常数级。
• 改进：记住二者增删查都是 O(log n)；区别是平衡强度、树高和旋转/调整次数。
• 问题：哈希表、堆、Dijkstra 和 A* 停留在“听过/会调用”的层面，无法完整说明实现和场景。
• 改进：手写堆的上浮、下沉和建堆；能说清哈希冲突/负载因子/rehash；掌握 Dijkstra 与 A* 的 g、h、f 关系。
• 问题：第 K 大先给出了正确的小顶堆方案，但没有立即指出它是 O(n log k)，不满足 O(n) 约束；限制 STL 后没有转换到 Quickselect 或手写堆。
• 改进：算法题先报朴素方案和复杂度，再根据约束选算法。该题优先练习随机化 Quickselect；同时保留手写小顶堆作为禁用库时的降级方案。

C++

• 问题：右值引用回答把“移动后对象不能用”说得过强，且没有区分 std::move 与实际发生的移动构造/赋值。
• 改进：统一表述为“移动后对象仍然有效，但值未指定”；std::move 只做类型转换。
• 问题：push_back 与 emplace_back 的区别、dynamic_cast 的失败行为、RTTI 的边界和 reinterpret_cast 的风险不够完整。
• 改进：用“已有对象 vs 构造参数”“编译期转换 vs 运行时安全检查”“对象生命周期/对齐/别名”建立对比表。
• 问题：把 volatile 解释成“每次从内存读、不走缓存”，容易误导；未明确它不能处理普通多线程同步。
• 改进：记住 volatile 主要约束编译器优化，MMIO 是典型场景；并发同步使用 atomic 或锁。
• 问题：智能指针回答已正确区分“控制块计数”和“对象线程安全”，但 weak_ptr、同一 shared_ptr 变量的并发读写边界没有展开。
• 改进：补齐 weak_ptr::lock()、循环引用和 atomic<shared_ptr<T>> 的使用边界。

操作系统与网络

• 问题：用户态/内核态、地址空间和 swap 都能说出关键词，但无法连成“虚拟地址 → 页表 → 缺页 → 物理页 → 回收/换出 → OOM”的完整链路。
• 改进：按 reserve、commit、resident 三层解释虚拟内存；再串联按需分页、swap、抖动和 OOM。
• 问题：TCP 可靠性回答混淆了 SYN 与序列号；只说出超时重传，没有快速重传；TIME_WAIT 错误地认为双方都会进入；流量控制和拥塞控制没有落到 rwnd、cwnd 与 min(rwnd, cwnd)。
• 改进：按“序列号/ACK/校验和/重传/重排/窗口”组织可靠性；明确主动关闭方通常进入 TIME_WAIT；区分保护接收端的 rwnd 与保护网络的 cwnd。

面试表达

• 问题：回答开头频繁出现“嗯、好像、应该、可能”，结论和复杂度不够靠前；部分熟悉的知识点因表述犹豫而显得没有掌握。
• 改进：固定使用“结论 → 原理 → 边界/取舍”结构。不会时先明确已知部分和推导路径，不要用不确定的术语填充。
• 问题：现场编码前没有先说不变量和边界，第二题在原方案不满足约束后缺少明确的切换策略。
• 改进：写代码前先复述约束、报告复杂度、声明选择的算法和循环不变量；每题至少手测空输入、单元素、重复值和极端 K。