面灵AI→

多益网络游戏服务端一面:大根堆、0/1 网格最短路与王者荣耀回放怎么设计

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

《面试题目》

  1. 自我介绍。
  2. 大根堆是什么?
  3. 数组和链表的内存分布情况?连续内存和不连续内存,插入数据后分别是什么样?
  4. 算法题:给定一个二维数组(值为 0/1),有一个开始节点 t、一个终点 s,值为 0 可以移动、为 1 不能移动,求 t 到 s 的最小距离。(10 分钟)
  5. 拷打实习:做过什么功能,挑一个展开讲。
  6. 了解过 MCP 和 Skill 吗?
  7. 项目里多智能体调用模型的策略是怎样的?
  8. harness 用的是 DSH 吗?了解过 DeepSeek Harness 吗?
  9. 场景题:王者荣耀里三杀、四杀、五杀时会录一段视频,对局结束后可以看这段对局的回放;如果要实现完整对局的回放(可以切换视角,第一人称/第三人称),怎么去做?
  10. Redis 的持久化方式有哪些?
  11. 实习期间上班的强度怎么样?能否接受高强度的工作?

《参考解析》

大根堆: 一种完全二叉树,每个节点的值都不小于其子节点,因此堆顶是整个集合的最大值。物理上用数组存储,下标 i 的子节点是 2i+1 和 2i+2,父节点是 (i-1)/2,不需要指针。核心操作是上浮(插入到末尾后与父节点比较交换,O(log n))与下沉(取出堆顶后把末尾元素放到根再向下比较交换,O(log n)),建堆用自底向上的下沉可以做到 O(n)。典型用途:优先队列、TopK(维护大小为 K 的小根堆求最大 K 个)、堆排序、定时器与任务调度。要补一句与「小根堆求 TopK」的方向关系——求最大的 K 个用小根堆,求最小的 K 个用大根堆,很多人这里答反。

数组与链表的内存分布: 数组是一段连续内存,元素地址 = 首地址 + i × 元素大小,所以随机访问 O(1),CPU 缓存预取友好、局部性好;代价是插入删除要搬移后续元素(尾部追加除外),扩容时要重新申请一块更大的连续内存并整体拷贝(ArrayList 的 1.5 倍扩容就是这个动作)。链表是离散的节点,每个节点存数据和指向下一个(或前后)节点的指针,插入删除只改指针 O(1)(前提是已经持有位置),但访问第 i 个必须从头走 O(n),且节点分散导致缓存命中率低、每个节点还要额外付出指针的内存开销。

插入数据后的差别要讲具体:数组中间插一个元素,后面所有元素后移一位,涉及一次 memmove;如果容量已满,先扩容拷贝再插入,最坏 O(n)。链表插入只新建节点并改两个指针(双向链表改四个),O(1),但 malloc 本身可能有开销、节点内存不连续。工程结论:读多写少、元素数量可预估用数组;频繁在中间增删、元素数量变化大用链表;需要同时兼顾随机访问与插入就用「分块」结构(如 std::deque)。

0/1 网格最短路: 无权图的最短路用 BFS,不是 Dijkstra。把起点入队、距离设 0,四方向(或八方向,要跟面试官确认)扩展,遇到 1 或越界跳过,第一次到达终点时的距离就是最短距离。时间 O(n·m),空间 O(n·m)(队列加访问标记)。要主动说明的几个点:原地把走过的 0 改成 1 可以省掉 visited 数组;起终点相同返回 0;起终点本身是 1 时无解;如果不允许斜走要说清是四连通。10 分钟写不完完整工程代码没关系,把「BFS + 队列 + 方向数组 + 边界判断」四段写清楚,再口述复杂度即可。

MCP 与 Skill 的区别: MCP(Model Context Protocol)是模型与外部工具/数据源之间的连接协议,把「有哪些工具、参数是什么、怎么调用」标准化,让同一套工具能被不同客户端复用;Skill 更像一份按需加载的操作手册或能力包,用自然语言描述某类任务该怎么做、有哪些步骤与注意事项,模型在需要时读进来照着做。一句话概括:MCP 解决「能调用什么」,Skill 解决「该怎么用」。答的时候举个自己的例子,比如用 MCP 接浏览器与文件系统、用 Skill 固化某条业务流程,比背定义有说服力。

多智能体调用模型的策略: 可以按四种模式讲——路由(一个调度者判断该交给哪个专职 Agent)、流水线(规划 → 执行 → 评审,逐级传递结构化产物)、辩论/投票(多个 Agent 独立给结论再汇总,适合判断类任务)、中心协调(Coordinator 拆任务、分发、汇总,适合长任务)。选型的判据是任务能否拆成弱耦合的子任务、对延迟与成本的容忍度、以及是否需要多视角。要补代价:多 Agent 会放大 token 成本与延迟,链路越长越难调试,所以简单任务一律单 Agent,只有任务确实可以并行、或需要独立评审时才上多 Agent。

王者荣耀完整对局回放怎么设计: 先分清「精彩片段」与「完整回放」——前者是录像文件,后者必须由服务端的状态与指令重建。核心思路是「记录输入,回放时重演」而不是「录视频」:服务端按固定帧率(如 15 或 30 tick/s)记录所有玩家的操作指令(移动、技能、攻击、购买装备)与随机种子,回放客户端用同一份战斗逻辑以确定性的方式重演,得到与当时完全一致的局面。这样数据量小(一局几十分钟的指令流通常只有几百 KB 到几 MB),还能自由切换视角、暂停、快进。

关键设计点:① 确定性——战斗逻辑里不能用浮点不确定运算、不能依赖帧率、随机数必须来自可复现的种子,否则重演会漂移;② 快照与关键帧——每隔 N 秒存一份完整状态快照,回放时先加载最近的快照再重演少量指令,避免从头算导致拖动进度条很慢;③ 视角切换——回放数据里保存每个单位的完整状态(位置、朝向、血量、技能 CD),客户端可以任意选择摄像机跟随哪个单位,第一人称就是把摄像机贴到该单位头部、第三人称是第三人称跟随,两者只是摄像机参数不同;④ 存储与分发——按对局 ID 存对象存储,客户端按需下载并流式加载;热门对局可以预生成缓存;⑤ 隐私与版本——版本升级会让旧逻辑失效,需要保留对局当时的逻辑版本号,回放客户端按版本加载对应规则。

Redis 持久化: RDB 是某一时刻的全量快照(bgsave 时 fork 子进程写临时文件,写完原子替换),文件紧凑、恢复快,适合备份与灾备,但两次快照之间的数据会丢。AOF 是追加写命令日志(appendfsync 可选 always / everysec / no),everysec 最多丢一秒,恢复时需要重放命令,文件比 RDB 大,所以有 AOF 重写把冗余命令压缩。Redis 4.0 起支持混合持久化(AOF 重写时前半段放 RDB 格式、后半段放增量命令),兼顾恢复速度与数据完整性。还要说清 fork 的代价:写时复制会让内存占用短时上升,大实例要控制快照频率;主从复制与哨兵/集群解决的是可用性,不能替代持久化。

工作强度题如实说自己的节奏即可,重点表达「能接受项目节点的阶段性高强度,但不认为长期靠加班补排期是可持续的」,并给一个自己真实扛过的高强度片段(版本上线前连续几天、怎么排优先级、结果如何)。