奇安信2023春招算法笔试复盘：KMP、堆排序与开放题全解析

2023年春招我把简历投到了奇安信的算法方向。大家一听网络安全公司下意识觉得笔试卷子里应该全是渗透测试、恶意流量检测、漏洞分析结果真坐到电脑前打开“奇安信2023春招算法方向试卷1”的时候第一反应是——这跟我想的不太一样。卷子前大半部分考的是KMP、堆排序、Dijkstra、快速幂、贪心这些经典基本功机器学习相关的内容占比有限安全业务题则集中在最后的场景题里。这篇文章是我结合自己的考场回忆和考后跟几个同学对答案的结论写的一份复盘重点不在罗列题目而在把每道题背后的考察意图、容易踩的坑、以及值得延伸的知识点讲清楚。如果你也在准备安全厂商的算法岗、或者单纯想搞清楚这类企业的笔试套路可以拿这份复盘当一份参考资料。1. 安全厂商算法卷的本质先筛代码能力再筛业务匹配度1.1 为什么“安全味”没有想象中浓我一开始也想不通我是来投网络安全的为什么前面全是 LeetCode 风格题后来在面试环节和面试官聊到这个问题他的解释让我印象很深奇安信的算法团队分布在多个方向有做恶意流量检测的有做威胁情报挖掘的有做 NLP 和知识图谱的也有做终端行为分析的。不同团队对候选人的要求不一样但笔试是统一出的所以只能把题出在“所有算法岗都必须具备的能力”上这就是数据结构、算法设计、数学基础和编码基本功。另一个原因是安全业务本身对算法的运用非常工程化。恶意样本识别里GBDT、孤立森林、聚类都能用威胁情报里BM25、Word2Vec、图算法都常见但这些模型和算法都会建立在“能写出高效、正确、边界清晰的代码”这个前提上。笔试筛的正是这个前提。我记得当时考场旁边有个投策略算法方向的女生笔试结束后聊了几句她说她们部门主要做规则引擎和对抗样本另一个男生投 NLP 方向重点看文本分类和情报抽取。同样是算法岗方向差异非常大但统一笔试大家都得做同一套卷子。所以这套卷子其实更像一张“入场券”——先确认你有扎实的算法功底再谈后面的业务匹配。1.2 试卷结构与时间分配我印象中的卷子大致分三块不同批次可能略有调整第一部分选择题覆盖数据结构、排序算法复杂度、字符串匹配等大约占三成。第二部分编程题覆盖字符串、图论、排序、快速幂、贪心等大约占四成。第三部分简答和开放题覆盖机器学习基础、聚类、检索、安全场景设计大约占三成。整套题的时间在 90 到 120 分钟不算宽裕。选择题里有些题目看似是概念题实际需要手推比如 KMP 的 next 数组。编程题大多不是纯裸题而是加了业务包装的变体后面我会详细讲。开放题则是工作量最大的部分因为要完整描述“目标—数据—特征—算法—评估”整个链路写得完整比写得多更重要。我对这套卷子最直观的感受是它不追求难追求的是稳定和全面。如果你能把 LeetCode 前 200 道中等难度的题练熟基础部分应该能拿大头真正的差距往往是在开放题和边界条件处理上拉开的。2. 字符串匹配里的高频送分题KMP的next数组到底有多少种答案2.1 模式串 abacaba 的 next 数组推导热搜里那题“对于模式串 pabacaba其 next 数组”是KMP的经典练习题。这题本身不难但它最大的坑在于next 数组的定义在教材和 OJ 之间并不统一。常见定义有两种。第一种定义是“前 i 个字符的最长公共前后缀长度不含该子串自身”很多教材里这么写。以 p abacaba 为例从 i 1 开始逐个看i1子串 a没有真前后缀长度为 0i2子串 ab最长公共前后缀为 0i3子串 aba前缀 a 和后缀 a 相等长度为 1i4子串 abac无法找到相等的前后缀长度为 0i5子串 abaca又是 a长度为 1i6子串 abacab前缀 ab 和后缀 ab 相等长度为 2i7子串 abacaba前缀 aba 和后缀 aba 相等长度为 3。所以按这种定义next 数组是 [0, 0, 1, 0, 1, 2, 3]。第二种定义是“失配时模式串指针回退的位置”很多 OJ 和竞赛模板里用这种写法。这种定义下数组长度等于模式串长度且 next[0] 通常设为 -1然后整体做一次移位。对于 abacaba结果是 [-1, 0, 0, 1, 0, 1, 2]。两种结果看着相似但含义不同如果题目没有明确给定义我建议在答题区先写一句“本文采用哪种定义”再列结果。这不是矫情而是 KMP 这类题目最容易因为定义不一致被误判的坑。2.2 一个容易忽略的推导细节为什么 next 数组里的最长公共前后缀不能等于整个子串如果允许相等那任何串的最长公共前后缀都会退化成自身KMP 的跳转就失去了意义。所以定义里一定会强调“真前后缀”也就是长度严格小于子串长度。从 abacaba 这个例子还能观察到一个特征整个串的最长公共前后缀长度是 3而 3 恰好也是前面某个位置的 next 值。这说明 abacaba 具有递归的周期结构出题人选这个模式串是有意的因为一旦理解了“后缀的某个前缀等于更早的前缀”KMP 的自匹配过程就通了。面试追问时可能会问next[i] 的递推过程中为什么 j next[j] 而不是 j--这里的关键是当 p[i] 与 p[j] 失配时说明我们已经确认 p[0..j-1] 是当前后缀的一部分而 next[j] 记录的是这段已匹配前缀的最长公共前后缀直接回退到那里就能跳过必然失败的比较。这是一个 O(n) 的时间复杂度保证也是 KMP 比朴素匹配高效的本质。2.3 KMP 在安全场景里有什么用很多人觉得字符串匹配离安全很远其实恰恰相反。恶意代码特征匹配、Web 应用防火墙规则匹配、网络流量特征库匹配底层全都依赖字符串匹配。设备扫描包内容时如果规则很多不会用暴力匹配而是结合 AC 自动机或 KMP 思想做多模式匹配。所以别觉得笔试考 KMP 是“脱离业务”它其实是最贴近内容安全工具链的一块地基。我当时在准备阶段把 KMP 的 next 数组推导手抄了五遍不是因为怕笔试考原题而是因为面试官太喜欢追问“为什么是 O(n)”。能把这个问题讲到“主串指针不回溯”这个层面基本就能过关。3. 编程题里最容易翻车的三类题Dijkstra、堆排序与快速幂3.1 Dijkstra别只会背模板编程题里考 Dijkstra 不算意外但奇安信这类厂商的版本往往不会直接问“给你一个图求源点到所有点的最短距离”而是加一层包装。常见变体有输出具体路径求次短路图上每条边有通过时间窗口只能在某个时间段经过多源最短路。这些变体的核心还是 Dijkstra 的松弛逻辑但如果只背模板一变就不认识了。使用堆优化的 Dijkstra 复杂度是 O((VE)logV)这里 V 是顶点数E 是边数。需要特别注意负权边不能处理这是很多人忽略的题干条件。考场如果出现负权边得立刻转向 Bellman-Ford 或 SPFA。另外图比较大时visited 数组的标记时机要小心堆里可能会同时存在某个节点的多个不同距离只有弹出最短的那个才能把它标记为已访问否则容易把次优解当成最优解。我见过不少人倒不是在算法思想上出错而是在细节上翻车比如有向图建边只建一条。这个错误特别隐蔽样例数据小的时候几乎测不出来一旦数据大了就会差很多。写 Dijkstra 之前先在草稿纸上确认“这是有向图还是无向图”能省下很多调试时间。3.2 堆排序从手写建堆到 Top-K堆排序的考法一般是两种手写构建大根堆或小根堆并排序或者求 Top-K。奇安信这类厂商的题目里更常见的是 Top-K因为对应到真实业务就是“从海量告警中取出最严重的 K 条”堆是最高效的做法。手写堆的时候siftDown向下调整和 siftUp向上调整的区别容易被记混。建堆时用 siftDown从最后一个非叶子节点往前调整插入时用 siftUp。很多人习惯用标准库的优先队列笔试当然可以但如果面试追问底层实现能讲清楚向上调整和向下调整的区别会明显加分。还有一个小细节C 的优先队列默认是大根堆取 Top-K 最小要用 greater。这个细节笔试很容易疏忽因为本地跑小数据看不出来提交后才发现排序结果反了。3.3 快速幂看似简单边界条件全是坑快速幂考法很直接计算 a 的 b 次方模 m。核心是把指数按二进制拆开幂次加倍底数平方取模。容易踩的坑有三个b 为 0 时返回值是 1a 可能很大乘之前先取模b 是 long long 甚至更大时循环终止条件要写好避免死循环。有些矩阵快速幂的变体会结合斐波那契数列把复杂度从 O(n) 降到 O(logn)。如果时间充足这部分值得延伸复习因为机器学习相关的算法题偶尔会出现类似的“计算加速”思路。编程题里贪心也常见但往往和排序结合。题目给一堆任务和截止时间求最多能完成多少任务这种题要用贪心 优先队列。核心逻辑是先按截止时间排序然后遍历任务能放就放放不下就把耗时最长的任务踢出去。这里的“踢出去”操作正好用上堆所以贪心和堆经常成对出现。4. 启发式算法与机器学习基础粒子群、模拟退火、聚类到底考什么4.1 粒子群算法的考场问法热搜里那题“粒子群算法原理”虽然我记不清是不是原题但这确实是安全算法岗位笔试、面试里出现频率不低的内容。原因很简单安全业务里的很多优化问题不好用梯度下降解比如特征选择、参数寻优、告警关联规则挖掘粒子群这类无梯度优化方法非常实用。粒子群的核心就三件事粒子位置代表候选解、速度代表更新方向和步长、目标函数值负责评价好坏。更新公式可以简单写成v w * v c1 * r1 * (pbest - x) c2 * r2 * (gbest - x) x x vw 是惯性权重c1 是自我认知系数c2 是社会认知系数。考场如果考原理多数会问这几个参数的意义或者问“相比网格搜索有什么优势”。回答“不需要对参数空间做离散化搜索过程有记忆性”就能拿分。笔试里如果让手写伪代码别漏了初始化这一步粒子位置和速度要在可行域内随机初始化如果初始范围太小后期很容易陷入局部最优。另外惯性权重 w 一般随着迭代次数的增加而线性减小前期大一点负责全局探索后期小一点负责局部收敛这个细节能体现你真的理解粒子群而不是背了个公式。4.2 模拟退火这个更容易理解模拟退火的考点通常和粒子群一起出现。它借鉴金属退火过程以一定概率接受更差的解从而跳出局部最优。刚开始温度高接受差解的概率大温度逐步降低接受差解的概率越来越小最终收敛。Metropolis 准则一般是如果新解更优就接受否则以 exp(-ΔE/T) 的概率接受。考场上容易写错的是温度下降方式。常见的有线性衰减和指数衰减指数衰减更容易收敛但要调好衰减系数。如果是简答题答出“温度不要降太快否则会直接退化成爬山算法”这句话基本就能踩中得分点。面试官还可能追问为什么要接受差解我的理解是因为目标函数可能不均匀局部最优附近往往没有信号只有跳到另一个区域才可能找到更好的解。这跟安全场景里的“对抗样本搜索”很像——只沿着梯度调整输入容易被困在局部奇怪的模式里而模拟退火的随机跳跃思路反而更接近真实攻击者探索漏洞的方式。4.3 聚类安全场景的顶梁柱聚类是所有安全厂商算法笔试几乎必考的一个方向。恶意样本聚类、入侵流量聚类、异常用户分群全都要用。K-Means 是入门级但考点往往在“怎么选 K”——肘部法则、轮廓系数、Gap Statistic或者“K-Means 的缺点”——对初始中心敏感、只能处理凸簇、需要预先指定 K。DBSCAN 则不需要指定簇数还能识别噪声点更适合恶意样本里大量离群样本的情况。如果笔试里出现海量数据场景可以答 Mini-Batch K-Means 或者用局部敏感哈希减少相似度计算量。这些看起来是加分项其实在安全场景下是刚需终端告警可能一天几千万条直接跑标准 K-Means 既耗内存又慢。能答出“Mini-Batch 迭代更新中心点”这个思路面试官会觉得你真的处理过海量数据。我在复盘时发现很多同学提到聚类只会说“K-Means 好用”但被问到“特征标准化了吗距离公式选的什么样本不均衡怎么处理”就卡住了。聚类本身不是难点难点在于把数据处理成“可聚类”的形式。5. 拉开差距的开放题安全场景下的算法设计怎么答才加分5.1 海量日志聚类从数据量倒推方案开放题往往是一个大场景假设你拿到一天上亿条终端日志里面混杂正常行为和恶意行为让你设计一个算法把恶意行为找出来。这时候不要只会写“用 K-Means”。要讲清楚整个链路先做特征工程比如行为序列、文件路径、进程父子关系如何向量化再降维比如 PCA 或 t-SNE再用 Mini-Batch K-Means 或 DBSCAN 做初聚类最后用规则或少量标注样本做校验和修正。答题时体现“数据量倒推算法选择”的思路很重要。上亿条日志跑不了标准 DBSCAN因为距离矩阵是 O(n^2)这时候可以考虑对数据抽样或用网格近似也可以用 LSH 把高维向量映射到桶里只比较同一桶内的样本。能考虑到这一步说明你不是在背题而是在真正解决规模问题。我在答这类题时养成了一个习惯先写数据量级再写算法复杂度最后写工程近似。哪怕只是简单列一下“日志一天 1 亿条所以不能用 O(n^2) 的算法”也比直接甩一个模型名称显得专业得多。5.2 BM25 与威胁情报检索BM25 的出现让我有点意外但细想也合理威胁情报平台里要搜索大量 IOC失陷指标、恶意域名、样本哈希底层其实就是一个检索引擎。BM25 比 TF-IDF 多考虑了文档长度对词频的影响公式里的 k1、b 两个参数用来做词频饱和与长度归一化。这类题如果出到不用把公式背到小数位但要把三个核心思想说出来词频不是越多越好超过一定阈值收益递减文档越长词频越要打折出现文档数越多的词权重越低。能说到这三点说明你真理解 BM25 而不是死记公式。还有一个容易忽略的点安全场景里的检索很多 query 本身很短比如一个 IP 或一个域名这就要求倒排索引设计得足够好。答题时如果能在 BM25 之外提到倒排索引和分词策略会更完整。5.3 开放题的回答框架目标到评估的一条线很多同学做开放题失分不是因为不会而是因为缺少结构化表达。我的建议是固定按五段来答第一句说业务目标第二句说可用数据第三句说特征怎么构造第四句说算法选型与理由第五句说怎么评估结果。例如题目问“如何识别钓鱼邮件”按照这个框架答即使选的算法不是最优也能让面试官看到完整的思考链路。安全场景里还有一个经常被忽略的点不能只看准确率。恶意样本通常是极少数一个把所有样本都判为正常的模型准确率可能高达 99%但没有任何用处。所有答案里一定要提到召回率、精确率、F1或者更贴近业务的分类阈值调整。这才是安全算法岗和普通算法岗的区别所在。安全产品里还有一个常被问到的周边算法是 Rete主要用于规则引擎的事实匹配。规则越多时重复条件匹配会浪费大量计算Rete 通过构建匹配网络、缓存中间结果来加速。如果开放题里提到 WAF 或风控规则引擎Rete 是一个不错的加分项因为大部分候选人根本不知道规则引擎底层还有这种优化。6. 复盘里的几条实用建议投安全厂商算法岗前值得知道的事6.1 不要被“网络安全”四个字带偏如果看网上讨论会发现这家公司的终端安全产品讨论度很高给人感觉这里全是安全产品知识。但如果你投的是算法岗笔试主要看代码能力和数学基础产品知识不会占太多。准备的时候不要花大量时间啃产品文档先把 KMP、堆、图、DP 这些基本功练到条件反射性价比最高。我当时差点陷入一个误区花了很多时间研究这家公司的产品线和安全攻防术语结果笔试里一道都没考。不是说这些知识不重要而是对校招笔试来说优先级远低于算法基本功。6.2 编程语言选型与输入输出细节如果是核心代码模式语言影响不大如果是 ACM 模式需要注意输入输出。C 选手要注意 cin 的取消同步Python 选手要小心读入大量数据时 input() 比 sys.stdin.readline() 慢很多可能因为 IO 超时被卡Java 选手注意别用 Scanner 大量读数据。这些细节在笔试里非常掉分因为题目本身不难输出去出问题就太冤了。我建议在笔试前把本地环境配好包括常用模板快速幂、Dijkstra 堆优化、KMP、并查集、二叉树遍历。临场再想模板很容易慌而且容易写错边界条件。6.3 面试追问环节算法细节比项目数量更重要笔试之后进了面试面试官会盯着你简历上写的算法深挖。比如你写了“用 K-Means 聚类恶意样本”他会追问K 怎么确定的特征标准化了吗距离公式选的什么样本不均衡怎么处理这些追问其实就是考你有没有真正理解算法而不是套个库跑完就拿结果。多准备几个这样的“为什么”比多看十个模型更有用。我印象比较深的是一个选 K 的问题。我说用肘部法则面试官当场追问“如果肘部不明显怎么办”这个问题问得特别好因为真实数据里肘部常常不明显。后来我补答了轮廓系数和业务约束才把这个问题圆回来。所以准备项目时别只准备“做了什么”要多准备“为什么选这个方案它有什么局限替代方案是什么”。6.4 我的个人教训回归基础才是王道最后说一个我自己的教训。准备这次春招时我有一段时间沉迷于看各种深度学习模型、Transformer 变体觉得安全算法岗应该要懂最新论文。结果模拟测试时 KMP 的 next 数组推错了Dijkstra 的堆优化也写不利索。那时候我才意识到对校招算法岗来说先把基础数据结构练成肌肉记忆才是最大的安全感。模型可以进组再学但代码基本功不行。我在实际笔试中把时间分配也做了一次调整选择填空控制在 25 分钟内编程题每道最多 20 分钟开放题留至少 30 分钟。如果一道编程题超过 20 分钟还没思路果断跳过先把开放题的结构写出来再回头补编程题。这套策略帮我稳住了节奏至少没有出现时间不够、开放题只写了两行的情况。如果你也在准备类似的安全厂商算法岗我的建议是优先刷题重点关注字符串匹配、图论、堆和排序把经典题的边界条件吃到透然后再花少量时间研究安全场景学会把聚类、检索、优化算法往业务上靠。这样不管是笔试还是后面的面试都会稳很多。