企业官网建设流程全解析

2020年秋招投58同城的算法岗，收到笔试链接那天我还挺期待。毕竟58的线下业务盘子和用户体量摆在那，算法岗的题应该不会太“学院派”。等真正打开试卷，我的判断基本上对了一半：基础题占大头，但真有几道题是贴着业务场景出的，尤其有一道KMP的next数组手算题，直接让我在考场里多待了十分钟。这篇文章就把这套题完整复盘一遍，顺带把笔试前前后后踩过的坑都交代清楚。

如果你正准备校招算法岗，或者想检验一下自己的数据结构与算法底子，这篇文章应该能帮你省下不少瞎摸索的时间。我会从试卷画像、高频考点、真题解法、做题策略到复盘教训一层层拆开讲，所有代码和推导都能直接照着推演。

1. 这套笔试题的画像：考点分布与难度评估

1.1 试卷构成与考场体感

58同城2020校招算法笔试，整体时长90分钟，题量不算小。我印象里是“单选+多选+填空+两道编程题”的组合，其中选择题覆盖了数据结构、计算机网络、操作系统、概率论这些计算机基础，编程题则集中在算法与数据结构。算法部分的单选和多选不会太绕，但有一个特点：喜欢考概念辨析和边界条件。比如排序算法的稳定性、快排在最坏情况下的复杂度、KMP中next数组的具体取值，这些在平时刷LeetCode时不太容易遇到，因为刷题更多是让你直接写完整代码，而笔试题更偏向“对细节的精确记忆”。

编程题则相对务实，一道是链表排序，一道是带业务背景的动态规划。难度算不上顶尖，但题面会裹上一层“信息平台”的外壳，比如“用户浏览记录按时间排序”“预算有限的情况下给不同类目分配流量”这类描述。你要是能一眼看穿包装，底层考的还是经典模型，做题速度就会快很多。

1.2 高频考点清单速查

结合我备考时的梳理和这次实际考到的内容，58同城这套卷子的算法考点可以整理成下面这张表：

这个分布其实很典型。信息平台类公司的算法笔试，不会像AI Lab那样死磕论文复现，也不会像游戏公司那样疯狂考计算几何，重点永远在“通过算法高效地处理海量信息和交易撮合”。所以排序、TopK、字符串匹配、资源分配这几类题几乎是必考的。

1.3 为什么重点考这些而不是那些

备考的时候我也纠结过要不要刷机器学习、深度学习、图像算法这些方向，毕竟热搜词里也能看到一堆相关内容。但后来我总结出一个规律：纯算法岗的校招笔试，除非岗位描述里明确写了“NLP方向”“CV方向”，否则机器学习深度学习只会以选择题形式出现，比如“以下哪个是过拟合的解决方法”“损失函数的作用”，很少让你手推反向传播。58这套卷子也是这样，机器学习相关内容出现得很浅，更多是概念层面的考察。

真正花时间的地方还是数据结构与算法。原因也简单：校招笔试是海量筛选，面试官需要通过一套标准化的题目快速判断候选人的基本功。基本功不扎实的人，就算会调参、会跑模型，也很难在业务里把一个排序或匹配模块写好。所以把排序、查找、字符串、动态规划这些硬功夫练扎实，是性价比最高的备考路线。

2. 字符串与匹配题复盘：KMP的next数组是重灾区

2.1 真题：模式串"abacaba"的next数组手算全过程

这套卷子里有一道填空题，几乎是照着经典教材出的：给定模式串 p="abacaba"，求它的next数组，并且明确next[i]定义为前i个字符组成的子串的最长相等真前后缀长度。也就是大家常说的前缀函数。

这题看着简单，但真要在考场手算，不下点功夫是容易出错的。我用手算的方式一步一步过一遍。

字符串下标从0开始：

• i=0，子串为"a"，最长相等真前后缀长度为0，所以next[0]=0。
• i=1，子串为"ab"，前缀集合为{"a"}，后缀集合为{"b"}，没有相等，next[1]=0。
• i=2，子串为"aba"，前缀集合为{"a","ab"}，后缀集合为{"ba","a"}，最长的公共前后缀是"a"，长度为1，next[2]=1。
• i=3，子串为"abac"，前缀集合为{"a","ab","aba"}，后缀集合为{"bac","ac","c"}，没有公共前后缀，next[3]=0。
• i=4，子串为"abaca"，前缀有{"a","ab","aba","abac"}，后缀有{"baca","aca","ca","a"}，公共的只有"a"，next[4]=1。
• i=5，子串为"abacab"，前缀有{"a","ab","aba","abac","abaca"}，后缀有{"bacab","acab","cab","ab","b"}，公共前后缀是"ab"，长度为2，next[5]=2。
• i=6，子串为"abacaba"，前缀有{"a","ab","aba","abac","abaca","abacab"}，后缀有{"bacaba","acaba","caba","aba","ba","a"}，公共的最长前后缀是"aba"，长度为3，next[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≥1，next[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(key=lambda 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分钟做最后的检查和整理。

具体节奏可以参考下面这张表：

这个时间分配不是固定的，但原则是：不在一道题上死磕。选择题蒙一个还有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数组的两种定义、失配跳转的具体过程、以及一道业务场景变体全部串起来讲清楚，这比死记硬背面经有说服力得多。校招的每一场笔试，都值得你认真对战，认真复盘。