科大讯飞 AI 算法工程师（数据岗）笔试复盘：重排算法题、概率与 C++ 编译原理

《面试题目》

1. 算法题：给定一个序列，怎么判断它能否按题目要求重排？
2. 概率题考了哪些知识点？
3. C++ template 的基础知识和编译器原理会考哪些内容？
4. 选择排序的过程是怎样的？二叉树的前序、中序、后序遍历分别怎么走？
5. 数据库后端和看板系统软件开发方向的题目考了什么？

---

《参考解析》

这场笔试考的是「数据岗的基础盘」。 从复盘看，题目分布集中在四块：一道思维型算法题（重排可行性判断）、概率论、C++ 语言与编译原理的基础、数据结构里的排序与遍历，再加上数据库与看板类系统开发的概念题。值得注意的是没有出现大模型相关的内容——候选人原本准备的 KV Cache 与推理优化部署一题未考，这提示数据岗笔试仍以计算机基础与数学为主，不必把复习全押在模型侧。另一个真实的教训是概率题：统计背景的人容易觉得「这块稳了」而在考场上放松，反而丢分，笔试里越是有把握的模块越要过一次边界情况。

「判断序列能否按要求重排」这类题怎么做。 这类题的通用解法是三步：先把文字条件翻译成可计算的约束 → 求可行性的必要条件并判断它是否充分 → 按最受限的元素优先构造。

拿到题先分清约束属于哪一类：

• 相邻约束（相邻元素不能相同、任意长度为 k 的窗口内不能有重复）——统计每种元素的频次，先算可行性上界。以「重排后任意长度 k 的窗口内元素互不相同」为例，它等价于「任意两个相等元素的下标之差不小于 k」，于是频次最高的元素必须满足 f_max ≤ ⌈n / k⌉，更完整的判定是「按频次从高到低排序后，第 i 个元素满足 f_i ≤ ⌈(n − i + 1) / k⌉」。只检查频次上界和「不同元素个数 ≥ k」这两个必要条件会漏判，必须逐个校验。
• 配对/分组约束（能否两两配对、能否分成若干组使每组和相等）——先看总和或总量的整除性与极值下界（最大值不能超过其余元素之和加一），再构造。
• 排序/相对顺序约束（能否通过交换或重排使某种单调关系成立）——排序后贪心，或转成逆序对计数问题。

构造阶段一律优先安排最受限的元素：频次最高的、取值范围最窄的先放，放的时候间隔地填（如按 k 列做列优先填充，保证同一元素的下标间隔恰好是 k）。中途发现放不下就直接判定无解，不要试图回溯——如果约束本身能给出可行性等价条件，判定和构造都是 O(n log n)，主要花在按频次排序上。写代码前先用小样例手推一遍（n = 1、k 大于 n、序列里有负数、全部元素相同这些边界），比直接上手敲能省很多调试时间。

概率题的高频考点。 这类笔试的概率题基本都在「可手算」的范围内，常见几类：古典概型与计数（放回/不放回抽球、排座位、至少一次的概率用补事件算最快）、条件概率与全概率/贝叶斯（先验与后验的换算，题干里的「已知…求…」要分清谁是条件）、常见分布的期望与方差（伯努利、二项、几何、泊松、均匀、正态，几何分布的期望 1/p 和方差 (1−p)/p² 最容易被现场推导卡住）、期望的线性性（把复杂随机变量拆成若干个指示变量之和，能省掉大量枚举）、方差与协方差（Var(X+Y) = Var(X) + Var(Y) + 2Cov(X,Y)，不独立时不能直接相加）、大数定律与中心极限定理的定性判断。做的时候先写清随机变量和它的取值，再套公式，别凭直觉报数；答案保留分数或写出表达式，比近似小数更稳妥。

C++ template 与编译原理的基础考点。 模板侧常问的是：模板在编译期实例化（不是运行时），因此同一模板用不同类型参数会生成多份代码，导致二进制膨胀；模板的两阶段查找（与模板参数无关的名字在定义处查找，依赖参数的名字在实例化处查找）以及为什么这会影响 typename / template 关键字的写法；特化与偏特化的区别（全特化是给某一组具体类型单独实现，偏特化是对部分参数做限定）；SFINAE（替换失败不是错误）与 enable_if 这类编译期约束，以及 C++20 之后用 concepts 表达约束；还有显式实例化、模板不能分离编译到 .cpp（否则链接期找不到符号）这些工程细节。编译原理侧通常是流程与概念题：预处理 → 词法分析 → 语法分析 → 语义分析 → 中间代码生成 → 优化 → 目标代码生成 → 链接，每一步的输入输出与典型工具（词法用正则/有限自动机，语法用上下文无关文法和 LL 与 LR 分析）；再往深会问符号表的作用、静态与动态链接的区别、编译期与运行期错误的划分。

选择排序与二叉树遍历。 选择排序的思路是每一轮从未排序区间里选出最小（或最大）的元素，与未排序区间的第一个位置交换：n 个元素要比较 n(n−1)/2 次，比较次数与初始顺序无关，但交换最多 n−1 次（这是它相对冒泡的优势），时间复杂度 O(n²)、空间 O(1)、不稳定（交换会把相等元素的相对顺序打乱）。二叉树遍历记住「根在第几个被访问」即可：前序是根 → 左 → 右，中序是左 → 根 → 右，后序是左 → 右 → 根；二叉搜索树的中序遍历得到有序序列，这是笔试里最常考的推论。还原题（给前序加中序求后序）的做法固定：前序的第一个是根，拿它去中序里切出左右子树，再对两段递归。层序遍历则是用队列做广度优先。

数据库与看板系统这类题。 数据库侧集中在 SQL 与索引：GROUP BY 与聚合函数、HAVING 和 WHERE 的执行顺序区别、JOIN 的类型与语义、索引与最左前缀、事务与隔离级别、分页写法。看板/报表类系统常考的是指标口径与实现方式：指标要能明确「统计口径、时间粒度、数据来源」；大数据量下实时看板一般走「预聚合 + 缓存」而不是每次现场扫明细（定时任务或流式计算把结果落到汇总表，查询只读汇总），并要考虑数据延迟、补数与重算、以及口径变更后的历史数据回溯。答题时把「先确认口径，再谈性能」这句带上，比直接背缓存方案更贴合实际。

以为会考却没考的部分，反而值得补。 KV Cache 是自回归生成时把每层注意力的 Key 和 Value 缓存下来复用的机制——不缓存的话每生成一个 token 都要对全部历史重算一遍 K、V，单步代价随序列长度平方增长；缓存后压到线性，代价是显存占用，其大小大致正比于「层数 × 2 × 注意力头数 × 头维度 × 序列长度 × batch × 精度字节数」，长文本加高并发时它会超过模型权重成为显存瓶颈。推理优化部署的常见手段包括 GQA/MQA 减少 KV 头数、PagedAttention 分页管理显存、KV 量化（INT8/FP8）、连续批处理、prefill 与 decode 分离部署、投机解码，以及从系统层面限制单请求最大长度与并发数。这部分即使本次没考，也是数据岗和大模型相关岗位后续面试的高频题，值得提前过一遍。