这份瓜子二手车2019秋招算法笔试卷我前前后后看了不少遍。它和我见过的很多互联网公司算法笔试风格很像看着是常规的数据结构与算法但实际把排序、字符串匹配、图论、搜索排序、甚至控制类算法的思路全揉进去了业务味道也藏得挺深。二手车平台的核心是车源定价、搜索推荐、供需匹配这些场景所以考算法不会只考纯理论而是会变着法子考察你把算法落到业务里的能力。这份试卷适合两类人一是准备秋招算法岗、还没做过车企或交易平台笔试题的应届生拿来摸底很合适二是在职工程师想查漏补缺看看自己脱离刷题状态后还能不能快速上手。下面我就照着试卷的题型分布把每一类核心考点拆开讲清楚包括解题思路、计算过程以及我在实际笔试和面试里踩过的坑。1. 整体题型结构与备考方向1.1 这份笔试卷的定位与出题逻辑瓜子二手车做的是C2C和B2C结合的二手车交易平台业务链条里最重的是三件事车源定价、搜索推荐、供需匹配。这三个业务方向基本决定了算法笔试的考点范围。车源定价需要回归模型、价格预测所以机器学习算法、特征工程这类考点会以简答题或应用题形式出现搜索推荐需要召回、排序所以BM25、排序算法、字符串匹配这类基础算法分量很重供需匹配要解决的是“哪辆车推给哪个用户”“哪个车商优先获得流量”这类组合优化问题所以贪心算法、二分图匹配HK算法、Dijkstra最短路这类图论算法也会频繁出现。和纯互联网公司不一样二手车平台的算法笔试会更“落地”。它不大会让你证明某个算法的严谨数学性质而是给你一个业务场景让你选算法、算复杂度、手写核心代码。所以备考的时候不能光背算法模板得习惯性地想一件事这个算法在这个真实场景里输入是什么、输出是什么、数据量有多大、瓶颈在哪里。1.2 高频考点分布与备考优先级我根据试卷内容和往年同学反馈把考点优先级整理成了下面这个表。笔试时间有限优先保证“必考且好拿分”的部分再攻难度大的。优先级考点分类典型考点考察形式备注高字符串匹配KMP算法、next数组计算填空/选择/编程手算next数组是必考必须熟练高排序与堆快排、堆排序、Top K选择/编程复杂度要倒背如流堆排要能手写高基础数据结构栈、队列、哈希表选择/简答注意边界条件和扩容策略中高图论算法Dijkstra、二分图匈牙利/HK算法选择/简答重点在适用条件和复杂度对比中数值算法快速幂、哈希算法编程/简答快速幂是手写题常客中机器学习聚类、KNN、粒子群算法选择/简答重点在原理、收敛性和适用场景中低业务算法BM25、PID、规则引擎RETE算法简答/延伸考察算法迁移到业务的能力低密码学基础SM2/SM3/SM4、ZUC算法了解了解各自用途即可不深入从这个表能看出来笔试拉分的关键不完全在难题而在“基础题能不能快速满分”。很多人挂在KMP手算上、挂在复杂度排序上丢的都是不该丢的分。2. 数据结构与经典算法逐题拆解2.1 KMP算法手算模式串abacaba的next数组KMP是字符串匹配里最高频的考点这份试卷直接给了一个具体模式串p abacaba。要求计算next数组next[i]定义为模式串前i个字符组成的子串中最长相等前缀和后缀的长度部分教材定义为前缀表整体右移一位再补-1这里我用国内教材最常见的定义。手工计算过程如下i0子串是a没有真前缀和真后缀next[0]0。i1子串是ab前缀集合是{ a }后缀集合是{ b }没有相等的next[1]0。i2子串是aba前缀是a、ab后缀是a、ba最长公共前后缀是a长度1next[2]1。i3子串是abac前缀a、ab、aba后缀c、ac、bac无公共项next[3]0。i4子串是abaca前缀...后缀...最长公共前后缀是anext[4]1。i5子串是abacab最长公共前后缀是ab长度2next[5]2。i6子串是abacaba最长公共前后缀是aba长度3next[6]3。所以完整的next数组是next [0, 0, 1, 0, 1, 2, 3]。这里有个进阶版本有的试卷会要求计算nextval数组优化后的next数组。nextval的思路是如果当前字符回退到的那个位置字符和当前字符相同就继续回退避免无效比较。手算nextval的规则是nextval[0]0对第i个位置若p[i] ! p[next[i]]则nextval[i]next[i]若p[i] p[next[i]]则nextval[i]nextval[next[i]]。逐个算nextval[0] 0。i1p[1]bp[next[1]]p[0]a不相等nextval[1]next[1]0。i2p[2]ap[next[2]]p[1]b不相等nextval[2]next[2]1。i3p[3]cp[next[3]]p[0]a不相等nextval[3]next[3]0。i4p[4]ap[next[4]]p[1]b不相等nextval[4]next[4]1。i5p[5]bp[next[5]]p[2]a不相等nextval[5]next[5]2。i6p[6]ap[next[6]]p[3]c不相等nextval[6]next[6]3。结果正好还是[0, 0, 1, 0, 1, 2, 3]。这个模式串比较特殊优化没有带来变化因为每个位置的字符都和回退目标位置的字符不同。注意不同教材对next数组的定义差别很大。有的定义是“前缀表整体右移一位第一位补-1”这时算出来是[-1, 0, 0, 1, 0, 1, 2]还有的定义是“最长相等前后缀长度减1”结果又不一样。答题时先写清楚自己采用的定义再开始计算避免阅卷时产生误解。2.2 排序与堆从冒泡到堆排序的复杂度图谱排序算法在笔试里属于“送分题”和“陷阱题”并存的部分。说送分是因为复杂度表背下来就能答说陷阱是因为题目会换着角度考比如“哪种排序算法在近乎有序的数组上表现最好”“哪种排序是不稳定的”“堆排序建堆的复杂度是多少”。我个人建议把常见排序算法按稳定性、时间复杂度、空间复杂度、适用场景四个维度整理成一张表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)左右O(n²)O(1)不稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定这里标红几个高频考点。快速排序的最坏情况是O(n²)发生在每次分区都极端不平衡时比如对已经有序的数组用固定基准值。这是笔试选择题喜欢挖的坑答案不是“快排一定O(n log n)”。堆排序虽然空间复杂度是O(1)但实际性能常常不如快排因为堆排序的缓存局部性差数组访问跳跃大。笔试如果考“哪种排序在大数据量下不稳定且常数因子大”优先想到堆排序。冒泡排序虽然平均复杂度不占优但它有一个特性在数组基本有序时如果加了“本轮无交换则提前退出”的优化最好情况能达到O(n)。这个点经常出现在“选择最优排序算法”的应用题里。另外Java的Arrays.sort()底层对基本类型用的是双轴快速排序对对象类型用的是TimSort一种优化的归并排序。这类“工程实现细节”题目在面试环节出现概率更高笔试也会以选择题出现一次。备考时可以顺带了解。2.3 图论与组合优化Dijkstra、二分图与HK算法图论算法在二手车业务里的映射非常直接Dijkstra可以用于城市间车辆调度最短路径、用户到线下门店的最短通勤距离二分图匹配用于“车源-用户”“车商-流量位”这类供需两侧的匹配问题。Dijkstra算法的核心是贪心每次从未确定最短路的节点中选一个距离最小的用它去松弛相邻节点。它的前提条件是图中不能有负权边。复杂度上朴素实现是O(V²)用二叉堆优化后是O((VE) log V)用斐波那契堆可以到O(E V log V)。笔试常考二选一题目给稠密图V在几千以内朴素实现够用题目给稀疏图V在十万级别必须用堆优化。二分图匹配是另一个高频考点。最经典的算法是匈牙利算法DFS实现复杂度O(VE)在数据量几百的规模下没问题。但瓜子这类平台做车源和用户匹配时数据量是百万级以上的匈牙利算法完全扛不住这时候就得用HK算法Hopcroft-Karp算法。HK算法的核心改进是用BFS构建多条不相交的最短增广路再用DFS沿着这些增广路同时匹配。这样做一轮可以处理多条增广路总复杂度降到O(E√V)。笔试如果考到HK算法通常不会让完整手写而是考察它比匈牙利算法优化在哪为什么用BFSDFS组合复杂度对比。实际笔试里二分图匹配的代码题一般会给小规模数据V 500这时候匈牙利算法足够。但你要是能在答案里提一句“数据量大时可以换成HK算法”会是不错的加分项。3. 机器学习与业务算法应用分析3.1 粒子群算法原理与代码实现粒子群算法PSO在试卷里作为机器学习/优化算法考点出现过。它模拟鸟群觅食行为每个解是搜索空间里的一个粒子粒子有位置和速度通过个体历史最优和群体历史最优来更新自己。核心公式有两个速度更新v_id w * v_id c1 * r1 * (pbest_id - x_id) c2 * r2 * (gbest_d - x_id)位置更新x_id x_id v_id其中w是惯性权重c1和c2是学习因子r1和r2是[0,1]的随机数。w大的时候全局搜索能力强w小的时候局部开发能力强常见做法是让w随迭代次数从0.9线性降到0.4。PSO适合处理连续优化问题比如二手车定价模型里的超参数调优、价格回归模型的权重初始化。笔试如果考PSO的简答题重点答三点粒子编码方式、适应度函数设计、收敛条件设置。如果考手写最简版Python实现大概是import random def pso(fitness, dim, n_particles30, max_iter100, w0.8, c12.0, c22.0): # 初始化粒子位置和速度 x [[random.uniform(-10, 10) for _ in range(dim)] for _ in range(n_particles)] v [[random.uniform(-1, 1) for _ in range(dim)] for _ in range(n_particles)] pbest [p[:] for p in x] pbest_val [fitness(p) for p in x] gbest_idx min(range(n_particles), keylambda i: pbest_val[i]) gbest pbest[gbest_idx][:] gbest_val pbest_val[gbest_idx] for _ in range(max_iter): for i in range(n_particles): r1, r2 random.random(), random.random() for d in range(dim): v[i][d] w * v[i][d] c1 * r1 * (pbest[i][d] - x[i][d]) c2 * r2 * (gbest[d] - x[i][d]) x[i][d] v[i][d] cur_val fitness(x[i]) if cur_val pbest_val[i]: pbest_val[i] cur_val pbest[i] x[i][:] if cur_val gbest_val: gbest_val cur_val gbest x[i][:] return gbest, gbest_val笔试真正考PSO代码的概率不大但考“如何设计适应度函数”的概率很高。比如车辆定价问题可以把适应度函数设计成预测价格和成交价的均方误差推荐问题可以设计成点击率的负对数似然。3.2 BM25在搜索排序中的角色BM25是搜索排序里非常经典的概率模型在二手车平台的搜索场景里用户搜“黑色汉兰达”“5万以下自动挡”系统需要先召回候选车源再按相关性排序。BM25就是召回和粗排阶段常用的相关性计算方法。BM25公式拆开看score(D, Q) sum( IDF(qi) * (tf(qi,D) * (k11)) / (tf(qi,D) k1 * (1 - b b * len(D)/avgdl)) )其中IDF(qi)是逆文档频率tf(qi,D)是词项在文档里出现的频率len(D)是文档长度avgdl是平均文档长度k1和b是调节参数通常取k11.2~2.0b0.75。BM25的核心思想是某个词在文档中出现次数越多越相关但出现次数带来的收益是边际递减的文档越长词频越容易被稀释所以要加上长度归一化某个词在越多的文档里出现区分度越低IDF权重越小。二手车场景下车源标题通常很短比如“2017款大众途观L自动两驱舒适版”搜索引擎如果用朴素TF-IDF长词“自动两驱舒适版”会因为词频低被忽略但用户搜“途观L 自动”时这个车源恰恰是高度相关的。BM25通过词频饱和曲线和文档长度归一化能比TF-IDF更稳地处理这种短文本匹配问题。如果笔试出“搜索相关性排序题”不要一上来就写BM25公式先分析场景特点标题短、词项少、类目词和品牌词很重要、同义词多。再点出为什么选BM25而不是TF-IDF或向量空间模型这样答题会更有层次。3.3 贪心、PID控制与规则引擎的跨域算法思维这份试卷有意思的地方在于它不仅考常规算法还会从业务系统里抽出一些看似“非算法”的考点。贪心算法在匹配问题里很常见比如“给定N个车源和M个用户每个用户最多分配一个车源如何让总成交概率最大”。如果每个用户对不同车源的偏好独立贪心可以按“全局最优”做近似但真正要最优解得靠匈牙利算法或HK算法。笔试考贪心有时候是为了对比“贪心为什么不是最优解”这个时候要会用反例说明。PID算法是控制论里的经典算法在CRPS电源模块、PSU电源控制这类硬件场景里很常见。它的核心是对偏差做比例、积分、微分三种运算。笔试考PID更多是考算法思维迁移能不能把一个业务问题抽象成闭环控制问题比如“广告出价调整”用PID的思路控制出价让转化量稳定在目标值附近。规则引擎Drools里的RETE算法也值得关注。RETE算法核心是构建一个网络结构把规则的条件部分拆成节点用共享节点避免重复匹配事实。它适合大量规则、大量事实且规则变化不频繁的场景。笔试考RETE概率不高但一旦考到通常会问“RETE算法为什么能加速规则匹配”答出“利用结构共享、缓存中间匹配结果、只在事实变化时更新增量”这三点就够用。备考时不要只盯着一类算法。2020年以后的大厂笔试题越来越喜欢混合考察一份卷子里同时出现排序、字符串、图论、机器学习甚至控制论算法拼的是你脑子里有没有一张“算法地图”。平时学习时多做“这个算法能用在业务的哪个环节”的映射练习笔试时看到业务场景题就不会慌。4. 编程题思路与手写代码要点4.1 KMP匹配实战求模式串在主串中的出现位置编程题第一题大概率是KMP的完整实现要求给定主串t和模式串p返回p在t中出现的所有起始下标主串和模式串长度都可能达到10^5不能用朴素匹配O(n*m)硬解。先求next数组再分两步匹配。我用C写一个标准版本#include vector #include string using namespace std; vectorint getNext(const string p) { int n p.size(); vectorint next(n, 0); for (int i 1; i n; i) { int j next[i - 1]; while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; } vectorint kmp(const string t, const string p) { vectorint res; int m t.size(), n p.size(); if (n 0) return res; vectorint next getNext(p); int j 0; for (int i 0; i m; i) { while (j 0 t[i] ! p[j]) { j next[j - 1]; } if (t[i] p[j]) { j; } if (j n) { res.push_back(i - n 1); j next[j - 1]; } } return res; }这里用的是“next[i]表示前i个字符的最长相等前后缀长度”的定义所以匹配失败时回退到next[j-1]而不是next[j]。这个细节非常容易写错一旦定义混了整个程序就会在原地打转或跳过答案。写KMP的代码我最常犯的错有两个模式串长度为1时next数组只有0匹配循环里访问next[j-1]会越界需要在jn后先保存结果再判断没有重置j导致匹配完一次后下一次匹配从错误位置开始。当然笔试如果语言不限可以直接用Python的str.find或Java的indexOf暴力过小数据但要是明确要求“实现KMP”还是得老老实实写。4.2 快速幂与Top K高频手写题模板快速幂是个容易考但很多人临场写不对的题。它解决的是计算a的b次方对m取模的问题b可以大到10^18。核心思路是二进制分解指数把乘法次数从O(b)降到O(log b)。long long quickPow(long long a, long long b, long long mod) { long long res 1 % mod; a % mod; while (b 0) { if (b 1) { res res * a % mod; } a a * a % mod; b 1; } return res; }注意点初始res要取1 % mod因为mod可能等于1底数要先取模每一步乘法都可能溢出long long在极端大模数下也可能不够需要按题目情况用快速乘或内置的__int128。Top K问题是堆排序的经典应用。我推荐记一个模板求前K个最大的数用小顶堆求前K个最小的数用大顶堆。堆的大小维护在K遍历一遍数据比堆顶大就替换并调整堆。C里直接用priority_queueJava用PriorityQueuePython用heapq。vectorint topK(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int x : nums) { if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } vectorint res(k); for (int i 0; i k; i) { res[i] pq.top(); pq.pop(); } return res; }这里有个笔试题陷阱如果数据量只有几千直接用sort再取前K个就行不用堆但如果数据量是几千万、内存放不下或者要求在线流式处理堆就是唯一合理方案。回答的时候先把场景说清楚再选方案能体现工程思维。4.3 边界条件与工程细节编程题最容易挂的不是算法本身而是边界条件。我在笔试和实际代码 review 里总结了四个高频边界坑空输入。模式串为空、数组为空、k为0、k大于数组长度这些情况在答题前就要想好怎么处理。建议在代码开头统一加防御性判断。溢出。涉及乘法和加法的题先确认数据范围是int还是long long模数有没有可能为0或1。下标越界。KMP、二分查找、滑动窗口这类题最容易在边界处访问-1或n。写完后一定要自己模拟一遍2-3个输入。重复结果。匹配类题目如果允许多个重叠匹配要确认res里能不能放重复位置比如“aaaa”里匹配“aa”答案应该是[0,1,2]还是[0,2]题目没说明时按常规允许重叠匹配处理。另外笔试环境通常不能调外部依赖手写代码时尽量避免用太高级的API。用C的优先队列没问题但千万别用boost用Python可以import collections和math但不能依赖numpy和pandas。提前熟悉在线平台的Python/Java/C环境能省很多时间。5. 笔试中的常见问题与避坑技巧5.1 时间分配与做题顺序我见过不少同学笔试挂掉不是因为不会做而是时间分配完全失控。算法笔试卷常见的组合是20道选择题、5道简答题、2道编程题总时长90到120分钟。我的做题顺序建议是先花5分钟通读全卷把选择题里一眼会的先做掉编程题优先选择自己最熟的那一道做先保证有一道AC再做简答题简答题分值高多写点关键词和公式最后回头啃选择题里的难题这种题通常是单个知识点死磕也花不了太多时间。选择题的答题技巧是排除法优先。比如考“哪项不是稳定排序”如果不记得哪些不稳定可以想想每个算法的交换行为冒泡和插入只在相邻元素间交换稳定性天然好快排、堆排、选择都涉及跨距离交换稳定性容易被破坏。这样推出来大致没问题。5.2 读题、复杂度与边界条件自查很多同学一看到“排序”两个字就直接开始写快排结果题目要的是“稳定排序且额外空间O(1)”——这个条件组合下传统稳定排序里只有原地归并能勉强做到或者直接用插入排序在小规模下凑合。读题时圈出“最小复杂度”“不能使用额外空间”“原地”“稳定”“有序数组”这些关键词比急着写代码重要得多。手写编程题写完不要立刻交留3分钟做三件事检查要不要处理long long和取模检查数组访问会不会越界用题目给的样例手工模拟一遍确认输出和题目一致。我在实际笔试里遇到过一次“自认为AC了但0分”的情况原因是循环里少写了一个break导致死循环超时。后来每道题写完都会强制自己逐行读一遍代码尤其是while和for的退出条件。5.3 笔试题背后的面试延伸笔试不只是为了筛选面试官看你的答卷会重点看你在简答题里展现的思考方式。比如笔试里考了BM25面试很可能追问“BM25的k1和b分别怎么调如果车源描述很长b应该调大还是调小”如果你能在简答题里写出b的调节逻辑文档越长词频稀释越严重所以长文本场景b调大面试官就会觉得你不只是背了公式。还有试卷里出现粒子群算法这种相对冷门的优化算法说明业务团队可能在用PSO做参数寻优或特征选择。面试时如果被问“你用过哪些优化算法”可以补充一个PSO用过的小案例哪怕是在项目里用PSO调过XGBoost的超参数都很加分。所以我的建议是备考时不要只刷LeetCode还要做一件事把每个高频算法都问自己三个问题——它解决什么问题它的复杂度瓶颈在哪它在二手车/交易平台的哪个场景能落地。带着这三个问题去看卷子思路会清晰很多。最后再分享一个实际经验手算next数组、手写快排、手动模拟堆排序这些“笨功夫”在笔试前一周值得每天过一遍。这些基础题不但帮你在选择题和编程题上拿稳分还能在面试手撕代码环节给你建立信心。真正到了笔试现场你会发现在安静的环境里脑子里最清晰的永远是练过最多遍的东西。 秋招算法笔试全解：从KMP到二分图匹配，二手车业务场景拆解
这份瓜子二手车2019秋招算法笔试卷我前前后后看了不少遍。它和我见过的很多互联网公司算法笔试风格很像看着是常规的数据结构与算法但实际把排序、字符串匹配、图论、搜索排序、甚至控制类算法的思路全揉进去了业务味道也藏得挺深。二手车平台的核心是车源定价、搜索推荐、供需匹配这些场景所以考算法不会只考纯理论而是会变着法子考察你把算法落到业务里的能力。这份试卷适合两类人一是准备秋招算法岗、还没做过车企或交易平台笔试题的应届生拿来摸底很合适二是在职工程师想查漏补缺看看自己脱离刷题状态后还能不能快速上手。下面我就照着试卷的题型分布把每一类核心考点拆开讲清楚包括解题思路、计算过程以及我在实际笔试和面试里踩过的坑。1. 整体题型结构与备考方向1.1 这份笔试卷的定位与出题逻辑瓜子二手车做的是C2C和B2C结合的二手车交易平台业务链条里最重的是三件事车源定价、搜索推荐、供需匹配。这三个业务方向基本决定了算法笔试的考点范围。车源定价需要回归模型、价格预测所以机器学习算法、特征工程这类考点会以简答题或应用题形式出现搜索推荐需要召回、排序所以BM25、排序算法、字符串匹配这类基础算法分量很重供需匹配要解决的是“哪辆车推给哪个用户”“哪个车商优先获得流量”这类组合优化问题所以贪心算法、二分图匹配HK算法、Dijkstra最短路这类图论算法也会频繁出现。和纯互联网公司不一样二手车平台的算法笔试会更“落地”。它不大会让你证明某个算法的严谨数学性质而是给你一个业务场景让你选算法、算复杂度、手写核心代码。所以备考的时候不能光背算法模板得习惯性地想一件事这个算法在这个真实场景里输入是什么、输出是什么、数据量有多大、瓶颈在哪里。1.2 高频考点分布与备考优先级我根据试卷内容和往年同学反馈把考点优先级整理成了下面这个表。笔试时间有限优先保证“必考且好拿分”的部分再攻难度大的。优先级考点分类典型考点考察形式备注高字符串匹配KMP算法、next数组计算填空/选择/编程手算next数组是必考必须熟练高排序与堆快排、堆排序、Top K选择/编程复杂度要倒背如流堆排要能手写高基础数据结构栈、队列、哈希表选择/简答注意边界条件和扩容策略中高图论算法Dijkstra、二分图匈牙利/HK算法选择/简答重点在适用条件和复杂度对比中数值算法快速幂、哈希算法编程/简答快速幂是手写题常客中机器学习聚类、KNN、粒子群算法选择/简答重点在原理、收敛性和适用场景中低业务算法BM25、PID、规则引擎RETE算法简答/延伸考察算法迁移到业务的能力低密码学基础SM2/SM3/SM4、ZUC算法了解了解各自用途即可不深入从这个表能看出来笔试拉分的关键不完全在难题而在“基础题能不能快速满分”。很多人挂在KMP手算上、挂在复杂度排序上丢的都是不该丢的分。2. 数据结构与经典算法逐题拆解2.1 KMP算法手算模式串abacaba的next数组KMP是字符串匹配里最高频的考点这份试卷直接给了一个具体模式串p abacaba。要求计算next数组next[i]定义为模式串前i个字符组成的子串中最长相等前缀和后缀的长度部分教材定义为前缀表整体右移一位再补-1这里我用国内教材最常见的定义。手工计算过程如下i0子串是a没有真前缀和真后缀next[0]0。i1子串是ab前缀集合是{ a }后缀集合是{ b }没有相等的next[1]0。i2子串是aba前缀是a、ab后缀是a、ba最长公共前后缀是a长度1next[2]1。i3子串是abac前缀a、ab、aba后缀c、ac、bac无公共项next[3]0。i4子串是abaca前缀...后缀...最长公共前后缀是anext[4]1。i5子串是abacab最长公共前后缀是ab长度2next[5]2。i6子串是abacaba最长公共前后缀是aba长度3next[6]3。所以完整的next数组是next [0, 0, 1, 0, 1, 2, 3]。这里有个进阶版本有的试卷会要求计算nextval数组优化后的next数组。nextval的思路是如果当前字符回退到的那个位置字符和当前字符相同就继续回退避免无效比较。手算nextval的规则是nextval[0]0对第i个位置若p[i] ! p[next[i]]则nextval[i]next[i]若p[i] p[next[i]]则nextval[i]nextval[next[i]]。逐个算nextval[0] 0。i1p[1]bp[next[1]]p[0]a不相等nextval[1]next[1]0。i2p[2]ap[next[2]]p[1]b不相等nextval[2]next[2]1。i3p[3]cp[next[3]]p[0]a不相等nextval[3]next[3]0。i4p[4]ap[next[4]]p[1]b不相等nextval[4]next[4]1。i5p[5]bp[next[5]]p[2]a不相等nextval[5]next[5]2。i6p[6]ap[next[6]]p[3]c不相等nextval[6]next[6]3。结果正好还是[0, 0, 1, 0, 1, 2, 3]。这个模式串比较特殊优化没有带来变化因为每个位置的字符都和回退目标位置的字符不同。注意不同教材对next数组的定义差别很大。有的定义是“前缀表整体右移一位第一位补-1”这时算出来是[-1, 0, 0, 1, 0, 1, 2]还有的定义是“最长相等前后缀长度减1”结果又不一样。答题时先写清楚自己采用的定义再开始计算避免阅卷时产生误解。2.2 排序与堆从冒泡到堆排序的复杂度图谱排序算法在笔试里属于“送分题”和“陷阱题”并存的部分。说送分是因为复杂度表背下来就能答说陷阱是因为题目会换着角度考比如“哪种排序算法在近乎有序的数组上表现最好”“哪种排序是不稳定的”“堆排序建堆的复杂度是多少”。我个人建议把常见排序算法按稳定性、时间复杂度、空间复杂度、适用场景四个维度整理成一张表算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)左右O(n²)O(1)不稳定选择排序O(n²)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定这里标红几个高频考点。快速排序的最坏情况是O(n²)发生在每次分区都极端不平衡时比如对已经有序的数组用固定基准值。这是笔试选择题喜欢挖的坑答案不是“快排一定O(n log n)”。堆排序虽然空间复杂度是O(1)但实际性能常常不如快排因为堆排序的缓存局部性差数组访问跳跃大。笔试如果考“哪种排序在大数据量下不稳定且常数因子大”优先想到堆排序。冒泡排序虽然平均复杂度不占优但它有一个特性在数组基本有序时如果加了“本轮无交换则提前退出”的优化最好情况能达到O(n)。这个点经常出现在“选择最优排序算法”的应用题里。另外Java的Arrays.sort()底层对基本类型用的是双轴快速排序对对象类型用的是TimSort一种优化的归并排序。这类“工程实现细节”题目在面试环节出现概率更高笔试也会以选择题出现一次。备考时可以顺带了解。2.3 图论与组合优化Dijkstra、二分图与HK算法图论算法在二手车业务里的映射非常直接Dijkstra可以用于城市间车辆调度最短路径、用户到线下门店的最短通勤距离二分图匹配用于“车源-用户”“车商-流量位”这类供需两侧的匹配问题。Dijkstra算法的核心是贪心每次从未确定最短路的节点中选一个距离最小的用它去松弛相邻节点。它的前提条件是图中不能有负权边。复杂度上朴素实现是O(V²)用二叉堆优化后是O((VE) log V)用斐波那契堆可以到O(E V log V)。笔试常考二选一题目给稠密图V在几千以内朴素实现够用题目给稀疏图V在十万级别必须用堆优化。二分图匹配是另一个高频考点。最经典的算法是匈牙利算法DFS实现复杂度O(VE)在数据量几百的规模下没问题。但瓜子这类平台做车源和用户匹配时数据量是百万级以上的匈牙利算法完全扛不住这时候就得用HK算法Hopcroft-Karp算法。HK算法的核心改进是用BFS构建多条不相交的最短增广路再用DFS沿着这些增广路同时匹配。这样做一轮可以处理多条增广路总复杂度降到O(E√V)。笔试如果考到HK算法通常不会让完整手写而是考察它比匈牙利算法优化在哪为什么用BFSDFS组合复杂度对比。实际笔试里二分图匹配的代码题一般会给小规模数据V 500这时候匈牙利算法足够。但你要是能在答案里提一句“数据量大时可以换成HK算法”会是不错的加分项。3. 机器学习与业务算法应用分析3.1 粒子群算法原理与代码实现粒子群算法PSO在试卷里作为机器学习/优化算法考点出现过。它模拟鸟群觅食行为每个解是搜索空间里的一个粒子粒子有位置和速度通过个体历史最优和群体历史最优来更新自己。核心公式有两个速度更新v_id w * v_id c1 * r1 * (pbest_id - x_id) c2 * r2 * (gbest_d - x_id)位置更新x_id x_id v_id其中w是惯性权重c1和c2是学习因子r1和r2是[0,1]的随机数。w大的时候全局搜索能力强w小的时候局部开发能力强常见做法是让w随迭代次数从0.9线性降到0.4。PSO适合处理连续优化问题比如二手车定价模型里的超参数调优、价格回归模型的权重初始化。笔试如果考PSO的简答题重点答三点粒子编码方式、适应度函数设计、收敛条件设置。如果考手写最简版Python实现大概是import random def pso(fitness, dim, n_particles30, max_iter100, w0.8, c12.0, c22.0): # 初始化粒子位置和速度 x [[random.uniform(-10, 10) for _ in range(dim)] for _ in range(n_particles)] v [[random.uniform(-1, 1) for _ in range(dim)] for _ in range(n_particles)] pbest [p[:] for p in x] pbest_val [fitness(p) for p in x] gbest_idx min(range(n_particles), keylambda i: pbest_val[i]) gbest pbest[gbest_idx][:] gbest_val pbest_val[gbest_idx] for _ in range(max_iter): for i in range(n_particles): r1, r2 random.random(), random.random() for d in range(dim): v[i][d] w * v[i][d] c1 * r1 * (pbest[i][d] - x[i][d]) c2 * r2 * (gbest[d] - x[i][d]) x[i][d] v[i][d] cur_val fitness(x[i]) if cur_val pbest_val[i]: pbest_val[i] cur_val pbest[i] x[i][:] if cur_val gbest_val: gbest_val cur_val gbest x[i][:] return gbest, gbest_val笔试真正考PSO代码的概率不大但考“如何设计适应度函数”的概率很高。比如车辆定价问题可以把适应度函数设计成预测价格和成交价的均方误差推荐问题可以设计成点击率的负对数似然。3.2 BM25在搜索排序中的角色BM25是搜索排序里非常经典的概率模型在二手车平台的搜索场景里用户搜“黑色汉兰达”“5万以下自动挡”系统需要先召回候选车源再按相关性排序。BM25就是召回和粗排阶段常用的相关性计算方法。BM25公式拆开看score(D, Q) sum( IDF(qi) * (tf(qi,D) * (k11)) / (tf(qi,D) k1 * (1 - b b * len(D)/avgdl)) )其中IDF(qi)是逆文档频率tf(qi,D)是词项在文档里出现的频率len(D)是文档长度avgdl是平均文档长度k1和b是调节参数通常取k11.2~2.0b0.75。BM25的核心思想是某个词在文档中出现次数越多越相关但出现次数带来的收益是边际递减的文档越长词频越容易被稀释所以要加上长度归一化某个词在越多的文档里出现区分度越低IDF权重越小。二手车场景下车源标题通常很短比如“2017款大众途观L自动两驱舒适版”搜索引擎如果用朴素TF-IDF长词“自动两驱舒适版”会因为词频低被忽略但用户搜“途观L 自动”时这个车源恰恰是高度相关的。BM25通过词频饱和曲线和文档长度归一化能比TF-IDF更稳地处理这种短文本匹配问题。如果笔试出“搜索相关性排序题”不要一上来就写BM25公式先分析场景特点标题短、词项少、类目词和品牌词很重要、同义词多。再点出为什么选BM25而不是TF-IDF或向量空间模型这样答题会更有层次。3.3 贪心、PID控制与规则引擎的跨域算法思维这份试卷有意思的地方在于它不仅考常规算法还会从业务系统里抽出一些看似“非算法”的考点。贪心算法在匹配问题里很常见比如“给定N个车源和M个用户每个用户最多分配一个车源如何让总成交概率最大”。如果每个用户对不同车源的偏好独立贪心可以按“全局最优”做近似但真正要最优解得靠匈牙利算法或HK算法。笔试考贪心有时候是为了对比“贪心为什么不是最优解”这个时候要会用反例说明。PID算法是控制论里的经典算法在CRPS电源模块、PSU电源控制这类硬件场景里很常见。它的核心是对偏差做比例、积分、微分三种运算。笔试考PID更多是考算法思维迁移能不能把一个业务问题抽象成闭环控制问题比如“广告出价调整”用PID的思路控制出价让转化量稳定在目标值附近。规则引擎Drools里的RETE算法也值得关注。RETE算法核心是构建一个网络结构把规则的条件部分拆成节点用共享节点避免重复匹配事实。它适合大量规则、大量事实且规则变化不频繁的场景。笔试考RETE概率不高但一旦考到通常会问“RETE算法为什么能加速规则匹配”答出“利用结构共享、缓存中间匹配结果、只在事实变化时更新增量”这三点就够用。备考时不要只盯着一类算法。2020年以后的大厂笔试题越来越喜欢混合考察一份卷子里同时出现排序、字符串、图论、机器学习甚至控制论算法拼的是你脑子里有没有一张“算法地图”。平时学习时多做“这个算法能用在业务的哪个环节”的映射练习笔试时看到业务场景题就不会慌。4. 编程题思路与手写代码要点4.1 KMP匹配实战求模式串在主串中的出现位置编程题第一题大概率是KMP的完整实现要求给定主串t和模式串p返回p在t中出现的所有起始下标主串和模式串长度都可能达到10^5不能用朴素匹配O(n*m)硬解。先求next数组再分两步匹配。我用C写一个标准版本#include vector #include string using namespace std; vectorint getNext(const string p) { int n p.size(); vectorint next(n, 0); for (int i 1; i n; i) { int j next[i - 1]; while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; } vectorint kmp(const string t, const string p) { vectorint res; int m t.size(), n p.size(); if (n 0) return res; vectorint next getNext(p); int j 0; for (int i 0; i m; i) { while (j 0 t[i] ! p[j]) { j next[j - 1]; } if (t[i] p[j]) { j; } if (j n) { res.push_back(i - n 1); j next[j - 1]; } } return res; }这里用的是“next[i]表示前i个字符的最长相等前后缀长度”的定义所以匹配失败时回退到next[j-1]而不是next[j]。这个细节非常容易写错一旦定义混了整个程序就会在原地打转或跳过答案。写KMP的代码我最常犯的错有两个模式串长度为1时next数组只有0匹配循环里访问next[j-1]会越界需要在jn后先保存结果再判断没有重置j导致匹配完一次后下一次匹配从错误位置开始。当然笔试如果语言不限可以直接用Python的str.find或Java的indexOf暴力过小数据但要是明确要求“实现KMP”还是得老老实实写。4.2 快速幂与Top K高频手写题模板快速幂是个容易考但很多人临场写不对的题。它解决的是计算a的b次方对m取模的问题b可以大到10^18。核心思路是二进制分解指数把乘法次数从O(b)降到O(log b)。long long quickPow(long long a, long long b, long long mod) { long long res 1 % mod; a % mod; while (b 0) { if (b 1) { res res * a % mod; } a a * a % mod; b 1; } return res; }注意点初始res要取1 % mod因为mod可能等于1底数要先取模每一步乘法都可能溢出long long在极端大模数下也可能不够需要按题目情况用快速乘或内置的__int128。Top K问题是堆排序的经典应用。我推荐记一个模板求前K个最大的数用小顶堆求前K个最小的数用大顶堆。堆的大小维护在K遍历一遍数据比堆顶大就替换并调整堆。C里直接用priority_queueJava用PriorityQueuePython用heapq。vectorint topK(vectorint nums, int k) { priority_queueint, vectorint, greaterint pq; // 小顶堆 for (int x : nums) { if (pq.size() k) { pq.push(x); } else if (x pq.top()) { pq.pop(); pq.push(x); } } vectorint res(k); for (int i 0; i k; i) { res[i] pq.top(); pq.pop(); } return res; }这里有个笔试题陷阱如果数据量只有几千直接用sort再取前K个就行不用堆但如果数据量是几千万、内存放不下或者要求在线流式处理堆就是唯一合理方案。回答的时候先把场景说清楚再选方案能体现工程思维。4.3 边界条件与工程细节编程题最容易挂的不是算法本身而是边界条件。我在笔试和实际代码 review 里总结了四个高频边界坑空输入。模式串为空、数组为空、k为0、k大于数组长度这些情况在答题前就要想好怎么处理。建议在代码开头统一加防御性判断。溢出。涉及乘法和加法的题先确认数据范围是int还是long long模数有没有可能为0或1。下标越界。KMP、二分查找、滑动窗口这类题最容易在边界处访问-1或n。写完后一定要自己模拟一遍2-3个输入。重复结果。匹配类题目如果允许多个重叠匹配要确认res里能不能放重复位置比如“aaaa”里匹配“aa”答案应该是[0,1,2]还是[0,2]题目没说明时按常规允许重叠匹配处理。另外笔试环境通常不能调外部依赖手写代码时尽量避免用太高级的API。用C的优先队列没问题但千万别用boost用Python可以import collections和math但不能依赖numpy和pandas。提前熟悉在线平台的Python/Java/C环境能省很多时间。5. 笔试中的常见问题与避坑技巧5.1 时间分配与做题顺序我见过不少同学笔试挂掉不是因为不会做而是时间分配完全失控。算法笔试卷常见的组合是20道选择题、5道简答题、2道编程题总时长90到120分钟。我的做题顺序建议是先花5分钟通读全卷把选择题里一眼会的先做掉编程题优先选择自己最熟的那一道做先保证有一道AC再做简答题简答题分值高多写点关键词和公式最后回头啃选择题里的难题这种题通常是单个知识点死磕也花不了太多时间。选择题的答题技巧是排除法优先。比如考“哪项不是稳定排序”如果不记得哪些不稳定可以想想每个算法的交换行为冒泡和插入只在相邻元素间交换稳定性天然好快排、堆排、选择都涉及跨距离交换稳定性容易被破坏。这样推出来大致没问题。5.2 读题、复杂度与边界条件自查很多同学一看到“排序”两个字就直接开始写快排结果题目要的是“稳定排序且额外空间O(1)”——这个条件组合下传统稳定排序里只有原地归并能勉强做到或者直接用插入排序在小规模下凑合。读题时圈出“最小复杂度”“不能使用额外空间”“原地”“稳定”“有序数组”这些关键词比急着写代码重要得多。手写编程题写完不要立刻交留3分钟做三件事检查要不要处理long long和取模检查数组访问会不会越界用题目给的样例手工模拟一遍确认输出和题目一致。我在实际笔试里遇到过一次“自认为AC了但0分”的情况原因是循环里少写了一个break导致死循环超时。后来每道题写完都会强制自己逐行读一遍代码尤其是while和for的退出条件。5.3 笔试题背后的面试延伸笔试不只是为了筛选面试官看你的答卷会重点看你在简答题里展现的思考方式。比如笔试里考了BM25面试很可能追问“BM25的k1和b分别怎么调如果车源描述很长b应该调大还是调小”如果你能在简答题里写出b的调节逻辑文档越长词频稀释越严重所以长文本场景b调大面试官就会觉得你不只是背了公式。还有试卷里出现粒子群算法这种相对冷门的优化算法说明业务团队可能在用PSO做参数寻优或特征选择。面试时如果被问“你用过哪些优化算法”可以补充一个PSO用过的小案例哪怕是在项目里用PSO调过XGBoost的超参数都很加分。所以我的建议是备考时不要只刷LeetCode还要做一件事把每个高频算法都问自己三个问题——它解决什么问题它的复杂度瓶颈在哪它在二手车/交易平台的哪个场景能落地。带着这三个问题去看卷子思路会清晰很多。最后再分享一个实际经验手算next数组、手写快排、手动模拟堆排序这些“笨功夫”在笔试前一周值得每天过一遍。这些基础题不但帮你在选择题和编程题上拿稳分还能在面试手撕代码环节给你建立信心。真正到了笔试现场你会发现在安静的环境里脑子里最清晰的永远是练过最多遍的东西。