柠檬微趣 U3D 客户端：笔试与一二三面全记录

《面试题目》

1. 自我介绍
2. 实习是否都是研究生阶段？研究方向和游戏相关吗？
3. C++ 编译时多态、运行时多态的实现原理是什么？
4. 虚指针的大小是多少？
5. 多重继承 A、B，C 继承 A、B 且都有同名虚函数，调用歧义怎么处理？虚继承后虚表布局是怎样的？
6. C++ 类对象大小由哪些因素决定？
7. 普通类成员函数占实例对象空间吗？
8. static 静态变量占对象实例空间吗？
9. 空类实例大小是多少？为什么？
10. 单继承的构造、析构执行顺序是怎样的？
11. 什么时候析构函数必须是虚函数？
12. 类不会被继承，是否需要虚析构？
13. 构造函数能不能为虚函数？原因是什么？
14. 析构函数内部调用虚函数会有什么行为？
15. unordered_map 的底层实现是什么？哈希冲突、哈希攻击怎么理解？
16. unordered_map 负载高时如何扩容？
17. vector 的扩容机制是怎样的？
18. vector 迁移元素的时间复杂度是多少（移动构造 / 拷贝构造）？
19. 虚拟内存的优势是什么？
20. 分页还是分段？页大小是多少？
21. 32 位系统单进程最大能申请多少堆内存？
22. malloc 的底层实现原理是什么？
23. malloc(1) 实际分配多少内存？
24. 手撕：spells × positions >= success，统计每个咒语满足条件的药水数量
25. 反问
26. 简单自我介绍
27. 谈谈你对游戏客户端开发岗位的理解
28. 面向程序的系统文档应该写哪些内容？策划需求文档和程序系统设计文档的区别是什么？
29. 设计炸弹倒计时组件：UI 显示剩余时间，协程每秒减 1 是否可靠？为什么？
30. 背包里有大量限时到期的道具，每个道具都挂倒计时性能差，如何优化？
31. 常见排序算法有哪些？从哪些维度选择排序算法？排序的稳定性指什么？
32. 单链表的定义是什么？两个单链表（每个节点最多 1 个后继）全部拓扑构型分析（有环无环分类讨论）
33. 手撕：两个无环单链表判断是否相交，找出第一个相交节点
34. 反问
35. C++ 获取内存有几种方式？
36. 最大能申请多少内存？
37. 红黑树和哈希表对比：时间空间复杂度是多少？怎么算的？

《参考解析》

虚函数与对象布局：运行时多态靠虚函数表——对象头部一个 vptr 指向类的 vtable，虚函数调用是”取 vptr → 按偏移取函数指针 → 间接跳转”，所以 64 位下 vptr 是 8 字节；编译时多态靠模板与重载在编译期定死调用目标，没有运行时代价。多重继承 A、B 且同名虚函数时，C 必须自己重写该函数（或用 using 明确指定）才能消除歧义，否则编译报错；虚继承（菱形继承）下最派生类对象里会有多个 vptr，虚基类子对象放在末尾并由虚基类表记录偏移，C 里会出现 thunk 做 this 指针调整。类大小由非静态数据成员、虚函数（vptr，多继承/虚继承可能多个）、对齐与 padding、[[no_unique_address]] 之类修饰决定；普通成员函数、static 数据成员、static 函数都不占对象空间（static 数据成员在数据段）；空类大小是 1 字节，保证不同对象地址唯一，含虚函数时空类变成 8 字节（只放 vptr）。构造顺序是基类 → 成员（按声明顺序）→ 自身构造函数体，析构完全逆序。析构函数必须是虚函数的情形是”会用基类指针删除派生类对象”；类不会被继承（final）就不需要虚析构；构造函数不能是虚函数，因为此时 vptr 还没建立、无法确定要构造哪个类型；析构函数体内调用虚函数只会调用当前类的版本，因为派生类部分已经析构、vptr 被重置回本类。

vector 与 unordered_map 的扩容：vector 容量不足时申请新块（GCC 是 2 倍、MSVC 是 1.5 倍）、搬移元素、释放旧块，所以 push_back 均摊是 O(1)，且扩容会让所有迭代器、指针、引用失效。迁移元素的复杂度取决于类型：移动构造函数是 noexcept 时走移动，单个元素 O(1)；否则为防止搬移中途抛异常导致数据丢失，标准库会退化成拷贝构造，单个元素 O(n)，总体从 O(n) 变成 O(n²)。这也是”自定义类型尽量把移动构造标 noexcept”的原因。unordered_map 是桶数组 + 链表（或红黑树化的桶），默认最大负载因子 1.0，超过就 rehash：桶数扩到大约两倍并取素数，全部节点重新分布，复杂度 O(n)，迭代器同样全失效。哈希冲突用链地址法解决；哈希攻击指攻击者构造大量落到同一桶的 key，把查找退化成 O(n)，防法是加随机种子（如 SipHash）、限制单桶长度、或对输入做 HMAC。

