点我达校招算法笔试复盘：从KMP到即时配送场景建模

点我达2019届校招算法笔试放到今天的即时配送赛道里看算是很有代表性的一套题。我当年备考算法岗的时候正好赶上这轮校招刷了不少公司的笔试题点我达这套给我的印象非常深——它不是单纯的LeetCode堆砌选择题、编程题、场景题混合着来明显能感觉到出题人想把算法落到实际的骑手调度和订单配送场景里。如果你正准备算法岗、机器学习岗的校招或者单纯想看看即时配送行业在算法上到底考什么这份复盘应该能给你一些不一样的参考。1. 笔试整体设计与考察逻辑1.1 这场笔试想筛什么样的人先说结论点我达的算法笔试不追求“偏题怪题”而是非常看重基础算法的熟练度、手推公式的严谨性以及把算法迁移到业务场景里的能力。这个定位和它的业务模式是强相关的——众包物流、即时配送核心问题无非是骑手怎么派、路线怎么走、时间怎么估、价格怎么定这些背后全是算法活儿。所以整张卷子给我的感觉是三个字接地气。它不会让你默写一个特别冷门的神经网络结构但是会反复考察KMP、排序、动态规划这些经典内容并且总喜欢在题目后面加一句“如果应用到配送场景中你会怎么改”。这就筛掉了一类只会背题、不懂业务的候选人。从题型结构上看印象中主要分为三块选择题涵盖数据结构、算法复杂度、机器学习基础、编程题大概两到三道核心是数据结构与算法的手写实现、问答与场景设计题给出业务问题让你建模并用文字描述算法方案。时间安排上比较紧张选择题要控制得很快否则后面编程题会很被动。1.2 知识点覆盖面与难度分布这套题的知识点覆盖率相当广从经典的数据结构到机器学习、深度学习都有涉及。我根据自己的回忆和当时的复盘记录整理了下面这张分布表方便你对照自己的薄弱环节知识模块常见考察形式大致难度数据结构数组、链表、栈、队列、树、图选择题、编程题中等经典算法KMP、排序、二分、贪心、动态规划选择题、编程题中高图论算法Dijkstra、最小生成树、二分图匹配选择题、场景题中等机器学习基础KNN、聚类、逻辑回归、特征工程选择题、问答中等深度学习基础CNN、RNN、损失函数选择题、问答中等偏易运筹优化与启发式算法模拟退火、粒子群、贪心问答、场景设计中高业务场景建模ETA预估、路径规划、运力调度问答与场景设计高从这张表能看出来它不是一个“纯计算机科班”的笔试更像是一个“计算机算法 机器学习 业务建模”的综合测试。这也意味着如果你只刷题不补充机器学习基础或者只学机器学习不练手撕代码都可能在某一部分栽跟头。2. 经典数据结构与算法题解析2.1 KMP算法与next数组的手推套路KMP那题我记得很清楚因为它在选择题里直接给了模式串 pabacaba要求判断next数组。这种题看起来很基础但现场手推的时候特别容易栽在next数组的定义上因为不同教材对next数组有两种主流定义一种是最长相等前后缀长度前缀函数另一种是失配时的跳转位置通常整体减一或从-1开始。我当时用的技巧是先明确题目给的“next[i]定义为前i个字符组成子串的最长相等前后缀长度”然后老老实实地逐项手推。以 abacaba 为例next[0] 约定为 0i1 时子串为 a没有真前后缀next[1]0i2 时子串为 ab0i3 时子串为 aba最长相等前后缀是 a长度 1next[3]1i4 时子串为 abac0i5 时子串为 abaca最长相等前后缀还是 anext[5]1i6 时子串为 abacab最长相等前后缀是 ab长度为 2next[6]2i7 时子串为 abacaba最长相等前后缀是 aba长度为 3next[7]3。所以最终结果是 0, 0, 0, 1, 0, 1, 2, 3。这里我踩过一个坑推到 i7 的时候容易因为前缀 aba 和后缀 aba 匹配就直接写3但没注意 i6 的时候 next[6]2 这个中间步骤是不是也正确导致前一个位置的next值写错。我的建议是宁可多花半分钟从头到尾把每个子串都老老实实写出来也不要跳步。注意KMP在很多笔试里还会继续追问“失配后模式串移动几位”这取决于next数组采用哪种定义。如果next[i]是最长相等前后缀长度那么失配位置 j 处应移动 j - next[j] 位如果是从-1起的失配跳转版本直接跳转到 next[j] 即可。审题时先下意识确认定义能省很多时间。2.2 排序算法从冒泡到堆排笔试到底考什么排序在选择题里出现了好几道而且问得挺细不是简单问“快排时间复杂度”那种送分题。比如有一道题给了个近乎有序的数组问哪种排序算法最快这种情况下插入排序只要O(n)级别比快排的O(n log n)更优但很多同学闭着眼睛选了快排这就是没有理解排序算法在不同数据分布下的表现差异。点我达这套题特别喜欢把排序算法和实际业务类比比如用“骑手按距离排序后派单”、“订单按创建时间稳定排序”来考察稳定性。这里我需要提醒一个要点稳定性的本质是相等元素的相对顺序是否保持不变。冒泡、插入、归并是稳定的快排、堆排、选择排序是不稳定的。堆排序的不稳定性来自建堆和堆顶交换的过程中相同元素可能被打乱这在使用二元组排序时是致命的。堆排序在编程题里也出现过如果题目要求“从不限长度的订单流中实时维护Top K”手写一个小顶堆是最稳的方案。我之前整理过一个模板核心思路是维护一个大小为K的堆新元素比堆顶大就替换并调整堆。这里特别容易犯的错是调整堆的时候只下沉不上升导致某些情况下堆的性质被破坏。正确的调整流程是从堆顶开始和左右子节点中较大的那个大顶堆或较小的那个小顶堆比较如果破坏堆序就交换并继续下沉。2.3 动态规划和贪心配送场景里最常用的两类思维点我达的编程题里有一道典型的动态规划题题目描述我记不太清了但本质上是一个带约束的最优化问题有点像“在限定时间内取多个订单求最大收益”的变体。这种题的核心是定义好状态我当时用的是“dp[i][j]表示前i个订单在时间j内能获得的最大收益”然后按经典背包的思路做状态转移。动态规划的难点从来不是转移方程本身而是状态定义和边界条件。这里我分享一个笔试时提效的方法不要一上来就写代码先在草稿纸上把状态定义、转移方程、初始化和最终答案写清楚大概一分钟就能完成但能避免写一半发现状态不对、推倒重来的尴尬。贪心算法在选择题和问答题里都出现了。让我印象很深的一道题是“如何给骑手分配一批订单使得总配送距离最短”这就是一个变体的贪心/指派问题。我当时选了“每次将距离最近的骑手分配给最近的订单”这种说法但事后复盘发现这其实是一个贪心策略在某种数据分布下并不是全局最优解。如果题目要求“最优解”应该用KM算法或最小费用最大流这类精确算法如果只要求“可行解且效率高”贪心才是一个合适的兜底方案。实操心得笔试遇到“求最优”和“求较优”要仔细区分。描述方案时一定要交代清楚你用的是精确算法还是启发式算法以及为什么在那种业务体量下可以接受。很多同学丢分不是因为不懂算法而是没有说清楚算法选择的边界条件。3. 机器学习与深度学习考点拆解3.1 KNN、聚类与逻辑回归基础模型背后的备考要点KNN在点我达这套题里出现得很自然毕竟“用户分类”、“骑手偏好识别”这类场景KNN是最容易想到的baseline之一。选择题考察了K值的选取对偏差方差的影响K太小容易过拟合K太大决策边界过于平滑、容易欠拟合。还有一个高频考点是距离度量不同特征量纲对欧氏距离影响极大所以要不要做标准化、用什么距离函数本身就是一道送分但容易失分的选择题。聚类算法也考了而且不是简单问K-Means流程而是问“如何确定聚类的类别数K”。这题我拿到时愣了一下因为教材里通常只讲K-Means怎么做很少展开讲K怎么选。我当时写了“轮廓系数”和“肘部法则”两个方法后来复盘觉得如果还能补充“Gap Statistic”会更有竞争力。另外要注意K-Means对初始中心点非常敏感笔试题目里如果提到“多次运行取最优”通常就是为了缓解局部最优问题。逻辑回归在问答题里有一个挺好的切入点“在ETA预估场景中如果只用逻辑回归你能怎么用”这里考的不是你会不会调库而是你理不理解模型本质。逻辑回归输出的是概率但它其实是一个线性分类器在特征交叉和业务先验信息引入上有很大局限。正确答法是先把它当baseline再做特征工程距离、天气、历史时长分位数再考虑用GBDT或深度学习模型来承接非线性关系。3.2 启发式算法粒子群和模拟退火在调度中的应用这part比较有意思点我达的笔试里出现了启发式优化算法的题目。当时是问答题描述了一个场景骑手数量很多订单动态到达要求实时给出比较好的配送路线问如何设计算法。我一开始想的是贪心或者动态规划但这是NP-hard的车辆路径问题VRP精确算法在大规模场景下根本算不动于是自然会想到启发式算法。粒子群算法PSO的原理是模拟鸟群觅食每个候选解是一个“粒子”它有自己的位置和速度通过个体历史最优和群体历史最优来更新速度与位置最终收敛到较优解。它的优势在于实现简单、参数少适合连续优化问题。模拟退火则是以一定概率接受更差的解从而跳出局部最优这在组合优化问题里特别常用。我当时答题时画了一个简化的思路先用贪心生成一条初始路径再用模拟退火对路径做“2-opt”邻域搜索即以一定概率接受更长的路径来避免陷入局部最优。注意在笔试里答启发式算法最忌讳只写“用PSO求解”这一句话。阅卷人想看的是你如何将真实问题编码成优化问题。你需要交代清楚决策变量是什么路径顺序、目标函数是什么总距离或总时间、约束是什么骑手容量、时间窗、用什么算法搜索、终止条件是什么。把这五件事说清楚比堆砌一堆算法名词有用得多。3.3 KL散度、ELBO与变分推断理论推导题的必要准备不得不说这套卷子里出现KL散度和ELBO相关的理论题时我是有点意外的。这说明点我达的算法团队对候选人的理论功底是有要求的不是只招“调参侠”。这道题更多是推导和理解比如给定一个简单的概率模型推导变分下界ELBO的形式并说明最大化ELBO与最小化KL散度之间的关系。复习这个知识点时我的经验是不要死记公式而是理解它的直觉我们想近似一个难解的后验分布于是找一个简单的分布q去逼近它。直接最小化q和真实后验的KL散度需要知道真实后验这很困难但可以证明ELBO等于对数似然减去KL散度最大化ELBO等价于让q逼近后验。考试时要特别注意符号的规范表达比如 q(z)、p(z|x)、E_{q}[\log p(x|z)] 每一项是怎么来的推导时漏掉一个期望符号整道题可能就崩了。这些问题也提醒了一个备考方向不要只看算法实现概率论和数理统计的基础同样重要。尤其是极大似然估计、贝叶斯公式、期望与方差、常见分布这些内容几乎是所有机器学习推导题的地基。4. 业务场景题与算法建模思路4.1 骑手路径规划问题从TSP到VRP的建模演进场景题是点我达笔试的重头戏。有一道题是“一个骑手手上有一批订单需要配送如何规划路线使总路程最短”。这个问题本质上是旅行商问题TSP但实际业务中很难直接套TSP因为有时间窗、骑手容量、订单时效这些约束。我在答题时先做了一个简化假设骑手一次只能从一个取货点取一个订单并送到一个收货点那么问题可以建模为一个带约束的路径规划问题精确解法可以用分支定界或动态规划但订单量大时只能用启发式方法。然后我补充说实际场景中更常见的是多骑手协作的车辆路径问题VRP可以用“先聚类再规划”的思路先把位置相近的订单分给同一个骑手再对每个骑手的订单做路径优化。这种“分而治之”的思路在笔试中很讨巧既展示了建模能力又体现了对大规模问题的理解。另外可以提一下Dijkstra算法在基础路径规划中的作用当骑手需要在两个点之间选择最短路径时路网可以被建模成带权图Dijkstra是最经典的单源最短路算法。不过要注意Dijkstra不能处理负权边如果路网中出现负权比如某种“惩罚系数”被建模成负权需要换成Bellman-Ford。这个细节很多人会忽略。4.2 ETA预估与订单定价回归问题怎么答才加分ETA预计送达时间预估在即时配送里属于核心算法之一笔试也很喜欢考。这个问题的本质是回归问题输入是订单信息、骑手位置、天气、路况、历史数据输出是配送时长。面试官其实不是想你手写一个XGBoost而是想看你有没有完整的建模思路。我的答题结构是先说明问题类型是回归问题评估指标可以用MAE、MAPE这类业务可解释的指标然后说特征工程包括距离特征、时段特征、天气特征、骑手历史速度分位数等再是模型选型从线性回归到GBDT再到深度学习逐步升级最后说线上部署时要注意特征的实时性和模型的更新频率。如果能把MAE和MAPE的优劣对比讲清楚通常能拿不错的印象分。订单定价和ETA其实是联动的问题配送费定高了用户不买单定低了骑手不接单。这类问题在笔试中经常出现的形式是“如何设计一个动态定价策略”这就可以引入供需平衡、价格弹性、强化学习等概念。我当时提到可以用一个简化的强化学习框架状态是当前供需差、天气、时段等动作是调价系数奖励是成交率或平台收益。用DQN模拟策略时要注意动作空间和奖励函数的设计否则模型很难收敛。4.3 运力供需平衡强化学习与PID思路的交叉热词里出现了PID算法但点我达这种互联网公司很少直接考PID控制器。不过在运力调度、价格调整这类场景里PID的思路是可以迁移的根据供需误差按比例、积分、微分来调整投入的运力或者补贴力度。比如当订单量突然暴增骑手供给不足可以用“比例项”来快速提升补贴单价用“积分项”来消除长期的供需缺口用“微分项”来抑制补贴的过度波动。我在回答这类场景题时通常会先画一条思路线问题定义 → 数据与特征 → 建模方案 → 评估方法 → 上线与迭代。这条线不会因为具体业务不同而变化是一种很通用的答题框架。比如运力供需平衡问题核心评估指标可以是“平均接单时长”或“无骑手接单率”模型的目标是让这个指标在控制成本的前提下尽量低。强化学习在运力调度中的应用也值得准备特别是如何用马尔可夫决策过程MDP来建模调度过程。你需要说清楚状态空间、动作空间、奖励函数、转移概率这四要素并且能解释在线学习时面临的数据探索与利用困境。我当时写了一个简单回答用上下文bandit替代完整强化学习在冷启动阶段先以探索为主积累一定数据后再切换为利用为主这个方案在笔试场景里显得务实且可行。5. 常见失分点与备赛建议5.1 手撕代码的三个常见坑编程题是算法笔试的重头戏很多时候不是你不会解而是“小坑不断”导致整体分数被拉低。第一个坑是边界条件处理循环结束条件、数组越界、空输入、单元素输入这些都要在写完代码后快速跑一遍心里测试用例。第二个坑是时间复杂度和空间复杂度的分析没有写清楚有些题目会要求你说明算法的复杂度不写等于白做。第三个坑是编码习惯问题比如变量命名随意、方法出口不统一、缺少注释这在阅卷人眼里非常减分。实操心得尽量提前准备一个“手写代码模板库”包括二分查找、快排、堆排、并查集、Dijkstra、KMP、动态规划背包模板等。笔试时先快速匹配模板再针对题目修改细节比自己从头写要稳得多。5.2 理论推导题的答题规范遇到KL散度、贝叶斯推导这类题目时答题格式是很重要的。我自己的习惯是第一步明确符号定义比如 q(z) 是变分分布、p(z|x) 是后验第二步写出核心公式比如 ELBO E_q[log p(x,z) - log q(z)]第三步逐步推导每一步都附上一句说明第四步验证边界条件比如当 q(z) 等于后验时KL为0ELBO达到最大。这样即使最终结果有小错阅卷人也能看出你的思路是清晰的。5.3 校招算法笔试的复习路线建议结合这套题的特点我给准备校招算法岗的同学一个复习优先级建议数据结构与经典算法永远是第一位KMP、排序、二分、动态规划、贪心、图论这几类必须滚瓜烂熟其次是机器学习基础KNN、逻辑回归、聚类、SVM、决策树、GBDT的原理和适用场景要能说清楚最后是深度学习基础CNN、RNN、损失函数、正则化方法等能做到有逻辑地讲述即可。业务场景题是最难临时抱佛脚的建议多看看即时配送、出行、电商推荐这些行业的算法案例思考每个问题背后的数学模型和求解框架。多练习“从业务问题到算法方案”的表述这类能力在笔试和面试中都非常吃香。最后再分享一个我自己的体会刷题不是目的理解算法背后的“为什么”才是关键。点我达这套笔试给我最大的启发是算法工程师不只是程序员更是一个能用算法解决真实业务问题的人。你掌握了多少算法公式不重要重要的是当一个问题摆在面前时你能不能快速判断出它属于哪类问题、用哪类算法、怎么建模、怎么评估。这套思维方式远比多刷一百道题更有价值。