2017年秋招季我做了一套让我印象格外深刻的在线编程题——网易有道的内推笔试。那会儿内推还没像现在这么普及能拿到内推名额基本等于提前锁定了面试机会。但真正的拦路虎不是简历而是笔试环节里那几道限时编程题。这套题让我第一次意识到会写代码和能通过在线评测根本是两回事。今天把这套题拿出来复盘不是因为题目有多新而是它背后那几个考点——字符串处理、分治思想、动态规划思维、标准输入输出——几乎在之后每一家公司的笔试题里都能看到。1. 内推笔试到底在筛什么不只是会不会写代码1.1 网易有道2017内推笔试的基本盘2017年互联网公司的内推笔试基本都跑不脱限时在线编程这个模式。网易有道的内推笔试一共三道编程题限时一小时在线评测支持C、Java、Python等主流语言。提交之后系统会给出通过用例的比例没有部分分——用例不过就是不过。那会儿和现在不太一样的地方在于内推笔试的题目风格更贴近业务里的小算法不会出那种特别偏的竞赛题但非常考验基础功。三道题大致覆盖了字符串操作、数组查找、子序列/子串问题这三类高频考点难度呈阶梯状第一题算热身第二题开始上强度第三题需要一点算法思维。我后来带新人时也常拿这套题举例因为它基本代表了校招笔试里正常难度的上限。1.2 这类题型的三个隐藏考察点第一个隐藏考察点是读题。题目里经常有输出格式输入的边界范围k可能大于字符串长度这类描述。很多人扫一眼就直接按直觉开写结果挂在了没取模这种细节上。第二个是复杂度意识。第一题如果只会Python切片第二题如果只会排序第三题如果只会暴力双重循环样例都能过但数据量一上去就会超时。在线评测不会提示请用更优算法它只会给你一个冷冰冰的超出时间限制。第三个是造测试用例的能力。本地写代码可以用print随便验证在线评测只告诉你有多少用例没过不告诉你是哪个。所以你得在脑子里过一遍数组为空、k等于0、数组全负数、输入带空格、字符串特别长……这些边界用例能不能抗住全靠平时写代码积累的习惯。2. 三道题的原题场景还原与考点定位做内推笔试题有个很现实的问题考完就忘网上能找到的真题版本往往也是七零八落的。我根据当年考完和同学对答案的结果把三道题的核心场景还原出来虽然和原题不保证一字不差但考点和思路是一样的。2.1 第一题字符串循环移位题目场景实现一个函数把给定的字符串str循环左移k位。例如strabcdefk2得到cdefab。考点拆解基础字符串/数组操作k可能大于n的取模处理是否理解三次反转这种O(1)空间的写法这道题放在第一题的位置属于典型的送分题热门程度高。但送分不等于白给k的处理和原地操作会筛掉一批人。如果连字符串的基本操作都不熟后面的题基本没戏。2.2 第二题数组中的第K大元素题目场景给定一个无序整数数组nums和一个整数k返回数组中第k大的元素要求平均时间复杂度O(n)。例如nums[3,2,1,5,6,4]k2返回5。考点拆解排序是O(nlogn)能过但显然不是出题意图快速选择Quick Select是平均O(n)的解法也可以用小根堆维护大小为k的堆时间O(nlogk)随机化pivot对避免最坏情况很重要这道题的区分度开始出来了。会排序的人很多但能在要求O(n)的前提下给出稳定解法的人说明真的理解分治和递归。2.3 第三题最大连续子序和题目场景给定一个整数数组nums找出具有最大和的连续子数组并返回最大和。例如[-2,1,-3,4,-1,2,1,-5,4]答案是6对应子数组[4,-1,2,1]。考点拆解暴力是三重循环O(n^3)起步完全不可接受Kadane算法本质是贪心加滚动更新一趟遍历O(n)考察对负数累加的敏感度一旦当前子数组和为负就应该果断丢弃这道题放在压轴位置表面上是动态规划入门实际上考的是对状态的抽象能力。它比前两道更考验为什么这样想的思维过程。3. 核心代码实现与为什么这样写3.1 三次反转空间O(1)的字符串移位写法先给出最基本的想法。字符串左移k位可以拆成三个步骤把前k个字符反转把剩余字符反转把整个字符串反转举例说明。sabcdefk2前两个字符ab反转得到ba剩余部分cdef反转得到fedc此时字符串是bafedc整体反转得到cdefab正好是答案Python实现如下def left_rotate(s, k): if not s: return s n len(s) k % n if k 0: return s lst list(s) # 反转前 k 个 lst[:k] reversed(lst[:k]) # 反转剩余部分 lst[k:] reversed(lst[k:]) # 整体反转 lst.reverse() return .join(lst)几个容易出错的地方k % nk可能比n大也可能等于0。取模之后如果k为0直接返回原字符串。Python里reversed返回的是迭代器切片赋值会把它转成列表这个行为在Python 3里没问题。字符串不可变所以先转成list。如果要求真正的原地操作C里直接对字符数组操作就行Python这样做已经是合理折中。有人会问Python里直接写s[k:] s[:k]不就行了确实行笔试也不禁止但这不是出题人想看到的。三次反转的价值在于空间O(1)如果只说用切片遇到字符串特别长、内存有限的追问就会哑火。练习的时候建议两种都写一遍至少明白切片的写法为什么更贵。3.2 快速选择从排序到O(n)平均复杂度的演进第二题如果写return sorted(nums, reverseTrue)[k-1]一句话结束测试也能过。但题目标明了要求平均时间复杂度O(n)直接排序只能拿到O(nlogn)。所以核心是快速选择。快速选择的基本思路借了快速排序的partition但只往包含第K大的那一侧递归另一侧直接丢弃。平均情况下每次把数据规模减半总复杂度O(n)。我倾向于先把partition部分写对这是最容易出错的地方。我采用选pivot - 放到最右 - 从左往右把大于pivot的元素换到前面 - 把pivot换回分界点这个流程。import random def find_kth_largest(nums, k): def quick_select(left, right): # 随机选 pivot尽量避免最坏情况 pivot_idx random.randint(left, right) pivot nums[pivot_idx] # 把 pivot 先挪到最右边 nums[pivot_idx], nums[right] nums[right], nums[pivot_idx] store left for i in range(left, right): if nums[i] pivot: nums[i], nums[store] nums[store], nums[i] store 1 # 把 pivot 放到正确的位置 nums[right], nums[store] nums[store], nums[right] # store 处就是 pivot 的最终位置 if store k - 1: return nums[store] elif store k - 1: return quick_select(store 1, right) else: return quick_select(left, store - 1) return quick_select(0, len(nums) - 1)这里几个细节值得展开为什么要随机选pivot如果每次选固定位置比如最左对于一个接近有序的数组partition后pivot很可能落在端点退化成O(n^2)。随机化能在概率上避免这个最坏情况。比较符号是而不是因为我们找第K大把所有比pivot大的元素换到左边。如果数组里有大量重复值会改变pivot的位置逻辑容易在边界上出问题。k - 1的坐标系第1大的元素应该在排序后数组下标0的位置。所以第k大对应下标k-1这个换算一开始容易搞混。如果不想手写快速选择堆也是一种可靠的方案维护一个大小为k的小根堆堆顶就是当前最大的K个元素里最小的那个也就是第K大。Python里直接用heapq就可以。import heapq def find_kth_largest(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[0]这段代码的时间复杂度O(nlogk)空间O(k)在笔试判题里同样能过而且代码量少、不容易写错。我个人的习惯是如果题目对时间限制特别严用随机化快速选择如果求稳用堆。两个方案都建议练熟。3.3 Kadane算法把负收益果断断舍离第三题暴力法会超时正经解法是Kadane算法。思路其实一句话就能说清楚遍历数组时维护两个变量一个是以当前元素结尾的最大子数组和cur一个是全局最大和ans。def max_subarray(nums): if not nums: return 0 ans nums[0] cur 0 for num in nums: # 如果 cur 加上当前元素还不如从当前元素重新开始大就重新开始 cur max(num, cur num) ans max(ans, cur) return ans为什么这样是对的用生活化的例子解释假设你经营一家店每天都在记累计盈亏。如果前几天的累计亏损已经把重新开店的起点拉得很低那么与其背着亏损继续不如直接关掉旧店、从今天重新算起。这里的cur就是到今天为止的累计盈利而max(num, cur num)就是在判断新开一家店是比接着老店经营更划算。这道题还有一个隐藏考点数组元素全为负数。这种情况下最大连续子数组就是最大的那个负数比如[-5, -2, -3]的答案是-2。很多人的第一版写法把ans初始化为0遇到全负数数组就直接返回0这是典型的边界漏判。正确做法是把ans初始化为nums[0]或者cur初始化为极小值。如果题目再延伸一步要求返回最大连续子数组的起始和结束下标Kadane算法同样适用只需要在cur被重置时记录起点在ans更新时记录终点。这种变体在面试追问里很常见练的时候可以顺手想一想。4. 在线评测的输入输出与边界条件最容易被扣分的环节4.1 标准输入解析的细节2017年的内推笔试是在在线评测平台上做的不是那种函数填空模式。这意味着除了算法本身你还得会处理标准输入输出。最容易翻车的点题目可能像这样给出输入abcdef 2一行字符串加数字中间空格分隔。要先split再分别处理。数组输入可能是逗号分隔3,2,1,5,6,4 2第一段是数组第二段是k。这种情况直接按空格split会把3,2,1,5,6,4当成一个整体还得再用逗号split一次。Python里稳妥的读法import sys def main(): data sys.stdin.read().strip().split() if not data: return # 假设最后一段是数字k前面是数组字符串 k int(data[-1]) arr_str data[0] if len(data) 2 else .join(data[:-1]) # 处理逗号分隔 nums [int(x) for x in arr_str.replace([, ).replace(], ).split(,) if x.strip()] # 调用算法函数 print(find_kth_largest(nums, k)) if __name__ __main__: main()这段代码里最容易被忽略的是if x.strip()。如果输入是3,2,1,5,6,4,结尾多了一个逗号split会生成一个空字符串直接用int()转换会报ValueError。加上这个判断就能扛住脏输入。另外sys.stdin.read()和input()的区别read会把所有输入一次性读进来适合多行数据input是一行一行读。对于内推笔试的输入形式read更稳因为它不怕题目输入里有多余换行。4.2 边界用例自查清单写完之后别急着提交先在本地把下面这些用例过一遍题目边界用例容易踩的坑字符串循环移位sa, k100忘记取模导致越界或输出错误字符串循环移位s, k0空字符串处理第K大元素nums[1], k1递归结束条件第K大元素nums[5,5,5,5], k2重复值导致的partition错乱最大连续子序和nums[-1,-2,-3]全负数时不能返回0最大连续子序和nums[1,2,3]正数数组要保证全加上这张表我在之后的笔试里反复用过每次提交前对照自查一遍基本能避开八成以上的隐藏扣分点。5. 踩坑实录从样例通过到全部AC的完整排查链路5.1 样例通过但提交0分的典型原因那年我第一题写完样例跑得好好的一提交0分。当时完全懵了后来冷静下来才发现是输入解析的问题我把整行的abcdef 2当成了字符串split之后忘了把数字部分转成int结果字符串做乘法整个逻辑全乱了。后来总结出一套排查顺序先检查输入解析再检查边界条件最后才怀疑算法本身。这个顺序特别重要因为算法错了至少有几个用例能过输入解析错了可能一个都过不了。还有一个常见问题是输出格式。有些题要求输出后跟换行有些要求空格分隔有些要求逗号。print默认自带换行一般没问题但如果你用sys.stdout.write就得自己加\n漏了就会因为格式不对被判0分。5.2 几个真实发生的错误现场再分享几个真实遇到过的错误第一快速选择里比较符号写反。我最早写的是if nums[i] pivot把大于pivot的留在右边逻辑上好像也行但后面store和k-1的对比坐标全反了样例能过换个用例就错。第二最大连续子序和初始化错误。我一开始把ans初始化为0遇到全负数组直接返回0。这个问题直到我随手测试[-1, -2]才发现。从那以后凡是涉及取最大值的问题第一个元素一定参与初始化。第三字符串移位k被写成0。题目说k可能等于0也可能大于字符串长度。我第一版没取模s[k:] s[:k]当k大于n时直接返回原字符串看起来没什么问题但实际上是错的——因为左移100位的abcdef正确答案是cdefab不是abcdef。这类问题有一个共同点它们不会在样例输入上报错但会在边界测试里撕开一个口子。所以写完题目至少花两分钟自己构造三组边界用例。这个习惯帮我省下了很多次再提交一次的机会。6. 今天回看这套题还能怎么练6.1 考点迁移2025年了这套题的题目本身可能已经不会再出现在笔试题库里但它考的几个点完全没有过时字符串操作很多业务场景都要处理序列、子串分治/堆海量数据TopK问题是面试常青树动态规划/贪心几乎每个算法岗都会追问我个人觉得这类校招经典题最好的用法不是死记答案而是当模板。比如字符串移位背熟三次反转下次遇到反转单词顺序旋转数组思路是一样的第K大背熟快速选择以后遇到求中位数求TopK直接套结构最大子序和背熟Kadane以后遇到买卖股票最佳时机最长子数组这类变体能看到它背后的选择逻辑。6.2 学习路径建议如果现在是准备校招的人我给的建议很简单。第一步每道经典题必须能手写一遍不借助编辑器补全。在线笔试的IDE不会给你那么多代码提示手写能力直接决定你写代码的速度。第二步把输入输出处理练成肌肉记忆。用sys.stdin.read()解析各种格式至少练习20道不同输入格式的题。第三步刷题时给自己一次通过的纪律。每道题提交前先过一遍自己写的边界用例清单确保在评测系统里能做到一遍AC而不是不断试错。这三条做到了应付内推笔试的编程题绰绰有余。有一件事我印象特别深。那年做完整套题我最大的感触不是算法练得不够而是平时积累的工程习惯救了我——因为平常写代码习惯考虑边界、习惯先解析好输入再动手、习惯写完自查所以哪怕算法不一定是最优的至少提交上去的代码是能跑的。后来我带新人也发现算法能力可以突击但写能用的代码这件事靠的是每天写代码时的小习惯。这套题就算今天再让我做一遍我想我还是会先花两分钟把三个边界用例写在草稿纸上再开始写第一行代码。