每年的校招季总有几套题会被反复拿出来讨论网易2016研发工程师的编程题就是其中之一。我身边不少后来进了大厂的朋友当年都把这份卷子当作练手标配。这轮题目的特点很鲜明不玩偏题怪题基础知识覆盖扎实链表、字符串、动态规划、贪心都有涉及难度梯度拉得比较开从能快速AC的签到题到需要静下心来推状态转移方程的压轴题都有。无论你是准备春招秋招的在校生还是想检验一下自己基础功底的从业者这套题都值得认真做一遍。我这次就把这套题里最具代表性的几类问题拆开揉碎了讲从出题人的视角分析每道题在考什么再给出可以直接落地的解法和代码。重点不是说答案而是把“拿到一道题之后怎么思考”这条链路完整走一遍。1. 整体设计思路与题目定位解析1.1 2016年前后校招笔试的出题风格聊这套题之前得先还原一下当年的笔试环境。2016年的时候线上笔试系统已经比较成熟了网易的校招笔试基本都是在线做题用自己电脑写代码然后提交。这种形式决定了出题上的几个倾向。第一题目不能太依赖本地调试环境所以输入输出格式一般比较常规不像现在有些公司用ACM赛制搞特别复杂的输入解析。第二题目数量不会太多大概4到6道编程题给两小时左右这样既覆盖了主要考点又不至于让人完全写不完。第三也是最重要的题目里不会出现特别偏门的算法重点还是放在基础数据结构和经典算法模型上。网易2016这轮题基本就是这个思路的典型代表。我当时做完之后的感觉是每道题你都知道它想考什么但能不能在规定时间内写对就是另一回事了。比如链表类的题知道要逆序不难难的是指针操作的边界处理动态规划的题能看出来是DP不难难的是状态定义和转移方程的细节。1.2 考点分布与难度梯度拆解从考点分布来看这套题覆盖的知识点大致可以分成四个层次基础数据结构操作链表逆序、链表判环、字符串处理等属于“必须拿分”的题目一般放在前面经典算法模型动态规划、贪心策略属于“区分度”题目中等偏上难度数学与逻辑思维数学变形、规律推导属于“拉分题”考验思维的灵活性代码实现能力边界处理、复杂度优化这个不单独成题但每道题都在考从实战角度看前两类题目是重点因为这些题目即便是在系统设计、架构面试里也可能以白板题的形式再次出现。举个例子链表的逆序和判环我在后来的技术面里就不止一次被要求手写。所以别觉得校招题就是刷完就扔很多基本功是长期的。2. 高频考点深度拆解链表与字符串操作2.1 链表逆序的两种写法和一个关键细节链表逆序应该说是面试里最经典的题目之一网易2016里就有一道和链表操作相关的题。这道题本身不难但非常能看出一个候选人代码基本功扎不扎实核心考察点是引用操作和边界条件。迭代写法是最直观的。我们需要维护三个指针前驱节点prev、当前节点cur、后继节点next。每次迭代做四件事先保存cur的下一个节点再把cur的next指向前驱然后把prev移动到cur最后把cur移动到之前保存的next。循环终止条件是cur为空此时prev就是新的头节点。struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; cur-next prev; prev cur; cur next; } return prev; }递归写法也值得掌握尤其面试时有时候会要求你用递归实现一遍。递归的思路是把“反转整个链表”拆成“反转除去第一个节点后的子链表再把原第一个节点接到子链表末尾”。注意递归的终止条件是当前节点为空或者当前节点的下一个节点为空直接返回当前节点。ListNode* reverseListRecursive(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; }这里有一个关键的细节也是我自己当年踩过的坑递归写法里head-next-next head 这一步必须在 head-next nullptr 之前。如果你的顺序写反了先把head的next置空后面的节点就找不到了整个链表就断了。这个顺序问题在纸上推演的时候很容易忽略最好自己在脑子里过一遍递归栈的展开过程。2.2 链表判环的数学原理另一类链表高频题是判断链表是否有环网易2016里也有涉及。判断有环的标准解法是快慢指针一个每次走一步一个每次走两步。如果链表里有环两个指针最终一定会相遇。很多同学背了这个解法但不知道为什么快慢指针一定能相遇。这里简单推一下假设链表无环部分的长度是a环的长度是b。当慢指针进入环的时候快指针已经在环里了设此时快指针距离慢指针还有k步按环内顺时针方向。因为快指针每次比慢指针多走一步所以经过k步之后快指针就会追上慢指针。也就是说在最坏情况下需要走的步数不会超过环的长度b所以时间复杂度是O(ab)也就是O(n)。快慢指针这个思路本身还可以延伸出不少变体比如找到环的入口节点。做法是相遇之后把一个指针移回链表头两个指针每次都走一步再次相遇的位置就是环的入口。这个结论的推导同样基于上面的数学关系面试时可以顺手写出来会是个不错的加分项。2.3 字符串处理循环移位与第一个只出现一次的字符字符串相关的题目在2016网易研发工程师编程题里也占了不小的比重。这类题通常不考太复杂的算法重点在于代码的简洁性和对常用技巧的掌握。循环移位判断是一个非常典型的问题给定两个字符串s1和s2判断s2是否由s1循环移位得到。比如abcde循环移位可以得到bcdea、cdeab等。最巧妙的解法是把s1拼接成s1s1然后判断s2是不是这个新串的子串。这个结论背后的逻辑很简单循环移位本质上是把一个字符串从某个位置切开然后交换两段的前后顺序而s1s1这个串里包含了所有可能的切分结果。另一个经典的字符串题是找第一个只出现一次的字符。直观做法是维护一个哈希表第一遍遍历统计每个字符出现的次数第二遍遍历找到第一个出现次数为1的字符。在C里可以用unordered_map但这道题有个更轻量的做法因为字符范围有限ASCII字符集256个可以直接用一个大小为256的数组来计数这样既避免了哈希表的开销代码也更简洁。char firstUniqChar(const string s) { int count[256] {0}; for (char c : s) count[(unsigned char)c]; for (char c : s) { if (count[(unsigned char)c] 1) return c; } return \0; }这里唯一需要注意的就是unsigned char的强转因为char默认可能是有符号的如果用负数下标访问数组会出问题。这个细节在实际笔试中可能会被测试用例打穿我就吃过一次亏。3. 进阶考点实战动态规划与贪心策略3.1 最长递增子序列的两种解法动态规划是网易2016研发工程师编程题里区分度的主要来源也是最值得花时间准备的部分。我先从最长递增子序列LIS说起因为它的状态转移思路非常经典而且有两种差距比较大的解法。第一种是基础的O(n²)动态规划。定义dp[i]表示以第i个元素结尾的最长递增子序列长度。状态转移的时候遍历i之前的所有元素j如果nums[j] nums[i]就用dp[j] 1去尝试更新dp[i]。int lengthOfLIS(vectorint nums) { int n nums.size(); vectorint dp(n, 1); int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }第二种是贪心加二分的O(n log n)解法。维护一个数组tailstails[k]表示长度为k1的递增子序列中最小的末尾元素值。遍历原数组时在tails里用二分查找找到第一个大于等于当前元素的位置替换掉它如果当前元素比tails所有元素都大就追加到末尾。最终tails的长度就是LIS的长度。这个解法的巧妙之处在于tails数组本身不一定是真正的LIS序列但它维护了“相同长度下的最小末尾元素”这个关键信息。这种贪心思路在面试里很受考官喜欢因为它体现了对问题的深入理解。3.2 网易经典DP题“合唱团”的完整推演网易2016年前后笔试中出现过一道“合唱团”问题这道题后来在各大论坛上被反复讨论基本成了网易校招DP题的代名词。题目大意是有n个学生站成一排每个学生有一个能力值要求从这n个学生中选出k个学生使得这k个学生的能力值乘积最大同时要求相邻两个被选中的学生编号之差的绝对值不超过d。这个题的难点在于乘积可能为负而且能力值也可能是负数。如果只维护最大值遇到两个负数相乘的情况就可能出错。所以需要同时维护最大值和最小值两个状态的转移。具体来说定义两个二维数组dpMax[i][j]和dpMin[i][j]分别表示以第i个学生作为最后一个被选中的学生、已经选了j个学生时的最大乘积和最小乘积。状态转移时从前一个被选中的学生p满足i-p不超过d转移过来dpMax[i][j] max(dpMax[i][j], max(dpMax[p][j-1] * val[i], dpMin[p][j-1] * val[i])); dpMin[i][j] min(dpMin[i][j], min(dpMax[p][j-1] * val[i], dpMin[p][j-1] * val[i]));初始条件是j1时dpMax[i][1]和dpMin[i][1]都等于val[i]。最终答案是所有dpMax[i][k]中的最大值。这道题之所以经典是因为它把DP中非常容易被忽略的“负负得正”情况做成了核心考点。我见过很多人在笔试时只维护了最大值最后死活过不了隐藏样例。所以在这里给一个建议只要题目涉及乘法、且数据范围允许负数就要立刻想到同时维护最大最小值。3.3 区间调度类贪心问题的两个视角贪心策略在2016年的题目里也有体现比较典型的是区间问题。区间调度类问题的核心是排序的基准选择我以最经典的不重叠区间问题为例展开讲讲。给定一系列区间问最多能选出多少个互不重叠的区间。常用的贪心策略是按区间右端点从小到大排序然后依次选择右端点最小且与已选区间不冲突的区间。为什么按右端点排序而不是按左端点或者区间长度排序因为右端点越小给后续区间留出的空间就越大这在直觉上是“最优的未来扩展性”。反过来如果是求“最少需要移除多少区间才能让剩余区间互不重叠”它的答案就等于总区间数减去最多互不重叠区间数。这个转化思路在面试中也很常用。这道题想明白之后你会发现贪心算法其实是很多题目的“第一直觉”经过严谨验证后的结果。面试时如果你能把“为什么这样贪心是正确的”用反证法讲清楚那比背一百道题的模板都有用。4. 笔试现场的代码实现与调试心得4.1 从读题到AC的标准工作流备考阶段刷题是一回事真正上了笔试考场又是另一回事。我总结了一套自己用起来比较顺的做题流程分享出来可以参考。拿到题目之后第一步不是马上写代码而是先花两到三分钟静下心来读题把输入输出格式、数据范围、边界条件这几个关键信息圈出来。尤其是数据范围它直接决定了你的算法需要什么复杂度。举个例子如果n的范围是10^5O(n²)大概率超时这时候就得想O(n log n)甚至O(n)的解法如果n只有1000那暴力枚举很多时候就够了。第二步是先在草稿纸上或者脑子里过一遍用例。手工构造一个最简单的输入把预期输出写出来再构造一个包含边界条件的输入比如空数组、只有一个元素、全是负数、最大值然后跟着自己的思路跑一遍看看输出是否符合预期。这个步骤能挡掉至少三成的低级错误。第三步才是写代码。写的过程中注意三个点循环边界、下标偏移、空指针判断。我的习惯是先写主体逻辑最后再统一补边界条件的处理这样思路不容易被打断。写完代码之后一定不要急着提交先用自己构造的测试用例在本地跑一遍确认输出正确了再提交。4.2 手写代码时最容易翻车的三个细节我在帮别人review代码以及复盘自己笔试时发现有几个细节是反复翻车的高发区这里单独拎出来说一下。第一个是整型溢出。很多题目的中间结果会超过int的范围尤其是在做乘法或累加的时候。2016年的题目里能力值的乘积就可能非常大。解决方案是只要涉及相乘或者求和就优先考虑用long long甚至在某些情况下用unsigned long long。虽然多写几个字节不费事但能省掉很多不必要的排查时间。第二个是动态规划数组的初始化。不同的初始化值直接决定了状态转移是否正确。比如求最小值的时候初始化为一个大数求最大值的时候初始化为一个负数这些都是老生常谈但真的很容易写错。我的习惯是初始化时从题目数据范围倒推而不是随手写一个INT_MAX或者INT_MIN了事。第三个是二分查找的边界写法。二分查找看似简单但死循环和越界是高频问题。我自己比较习惯的写法是闭区间写法循环条件用left right更新时用left mid 1和right mid - 1这样能避免很多边界上的坑。4.3 推荐使用的代码模板准备笔试的时候可以提前准备几个常用算法的代码模板到了考场直接默写能节省不少时间。我常用的模板包括二分查找、链表操作、二叉树遍历、回溯框架这几个大类。这里给一个我常用的二分查找框架对绝大多数变体都适用int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }mid的计算推荐用left (right - left) / 2而不是(left right) / 2这样可以防止left和right都很大时的整型溢出。虽然现代编译器里int溢出在竞赛环境下未必会暴露但在生产代码里这是一个好习惯。5. 高频问题与备考实战建议5.1 常见错误速查表我把平时刷题和笔试中遇到的典型问题整理成一个速查表每一条都是亲手踩过的坑不是从书上抄来的理论。问题类型典型表现排查思路数组越界本地运行崩溃线上报Runtime Error检查循环变量边界尤其是i1、i-1、j1这类下标偏移死循环程序一直不退出超时检查while循环中指针/索引是否一定会更新考虑快慢指针相遇条件输出格式Wrong Answer检查是否多输出了空格、换行是否漏了#Case 1这类前缀类型溢出结果异常大数据量时出错把所有涉及乘法的中间量改成long long逻辑遗漏只能过部分样例思考负数、零、空输入、单元素输入是否都覆盖了指针丢失链表操作结果错误画图模拟指针变化尤其注意临时节点的保存这张表其实不只是针对网易2016这套题其他任何笔试都适用。每次做完题复盘的时候把自己犯错的原因归类到对应行刷几套题之后你就会发现自己有一两个固定的“弱点模式”针对性地去练比盲目刷题有效得多。5.2 从一套题延伸出的备考知识树网易2016这套题其实是一棵很好的知识树主干以它为起点可以延伸出大量的关联考点。链表逆序可以延伸出K个一组反转链表、回文链表判断链表判环可以延伸出寻找环入口、求环长度LIS可以延伸出最长公共子序列、最长回文子序列合唱团这道DP题可以延伸出状态压缩DP、树形DP。我建议备考时不要只盯着题解看而是每做完一道题就做一次横向扩展这道题的数据结构还能支持什么操作这道题的DP状态定义还能迁移到哪些问题上这样坚持两周覆盖面会明显上一个台阶。提示刷题的时候给自己定个规矩每道题搞懂之后花三分钟在笔记本上写一句话总结。别小看这个动作它能在你复习的时候省下很多时间。5.3 笔试时的时间分配建议网易这种校招笔试一般两小时左右、4到6道题。我的建议是不要把时间平均分配而是先把所有题目快速看一遍把题目按难度和熟悉度分成三档马上能写的、有点思路但需要推一推的、完全没思路的。第一档题直接写争取拿满分。第二档题给自己设置一个时间上限比如30分钟如果到时间了还是一点头绪都没有先跳过去做后面的题积累分数。第三档题留在最后就算只能写个暴力解法也要把代码框填满因为很多时候暴力解法能帮你拿到部分测试用例的分数。压轴题如果已经明确是DP而且你状态定义也推得差不多了建议先写主逻辑把核心转移方程实现出来再回头补初始化和边界。因为阅卷系统通常是按测试用例给分的主逻辑写对就能覆盖不少用例。写在最后网易2016研发工程师编程题这套题对我的意义不只是一次笔试的练兵更像是一面镜子。它让我看清了自己在数据结构和算法上的薄弱环节也让我意识到面试考查的其实不是“你背了多少题”而是“你在面对一个没见过的问题时能不能冷静地拆解、建模、实现、验证”。我自己在实际操作中的体会是刷题不追求数量追求的是每道题都能讲到“为什么”的层面。哪怕一天只吃透一道题坚持三个月效果一定比一天刷十道题然后转头就忘好得多。最后再分享一个小技巧做这套题的时候可以给自己模拟一下真实的笔试环境开一个计时器关闭编译器自动补全甚至把手机关机放到另一个房间。这种略带紧张感的练习比漫无目的地刷题更能锻炼临场状态。如果你能把这套题的每个考点都吃透我相信你面对大多数公司的研发岗笔试都能多一分底气。