波克城市游戏客户端开发一面：消息乱序治理与方块放置算法

《面试题目》

1. 请做个人介绍
2. 你对这个岗位了解吗？目前主要找哪些方向？
3. 快手四个月实习中，哪个需求最有印象或成长最大？
4. 新人入团相关消息为什么会乱序？
5. 消息使用长连接还是短连接？
6. 接收部分消息后断网，重连后怎么处理？
7. 是否通过消息序列号判断漏收？序列号如何定义？
8. 900 毫秒短时缓冲的作用是什么？发生在客户端还是服务端？
9. 跨设备点击无法由单个客户端合并，缓冲的意义是什么？
10. 「身份键组合、批量追加、二次规整、历史分页和增量插入」分别是什么意思？
11. 大量历史消息如何分页？分页底层是否由你实现？
12. AIGC 项目中你具体设计和实现了什么？
13. 异步任务的调用、轮询和返回处理如何工作？
14. 歌词匹配、素材上传、视频生成分别由谁实现？
15. 音频与口型对齐问题如何排查、修复和验证？
16. 如何为 Block 类游戏组织棋盘和方块的数据结构？
17. 如何判断方块在指定位置能否放置？
18. 如何判断棋盘中是否还存在任意可放位置？
19. 梯形等不规则方块如何定义？
20. 支持 0°、90°、180°、270° 四个方向时如何实现？
21. 大四是否还有课程？
22. 你有什么想了解团队的？

《参考解析》

消息乱序的根因是「多路来源 + 异步处理」而不是网络本身。 同一个业务事件的数据可能来自切服/合服、多个异步请求、客户端本地操作与服务端推送，各自的到达时间不同；TCP 只保证单连接内有序，不保证跨连接、跨服务、跨端的有序。解决思路是给消息一个可比较的全序标识（如「服务端统一分配的单调递增序列号」或「时间戳 + 逻辑时钟」），客户端按标识排序与去重，而不是按到达顺序渲染；如果业务要求全局有序，就只能在单一分区/单一入口串行化，代价是吞吐。断网重连的正确做法：客户端记录已成功处理的最大连续序列号（水位），重连时带上水位请求增量补齐；服务端返回水位之后的增量，客户端再与本地缓存做合并排序；缺口无法补齐时降级为全量拉取最新一页。要强调「至少一次投递 + 客户端去重」比追求「恰好一次」更现实。

900ms 短时缓冲是「用延迟换有序」的工程折中。 消息到达后不立即渲染，先放进缓冲窗口（900ms）等待可能的乱序前置消息，窗口结束再按序列号排序统一提交渲染；这样能吸收网络抖动与多路来源造成的短时乱序，代价是每条消息的可感知延迟增加。它放在客户端（渲染层做规整），因为服务端无法知道客户端本地的到达顺序，而且跨设备的点击也无法由单个客户端合并——服务端只能保证下发的顺序，客户端要负责「按序与去重地呈现」。身份键组合指用「用户 id + 设备 + 业务类型」等字段拼出唯一定位键，用来判断两条消息是否是同一逻辑事件（去重）或同一用户的不同动作（合并）；批量追加是把窗口内的消息一次性写入列表而不是逐条触发渲染（减少重排与刷新）；二次规整是在批量追加后再做一次排序与去重（因为追加过程中可能又有新消息到达）；历史分页 + 增量插入指历史消息按游标分页拉取、新消息按序列号插到合适位置，两者在列表数据结构上要能共存（用可插入的有序结构，避免每次全量排序）。

AIGC 音画对齐的排查要落到「分段与时间轴」上。 链路通常是：上传素材 → 异步任务（歌词对齐/口型驱动/视频合成）→ 轮询或回调取结果 → 客户端回填播放。口型对不齐的常见原因：音频与视频的时间基准不一致（采样率、帧率、起始偏移）、分段驱动时每段的边界处理（段间静音或重叠）、以及歌词时间戳本身不准。排查手段是把链路拆成可量化节点：先用工具（如 ffmpeg）取出音频波形与歌词时间戳比对，再逐帧导出视频检查口型帧与音素的对齐偏移，确认是「整体偏移」（补一个固定 offset）还是「渐进漂移」（时间基准或帧率问题）；验证要自动化——固定一组素材跑回归，比较关键时间点的偏移量是否在阈值内。异步任务本身的设计要点：任务要有唯一 id 与状态机（排队/处理中/成功/失败，失败可重试并带原因），客户端用轮询（带退避）或 WebSocket 推送，结果要落可长期访问的存储而不是临时链接。

Block 类游戏的棋盘与方块设计，是这一场最实在的算法题。 棋盘用「二维数组或一维数组 + 索引换算」存储每个格子的状态（空/已占用/特殊块），方块则用相对坐标集合表示（例如 [(0,0),(0,1),(1,0),(1,1)] 表示 2×2），而不是用固定形状枚举——不规则的梯形、L 形都可以用坐标集合统一表达，配合一个 width/height 的包围盒加速边界判断。能否放置：把方块的相对坐标加上锚点得到绝对坐标，逐格判断「是否在棋盘内」且「目标格为空」，任一失败即不可放；优化上可以预计算每行的占用位图（bitmask），用位运算一次判断一整行（把「是否可放」变成几个按位与操作），这在每帧要枚举大量候选位置时是必要的。是否还存在可放位置：朴素做法是对每个空格 × 每个方块 × 四个方向依次尝试，复杂度是 格子数 × 方块数 × 4 × 方块格数；优化思路是只遍历空格的边界点（只有贴着已有块的位置才可能放得下）、对每种方块预生成四个方向的坐标模板、并对「所有方块都无法放入」提前剪枝；如果要频繁判断，可以维护「每种方块的可放位置计数」在落子时增量更新，而不是每次全盘重扫。四方向旋转的实现是把相对坐标做 90° 旋转（(x, y) → (y, -x)），再平移回非负坐标并重算包围盒；预生成四个方向的模板在初始化时算一次，运行期只做查表，避免每帧旋转计算。