1. 笔试整体认知先搞清楚58同城算法笔试到底在考什么我当年参加58同城校招笔试的时候第一感受是这绝不是那种背背书就能蒙混过关的考试。58同城作为生活服务平台业务线覆盖招聘、房产、二手车、本地生活服务等对算法的考察非常注重基本功和工程落地能力。整张卷子给我留下的印象是“扎实”两个字题型分布大概可以分为三类基础选择题、算法编程题、少数岗位相关的简答题。先说选择题覆盖面非常广数据结构、操作系统、计算机网络、概率统计、机器学习基础都会涉及。很多同学只盯着算法题看忽略了前面的基础题结果栽了跟头。编程题一般是2到3道难度从简单到中等偏上递增时间控制在90到120分钟考察的核心是字符串处理、动态规划、贪心策略、图论基础这些高频考点。如果你准备过LeetCode或牛客网的企业真题会发现58同城的出题风格和互联网大厂的中等难度题比较接近不会刻意出偏题怪题但非常考验你能否在有限时间内写出无bug的代码。这篇文章我打算从试卷结构、高频考点、编程题实战、非算法考点、常见坑位、备考路线几个角度完整拆一遍把我在准备和参加这场笔试过程中的经验、踩过的坑、总结出来的技巧都写出来希望能给后面要参加同类笔试的同学一些实际参考。2. 高频考点拆解必考的数据结构与经典算法2.1 KMP算法next数组推导必须手到擒来字符串匹配是笔试的常客而KMP算法又是字符串匹配里的核心考点。很多同学能背出KMP的代码但一让手动推导next数组就卡壳这在笔试选择题里非常吃亏。KMP的核心思想是利用已经匹配的部分信息让模式串尽可能多地右移避免主串指针回溯。next数组的定义是对于模式串Pnext[i]表示P[0...i-1]这个子串中最长的相同真前缀和真后缀的长度。我用一个具体例子来演示比如模式串P abacaba。手动推导next数组时我习惯按以下步骤走next[0] -1这是约定俗成的初始值next[1] 0因为P[0...0]只有一个字符没有真前缀和真后缀计算next[2]时看P[0...1] ab最长相同真前后缀长度为0所以next[2] 0计算next[3]时看P[0...2] aba前缀a和后缀a相同长度为1所以next[3] 1计算next[4]时看P[0...3] abac没有相同前后缀next[4] 0计算next[5]时看P[0...4] abaca前缀a和后缀a相同长度为1所以next[5] 1计算next[6]时看P[0...5] abacab前缀ab和后缀ab相同长度为2所以next[6] 2计算next[7]时看P[0...6] abacaba最长相同前后缀是aba长度为3所以next[7] 3。如果你觉得手动推导容易乱我给你一个稳定的技巧用一个指针j记录当前最长相同前后缀的长度遍历模式串如果P[i] P[j]则j加1否则j回溯到next[j]。这个回溯的过程可以用递推的方式在O(n)时间内求出next数组。笔试里如果考KMP大概率会给你一个模式串让你求next数组或优化后的nextval数组这类题只要推导熟练基本是送分题。2.2 排序算法对比从冒泡到快排再到堆排序排序算法是数据结构的基础也是58同城这类公司笔试选择题的常客。我整理了一个高频对比表考前可以反复看几遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定这里特别提醒一下快速排序最坏情况发生在每次划分都极度不平衡时比如序列已经有序且每次选第一个元素作为基准时间复杂度会退化到O(n²)。优化手段有三板斧随机选取基准、三数取中、在小区间内切换到插入排序。堆排序在笔试中更多以“TopK问题”的形式出现比如从海量数据中找出最大的K个数用最小堆维护K个元素遍历完所有数据后堆里的元素就是答案时间复杂度O(n log K)空间复杂度O(K)。C选手要注意STL里的sort是内省排序数据量大的时候用快排递归层数过深时切换成堆排序所以基本不会退化到O(n²)。但如果你自己手写快排一定要处理退化的情况。我用C手写冒泡排序可以做如下验证void bubbleSort(vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; // 提前退出优化 } }我记得笔试选择题里有一道关于稳定性的题选项里混着“快速排序是稳定的”这种错误说法如果没有背熟这个表很容易被绕进去。2.3 贪心算法与动态规划如何快速判断用哪种策略贪心和动态规划是笔试编程题的灵魂几乎每场笔试都会有一道。两者的本质区别在于贪心算法每一步都做当前看起来最优的选择且不回溯动态规划则会把问题拆分成子问题保存子问题的解并利用最优子结构来构建全局最优解。判断标准很简单如果局部最优能推导出全局最优就用贪心如果子问题之间有重叠且需要比较多种决策才能确定最优就用动态规划。常见的贪心题目有活动安排区间调度、跳跃游戏、分发饼干、加油站等。常见动态规划题目有背包问题、最长递增子序列、最长公共子序列、编辑距离、打家劫舍。我见过58同城笔试的编程题里有一道类似“任务调度最大收益”的题其实就是经典的加权区间调度问题用动态规划加二分查找可以把时间复杂度压到O(n log n)。这里有一个我的经验编程题一旦涉及“最大/最小/最长/最短”这类关键词首先要想到DP和贪心再结合数据范围判断。如果n的范围是10的5次方级别大概率要用贪心或者带优化的DP如果n只有几百可以直接上O(n²)的二维DP。2.4 图论三件套Dijkstra、Kahn拓扑排序、二分图HK算法图论在58同城的笔试中出现频率不如字符串和DP高但一旦出现往往是区分度较大的题目。Dijkstra算法用于求解单源最短路径要求图中不能有负权边核心思路是贪心地选择当前距离源点最近的未访问节点松弛其邻居。如果是稠密图用O(V²)的朴素实现如果是稀疏图用优先队列优化的版本时间复杂度达到O(E log V)。Kahn算法是拓扑排序的经典实现思路非常直观统计每个节点的入度将入度为0的节点入队列不断弹出节点并减少其邻居的入度当某个邻居的入度变为0时也入队列整个过程类似BFS。拓扑排序可以用来检测有向图中是否存在环如果排序后访问的节点数小于总节点数说明图中存在环。这在笔试里经常以“课程表”类题目的形式出现比如给定课程之间的先修关系判断能否完成所有课程。二分图HK算法Hopcroft-Karp算法比朴素匈牙利算法更快适合大规模二分图最大匹配问题。虽然笔试里直接考HK的概率不高但一旦出现“匹配”“覆盖”类题目懂得用网络流或者HK算法的人就能在时间上碾压只会暴力枚举的选手。我记得有一道选择题考察“二分图最大匹配的应用场景”选项里有任务分配问题、相亲配对问题、棋盘覆盖问题等这类题考察的是建模能力知道二分图匹配能解决什么问题比背代码更重要。3. 编程题实战完整复盘三道高频题型3.1 滑动窗口解决最长不重复子串字符串题在笔试编程题里出现的概率极高。我复盘一道很经典的题给定一个字符串找出其中不含有重复字符的最长子串的长度。这道题看起来简单但很多人在边界条件上栽跟头。标准解法是滑动窗口加哈希表int lengthOfLongestSubstring(string s) { unordered_mapchar, int window; int left 0, ans 0; for (int right 0; right s.size(); right) { char c s[right]; window[c]; while (window[c] 1) { char d s[left]; window[d]--; left; } ans max(ans, right - left 1); } return ans; }这里有个细节要提醒大家while循环里收缩左边界时条件是window[c] 1意味着当前右指针指向的字符在窗口内出现了重复所以不断右移左指针直到该字符在窗口内只剩一个。这样保证窗口内永远没有重复字符。这道题还有优化空间用vector 记录每个字符最后出现的位置直接把left跳到max(left, last[c] 1)不需要while循环。笔试时优先写后者因为代码更少、不容易出错。很多同学写这道题会忘记处理空字符串或者忘记更新ans建议在脑子里面把边界用例都过一遍再提交。3.2 动态规划解决0-1背包变体0-1背包是动态规划的入门经典也是笔试中很多难题的“底子”。我把一道常见的变体题分享出来给定n个物品的重量和价值背包容量为W每个物品只能选一次求能装入背包的最大价值。二维DP的状态定义是dp[i][j]表示前i个物品中容量为j的背包能装下的最大价值。状态转移方程是不选第i个物品dp[i][j] dp[i-1][j]选第i个物品前提是j weight[i]dp[i][j] max(dp[i-1][j], dp[i-1][j - weight[i]] value[i])空间优化是最常考的延伸点将二维数组压缩成一维但内层循环必须从大到小遍历int knapsack(int W, vectorint wt, vectorint val) { int n wt.size(); vectorint dp(W 1, 0); for (int i 0; i n; i) { for (int w W; w wt[i]; --w) { dp[w] max(dp[w], dp[w - wt[i]] val[i]); } } return dp[W]; }这里有一个很容易踩的坑如果内层循环从小到大遍历dp[w - wt[i]]可能在当前物品还没有放入时就已经被更新过导致同一件物品被放入多次这就变成了完全背包问题。笔试面试时面试官经常会追问“为什么一维DP要倒序遍历”这个问题要能一口气解释清楚。扩展的二维费用背包、分组背包其实都是在0-1背包的状态定义上加维度核心思路完全一样。3.3 贪心策略解决区间调度问题区间调度类问题是贪心算法最经典的出题方向。我拿“给定n个区间选择尽可能多的不重叠区间”举例。这道题的关键在于按结束时间排序然后贪心地选择结束时间最早且不与已选区间重叠的下一个区间。证明的思路是对于最早结束的区间一定存在一个最优解包含它所以贪心策略正确。int intervalSchedule(vectorvectorint intervals) { if (intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) { return a[1] b[1]; }); int count 1; int end intervals[0][1]; for (int i 1; i intervals.size(); i) { if (intervals[i][0] end) { count; end intervals[i][1]; } } return count; }这道题看似简单但有几个变体会增加难度区间变成带权重的加权区间调度就需要用动态规划而非贪心区间变成开会时间安排还要考虑一天的开始和结束时间区间变成长度不一的线段要覆盖目标区间且选择的线段数量最少就要用贪心的另一种策略——按起点排序每次选择能覆盖当前起点且右端点最远的线段。我在做这类题时的一个习惯是先把区间的排序规则写清楚再套用模板。大多数情况下按右端点排序对应的是“选择最多不重叠区间”按左端点排序对应的是“用最少区间覆盖目标区间”这两个方向不要搞混。4. 笔试中的非算法考点机器学习与工业级算法延伸4.1 机器学习基础XGBoost、KNN、聚类的常见问法58同城算法岗的笔试会考一部分机器学习基础知识毕竟招的是算法工程师而不是纯编码工程师。选择题里常考的有KNN算法的三个核心能力——分类、回归、异常检测K-Means聚类的初始中心选择对最终结果的影响XGBoost相对于GBDT的改进点。XGBoost在目标函数中加入了正则化项叶子节点数加叶子节点权重的L2范数支持二阶导数信息还做了列采样这些都是高频考点。我建议大家把常见的机器学习算法按照“模型定义、损失函数、优化方法、优缺点、适用场景”五个维度整理成自己的笔记。比如KNN模型定义是“基于实例的学习”损失函数可以理解为错误分类率优化方法就是K值选择和距离度量优点是简单、无需训练缺点是预测时间复杂度高、对高维数据不友好。4.2 工程优化算法粒子群、模拟退火、PID、卡尔曼滤波的应用场景有些同学看到粒子群算法PSO、模拟退火算法SA、PID算法、卡尔曼滤波这些名词就发怵担心笔试会考深度的推导。从我参加过的情况来看这类算法在笔试选择题或简答题中更多考察“是什么”和“用在哪儿”不会要求你现场推导完整的数学公式。粒子群算法和模拟退火算法都属于启发式优化算法用于在搜索空间巨大且目标函数不光滑、不可导的场景下寻找近似最优解。比如你需要给一个推荐系统的排序模型调一组超参数如果用网格搜索假设有10个参数每个参数有100个候选值组合数就是100的10次方根本不可能遍历完。这时候用粒子群或模拟退火能在有限时间内找到不错的解。在58同城的业务里这种优化思想可以应用于广告出价策略、流量分配等场景。PID算法起源于自动控制领域核心思想是根据误差的比例P、积分I、微分D来调整输出使系统逼近目标值。在互联网场景中PID算法可以用于在线流量调控比如系统希望把某个接口的调用量稳定在每秒1万次但线上流量波动很大就可以用PID算法动态调整限流阈值。这类知识如果出现在卷子里大概率是给你一段描述让你判断用了什么算法或者问你PID三个环节各自的作用。卡尔曼滤波是一种状态估计算法它结合系统的动态模型和传感器的观测数据迭代地估计系统状态。在58同城的业务里类似于车辆定位轨迹平滑、用户行为预测等场景都有应用。笔试选择题喜欢考“卡尔曼滤波的两个核心步骤是什么”答案是预测和更新。4.3 规则引擎与RETE算法、图像算法扩展点如果投的是风控、搜索或者图像相关方向笔试可能会加入少量领域知识题。规则引擎Drools的核心是RETE算法它的思想是构建一个模式匹配网络当事实对象发生变化时只更新受影响的节点避免对全部规则做全量匹配从而大幅提升规则匹配的效率。笔试如果问到RETE更多是考察“为什么规则引擎比暴力匹配快”抓住“共享子条件”和“增量匹配”这两个关键词就不难回答。图像方向的题目会涉及边缘检测Sobel算子通过计算图像在水平和垂直方向的梯度幅值来检测边缘而拉普拉斯算子属于二阶微分算子对噪声比较敏感但可以用于图像锐化。如果笔试中出现了这类题说明该岗位对图像处理有额外要求。我建议非图像方向的同学也不要完全放弃这部分至少要能说出Sobel算子和拉普拉斯算子的区别。5. 常见问题与排查技巧实录笔试现场最实用的避坑指南5.1 数组越界与指针问题笔试编程题最让人崩溃的bug就是数组越界尤其是C/C环境下越界不一定会报错而是会静默地破坏内存导致结果诡异莫测。我自己的排查顺序是先检查for循环的终止条件再确认索引是否从0开始最后检查二维数组的行列是否写反。一个典型的错误是二分查找里写mid (left right) / 2当left和right都很大时可能溢出。正确的写法是mid left (right - left) / 2。这个细节在笔试中看起来不起眼但很多大数场景下会导致死循环。我建议所有涉及加法后除以2的地方都改成这个安全写法形成条件反射。5.2 递归爆栈问题当递归深度超过系统栈的容量时程序会直接崩溃。笔试中如果遇到DFS或递归实现的分治问题数据范围又特别大就要考虑把递归改成迭代。我遇到过一道题要求计算二叉树的深度用递归写法很简洁但当二叉树退化成链表时深度可能达到10的5次方这时候递归会爆栈改成非递归的层序遍历或栈模拟就很稳。另一个常见场景是快速排序、归并排序在大规模输入下的递归深度。归并排序的递归深度是O(log n)一般没问题快排最坏情况是O(n)如果数据是精心构造的有序序列递归深度可能过大。这是我强烈建议使用STL的sort而不自己手写快排的原因之一除非题目明确要求手写。5.3 时间复杂度超限怎么办笔试判题系统对运行时间有严格限制如果时间复杂度明显超出范围再好的思路也是白搭。我给出的优化顺序是第一步分析数据规模估算暴力解法的时间复杂度第二步确定核心瓶颈是循环嵌套还是重复计算第三步选择经典的优化策略。具体来说O(n²)的解法在n10的5次方时肯定是超时的需要想到排序、二分、双指针、哈希表或前缀和如果DFS的状态空间太大要考虑剪枝或状态压缩DP。我记得有一道笔试编程题第一版用暴力大循环只通过了30%的用例后来加上前缀和优化直接把时间复杂度从O(n²)降到O(n)全部用例通过。5.4 边界条件和特殊输入空数组、全重复、单元素一个稳健的程序必须处理所有合法的输入。我给自己定了一个检查清单数组是否为空、数组长度是否为1、是否所有元素都相同、是否已经有序、是否有负数、是否有0、输入值是否在题目给定范围内。很多同学能写出正确的大体逻辑却在边界用例上丢掉测试点非常可惜。笔试结束后复盘时我发现自己丢分的地方往往不是中间的大规模用例而是开头或结尾的几个边界用例。5.5 输入输出格式问题笔试环境对输入输出格式非常严格多一个空格或少一个换行都可能导致wrong answer。使用C时我习惯用cin和cout但需要关闭同步ios::sync_with_stdio(false)否则大量输入时速度会慢得离谱。使用Python时用sys.stdin.readline而不是input来做大量读取性能差距明显。如果题目要求保留两位小数直接用printf(%.2f)或fixed setprecision(2)不要手动截断。6. 备考路线与实战心法6.1 多长时间准备比较合适我根据自己的经历给一个参考时间线如果还有3个月前1个月主攻数据结构和基础算法中间1个月刷LeetCode热门题型和企业真题最后1个月做整套模拟卷严格卡时间。如果只有1个月就压缩第一段直接进入刷题阶段优先刷字符串、DP、贪心、栈和队列、二叉树这五个板块因为它们是笔试出题频率最高的板块。6.2 刷题的正确姿势重质量而非数量很多人陷入一种误区一天刷20道简单题感觉很充实其实大多在重复已经掌握的知识点。我更推荐用“分类突破”的方式做题每个算法专题集中刷10到15道题要求自己能独立推导状态转移方程、能讲清楚贪心策略的正确性证明而不是看到题就想不起来解法。每道题刷完后隔两天重新做一遍巩固度比一次性刷很多题好得多。6.3 笔试前的最后一个晚上做什么笔试前最后一个晚上不适合刷新题更建议把错题本翻一遍、背熟KMP的next数组推导流程、熟记排序算法对比表、把常见DP模板默写一遍。同时准备一份自己的代码模板包括二分查找模板、双指针模板、滑动窗口模板、二叉树遍历模板、并查集模板、Trie树模板。考试的时候直接套模板能省出大量时间这个技巧我一直在用实测非常稳。6.4 除了笔试算法能力在面试中的延伸通过笔试之后面试环节还会考察算法但形式变成了“白板编程”加上思路讲解。面试官更看重的是沟通能力、边界考虑、优化意识比如你写完代码后要主动说“这段代码在遇到极端输入时会怎样我可以怎么优化”。如果一个函数有多个参数要不要做参数校验如果数据规模扩大十倍当前的方案还能不能扛住。这些能力在笔试阶段就需要养成不要等到面试才临时抱佛脚。算法岗的笔试是一道门槛但本质上考察的是扎实的编程基本功和严谨的思维习惯。我踩过很多坑比如考前只刷算法题不复习基础数据结构、写代码不处理边界条件、坚持用手写快排而不使用STL。希望这篇文章能帮你少走一些弯路把时间花在刀刃上。