2020年秋招投58同城的算法岗收到笔试链接那天我还挺期待。毕竟58的线下业务盘子和用户体量摆在那算法岗的题应该不会太“学院派”。等真正打开试卷我的判断基本上对了一半基础题占大头但真有几道题是贴着业务场景出的尤其有一道KMP的next数组手算题直接让我在考场里多待了十分钟。这篇文章就把这套题完整复盘一遍顺带把笔试前前后后踩过的坑都交代清楚。如果你正准备校招算法岗或者想检验一下自己的数据结构与算法底子这篇文章应该能帮你省下不少瞎摸索的时间。我会从试卷画像、高频考点、真题解法、做题策略到复盘教训一层层拆开讲所有代码和推导都能直接照着推演。1. 这套笔试题的画像考点分布与难度评估1.1 试卷构成与考场体感58同城2020校招算法笔试整体时长90分钟题量不算小。我印象里是“单选多选填空两道编程题”的组合其中选择题覆盖了数据结构、计算机网络、操作系统、概率论这些计算机基础编程题则集中在算法与数据结构。算法部分的单选和多选不会太绕但有一个特点喜欢考概念辨析和边界条件。比如排序算法的稳定性、快排在最坏情况下的复杂度、KMP中next数组的具体取值这些在平时刷LeetCode时不太容易遇到因为刷题更多是让你直接写完整代码而笔试题更偏向“对细节的精确记忆”。编程题则相对务实一道是链表排序一道是带业务背景的动态规划。难度算不上顶尖但题面会裹上一层“信息平台”的外壳比如“用户浏览记录按时间排序”“预算有限的情况下给不同类目分配流量”这类描述。你要是能一眼看穿包装底层考的还是经典模型做题速度就会快很多。1.2 高频考点清单速查结合我备考时的梳理和这次实际考到的内容58同城这套卷子的算法考点可以整理成下面这张表考点模块具体考点常见出题方式重要程度数据结构基础链表、栈、队列、哈希表选择题辨析、手写链表操作高字符串算法KMP、滑动窗口、哈希匹配next数组手算、判断子串高排序算法快排、归并、堆排、稳定性复杂度选择、链表排序编程高动态规划背包、路径、区间DP业务背景包装的编程题高贪心算法区间调度、任务分配选择题判断、编程题中高树与图二叉树遍历、拓扑排序、二分图选择题、填空中海量数据TopK、去重、外部排序简答或选择中数学与位运算快速幂、位操作填空、选择低这个分布其实很典型。信息平台类公司的算法笔试不会像AI Lab那样死磕论文复现也不会像游戏公司那样疯狂考计算几何重点永远在“通过算法高效地处理海量信息和交易撮合”。所以排序、TopK、字符串匹配、资源分配这几类题几乎是必考的。1.3 为什么重点考这些而不是那些备考的时候我也纠结过要不要刷机器学习、深度学习、图像算法这些方向毕竟热搜词里也能看到一堆相关内容。但后来我总结出一个规律纯算法岗的校招笔试除非岗位描述里明确写了“NLP方向”“CV方向”否则机器学习深度学习只会以选择题形式出现比如“以下哪个是过拟合的解决方法”“损失函数的作用”很少让你手推反向传播。58这套卷子也是这样机器学习相关内容出现得很浅更多是概念层面的考察。真正花时间的地方还是数据结构与算法。原因也简单校招笔试是海量筛选面试官需要通过一套标准化的题目快速判断候选人的基本功。基本功不扎实的人就算会调参、会跑模型也很难在业务里把一个排序或匹配模块写好。所以把排序、查找、字符串、动态规划这些硬功夫练扎实是性价比最高的备考路线。2. 字符串与匹配题复盘KMP的next数组是重灾区2.1 真题模式串abacaba的next数组手算全过程这套卷子里有一道填空题几乎是照着经典教材出的给定模式串 pabacaba求它的next数组并且明确next[i]定义为前i个字符组成的子串的最长相等真前后缀长度。也就是大家常说的前缀函数。这题看着简单但真要在考场手算不下点功夫是容易出错的。我用手算的方式一步一步过一遍。字符串下标从0开始i0子串为a最长相等真前后缀长度为0所以next[0]0。i1子串为ab前缀集合为{a}后缀集合为{b}没有相等next[1]0。i2子串为aba前缀集合为{a,ab}后缀集合为{ba,a}最长的公共前后缀是a长度为1next[2]1。i3子串为abac前缀集合为{a,ab,aba}后缀集合为{bac,ac,c}没有公共前后缀next[3]0。i4子串为abaca前缀有{a,ab,aba,abac}后缀有{baca,aca,ca,a}公共的只有anext[4]1。i5子串为abacab前缀有{a,ab,aba,abac,abaca}后缀有{bacab,acab,cab,ab,b}公共前后缀是ab长度为2next[5]2。i6子串为abacaba前缀有{a,ab,aba,abac,abaca,abacab}后缀有{bacaba,acaba,caba,aba,ba,a}公共的最长前后缀是aba长度为3next[6]3。所以最终next数组为 [0, 0, 1, 0, 1, 2, 3]。如果写成代码就是经典的前缀函数求解def prefix_function(p): n len(p) pi [0] * n for i in range(1, n): j pi[i - 1] while j 0 and p[i] ! p[j]: j pi[j - 1] if p[i] p[j]: j 1 pi[i] j return pi print(prefix_function(abacaba))输出结果[0, 0, 1, 0, 1, 2, 3]这段代码值得背下来。笔试或者面试手写KMP的时候很多人的问题不是不理解原理而是边界条件处理不好导致匹配阶段死循环或者跳错位置。用前缀函数作为基础后面再接匹配逻辑会清晰很多。2.2 为什么next数组总是算错常见的下标偏移坑我在备考群里见过不少人纠结next数组的定义有的教材说 next[0] -1有的说 next[0] 0。其实这是因为“next数组”有两种常见约定考试前一定要看清题目给的定义。第一种约定next[i] 表示“以p[i]结尾的子串的最长相等真前后缀长度”也就是前缀函数上面算了 [0,0,1,0,1,2,3]。第二种约定next[i] 表示“当p[i]匹配失败时模式串应该回退到的目标位置”这时通常令 next[0] -1并且对 i≥1next[i] 前缀函数值π[i-1]。按照这个约定abacaba的next数组就是 [-1, 0, 0, 1, 0, 1, 2]。这两种写法都能实现KMP匹配只是匹配时代码里判断回退的方式略有不同。第一种写法在失配时用 while j 0 and p[i] ! p[j]: j pi[j-1]第二种写法在失配时直接用 j next[j]。如果你习惯用LeetCode的模板大概率用的是第一种如果你本科教材是严蔚敏那本可能是第二种。考场上不要想当然先看题目里给的示例验证一下定义再往下做。这个坑我栽过一次。之前有一次模拟笔试题目写“next[i]定义为模式串中第i个字符前面的子串的最长相等前后缀长度”我按前缀函数算完结果选项里没有答案才发现题目要求是从0开始计数的下标版本。花了两分钟重新算完全打乱了做题节奏。2.3 字符串题的高频变体滑动窗口与哈希匹配KMP不是字符串题的唯一考点58这套卷子的选择题里还出现了一些滑动窗口和哈希匹配的题。最经典的一个是“给定一个字符串找出不含重复字符的最长子串长度”这道题在LeetCode上是第3题校招笔试出镜率极高。滑动窗口的思路是固定左边界右边界不断向右扩展同时用一个哈希表或数组记录字符最近一次出现的位置。一旦遇到重复字符就把左边界跳到重复字符上次出现位置的下一个再继续扩展。def length_of_longest_substring(s): last {} left 0 ans 0 for right, ch in enumerate(s): if ch in last and last[ch] left: left last[ch] 1 last[ch] right ans max(ans, right - left 1) return ans这里有两个容易错的地方一个是更新左边界时要判断重复字符上次出现的位置是否在窗口内也就是 last[ch] left 这个条件不能漏另一个是每次都要把当前字符的最新位置写进哈希表哪怕它重复出现过。漏掉任何一个条件结果都会偏大或偏小。字符串匹配这一类题说到底考察的是对“指针移动条件”的精确控制。校招笔试不会要求你用后缀数组或者自动机这种高级数据结构能熟练写出KMP、滑动窗口、两个哈希表的经典题就足够拿到大部分分数了。3. 排序与链表基础题里的失分点3.1 给链表排序为什么归并排序是最优解编程题第一道就是“对单链表进行排序要求时间复杂度O(n log n)空间复杂度O(1)”。看到这个要求第一反应应该是归并排序。因为链表不支持随机访问快排的partition操作会很别扭堆排序需要额外数组存索引插入排序是O(n^2)太慢。归并排序天然适合链表因为它只需要修改指针不需要搬动数据。实现上先通过快慢指针找到链表中点把链表拆成两半然后递归排序两半最后合并两个有序链表。这里有个细节快慢指针的初始位置快指针要从 head.next 开始否则链表长度为2时慢指针会停在后半段递归永远不会结束。def sort_list(head): if not head or not head.next: return head slow, fast head, head.next while fast and fast.next: slow slow.next fast fast.next.next mid slow.next slow.next None left sort_list(head) right sort_list(mid) return merge(left, right) def merge(l1, l2): dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next我写的时候栽过一次合并时忘记把 cur 指向下一个节点结果链表串成了一团乱麻。这种低级错误在本地IDE里很容易发现但在笔试的在线编辑器里没有断点、没有调试工具只能靠一遍遍读代码硬找。所以平时练习时一定要养成“写完代码用简单样例手跑一遍”的习惯。3.2 排序稳定性与原地排序的选择58这套笔试题的选择题部分考了不少排序概念的辨析比如“以下排序算法中哪些是稳定的”“哪些是原地排序”。这类题看似送分其实非常容易混淆。稳定排序冒泡、插入、归并、基数。不稳定排序快排、堆排、选择排序。原地排序冒泡、插入、选择、快排、堆排归并排序不是严格意义上的原地排序因为需要额外O(n)的空间虽然链表的归并排序可以做到O(1)额外空间但那是靠修改指针绕过的。还有一个高频考点快速排序在最坏情况下的时间复杂度是O(n^2)发生在每次partition都选到最大或最小元素的时候比如数组本来就有序且每次选第一个元素作为pivot。堆排序和归并排序最坏也是O(n log n)。这些结论得烂熟于心因为选择题选项里经常混着“快排平均O(n log n)最坏O(n log n)”这种错误描述。3.3 快排退化与堆排序TopK问题排序考得不只是“把数组排好”更常见的是“不完全排序”的问题最典型的就是TopK。58的业务场景里给热门职位排序、给搜索关键词排序本质都是在海量数据里找前K个。经典的解法是用大小为K的小顶堆遍历所有元素如果当前元素比堆顶大就弹出堆顶并插入当前元素。这样堆里始终保存着当前见过的最大K个元素堆顶就是第K大的元素。时间复杂度O(N log K)空间复杂度O(K)。import heapq def top_k(nums, k): heap [] for num in nums: if len(heap) k: heapq.heappush(heap, num) elif num heap[0]: heapq.heapreplace(heap, num) return heap注意这里用的是小顶堆堆顶是K个元素里最小的。如果题目问“第K大”堆顶就是答案如果问“前K大”把堆逐个弹出再反转就是结果。选错堆的类型是新手很容易犯的错。4. 贪心与动态规划生活场景建模题4.1 区间调度类贪心会议室预订问题编程题第二道裹着业务外壳题目大意是一批用户提交了看房预约每个预约有开始时间和结束时间同一个销售顾问同一时间只能接待一个用户问最多能安排多少个预约。这个模型就是经典的区间调度问题。解法很简单按结束时间从小到大排序然后贪心地选择第一个能选的区间更新当前结束时间遍历所有区间统计能选的区间数量。贪心选择性质是优先选结束时间最早的区间可以为后面的区间留下最多的余地从而保证得到全局最优解。这个直觉很符合生活常理但笔试里可能会问“为什么不能按开始时间排序”或者“为什么不能按区间长度排序”。反例也很好找按开始时间排序可能选到超长区间把后面多个短区间全挡住了按长度排序可能选到中间区间导致左右两边都放不下。def max_appointments(intervals): intervals.sort(keylambda x: x[1]) ans 0 end float(-inf) for start, finish in intervals: if start end: ans 1 end finish return ans这个题在LeetCode上是“无重叠区间”和“会议室”的变体笔试遇到了不要慌剥掉业务场景的壳核心还是排序加贪心。4.2 二维动态规划最小路径和另一道编程题我记得很清楚给了一个二维网格每个格子有非负权值从左上角走到右下角每次只能向右或向下走求路径上权值和的最小值。这就是LeetCode第64题最小路径和。状态转移方程很直接设dp[i][j]表示从左上角走到(i,j)的最小路径和那么 dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1])。边界条件是第一行只能从左边来第一列只能从上边来。def min_path_sum(grid): if not grid: return 0 m, n len(grid), len(grid[0]) dp [[0] * n for _ in range(m)] dp[0][0] grid[0][0] for j in range(1, n): dp[0][j] dp[0][j-1] grid[0][j] for i in range(1, m): dp[i][0] dp[i-1][0] grid[i][0] for i in range(1, m): for j in range(1, n): dp[i][j] grid[i][j] min(dp[i-1][j], dp[i][j-1]) return dp[m-1][n-1]很多参考书上会强调可以用滚动数组把空间压到O(n)笔试时如果题目不要求空间复杂度写二维dp更不容易出错。但如果题目故意在数据范围上卡你内存比如m和n都到10^5级别就必须用滚动数组或者降维写法。我建议平时两种写法都练熟考场上根据数据范围灵活选择。4.3 背包变体预算限制下的资源分配除了路径类DP背包类问题也在58的考察范围内。有一道选择题给出了类似0-1背包的场景预算有限要在多个候选方案里选出总价值最大的一组且每个方案最多选一次求最大价值。0-1背包的一维滚动数组写法更新顺序必须从后往前这是考点中的考点。如果从前往后更新同一个方案会被重复选取变成完全背包问题。我当时就是靠这个细节区分了两个概念。def knapsack_01(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]为什么必须倒序可以这样理解dp[j] 依赖的是上一轮计算出的 dp[j - weights[i]]如果正序更新j - weights[i] 在 j 之前已经被本轮更新过里面可能已经包含了当前方案等于一个方案用了无数次。这种细节题目直接靠背代码而不理解原理很容易掉坑。我在笔试前专门把所有经典DP的状态转移方程和更新顺序手推了一遍成效很明显。5. 树、图与海量数据最后几道压轴小题5.1 二叉树层序遍历与最近公共祖先选择题和填空题里出现了一些树相关的题。比较基础的是层序遍历也就是BFS要求按层级输出节点。这个题只要会用队列就能写对但有一个细节需要在每一层开始时记录当前队列的长度这样循环length次才能保证一次处理完整的一层而不是一层没处理完就混到下一层。from collections import deque def level_order(root): if not root: return [] res [] q deque([root]) while q: level [] size len(q) for _ in range(size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return res最近公共祖先也是一道常考题LeetCode第236题。递归思路是如果root为空或者等于p、q中的任意一个直接返回root然后递归搜索左子树和右子树如果两边都找到了说明当前节点就是LCA如果只有一边找到就返回那一边的结果。这道题考察的是对递归返回值的理解而不是什么高深的技巧。很多人在“左右都非空时返回当前节点”这一步想不通其实画个递归树就很好理解了。5.2 拓扑排序与二分图匹配58这套题里图论部分不算深但出现了一个让我记忆犹新的填空给一个有向无环图求拓扑排序序列。标准解法是Kahn算法维护一个入度为0的节点队列每次弹出队首把它指向的节点的入度减1再把新的入度为0的节点入队。from collections import deque def topological_sort(n, edges): indegree [0] * n graph [[] for _ in range(n)] for u, v in edges: graph[u].append(v) indegree[v] 1 q deque([i for i in range(n) if indegree[i] 0]) res [] while q: u q.popleft() res.append(u) for v in graph[u]: indegree[v] - 1 if indegree[v] 0: q.append(v) return res if len(res) n else []判断最后结果长度是否等于n这一步千万不能省否则遇到有环图的时候返回的结果是不完整的。考场上时间紧很容易在简单题上犯这种漏判断的毛病。二分图匹配在热搜词里出现了“hk算法”也就是Hopcroft-Karp算法用于求二分图最大匹配。58的笔试里没有直接考实现但有一道选择题问了“如何判断一个图是二分图”答案是用染色法BFS相邻节点不能染成同色。如果题目要求最大匹配匈牙利算法O(VE)是入门标配HK算法是进阶优化。校招笔试通常不会要求当场手写HK但面试聊天时能说清楚两种算法的复杂度差异会加不少印象分。5.3 海量数据的TopK与去重还有一道简答题大概意思是给出一百亿条用户搜索记录内存只有几百兆要求统计出现频率最高的Top100关键词怎么办。这个题不要求写完整代码但要求说清思路。最稳健的回复是“分治哈希小顶堆”三层结构先把大文件用哈希函数切片到多个小文件保证同一个关键词的所有记录落到同一个切片里然后对每个切片用哈希表统计频率再在每个切片内维护一个大小为100的小顶堆最后把所有堆合并再求一次全局Top100。如果切片后单个文件仍然太大就继续递归切片。还有一个思路是使用近似算法比如Count-Min Sketch或者Bloom Filter但笔试里提到“允许一定误差”才能用准确统计还是要走哈希分片。这个题能看出你有没有处理海量数据的经验而不只是会刷题。6. 笔试实战策略与复盘教训6.1 时间分配90分钟的做题节奏笔试总时长90分钟我的实际分配策略是选择题和填空题控制在35分钟以内编程题留55分钟。留出10分钟做最后的检查和整理。具体节奏可以参考下面这张表题目类型建议用时策略单选 多选20分钟不会的果断标记跳过不纠结填空/简答15分钟手算题在草稿纸上写清楚避免重复算编程题第一道25分钟先确认数据结构再写代码编程题第二道30分钟如果卡壳超过10分钟先写暴力解保底检查10分钟重点看数组越界、空指针、循环边界这个时间分配不是固定的但原则是不在一道题上死磕。选择题蒙一个还有25%的正确率编程题卡住不动等于直接丢分。先把能拿的分全部拿到再回头啃硬骨头。6.2 代码规范与边界处理在线笔试的代码编辑器往往没有自动补全也没有本地调试器所以代码规范非常重要。我复盘时发现自己丢分最多的地方反而不是算法想不出来而是“输出格式不对”和“边界条件漏判”。几个高频的边界场景链表题输入为空、只有一个节点、只有两个节点。数组题长度为0、长度为1、全是相同元素、已经有序。字符串题空串、单个字符、全重复字符、无重复字符。矩阵题只有一行、只有一列、只有一个格子。每次写完代码我都习惯性地用这几组边界数据在心里跑一遍能拦下至少一半的bug。还有一个实操技巧在线编程题很多支持“自测用例”哪怕系统只给了一个样例也要自己构造几个边界用例提交自测。这一步花不了两分钟但能救命。6.3 复盘发现的三个致命失误笔试结束后我做了详细复盘发现自己犯了三个比较典型的错误写出来给大家提个醒。第一个失误是KMP的next数组定义没开清。我当时看到“next[i]定义为最长相等真前后缀长度”心里想的是“哦这不是很简单”结果手算时默认从1开始计数导致数组整体右移了一位差点选错选项。后来我给自己立了个规矩凡是涉及数组下标的题目先拿题目给的例子验证一下自己的理解再开始算。这道题虽然没做错但浪费的时间比预想多很多。第二个失误是链表排序时快慢指针的死循环问题。第一次提交的代码快指针初始化设成了 slow, fast head, head结果链表长度为2时slow永远停在head递归拆分永远分不完运行时直接栈溢出。改成 fast head.next 之后才通过。这个坑在LeetCode上其实不会踩因为链表长度一般比较大只有在长度为2这种极小规模时才暴露问题。第三个失误是动态规划题只写了核心函数忘了处理多组输入输出。笔试编程题经常要求自行处理输入比如读多个用例直到EOF。我习惯性写了单组输入结果自测能过提交却报运行时错误。这个纯粹是经验不足平时用leetcode用惯了没有做ACM风格题目的意识。从那以后我每次笔试前都会特意练几道牛客网风格的输入输出题专门熟悉 while True: try: ... except EOFError: break 这种结构。这些失误都不是算法能力的问题而是实战经验的问题。多参加几次模拟笔试踩过几次坑后面自然就稳了。最后再分享一个心得笔试不只是用来筛人的更是一场高强度的自我体检。我在复盘时把每道题的解法、复杂度、变体都写进了一个表格然后对着表一项一项补短板。后来面试时面试官问起笔试里的KMP题我能把next数组的两种定义、失配跳转的具体过程、以及一道业务场景变体全部串起来讲清楚这比死记硬背面经有说服力得多。校招的每一场笔试都值得你认真对战认真复盘。