内存分配相关：虚拟内存、malloc 与 32 位上界：虚拟内存的优势是进程隔离（各有独立地址空间，越界不会踩别人）、可以映射不连续的物理页从而支持碎片化物理内存、按需分页与换出、文件映射与共享库只加载一份、以及 overcommit 让进程能申请超过物理内存的地址空间。x86-64 实际以分页为主，段机制基本扁平化，常规页大小 4KB，还有 2MB/1GB 的大页（减少 TLB miss）。32 位系统单进程用户态地址空间通常只有 2GB（Windows 默认 2GB、开 3GB 开关或 Linux 的 3G/1G 划分），所以单次连续申请的上限是 GB 级且受碎片影响，实际拿不到满额。malloc 在 glibc 里对小内存走 brk 维护的堆区、按 bin（fastbin/smallbin/unsorted bin 等）管理空闲块，对大内存（默认 ≥128KB）走 mmap 直接映射并在 free 时归还操作系统。malloc(1) 的实际可用大小是 24 字节（chunk 总长 32 字节，含 8 字节头部和对齐），因为分配器有最小块与 16 字节对齐要求，具体数值依赖分配器实现与位数。

倒计时组件与限时道具优化：用协程每秒减 1 不可靠，原因有三：协程受帧率与 Time.timeScale 影响（暂停、加速、切后台都会走偏）、每秒一次整数递减会累积误差且丢掉秒内精度、道具数量一多就是成百上千个协程，每个都要被调度器轮询。正确做法是存绝对到期时间戳（客户端展示用 Time.unscaledTime 或服务器时间），显示时用 Mathf.CeilToInt(endTime - now) 现算，切后台回来一次性对齐；显示层再降频（每 0.2~0.5 秒刷新一次 UI 文本）并对相同秒数的文本做缓存。背包里大量限时道具的优化思路是集中管理：把所有到期时间放进最小堆或时间轮，只对最近要到期的一批注册定时器，到期时批量处理并触发一次列表刷新；UI 只对可见格子开通”每秒刷新”，滚动列表复用单元格；再配合分层（分钟级只显示”剩余 X 分钟”，进入最后一分钟才按秒显示）把刷新次数压到很低。

排序选型、链表拓扑与相交链表：常见排序有冒泡/插入/选择（O(n²)，插入排序在近乎有序时有优势）、希尔、归并（稳定、O(n log n)、需要 O(n) 额外空间、适合链表与外排）、快排（平均 O(n log n)、原地、最坏 O(n²)、不稳定，需要随机化基准或三数取中）、堆排（O(n log n)、原地、不稳定）、计数/基数/桶（非比较排序，数据范围小时线性）。选择维度：数据规模与范围、初始有序度、是否需要稳定、额外空间是否受限、比较与交换的代价（对象大就排索引）。链表拓扑分析按有环/无环分成四类：两个都无环（要么不相交，要么尾部汇聚成 Y 形，不可能 X 形）、一个有一个无环（必不相交）、两个都有环（可能不相交、可能共环相交于环上同一点、也可能在入环前就相交成同一个环，需要先各自求环入口再判断）。判断相交的经典解法：两个无环链表先各求长度，长的先走长度差，再同步前进，第一个相同节点就是交点，时间 O(m+n)、空间 O(1)；也可以让两个指针互相”接力”遍历对方链表，走完 m+n 步后必然相遇。有环的情况先用快慢指针求环入口，再分别判断交点是否在环上。

面试复盘：作者总结三面的差异：一、二面偏基础与工程，答得顺、当天通知通过；三面面试官更偏纯粹的技术爱好者，问题更深，建议后面的人”从更底层的角度去回答”。笔试要特别注意题型——这家是 ACM 模式，需要自己引入给定的头文件（官方头文件与本地 IDE 冲突时会出现满屏报错，提前熟悉这种写法能省不少时间），AI 面的题目基本能在公开面经里找到原型，准备过就能过。