1. 2016年的题库筛选的其实是通用工程思维2016年春天我还在学校准备暑期实习每天泡在牛客网上刷真题。那时候刷题生态远没有现在这么完善题库少解析少很多公司真题都得靠前人口述和评论区拼凑。网易这套2016实习研发工程师编程题就是当年刷题群里被反复贴出来的一套。前两天整理资料时又翻出来重做了一遍发现即使过了快十年里面的考点依然是笔试高频区模拟、几何、排序统计、边界处理一个都没过时。如果你是准备暑期实习或者秋招提前批的研发岗这套题值得认真做一遍如果你只是想练算法基础它也比很多偏题怪题有价值得多。网易当时的实习笔试一般就是2到3道编程题在线OJ判题语言不限C、Java、Python都可以。题目难度不追求偏难怪反而特别看重“能不能把一个简单问题想完整”。这套题流传下来的回忆版里最常被讨论的是三道小易的升级之路、炮台攻击、有趣的数字。三道题覆盖了模拟、几何、排序统计三个完全不同的方向恰好能反映大厂笔试的一个隐藏逻辑——他们不是在找竞赛选手而是在找能写干净代码、能处理边界情况、能在限定时间内快速建模的准工程师。先说结论这套题如果现在让我去笔试现场做我会把时间分配成“10分钟审题建模、20到25分钟写代码、剩下的时间全部用来构造边界用例”。因为这三道题本身都不难真正让大部分人丢分的不是算法不会而是想得不全。下面我就按原题思路逐题拆解代码统一用Python力求看完就能跑、跑完能过。2. 小易的升级之路模拟过程里的数论暗礁2.1 原题回顾与示例题目大意是小易的角色初始能力值为a按顺序遇到n个怪物每个怪物有一个防御力b_i。判断规则只有两条如果当前能力值大于等于怪物防御力击败怪物后能力值增加怪物的防御力。如果当前能力值小于怪物防御力也能击败怪物但能力值只能增加“当前能力值与怪物防御力的最大公约数”。求最终能力值。输入第一行是n和a第二行是n个怪物的防御力。看一个典型的例子输入 3 50 50 105 200 输出 110手动推一遍初始a50遇到505050击败a变成100遇到105100105所以a增加gcd(100,105)5变成105遇到200105200a增加gcd(105,200)5变成110。最终输出110。2.2 题意拆解两个分支一次循环这道题本质是纯模拟连复杂的数据结构都不需要。你只需要维护一个变量a按顺序遍历怪物数组每次判断当前a和b_i的大小关系然后走对应的累加分支即可。复杂度是O(n log M)其中log M来自最大公约数计算的辗转相除过程M是数值上限。但也正因为“简单”很多人会犯一个低级错误在第二个分支里用初始能力值a0去和怪物防御力求gcd而不是用“当前能力值”。这是题意理解上的偏差怪物是依次遇到的能力值会随着前面怪物的击败而变化后面的判定和累加都基于当前状态不是初始状态。另一个容易忽略的点是第二个分支里即使当前能力值小于怪物防御力怪物依然会被击败。有些同学读完题第一反应是“打不过就跳过”于是直接break或者continue这会导致后续怪物全部没有处理。题目明确写了“怪物也能被击败”只是加成变成了gcd所以循环必须完整走完。2.3 Python实现与逐行解读import sys import math def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) a int(next(it)) for _ in range(n): b int(next(it)) if a b: a b else: a math.gcd(a, b) print(a) if __name__ __main__: solve()几个实现细节说明用sys.stdin.read()一次性读取全部输入再按空白字符切分比逐行input()更稳能避免输入末尾多一个换行符导致的解析问题。用迭代器iter(data)逐个取数不需要真的维护数组省内存也省代码。math.gcd是Python标准库自带的辗转相除实现不要自己写递归容易在深处出问题标准库足够可靠。如果你用的Python版本低于3.5math.gcd不存在只有fractions.gcd不过如今绝大多数OJ环境都支持Python 3.8以上这个细节基本可以忽略。如果环境里必须兼容旧版本可以自己写两行辗转相除。2.4 最容易翻车的三个细节第一个细节是gcd参数的顺序。虽然gcd(a,b)和gcd(b,a)结果一样但如果某个用例里出现了0需要额外处理。比如能力值恰好为0或者怪物防御力为0math.gcd(0, b)返回bmath.gcd(a, 0)返回a逻辑上问题不大但前提是你传进去的是整数。笔试数据一般不会出现0但自己构造边界用例时值得测一下。第二个细节是数据规模。原题n一般不超过1000a和b_i不超过几万Python的int完全没有溢出顾虑。但如果你平时用C或Java刷题一定要记住能力值累积之后可能超过int的范围该用long long就老老实实用long long否则大用例会莫名WA排查起来很痛苦。第三个细节是输入解析要容错。有些在线OJ的第一个测试点就是空输入或者只有第一行没有第二行sys.stdin.read().strip()之后可能为空字符串直接split会得到空列表。代码里加了if not data: return是为了防止这种情况导致StopIteration崩溃。这个习惯对所有在线笔试都通用。3. 炮台攻击圆内点的判断别让浮点数拖后腿3.1 原题回顾与示例这道题的场景是平面射击游戏小易在原点(0,0)平面上有n个怪物第i个怪物坐标是(x_i, y_i)。小易有一次攻击技能可以消灭所有在以原点为圆心、半径为r的圆内含圆上的怪物。求一次攻击最多能消灭多少个怪物。输入格式是第一行两个整数n和r第二行n个整数为所有怪物的x坐标第三行n个整数为所有怪物的y坐标。也就是说x数组和y数组是分开输入的并不是按“每个怪物一行坐标”给的。一个简单示例输入 3 1 0 1 0 0 0 1 输出 3三个点分别是(0,0)、(1,0)、(0,1)到原点的距离分别为0、1、1都不超过半径1所以全部能被消灭。3.2 距离比较的正确打开方式这个题的数学模型太直接了对每个点计算距离判断是否小于等于r。但“怎么算距离”是有讲究的。第一反应可能写math.sqrt(x*x y*y) r这在大数据量下容易踩浮点数精度的坑。比如某个点刚好在圆上坐标是(3,4)r5sqrt(916)理论上等于5.0但在某些浮点实现下可能得到4.999999999999999于是判断结果为False把本应算作消灭的怪物漏掉了。一旦数据里大量出现“恰好在圆上”的用例AC率会非常难看。更好的做法是两边同时平方用整数比较x*x y*y r*r这样完全绕开浮点数所有比较都是整数运算结果精确无误。半径r在输入时是整数坐标也是整数平方之后依然在整数范围内没有任何精度问题。这个优化不只是这道题凡是涉及距离、半径、直线位置关系判断的题都应该优先考虑能不能用整数平方代替开根号。3.3 Python实现与复杂度分析import sys def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) r int(next(it)) xs [int(next(it)) for _ in range(n)] ys [int(next(it)) for _ in range(n)] r2 r * r count 0 for x, y in zip(xs, ys): if x * x y * y r2: count 1 print(count) if __name__ __main__: solve()一次遍历时间复杂度O(n)空间复杂度O(n)用于存坐标。其实空间还可以再优化读x数组时必须先存下来因为y数组在第三行才出现但读y数组时就可以边走边统计了。如果你追求极致省内存可以只存x数组读完y逐个判断。不过笔试场景下n通常不大这点空间无伤大雅清晰优先。3.4 输入格式一变你还稳吗这类真题最常见的变化是输入格式调整。比如有的版本不是提供x数组和y数组而是每个怪物坐标占一行有的版本坐标可能用浮点数给出还有的版本把r放在第二行。我见过不少同学在本地IDE里写习惯了固定格式到OJ上稍微一变就不会了。应对思路很简单无论格式怎么变一律用sys.stdin.read()读取全部内容然后按顺序解析。你只需要根据题意确认“到底有几个数、每个数代表什么”然后按顺序取就好。不要用input().split()去假设每一行有固定数量的数据那样一旦某行出现意外空白就会踩坑。这道题还有一个隐藏考点如果某个怪物恰好位于原点(0,0)距离是0显然在半径内。如果你用浮点开根号判断0的平方根是0没问题但如果你不小心把距离公式写成x*x - y*y这类错误形式0也会掩盖问题。写完代码后可以用包含原点、恰好圆周点、圆外点三个用例去自测保证逻辑完整。4. 有趣的数字排序之后重复元素才是大坑4.1 原题回顾第三道题在流传版本里被叫做“有趣的数字”不同回忆帖对细节的描述略有出入但核心考点是一致的给定长度为N的正整数序列求所有数对(i j)的差值绝对值中的最小值并输出能达到这个最小值的数对个数。示例输入 5 1 5 3 9 7 输出 2 4序列排序后是[1,3,5,7,9]相邻差值都是2共有4对。所以最小差值是2数对数量是4。如果序列中存在重复元素比如输入 6 1 2 2 3 3 3 输出 0 4排序后是[1,2,2,3,3,3]最小差值为0因为两个2、三个3内部都能形成差值0的数对。2出现2次贡献C(2,2)1对3出现3次贡献C(3,2)3对总共4对。4.2 为什么最小差只可能出现在排序后的相邻位置如果所有数两两之间求差值暴力做法的复杂度是O(N^2)。当N到10^5级别时1秒内基本跑不完这在笔试里就是超时。要优化核心观察是数组排序后任意两个不相邻元素之间的差值一定大于等于它们中间某个相邻元素的差值。换句话说全局最小差一定出现在排序后的某两个相邻元素之间。这个结论很好理解假设排序后有三个数a b c那么c - a (b - a) (c - b) b - a 且 c - b。所以差的最小值总能在相邻元素对里找到。这样一来只需要排序后扫描一遍相邻差值时间复杂度降为O(N log N)空间复杂度O(1)。4.3 重复元素才是真正的坑很多人排序后统计出最小差值min_diff然后直接再扫一遍相邻元素统计有多少对相邻元素差值等于min_diff就提交了。这个做法在“所有元素互不相同”时是对的但一旦存在重复元素就会出错。原因在于重复元素之间的差值为0但这些重复元素不一定在排序后“相邻”紧挨着可能中间还隔着别的值不会排序后相同值必然连续排在一起。真正的问题在于统计方式如果直接用“相邻差值等于min_diff”去数比如[1,2,2,3,3,3]相邻差为0的位置有1对2和2之间、2对3和3之间总共统计出3对但正确答案是4对因为2出现2次贡献1对3出现3次贡献3对加起来是4对。问题出在哪三个3在排序后依次相邻只有两个“相邻差值”的位置但三个3里面任取两个形成数对一共有C(3,2)3对。所以当min_diff等于0时不能用相邻位置计数要通过每个数字的出现次数做组合数统计。4.4 Python实现与复杂边界import sys from collections import Counter def solve(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) arr [int(next(it)) for _ in range(n)] arr.sort() min_diff float(inf) for i in range(1, n): d arr[i] - arr[i - 1] if d min_diff: min_diff d if min_diff 0: cnt Counter(arr) ans 0 for v in cnt.values(): if v 1: ans v * (v - 1) // 2 else: ans 0 for i in range(1, n): if arr[i] - arr[i - 1] min_diff: ans 1 print(min_diff, ans) if __name__ __main__: solve()这里的边界情况是N1。只有一个数的时候没有任何数对理论上题目通常会保证N2但代码里如果N1min_diff会保持inf最后的输出会不符合预期。稳妥做法是在扫完差值后判断如果N 2直接输出0 0。虽然大部分用例不会给这种数据但多一行业务判断不会错。另一个坑是输出顺序和格式。有的版本要求先输最小差值再输对数有的版本反过来有的版本要求输出在同一行有的版本要求换行。提交前一定看清题目描述。5. 从这套真题看校招笔试的备战优先级5.1 网易这类公司笔试的“筛人”逻辑我曾经和参与过校招出题的朋友聊过一次他们的说法让我印象很深笔试编程题并不是为了筛出“算法天才”而是为了筛掉三类人。第一类是不会建模的给一个生活化场景无法抽象成明确的输入输出和流程第二类是代码能力不达标的思路对但写出来一堆边界错误第三类是体力不足的简单题能做但速度太慢导致后面没时间。对照这套2016年真题你会发现三道题全是“基本功”没有一道涉及冷门算法。小易的升级之路考的是按规则模拟炮台攻击考的是距离模型和数值稳定性有趣的数字考的是排序后统计。只要数据结构基础扎实、编码习惯好完全可以在时间内AC。所以备战重点不是刷偏题而是把高频基础题练到肌肉记忆。5.2 刷题之外的三个应试习惯第一个习惯是审题后先手推样例。无论题目描述多长拿到题先照着示例手动走一遍流程再开始写代码。这样做能帮你验证对题意的理解也能提前发现类似“这里要取gcd”这种关键分支。很多WA不是因为代码错而是从第一步就把题意理解偏了。第二个习惯是提交前构造三个边界用例。我的固定动作是最小规模用例n1、最大规模极端用例n很大、数值很大、临界值用例半径刚好等于距离、能力值刚好等于怪物防御力。这三个用例能覆盖至少七成的隐藏坑。第三个习惯是不要死磕一道题。笔试总时间固定如果一道题写了20分钟还没AC先跳过去做后面的。大厂笔试一般按通过的测试用例比例给分把简单题稳稳拿下比在一道难题上耗死要划算得多。5.3 基于这套真题的复习清单如果你现在准备校招笔试我的建议是按这个顺序覆盖知识点模拟与状态维护、排序与双指针、哈希表、字符串处理、栈与队列、递归、动态规划入门、树与图的遍历。这套2016年的题恰好覆盖了前两块后面几块可以用同类型的经典题补上。具体到刷题数量不需要刻意追求上千题。重要的是每一类题都能独立写出无bug版本并且知道复杂度。面试官问起某道题你能说出“暴力为什么不行、优化点在哪里、边界情况有哪些”就已经超过大多数候选人了。我现在面试新人时其实更关注他在解题过程中能不能把思路讲清楚而不是他刷了多少道题。这套真题我偶尔还会拿出来让准备面试的同学做一遍不为别的就因为它在简单和复杂之间拿捏得刚刚好每一题都能做但每一题都有让人丢分的暗坑。把这些坑一个个踩平笔试能力会有一个肉眼可见的进步。