面灵AI→

米哈游游戏服务端研发一面凉经:gdb、epoll、手撕 vector 与树路径计数

轮次
一面
时间
2026-11
来源
牛客网

《面试题目》

  1. 自我介绍。
  2. 实习的工作经历追问。
  3. gdb 命令怎么使用?
  4. 项目经历追问,重点问数据结构是怎么设计的。
  5. epoll 的 API 有哪些?(项目里用了 IO 多路复用)
  6. 手撕:实现一个 vector,包括 push_back、pop_back、begin 等操作。
  7. 手撕:对一棵树遍历,统计从某个节点到其后代的路径上节点值之和等于 target 的条数,起点不必是根节点,终点也不必是叶子节点。
  8. MySQL 的索引是怎么实现的?为什么用这种结构?
  9. C++ 的迭代器失效是什么?哪些情况下会出现?
  10. 你对游戏服务端研发有哪些理解?
  11. 怎么用 Redis 实现令牌桶算法?(实习经历)
  12. 一个很大的数组排序,用哪个排序最好?
  13. MySQL 的表锁和行锁分别是什么?
  14. fork 的返回值是什么?

《参考解析》

gdb 的常用操作:启动与附加(gdb ./bin、gdb -p <pid>)、断点(b file:line、b func、条件断点 b x if v==1)、运行控制(run、continue、next、step、finish、until)、栈与变量(bt、frame n、info locals、print、p *ptr@10 看数组)、线程(info threads、thread n、set scheduler-locking)、监视点(watch 观察内存写入)、以及崩溃后的 core dump 分析(gdb ./bin core、bt full)。生产环境更常用 pstack、gcore 与 catchsegv,回答时说明「先定位是哪类崩溃(空指针、越界、重复释放),再回到具体帧看参数」。

epoll 的 API:epoll_create1 创建实例,epoll_ctl(EPOLL_CTL_ADD/MOD/DEL) 注册与修改关注的事件,epoll_wait 等待就绪事件。触发模式有水平触发(LT,只要可读就持续通知)与边缘触发(ET,只在状态变化时通知一次,必须配合非阻塞 fd 一次读到 EAGAIN)。相比 select/poll,epoll 用内核中的红黑树管理 fd、就绪链表返回结果,避免每次调用全量拷贝与 O(n) 扫描,适合大量连接中只有少量活跃的场景。常见追问是「ET 下漏读会怎样」「惊群怎么处理」(EPOLLEXCLUSIVE、SO_REUSEPORT)。

手写 vector 的要点:三个指针 begin_、end_(有效元素末尾)、cap_(容量末尾);push_back 时若 end_ == cap_ 就按 1.5 或 2 倍扩容,申请新内存、移动或拷贝旧元素、释放旧内存、更新指针,注意扩容后所有迭代器与指针失效;pop_back 只析构末尾元素并前移 end_、不释放内存;begin/end 返回迭代器(可先用 T* 代替);还要补齐拷贝构造、赋值、析构(Rule of Three/Five),reserve、size、capacity。异常安全上,扩容时若移动构造抛异常要保证原容器不变。

树的路径计数:题目要求起点任意、终点是其子孙,本质是统计「祖先到后代」的路径和为 target 的对数。做法是 DFS 维护根到当前节点路径上的前缀和(哈希表记录每个前缀和出现的次数),到节点 u 时前缀和 S(u),若 S(u) - target 在表中出现过 k 次,就新增 k 条以 u 为终点的路径;处理完子树后把 S(u) 从表中减一(回溯)。复杂度 O(n)。原帖的写法是 DFS 时带一个 bool 表示「是否已经开始取值」,即每个节点可以选择作为起点或不选,把所有可能的起点都枚举一遍,复杂度退化到 O(n²),但思路直观、面试时讲清取舍即可。

MySQL 索引为什么是 B+ 树:B+ 树是多路平衡树,非叶子节点只存键、叶子节点存数据并用链表相连,因此同样大小的页能容纳更多键、树高更低(通常 3~4 层就能覆盖千万级数据),一次查询的磁盘 IO 次数少且稳定;叶子链表让范围查询与排序可以顺序扫描。相比 B 树,B+ 树的数据都在叶子、查询路径等长;相比哈希索引,它支持范围与排序;相比跳表,它更适合磁盘页对齐的读写。

迭代器失效:vector 在扩容时全部失效,insert/erase 位置之后的失效;deque 在中间插入删除时全部失效、首尾操作只影响被操作的迭代器;list/map/set 只有被删除元素的迭代器失效;unordered_* 在 rehash 时全部失效。根因是底层存储被重新分配或元素位置移动。规避方式是用索引代替迭代器、在修改后重新获取、或用 erase 的返回值继续遍历。

游戏服务端的理解:核心是「有状态的长连接 + 强实时的广播」。要处理连接保持与断线重连、房间/场景的会话管理、状态同步(帧同步或状态同步)与广播风暴、定时器与心跳、以及单局内的顺序与一致性;工程上关心单机承载、GC 与延迟抖动(C++ 服务更多是内存池与对象复用)、跨服与分线、防作弊与日志回放。可以结合项目说明「你做的那部分在整条链路的哪个位置」。

Redis 实现令牌桶:用 Hash 存 tokens 与 last_refill_ts,取令牌时用 Lua 脚本原子地算出距上次补充的时间、按速率补桶(上限为容量),够则扣减并放行,不够则拒绝或返回需要等待的时间。Lua 保证「读-算-写」不被并发打断;过期时间设在桶满所需时间之后即可自动清理。另一种做法是用 Redis 的计数 + 过期做固定窗口,但它有边界突刺,令牌桶能平滑限流。要说明时钟用 Redis 服务端时间(TIME)还是客户端时间,多实例部署时前者更可靠。

很大的数组排序:先问数据特征。全是整数且范围有限用计数排序(O(n+k));内存放得下、要求稳定用归并;平均性能最好、原地排序用快排(最坏 O(n²),用三数取中或随机 pivot 缓解);要求最坏 O(n log n) 用堆排;几乎有序用插入排序或 Timsort。数据放不进内存时要外部排序:分块排序写临时文件、再多路归并。回答时给出「数据量、内存、是否稳定、能否接受最坏情况」这四个前提,再选算法。

表锁与行锁:表锁锁整张表,开销小、并发度低,MyISAM 只有表锁;行锁锁住具体索引记录,开销大、并发度高,InnoDB 支持。行锁是加在索引上的,所以「没走索引的更新会退化成锁全表(实际是锁所有扫描到的行 + 间隙)」。InnoDB 还有间隙锁与 next-key lock(RR 隔离级别下防幻读),以及意向锁(表级,表示事务准备在表中加行锁)。

fork 的返回值:父进程返回子进程的 PID(大于 0),子进程返回 0,出错返回 -1 并设置 errno。父子进程返回后各自继续执行 fork 之后的代码,靠返回值区分分支;子进程继承父进程的文件描述符表(共享打开文件偏移)与内存的写时复制副本。常追问的是「一次调用两次返回」「子进程要不要 exec」「父进程不 wait 会产生僵尸进程」。