奇安信算法笔试复盘：从KMP到安全场景，基础算法如何考察

这不是第一次帮人复盘奇安信这类安全厂商的算法笔试题了。每年春招秋招都有大量候选人抱着“安全公司算法岗是不是只考机器学习”的预期进场结果被一套纯数据结构和算法题打懵或者反过来以为安全公司不考算法结果栽在KMP、堆排这类基础题上。这份“2023奇安信春招算法方向试卷2”我专门刷过几遍也和拿到offer的学弟对过答案今天就把它拆开揉碎从考察逻辑、高频考点、安全场景特色题型到笔试现场的工程细节和踩坑实录一次性讲清楚。无论你是准备投递奇安信还是想摸底国内安全大厂算法笔试的难度这篇都值得收藏。1. 试卷整体设计与考察思路拆解1.1 这份试卷到底在考什么先说结论奇安信的算法方向笔试试卷主体仍然是通用的数据结构与算法但它的选题风格明显带着安全业务的影子。试卷2的整体结构大致分三块基础数据结构与字符串处理、经典算法设计与优化、安全场景下的工程算法题。从热搜词里也能看出来KMP的next数组、排序算法、粒子群、模拟退火、Dijkstra、K-Means聚类这些高频词和实际试卷的考点高度重合。为什么要这样设计一个核心逻辑是算法方向的同学进入公司后接触的绝不是单纯的推荐系统或CV模型而是大量与流量分析、样本检测、威胁情报、日志挖掘相关的场景。这些场景对基础数据结构的要求极高——处理特征向量要懂哈希表和红黑树解析协议要懂字符串匹配和状态机聚类告警要懂图算法和并查集这些底层能力都必须通过笔试先筛一遍。另外这份试卷有一个明显的倾向它不追求偏题怪题但追求熟练度和正确率。题量大概在20道选择题加2-3道编程题选择题覆盖复杂度分析、排序稳定性、KMP匹配、贪心策略、动态规划、图论基础编程题则偏向“能直接落地的算法实现”。这意味着什么意味着刷题量不够、只背模板不理解原理的同学在选择题阶段就会被大量扣分因为很多选择题是“找错”而不是“选对”。1.2 为什么安全厂商的笔试题长这样很多人好奇奇安信作为国内网络安全领域的头部厂商为什么笔试不直接考渗透测试、不考漏洞分析反而先来一套通用算法题这点我实际入职后体会特别深安全产品和算法结合的岗位本质上仍然需要极强的算法工程能力。以Web安全检测为例检测CC攻击需要滑动窗口计数检测DNS隧道需要熵值分析和时序异常检测恶意流量分类需要决策树或集成模型。再往下挖规则引擎里用到的Rete算法、误报日志聚类的DBSCAN、威胁图谱里的路径搜索每一个都是笔试里那些基础算法的变形。试卷2里出现与KMP、排序、动态规划相关的题目就是提前确认候选人“底子正不正”。说白了安全算法方向的笔试不是考你能不能写出一个完美的人工智能模型而是考你有没有能力在一个高并发、海量数据、实时性要求极高的安全系统里写出时间和空间都足够高效的算法模块。这也是为什么这份试卷值得反复刷——它是安全行业算法岗的一个缩影。2. 高频核心考点逐个拆解2.1 KMP算法与next数组的精确计算试卷2里字符串匹配相关的题目几乎是必考的。热搜词里那个“对于模式串 pabacaba其next数组”的问题就是非常典型的真题风格。KMP的难点从来不是匹配过程而是next数组怎么用手算算对、用代码写对。先把手算逻辑完整过一遍。对于模式串abacaba我们约定next[i]表示“当第i位失配时模式串应该回退到的位置下标”标准写法里通常定义next[0] -1next[1] 0。从i2开始看前缀后缀的最长相等长度i0next[0] -1或0看题目定义奇安信一般默认-1起点i1字符串a最长相等前后缀为0next[1] 0i2字符串ab前缀a后缀b不相等next[2] 0i3字符串aba前缀a后缀a相等且长度为1next[3] 1i4字符串abac前缀ab后缀ac不等前缀a后缀c不等next[4] 0i5字符串abaca前缀abaca的最长相等前后缀看前缀aba后缀aca不等前缀ab后缀ca不等前缀a后缀a相等长度1next[5] 1i6字符串abacab前缀ab后缀ab相等长度2next[6] 2i7字符串abacaba前缀aba后缀aba相等长度3next[7] 3所以abacaba的next数组为[-1, 0, 0, 1, 0, 1, 2, 3]。注意不同教材有“next[j]表示失配前已匹配j个字符时回退位置”和“next[j]表示第j位失配时回退位置”两种定义值会错开一位。笔试时先花10秒确认题目给的next定义能避免整道题白算。然后是代码实现。严谨的写法是vectorint buildNext(const string p) { int m p.size(); vectorint next(m); next[0] -1; int j 0, k -1; while (j m - 1) { if (k -1 || p[j] p[k]) { j; k; // 优化如果失配时 p[j] p[k]则继续回退 next[j] (p[j] ! p[k]) ? k : next[k]; } else { k next[k]; } } return next; }很多人在笔试里直接用最朴素的版本不优化p[j] p[k]的情况这在选择题里判断时间复杂度时问题不大但在编程题里如果模式串全是重复字符比如aaaaaaab最坏情况会退化。奇安信的编程题数据量通常不会给到10^7以上但养成写优化版的习惯总没错这也是阅卷时拉开差距的细节之一。2.2 排序算法全家桶与复杂度对比排序算法在试卷2里几乎是以“选择题连环炮”的形式出现的。最常考的几个点快速排序的最坏时间复杂度、堆排序的不稳定性、归并排序的额外空间、桶排序的适用条件。热搜词里“数据结构排序算法”、“冒泡排序算法c”、“堆排序算法”扎堆出现说明这是通用高频考点。这里把面试笔试最常考的五个排序算法整理成一张速查表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景冒泡排序O(n²)O(n²)O(1)稳定几乎不用仅教学快速排序O(n log n)O(n²)O(log n)不稳定通用排序工程首选归并排序O(n log n)O(n log n)O(n)稳定链表归并、外部排序堆排序O(n log n)O(n log n)O(1)不稳定TopK、优先级队列计数排序O(nk)O(nk)O(k)稳定小范围整数排序奇安信选择题比较刁钻的点在于它会给一段快速排序的中间过程问你某次Partition之后数组长什么样或者给一个特定输入序列比如已经有序的数组问你快速排序会递归多少层。这类题想拿分光背复杂度不够必须能手写Partition过程。建议备考时把Lomuto分区和Hoare分区两种写法都练熟因为选择题里两种都可能出现而且两者的交换次数和指针移动方式完全不同算错一步就全错。还有一个高频延伸考点是TopK问题。安全场景里TopK极其常见——查日志里出现频率最高的前100个攻击IP、挖流量特征里最重要的前50个字段。笔试考法一般是“海量数据找TopK用什么方案”正确答案不是全排序而是堆排序维护一个大小为K的小顶堆时间复杂度O(n log K)。如果有人选快速排序那就暴露了对海量数据处理的理解不足。2.3 动态规划与贪心策略的边界判定动态规划和贪心算法是试卷2编程题的重灾区。奇安信的DP题不会出得太偏但往往包装在一个安全业务场景里比如“给定一组日志采集任务每个任务有开始时间、结束时间和奖励值如何选择任务集合使得奖励最大”——本质就是经典的加权区间调度问题。加权区间调度的标准解法是先按结束时间排序定义dp[i]为前i个任务能获得的最大奖励状态转移方程为dp[i] max(dp[i-1], dp[p[i]] w[i])其中p[i]表示与第i个任务不冲突的最近前驱任务编号。求p[i]需要二分查找整体复杂度O(n log n)。这个题在奇安信技术岗的笔试题里出现过至少三次变体强烈建议把模板背熟。贪心算法这边常考的是“判断一个题目能不能用贪心”。记住一个关键判定原则只有具备贪心选择性质和最优子结构的问题才能用贪心否则要用DP。经典反例是0-1背包不能用贪心、分数背包可以用贪心。选择题里会给一个场景让你选方案比如“找零钱问题硬币面额1、5、11要凑出15元贪心得到1张11加4张1共5枚但最优解是3张5共3枚”这种就是要选“贪心失败”的选项。别看到有面额就开始算先想贪心策略对不对再动笔。还有一个奇安信比较爱考的点最长递增子序列LIS。这个题有两个版本O(n²)的DP版本和O(n log n)的贪心二分版本。后者用tails数组维护“长度为i的递增子序列的最小末尾值”笔试编程题如果数据范围n≤10^5必须写二分版本才能过。这个题和前面的TopK一样都是考察“有没有意识到基础算法在数据规模变大时需要优化”的能力。2.4 图论算法与并查集的工程化应用图论在奇安信算法卷里占的比重不低。Dijkstra、最小生成树、拓扑排序、并查集都有可能出现。热搜词里Dijkstra和二分图HK算法出现说明不少人在搜这些题的解法。Dijkstra的堆优化版本是必须烂熟于心的因为它的应用场景在安全里非常直白网络拓扑中计算攻击路径的最短跳数、威胁扩散的最小步数。笔试不会考你SPFA因为SPFA在最坏情况下会被卡到O(VE)堆优化Dijkstra的O((VE)log V)才是安全推荐的标准写法。并查集是另一个高频考点而且经常不单独出道而是作为一道“连通性判断”大题的底层工具。真题风格类似“给定n台服务器和m条网络连接再给q个查询每个查询问两台服务器是否连通”。标准解法就是并查集先union再find路径压缩加按秩合并复杂度近乎O(1)。需要提醒的是笔试时并查集的初始化千万别漏——parent[i] i我第一次做这类题时就是漏了初始化导致后面find陷入死循环白白丢了整道编程题的分。3. 安全场景特色题目与应对策略3.1 输入校验与路径遍历检测的算法本质奇安信笔试区别于普通互联网大厂的地方在于它会出一些“安全味儿”很浓的算法题。热搜词里“奇安信 输入验证路径遍历”就是这类题的代表。这道题本质是给定一个文件路径字符串包含..和.要求规范化路径同时识别是否存在路径遍历攻击。这题的标准解法是用栈模拟。把路径按/分割遇到普通目录名就入栈遇到..就弹栈如果栈不为空遇到.或空字符串就跳过。最后把栈里的目录拼接起来。但安全版本的题目会进一步问如果..导致栈为空时还继续弹说明存在路径穿越风险应该返回“非法”而不是继续处理。这个考察点非常有安全特色因为在实际WAF规则、文件上传校验里处理路径穿越就是这么做的。用代码实现时有一个容易踩的坑字符串分割时/../a//b/./c/这种连续斜杠和混合..的情况一定要先按分隔符切割再过滤空串否则会在弹栈边界上出错。下面是一个可以直接背下来的标准实现def normalize_path(path: str) - str: parts path.split(/) stack [] for part in parts: if part or part .: continue elif part ..: if not stack: return INVALID # 安全检测视角路径越界 stack.pop() else: stack.append(part) return / /.join(stack)这道题给我们的备考启示是安全公司的算法题往往是在经典算法外面套一层安全场景的壳但壳里面的核心还是栈、队列、字符串处理这些基本功。刷题时遇到这类题先剥壳看核心别被题目描述吓住。3.2 弱哈希算法识别与哈希表设计热搜词里有一条“ssl 证书使用了弱 hash 算法 (cve-2005-4900)怎么修复”这虽然是运维层面的话题但奇安信的笔试题确实会考哈希相关的基础算法从MD5、SHA-1的冲突安全性到哈希表的开链法和线性探测法都出现过。选择题典型考法是给出哈希函数h(key) key % 13依次插入几个数问用链地址法解决冲突后某个桶里有几个元素。这类题考察的是哈希表的存储机制没有任何捷径只能老老实实手算取模、模拟插桶。编程题层面哈希表相关的题目一般是“找出数组中出现次数超过一半的元素”或者“找两个数组的交集”。前者有一个非常经典的摩尔投票法空间O(1)、时间O(n)比哈希表计数更优。后者可以用哈希集合去重后遍历。这类题在安全场景中的映射是海量告警日志里找高频攻击源IP、求两个威胁情报库的共有IOC。备考时要把哈希表底层原理和常见哈希类题型的模板都练到。另外提醒一句笔试时如果题目限定了“不能使用内置哈希表”不要慌这往往是在考察手写哈希表的能力。奇安信这种大厂笔试环境通常是允许用Python的dict或C的unordered_map的但有个别选择题会问手写哈希表的装载因子、扩容时机、rehash代价这些概念必须清楚。3.3 日志异常检测中的聚类与分类算法虽然试卷2的主体是数据结构和基础算法但最后面一般有一两道机器学习相关的选择题用于区分候选人是否真的理解算法在业务中怎么落地。热搜词里“机器学习算法”、“聚类算法”、“K-Means”扎堆出现就是这类题目的关键词。奇安信爱考的ML题不走“背诵理论”路线而走“场景选型”路线。比如“现有一批DNS日志需要检测出异常域名请求行为特征包括请求频率、域名长度、子域名数量、熵值应选择什么聚类算法”正确答案往往是K-Means、DBSCAN或孤立森林而不是逻辑回归或朴素贝叶斯。原因在于异常检测场景下正常样本和异常样本极度不平衡监督学习很难拿到足够的标注数据无监督或半监督方法更合适。再比如“在流量特征选择中要评估每个特征对分类结果的贡献度应该用什么方法”这对应的是信息增益、基尼系数或卡方检验。不要一上来就说PCAPCA是无监督降维和“特征对分类的贡献度”不是一个概念。这里给一个备考建议不要死磕机器学习论文把常见聚类算法的原理、适用场景、核心参数、优缺点用一周时间整理成一张对比表性价比远高于刷十道偏题怪题。奇安信这类安全厂商的ML题考察的是工程判断力不是学术推导能力。4. 笔试实操环节的几个关键细节4.1 编程题的输入输出模式ACM模式还是核心代码模式奇安信的在线笔试系统支持多种语言编程题默认使用ACM模式需要自己处理输入输出这个和牛客网的模式一致。很多人刷LeetCode刷习惯了只写核心函数结果笔试第一题就在输入解析上卡了半小时。ACM模式的常见坑有两个。第一个是读入不定长的行、不定数量的整数比如输入第一行是n第二行是n个数但第二行的换行符可能在每行末尾不一致。稳妥的办法是用BufferedReader逐行读然后用split( )逐段解析别用Scanner一个个nextInt大数据量下Scanner会慢到怀疑人生。第二个坑是输出格式题目要求“每个结果占一行”结果你全打在一行里编译器不会报错但判题直接判错。C的高速读写模板也很重要#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint nums(n); for (int i 0; i n; i) { cin nums[i]; } // 处理逻辑 return 0; }这两行ios::sync_with_stdio(false)和cin.tie(nullptr)一定要加上。实测数据量到10^5以上时不加这两行输入耗时可能是加上之后的5到10倍。笔试环境里时间就是分数这种细节不能丢。4.2 时间复杂度预估别让TLE毁掉整卷很多候选人做编程题时写完代码本地测试通过就提交结果被判超时TLE甚至不知道哪一步超了。这里给一个非常实用的预估方法**1秒内C可以稳定跑完10^8次简单运算Java大概是10^7到10^8Python则是10^6到10^7。**看题目的数据范围反推自己的算法复杂度是否可行。具体操作如果n的范围是10^5那么O(n²)就是10^10无论什么语言都必超时必须想O(n log n)或O(n)的算法如果n的范围是10^3O(n²)可以接受可以放心写DP或双循环。这个判断应该在动笔写代码之前就完成而不是提交被TLE之后才回去想优化。奇安信的编程题数据范围给得通常会比较规矩一般不搞极限值刁难人但如果你在时间复杂度上做出了错误选择哪怕算法思路完全正确也会被大数据集卡死。所以拿到题目第一步一定是看数据范围第二步才是想算法。4.3 边界条件与极端用例自查清单编程题最冤枉的丢分方式是在边界条件上翻车。我总结了一个笔试提交前的自查清单至少对奇安信这套卷子的编程题非常适用数组长度为0或1时代码能否正确处理输入中存在负数、零、重复值时算法逻辑是否依然成立字符串包含空格、空串、连续分隔符时解析是否会出错整数相加、相乘时是否可能溢出int范围要不要用long递归深度是否可能导致栈溢出要不要改成迭代在奇安信的笔试里有一个高频隐藏扣分点就是整数溢出。安全场景中经常涉及大整数运算比如哈希取模、时间戳转换、IP字符串转整型IPv4的a.b.c.d转a*256^3 b*256^2 c*256 d一个不留神就爆了int。笔试代码里该用long就用long该用Python的天然大整数就用Python不要因为“感觉值不大”就大意。5. 常见问题与避坑经验实录5.1 选择题陷阱KMP next数组定义混淆这是每次笔试后讨论度最高的话题。KMP的next数组在不同教材、不同题目里有不同的起点定义和整体偏移极容易看错。我的经验是做题前先在草稿纸上写上“此题next[0] -1还是next[0] 0”确定之后再用草稿计算不要直接在选项上心算。另外候选项里经常会出现“部分匹配值表”的数值那是PMT表不是next数组两者从第二个位置开始结果相同但偏移一位。遇到时先做转换再选别直接对答案。5.2 编程题Debug在线IDE不给你断点怎么办奇安信的笔试系统自带在线编辑器但往往不支持断点调试。遇到这种环境最有效的debug方式是“打印中间变量”。但注意你打印的东西会留在输出里提交判题时会被当成答案。所以我的习惯是本地写一个调试版本用System.err.println或cerr输出调试信息确认无误后再删除或注释掉所有调试输出提交干净版本。笔试时间紧凑不要试图靠肉眼读代码找bug尤其是数组越界、边界判断这类问题。如果一段代码死活不对直接在关键循环里打印数组的状态立刻能看到逻辑哪里断了。5.3 时间分配选择题和编程题怎么权衡奇安信这套试卷的题量正常速度做完大概需要90分钟左右。我的建议是先花50分钟把选择题做完其中拿不准的先做标记、不纠结再花40分钟做编程题优先做思路最清晰的那一道。千万不要在某个选择题上死磕超过5分钟因为一道选择题的分值远低于一道能完整跑通的编程题。编程题如果三道只来得及做两道一定要把第三题的暴力解法写上去哪怕只过30%的数据也能拿部分分。奇安信的判题系统是分测试点给分的不是“全对才得分”所以暴力法永远比空着强。5.4 备考资料与方法一个月怎么准备最划算最后聊一点备考方向。如果你投奇安信算法岗倒推一个月的准备时间最划算的组合是力扣Hot 100刷两遍第一遍按题型刷第二遍按难度刷。其中数组、字符串、链表、二叉树、动态规划这五类题每个至少做20道以上。字符串匹配专题单独练KMP的next数组手算和代码实现必须滚瓜烂熟因为这是安全公司的压轴考点之一。排序算法不能只会调库冒泡、快排、归并、堆排、计数排序的手写代码都过一遍选择题稳了编程题的基础也稳了。机器学习常见算法原理准备一份“一句话解释适用场景”的速记不用深究推导但要说清楚KNN、K-Means、DBSCAN、决策树、逻辑回归之间怎么选。刷几套“安全场景包装”的算法题比如日志去重、IP排序、路径规范化、字符串模式匹配。这些在牛客网搜“奇安信”或者“安全算法”基本都能找到类似题目。这套流程坚持下来不敢说稳过但至少进场之后不会因为没见过题型而慌乱。笔试只是整个春招流程的第一关后面还有面试的手撕算法和项目深挖基础打得越扎实后面的路才越顺。我个人实际刷这份试卷时最深刻的体会不是题目有多难而是它让我重新审视了一件事安全行业做算法的本质上还是在做工程工程能力的底座永远是数据结构和算法。别觉得这些基础题“小儿科”真正到了线上集群里跑模型、处理海量告警的时候一个数据结构选型失误代价远比笔试里丢几分高得多。所以这份试卷值得认真对待也希望这篇拆解能帮你少走一些弯路。