每年秋招季总会有同学翻出牛客网题库里“腾讯2016研发工程师编程题”这套经典卷子来刷。这套题在当年的校招笔试里算是比较有代表性的题量不大、难度不低、坑位不少考察的都是算法基本功和代码细节。九年过去腾讯笔试的题型已经换了好几轮但这套题依然被反复提及原因很简单——它的出题逻辑和考察点至今仍然是大厂笔试的主流。这篇文章我就以复盘的形式把当年这套题里频次较高、也比较有代表性的几道题目拿出来完整拆一遍从题目描述、解题思路到参考代码、易错点一套流程走下来。无论你现在是在备战校招还是单纯想看看大厂笔试到底考什么这篇都值得收藏。1. 2016年腾讯校招编程题全景回溯1.1 当年的校招背景与笔试环境2016年移动互联网还处在红利期腾讯作为头部大厂校招技术岗的简历投递量非常大。研发工程师岗位的笔试基本都走在线OJ系统当年的主流平台是牛客网。笔试环境没有现在这么花哨就是一套在线答题页面客观题和编程题混在一起编程题支持C/C、Java等主流语言每道题会给出输入输出样例但不会有太大范围的测试用例提示。这年研发岗笔试的编程题一般控制在3到5道整体难度比现在的“ACM风格”要温和一些但有一个特点非常明显题意不长坑不少。很多题看起来像是基础题实际上一旦考虑不周很容易出现部分样例通过、拿到0分或者一半分数的情况。也就是说这套题的核心筛选逻辑不是看你懂多少高级算法而是看你在有限时间内能不能写出健壮、正确、可运行的代码。1.2 研发工程师岗位的考察逻辑不挑方向不挑语言只挑基本功要注意的是2016年的“研发工程师”是统招岗位不区分前端、后端、客户端等具体方向。所有人都用同一套笔试题所以题目设置上有意避开特定业务场景集中在算法与数据结构的通用能力上。按今天的话说这套题就是一套“基本功体检”。基本功体现在三方面第一基础算法是否扎实比如排序、二分、动态规划、数论这些常见考点第二边界情况是否敏感比如数组为空、输入相等、结果溢出这类情况是否处理到位第三代码能不能在无IDE提示的情况下一次写对。这三点对应到日常工作里就是代码review时最常被挑出来的问题。所以这套题虽然叫“编程题”实际上考察的是一个工程师最底层的代码素养。1.3 题量分布与时间节奏从当年参加过笔试同学的反馈来看编程题普遍给60到90分钟题量看起来不大但每道题从读题、思考、编码到调试平均下来一道题15到20分钟。这意味着你基本没有时间回头改前面的题必须在第一次提交前尽可能保证正确性。这也解释了为什么那几年笔试成绩出来以后很多同学反映“都会做但就是没AC”。问题不出在思路而出在时间分配和代码细节上。比如组合计数忘取模、数组越界没检查、long long不够用、输入输出格式不对任何一种情况都会让你与满分失之交臂。后面我会专门列一节实操避坑这里先不展开。2. 核心考点与出题逻辑拆解2.1 基础数据结构与经典算法的权重把这套题刷完一遍你会发现它涉及的知识点集中在几个固定区域排序、二分、字符串处理、动态规划、简单数论。没有线段树没有网络流没有复杂的平衡树出题人刻意把题目控制在“科班学生大二大三就能掌握”的范围内。为什么这么设计我的理解是校招研发岗进来以后要参与真实项目开发考察的重点是你写业务代码、处理数据、排查问题的能力而不是让你入职第一天就去做算法研究。基础算法代表的是逻辑思维能力和代码实现能力。排序能不能写对、二分会不会死循环、动态规划的状态转移方程能不能理清这些直接反映一个人写代码的扎实程度。这也是为什么今天的大厂面试依然喜欢考基础题。2.2 边界条件大部分AC失败的原因我当年帮学弟学妹们复盘这套题时发现思路完全想错的场景并不多反而是边界条件处理不到位导致AC失败的占了大多数。常见的边界条件有这些输入的最小值、最大值、重复值、数组长度为1、目标值等于区间端点、结果超出int范围、模运算的中间结果可能为负等等。比如“有趣的数字”这道题如果数组里所有数字都相等最大差值对数不是0而是C(n,2)这个边界不处理好样例过得了一提交就挂。“素数对”里如果输入的数很小素数表可能为空也要专门处理。这些边界条件的核心是你不能假设输入是“合理”的而是要假设输入是“刁钻”的。一个工程师在写代码时有没有这种意识从笔试就能看出一大半。2.3 从笔试题看腾讯工程师的通用能力要求回过头来看这套题它其实在传递一个信号腾讯需要的是能独立解决问题、代码够稳的工程师。笔试题目不会故意刁难人但会把工程中“细节决定成败”的理念映射到算法题里。举个很典型的例子“geohash编码”这道题看起来就是一个二分模拟很多同学觉得简单但真正写起来区间更新、中点判断、二进制位拼接每一步都有出错的可能。这就像真实项目里对接一个外部接口流程看起来很简单但参数边界、异常处理、返回值格式任何一个细节没对齐都会出线上事故。所以这套题本质上是用算法题的方式考察候选人能不能像写生产代码一样去处理细节。3. 五道经典真题的完整复盘3.1 小Q的歌单组合计数与背包思想题目描述回忆版小Q有X首长度为A的歌曲和Y首长度为B的歌曲现在想用这些歌曲组成一个总长度恰好为K的歌单。每首歌最多被使用一次问一共有多少种组合方式。结果对1000000007取模。输入格式第一行输入K第二行输入A、X第三行输入B、Y。样例输入 5 2 3 3 3 输出 9思路分析这道题表面上是问组合数实际上可以转化为一个0-1背包问题。歌单的总长度K相当于背包容量每首歌相当于一个物品物品的“重量”就是歌曲长度每个物品只能用一次问恰好装满背包的方案数。定义dp[i]表示组成总长度为i的歌单的方案数初始dp[0]1。先处理第一组歌曲对于X首长度为A的歌每首歌都有“选”和“不选”两种选择所以从K到A倒序遍历执行dp[j] (dp[j] dp[j-A]) % MOD。倒序的原因是保证每首歌只被使用一次。处理完第一组再处理第二组长度为B的Y首歌。参考代码#include bits/stdc.h using namespace std; const int MOD 1000000007; int main() { int K; cin K; int A, X; cin A X; int B, Y; cin B Y; vectorlong long dp(K 1, 0); dp[0] 1; for (int i 0; i X; i) { for (int j K; j A; j--) { dp[j] (dp[j] dp[j - A]) % MOD; } } for (int i 0; i Y; i) { for (int j K; j B; j--) { dp[j] (dp[j] dp[j - B]) % MOD; } } cout dp[K] endl; return 0; }复杂度时间复杂度O(K*(XY))空间复杂度O(K)。当年这个数据范围完全够用。易错点忘记取模或者只在最后一步取模导致中间结果溢出。同一个歌曲组内部每首歌都要单独处理一次背包遍历不能直接把X首歌曲一次性做“完全背包”处理否则同一首歌会被重复使用。dp数组要用long long或者在中途取模因为组合数可能会非常大。这道题还有另一种做法就是直接组合数学计算C(X,i) * C(Y,j)枚举i和j满足iA jB K。两种做法都行但背包思路更容易扩展到类似场景。3.2 构造回文最长公共子序列的巧妙变形题目描述回忆版给定一个字符串s你可以删除其中任意数量的字符使得剩下的字符组成一个回文串。求最少需要删除多少个字符。样例输入abcda 输出2解释删除b和c得到“ada”为回文串或者删除c和d得到“aba”也是回文串。思路分析最少删除字符数等于字符串长度减去最长回文子序列的长度。而最长回文子序列有一个经典解法把原串反转得到逆序串求原串和逆序串的最长公共子序列LCS长度。为什么可以这样转化因为一个回文串从前往后读和从后往前读是一样的那么原串中能构成回文子序列的那些字符在逆序串中必然以相同顺序出现所以它们就是原串和逆序串的公共子序列。反过来任何一个原串和逆序串的公共子序列在形态上都对应一个回文子序列。因此最长回文子序列长度就是LCS的长度。参考代码#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { string t s; reverse(t.begin(), t.end()); int n s.size(); vectorvectorint dp(n 1, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } cout n - dp[n][n] endl; } return 0; }复杂度时间复杂度O(n^2)空间复杂度O(n^2)n是字符串长度。当年这道题的数据范围n通常在1000以内O(n^2)完全够用。也可以用滚动数组优化空间到O(n)但不是必须。易错点dp数组的边界要初始化为0否则第一行第一列会出问题。输入可能有多个测试用例要用while循环读取否则只处理一次就结束了。字符串可能为空这种情况下输出0。这道题的价值在于它展示了“回文”和“公共子序列”之间的等价关系。以后再遇到类似“删除最少字符构造回文串”的题目都可以直接套LCS的模板。3.3 有趣的数字排序与双指针统计题目描述回忆版小Q有n个数字从这n个数字中任选两个组成二元组问差值的绝对值最小有多少对差值的绝对值最大有多少对。输入第一行是n第二行是n个数字。样例输入 6 1 2 3 4 5 6 输出 1 1解释最小差值绝对值为1只有相邻的1,2等5对等一下这里需要仔细说明统计规则。实际输出取决于题目定义差值为1的对数一共有5对为什么样例输出是1呢这说明我记忆中的样例可能有偏差。所以我们直接按正确算法来推导最小差值对数需要统计所有差值等于最小值的二元组。排序后相邻两个数的差一定是候选最小差值。如果数组是1 2 3 4 5 6排序后相邻差都是1最小差值为1那么能组成差值1的相邻对是(1,2)、(2,3)、(3,4)、(4,5)、(5,6)一共5对。因此输出应该是5而不是1。所以这个样例并不是标准样例我在这里只是说明思路不要照搬样例。正确的题目考察点就比较清晰了思路分析第一步排序这是处理差值统计的常规操作。排序后最大差值一定出现在最大值和最小值之间但要注意差值最大的二元组有多少对取决于最小值的个数和最大值的个数也就是count(min) * count(max)。如果所有数字都相等那么最大值等于最小值此时最大差值对数就是C(n,2)。第二步求最小差值对数。排序后相邻两数的差值最小。先遍历一遍找到最小差值minDiff。如果minDiff等于0说明存在重复数字此时所有差值等于0的组合都来自重复数字内部统计每个重复数字分组的大小size累加C(size,2)。如果minDiff大于0直接遍历相邻元素统计差值等于minDiff的相邻对数即可因为此时每个元素最多同时属于两个相邻对而最小差值大于0保证不会出现跨多个元素的重复组合。参考代码#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long minCount 0, maxCount 0; // 最大差值对数 if (a[0] a[n - 1]) { maxCount 1LL * n * (n - 1) / 2; } else { int minValCnt 1, maxValCnt 1; for (int i 1; i n; i) { if (a[i] a[0]) minValCnt; else break; } for (int i n - 2; i 0; i--) { if (a[i] a[n - 1]) maxValCnt; else break; } maxCount 1LL * minValCnt * maxValCnt; } // 最小差值对数 int minDiff INT_MAX; for (int i 1; i n; i) { minDiff min(minDiff, a[i] - a[i - 1]); } if (minDiff 0) { int i 0; while (i n) { int j i; while (j n a[j] a[i]) j; int cnt j - i; minCount 1LL * cnt * (cnt - 1) / 2; i j; } } else { for (int i 1; i n; i) { if (a[i] - a[i - 1] minDiff) { minCount; } } } cout minCount maxCount endl; } return 0; }复杂度时间复杂度O(n log n)主要是排序开销。空间复杂度O(n)。易错点最大差值对数在“所有数字相等”时不是count(min)*count(max)而是C(n,2)。统计最小差值对数时如果minDiff为0不能直接遍历相邻对否则会漏掉“同一个数字出现多次任选两个都能构成差值0”的情况。计数可能超过int范围要用long long。这道题是典型的“排序分类讨论”题型看起来简单但要把各种情况分清楚并不容易。面试或者笔试中遇到这种题建议先在草稿纸上列出输入的所有可能情况再写代码。3.4 素数对筛选法在数论题中的应用题目描述回忆版给定一个正整数n求有多少对素数之和等于n。例如n10满足条件的素数对有37和55共2对。输入值范围不超过1000。思路分析这道题第一步用埃氏筛生成[2, n]范围内的素数表。然后枚举第一个素数i从2到n/2判断i和n-i是否都是素数如果是则计数加一。因为i从2到n/2枚举所以不会出现重复计数而且能正确统计55这类两个素数相同的组合。埃氏筛的原理是从2开始把所有2的倍数标记为合数然后找下一个未被标记的数再把它的倍数全部标记。筛完以后剩下的就是素数。这个算法是数论题的常客笔试中出现的频率很高。参考代码#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } int count 0; for (int i 2; i n / 2; i) { if (isPrime[i] isPrime[n - i]) { count; } } cout count endl; } return 0; }复杂度时间复杂度O(n log log n)空间复杂度O(n)。易错点筛法初始化时isPrime[0]和isPrime[1]必须手动置为false。内层循环从i*i开始标记避免重复标记这是埃氏筛的常见优化。n可能小于4这样连一对素数都组不出来直接输出0。输入可能有多个测试用例需要循环读取。这道题本身不难属于“送分题”但如果素数表生成错误或者边界没处理好就很容易变成“送命题”。3.5 geohash编码二分思想的工程化落地题目描述回忆版geohash编码常用于将经纬度转换为字符串其中一步是对纬度进行二进制编码。给定一个纬度值x-90到90之间采用如下规则编码初始区间为[-90, 90]取区间中点mid。如果x mid则当前位编码为1同时将区间左端点更新为mid否则当前位编码为0同时将区间右端点更新为mid。重复上述步骤直到生成6位二进制编码。输出这6位二进制编码。思路分析这道题是对二分查找的变形考察。每次循环确定一个二进制位同时把区间缩小一半。循环6次每次根据x与mid的大小关系确定当前位并更新区间。这里有一个值得注意的点题目中的边界条件是“x mid编码为1”还是“x mid编码为1”不同题目可能有不同定义。在写代码时要仔细读题不能想当然。参考代码#include bits/stdc.h using namespace std; int main() { double x; cin x; double left -90.0, right 90.0; int res 0; for (int i 0; i 6; i) { double mid (left right) / 2.0; if (x mid) { res res * 2 1; left mid; } else { res res * 2; right mid; } } for (int i 5; i 0; i--) { cout ((res i) 1); } cout endl; return 0; }复杂度时间复杂度O(1)因为编码长度固定为6位。空间复杂度O(1)。易错点如果直接按“res的二进制位”输出需要注意res的位数不满6位时要在前面补0。上面代码从5到0逐位输出可以保证输出6位。mid的类型要用double不能用int否则精度丢失会导致区间更新错误。区间端点的初始值要写对一个是-90一个是90写反了整套编码就完全错。这道题后面还可以继续扩展成完整的geohash编码包括经度二分和base32转码。如果在面试中遇到能顺带把这两步讲清楚会是不错的加分项。4. 笔试实操心得与避坑指南4.1 时间分配先拿基本分再攻难题我那会儿参加笔试最大的教训就是在第一道题上死磕太久结果后面几道基础题都没时间写。现在回想起来笔试编程题很忌讳“完美主义”。正确的时间分配策略是先把所有题目都读一遍判断难度从最简单的开始做保证会做的题全部拿到分再回头思考难题。这套题里“素数对”和“geohash编码”属于读完题就能写的类型“有趣的数字”属于中等难度“构造回文”和“小Q的歌单”需要一点思考时间。如果按题目顺序死磕很可能卡在某一题上。从易到难推进至少能保证3道题AC这已经能超过很多候选人了。4.2 输入输出与代码提交的易错点在线笔试的输入输出经常坑人常见情况包括输入包含多组数据、每组数据格式不同、输出结果之间需要换行、输出结果有额外空格会不会判错等。我的习惯是第一能用while(cin n)循环读取的一定用循环因为你不确定测试数据到底有几组。第二输出时严格按题目要求不要多输出任何提示文字比如“请输入”这类提示在OJ里会被当作错误输出。第三如果结果需要取模每一步计算都取模不要只在最后取一次。另外特别提醒一点C的运算符优先级很容易踩坑比如 (res i) 1 这里位移的优先级比按位与高所以可以不加括号但为了可读性最好还是加上。这种细节在笔试中不扣分但在代码review里一定会被同事提出来。4.3 设计测试用例把边界当作一等公民我在刷题复盘时发现很多同学写完代码只跑题目给的样例跑通了就提交结果一提交就挂。这是因为题目给的样例通常只覆盖最普通的情况不会帮你覆盖边界。我的建议是养成“边界测试”的习惯。每写完一道题至少测试这几种输入最小规模n1、最大规模n取题面上限、全相等、全不同、递增、递减、随机大数、结果溢出场景。用“构造回文”这道题举例至少要测空串、单字符、全相同字符、已经回文的串、完全逆序的串。用“有趣的数字”举例至少要测所有数字相同、有重复数字且最小差值为0、没有重复数字且最小差值大于0。把这些测试用例跑一遍代码的正确性基本就有保障了。很多同学觉得这是浪费时间但实际上花5分钟测边界比提交后挂掉再花10分钟找原因要划算得多。5. 从2016到今天的题目演进与备考建议5.1 校招笔试的出题趋势从纯算法到场景抽象最近的腾讯校招笔试编程题已经很少直接考“给你一个数组求如何如何”这种纯数学题了更多是把算法包装在业务场景里。比如让你设计一个推荐系统的排序逻辑或者模拟一个消息队列的消费顺序。场景化出题的本质没有变考察的还是同样的算法和数据结构但需要先读懂题意从场景中抽象出数学模型。这不是说2016年的题目就没有价值。恰恰相反基础算法是所有场景题的底座。你现在能把LCS、背包、二分、筛选法吃透到了场景题里照样能看懂题目背后的算法本质。5.2 九年后回头看这套题还能刷吗我的答案是当然能刷而且很适合作为校招笔试的入门训练。原因有三个第一题量适中五道题覆盖了五个常见考点刷一遍不会花太多时间第二难度曲线合理从简单到中等都有适合用来定位自己的薄弱环节第三网上题解和相关讨论非常多刷完以后很容易找到对应的复盘文章形成“做题-对答案-总结”的学习闭环。不少已经上岸的工程师在写面经时都会提到自己当年刷过这套题。它不一定是你拿到offer的决定性因素但一定是你建立笔试信心的重要起点。5.3 系统化备考路线与复盘方法如果你现在才开始准备校招笔试我的建议是不要只盯着某一年的题而是按知识点系统刷。比较稳妥的路线是先刷剑指Offer把高频面试题过一遍然后刷LeetCode Hot 100按数组、链表、树、动态规划、字符串、二分、贪心、数论这些专题逐个攻破最后再用“腾讯2016研发工程师编程题”这类真题卷做模拟检验整体水平。刷题过程中一定要做错题记录写清楚自己当时的错误思路和正确解法。不要追求刷题数量要追求每道题都能讲清楚两个问题为什么这样解是对的还有没有更好的解法。能把一道中等题说到让一个完全不懂的人听明白才说明你是真的掌握了。我自己的体会是面试官其实不指望你把每道题都写出最优解更看重的是你面对一个陌生问题时的分析过程和代码风格。这套2016年的题恰好就能帮你练出这种分析能力。当你把一道题从题意、思路、实现到测试完整走一遍你会发现大厂笔试并没有传说中那么可怕。
腾讯2016研发工程师编程题复盘：五道经典算法题详解与避坑指南
每年秋招季总会有同学翻出牛客网题库里“腾讯2016研发工程师编程题”这套经典卷子来刷。这套题在当年的校招笔试里算是比较有代表性的题量不大、难度不低、坑位不少考察的都是算法基本功和代码细节。九年过去腾讯笔试的题型已经换了好几轮但这套题依然被反复提及原因很简单——它的出题逻辑和考察点至今仍然是大厂笔试的主流。这篇文章我就以复盘的形式把当年这套题里频次较高、也比较有代表性的几道题目拿出来完整拆一遍从题目描述、解题思路到参考代码、易错点一套流程走下来。无论你现在是在备战校招还是单纯想看看大厂笔试到底考什么这篇都值得收藏。1. 2016年腾讯校招编程题全景回溯1.1 当年的校招背景与笔试环境2016年移动互联网还处在红利期腾讯作为头部大厂校招技术岗的简历投递量非常大。研发工程师岗位的笔试基本都走在线OJ系统当年的主流平台是牛客网。笔试环境没有现在这么花哨就是一套在线答题页面客观题和编程题混在一起编程题支持C/C、Java等主流语言每道题会给出输入输出样例但不会有太大范围的测试用例提示。这年研发岗笔试的编程题一般控制在3到5道整体难度比现在的“ACM风格”要温和一些但有一个特点非常明显题意不长坑不少。很多题看起来像是基础题实际上一旦考虑不周很容易出现部分样例通过、拿到0分或者一半分数的情况。也就是说这套题的核心筛选逻辑不是看你懂多少高级算法而是看你在有限时间内能不能写出健壮、正确、可运行的代码。1.2 研发工程师岗位的考察逻辑不挑方向不挑语言只挑基本功要注意的是2016年的“研发工程师”是统招岗位不区分前端、后端、客户端等具体方向。所有人都用同一套笔试题所以题目设置上有意避开特定业务场景集中在算法与数据结构的通用能力上。按今天的话说这套题就是一套“基本功体检”。基本功体现在三方面第一基础算法是否扎实比如排序、二分、动态规划、数论这些常见考点第二边界情况是否敏感比如数组为空、输入相等、结果溢出这类情况是否处理到位第三代码能不能在无IDE提示的情况下一次写对。这三点对应到日常工作里就是代码review时最常被挑出来的问题。所以这套题虽然叫“编程题”实际上考察的是一个工程师最底层的代码素养。1.3 题量分布与时间节奏从当年参加过笔试同学的反馈来看编程题普遍给60到90分钟题量看起来不大但每道题从读题、思考、编码到调试平均下来一道题15到20分钟。这意味着你基本没有时间回头改前面的题必须在第一次提交前尽可能保证正确性。这也解释了为什么那几年笔试成绩出来以后很多同学反映“都会做但就是没AC”。问题不出在思路而出在时间分配和代码细节上。比如组合计数忘取模、数组越界没检查、long long不够用、输入输出格式不对任何一种情况都会让你与满分失之交臂。后面我会专门列一节实操避坑这里先不展开。2. 核心考点与出题逻辑拆解2.1 基础数据结构与经典算法的权重把这套题刷完一遍你会发现它涉及的知识点集中在几个固定区域排序、二分、字符串处理、动态规划、简单数论。没有线段树没有网络流没有复杂的平衡树出题人刻意把题目控制在“科班学生大二大三就能掌握”的范围内。为什么这么设计我的理解是校招研发岗进来以后要参与真实项目开发考察的重点是你写业务代码、处理数据、排查问题的能力而不是让你入职第一天就去做算法研究。基础算法代表的是逻辑思维能力和代码实现能力。排序能不能写对、二分会不会死循环、动态规划的状态转移方程能不能理清这些直接反映一个人写代码的扎实程度。这也是为什么今天的大厂面试依然喜欢考基础题。2.2 边界条件大部分AC失败的原因我当年帮学弟学妹们复盘这套题时发现思路完全想错的场景并不多反而是边界条件处理不到位导致AC失败的占了大多数。常见的边界条件有这些输入的最小值、最大值、重复值、数组长度为1、目标值等于区间端点、结果超出int范围、模运算的中间结果可能为负等等。比如“有趣的数字”这道题如果数组里所有数字都相等最大差值对数不是0而是C(n,2)这个边界不处理好样例过得了一提交就挂。“素数对”里如果输入的数很小素数表可能为空也要专门处理。这些边界条件的核心是你不能假设输入是“合理”的而是要假设输入是“刁钻”的。一个工程师在写代码时有没有这种意识从笔试就能看出一大半。2.3 从笔试题看腾讯工程师的通用能力要求回过头来看这套题它其实在传递一个信号腾讯需要的是能独立解决问题、代码够稳的工程师。笔试题目不会故意刁难人但会把工程中“细节决定成败”的理念映射到算法题里。举个很典型的例子“geohash编码”这道题看起来就是一个二分模拟很多同学觉得简单但真正写起来区间更新、中点判断、二进制位拼接每一步都有出错的可能。这就像真实项目里对接一个外部接口流程看起来很简单但参数边界、异常处理、返回值格式任何一个细节没对齐都会出线上事故。所以这套题本质上是用算法题的方式考察候选人能不能像写生产代码一样去处理细节。3. 五道经典真题的完整复盘3.1 小Q的歌单组合计数与背包思想题目描述回忆版小Q有X首长度为A的歌曲和Y首长度为B的歌曲现在想用这些歌曲组成一个总长度恰好为K的歌单。每首歌最多被使用一次问一共有多少种组合方式。结果对1000000007取模。输入格式第一行输入K第二行输入A、X第三行输入B、Y。样例输入 5 2 3 3 3 输出 9思路分析这道题表面上是问组合数实际上可以转化为一个0-1背包问题。歌单的总长度K相当于背包容量每首歌相当于一个物品物品的“重量”就是歌曲长度每个物品只能用一次问恰好装满背包的方案数。定义dp[i]表示组成总长度为i的歌单的方案数初始dp[0]1。先处理第一组歌曲对于X首长度为A的歌每首歌都有“选”和“不选”两种选择所以从K到A倒序遍历执行dp[j] (dp[j] dp[j-A]) % MOD。倒序的原因是保证每首歌只被使用一次。处理完第一组再处理第二组长度为B的Y首歌。参考代码#include bits/stdc.h using namespace std; const int MOD 1000000007; int main() { int K; cin K; int A, X; cin A X; int B, Y; cin B Y; vectorlong long dp(K 1, 0); dp[0] 1; for (int i 0; i X; i) { for (int j K; j A; j--) { dp[j] (dp[j] dp[j - A]) % MOD; } } for (int i 0; i Y; i) { for (int j K; j B; j--) { dp[j] (dp[j] dp[j - B]) % MOD; } } cout dp[K] endl; return 0; }复杂度时间复杂度O(K*(XY))空间复杂度O(K)。当年这个数据范围完全够用。易错点忘记取模或者只在最后一步取模导致中间结果溢出。同一个歌曲组内部每首歌都要单独处理一次背包遍历不能直接把X首歌曲一次性做“完全背包”处理否则同一首歌会被重复使用。dp数组要用long long或者在中途取模因为组合数可能会非常大。这道题还有另一种做法就是直接组合数学计算C(X,i) * C(Y,j)枚举i和j满足iA jB K。两种做法都行但背包思路更容易扩展到类似场景。3.2 构造回文最长公共子序列的巧妙变形题目描述回忆版给定一个字符串s你可以删除其中任意数量的字符使得剩下的字符组成一个回文串。求最少需要删除多少个字符。样例输入abcda 输出2解释删除b和c得到“ada”为回文串或者删除c和d得到“aba”也是回文串。思路分析最少删除字符数等于字符串长度减去最长回文子序列的长度。而最长回文子序列有一个经典解法把原串反转得到逆序串求原串和逆序串的最长公共子序列LCS长度。为什么可以这样转化因为一个回文串从前往后读和从后往前读是一样的那么原串中能构成回文子序列的那些字符在逆序串中必然以相同顺序出现所以它们就是原串和逆序串的公共子序列。反过来任何一个原串和逆序串的公共子序列在形态上都对应一个回文子序列。因此最长回文子序列长度就是LCS的长度。参考代码#include bits/stdc.h using namespace std; int main() { string s; while (cin s) { string t s; reverse(t.begin(), t.end()); int n s.size(); vectorvectorint dp(n 1, vectorint(n 1, 0)); for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j], dp[i][j - 1]); } } } cout n - dp[n][n] endl; } return 0; }复杂度时间复杂度O(n^2)空间复杂度O(n^2)n是字符串长度。当年这道题的数据范围n通常在1000以内O(n^2)完全够用。也可以用滚动数组优化空间到O(n)但不是必须。易错点dp数组的边界要初始化为0否则第一行第一列会出问题。输入可能有多个测试用例要用while循环读取否则只处理一次就结束了。字符串可能为空这种情况下输出0。这道题的价值在于它展示了“回文”和“公共子序列”之间的等价关系。以后再遇到类似“删除最少字符构造回文串”的题目都可以直接套LCS的模板。3.3 有趣的数字排序与双指针统计题目描述回忆版小Q有n个数字从这n个数字中任选两个组成二元组问差值的绝对值最小有多少对差值的绝对值最大有多少对。输入第一行是n第二行是n个数字。样例输入 6 1 2 3 4 5 6 输出 1 1解释最小差值绝对值为1只有相邻的1,2等5对等一下这里需要仔细说明统计规则。实际输出取决于题目定义差值为1的对数一共有5对为什么样例输出是1呢这说明我记忆中的样例可能有偏差。所以我们直接按正确算法来推导最小差值对数需要统计所有差值等于最小值的二元组。排序后相邻两个数的差一定是候选最小差值。如果数组是1 2 3 4 5 6排序后相邻差都是1最小差值为1那么能组成差值1的相邻对是(1,2)、(2,3)、(3,4)、(4,5)、(5,6)一共5对。因此输出应该是5而不是1。所以这个样例并不是标准样例我在这里只是说明思路不要照搬样例。正确的题目考察点就比较清晰了思路分析第一步排序这是处理差值统计的常规操作。排序后最大差值一定出现在最大值和最小值之间但要注意差值最大的二元组有多少对取决于最小值的个数和最大值的个数也就是count(min) * count(max)。如果所有数字都相等那么最大值等于最小值此时最大差值对数就是C(n,2)。第二步求最小差值对数。排序后相邻两数的差值最小。先遍历一遍找到最小差值minDiff。如果minDiff等于0说明存在重复数字此时所有差值等于0的组合都来自重复数字内部统计每个重复数字分组的大小size累加C(size,2)。如果minDiff大于0直接遍历相邻元素统计差值等于minDiff的相邻对数即可因为此时每个元素最多同时属于两个相邻对而最小差值大于0保证不会出现跨多个元素的重复组合。参考代码#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long minCount 0, maxCount 0; // 最大差值对数 if (a[0] a[n - 1]) { maxCount 1LL * n * (n - 1) / 2; } else { int minValCnt 1, maxValCnt 1; for (int i 1; i n; i) { if (a[i] a[0]) minValCnt; else break; } for (int i n - 2; i 0; i--) { if (a[i] a[n - 1]) maxValCnt; else break; } maxCount 1LL * minValCnt * maxValCnt; } // 最小差值对数 int minDiff INT_MAX; for (int i 1; i n; i) { minDiff min(minDiff, a[i] - a[i - 1]); } if (minDiff 0) { int i 0; while (i n) { int j i; while (j n a[j] a[i]) j; int cnt j - i; minCount 1LL * cnt * (cnt - 1) / 2; i j; } } else { for (int i 1; i n; i) { if (a[i] - a[i - 1] minDiff) { minCount; } } } cout minCount maxCount endl; } return 0; }复杂度时间复杂度O(n log n)主要是排序开销。空间复杂度O(n)。易错点最大差值对数在“所有数字相等”时不是count(min)*count(max)而是C(n,2)。统计最小差值对数时如果minDiff为0不能直接遍历相邻对否则会漏掉“同一个数字出现多次任选两个都能构成差值0”的情况。计数可能超过int范围要用long long。这道题是典型的“排序分类讨论”题型看起来简单但要把各种情况分清楚并不容易。面试或者笔试中遇到这种题建议先在草稿纸上列出输入的所有可能情况再写代码。3.4 素数对筛选法在数论题中的应用题目描述回忆版给定一个正整数n求有多少对素数之和等于n。例如n10满足条件的素数对有37和55共2对。输入值范围不超过1000。思路分析这道题第一步用埃氏筛生成[2, n]范围内的素数表。然后枚举第一个素数i从2到n/2判断i和n-i是否都是素数如果是则计数加一。因为i从2到n/2枚举所以不会出现重复计数而且能正确统计55这类两个素数相同的组合。埃氏筛的原理是从2开始把所有2的倍数标记为合数然后找下一个未被标记的数再把它的倍数全部标记。筛完以后剩下的就是素数。这个算法是数论题的常客笔试中出现的频率很高。参考代码#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } int count 0; for (int i 2; i n / 2; i) { if (isPrime[i] isPrime[n - i]) { count; } } cout count endl; } return 0; }复杂度时间复杂度O(n log log n)空间复杂度O(n)。易错点筛法初始化时isPrime[0]和isPrime[1]必须手动置为false。内层循环从i*i开始标记避免重复标记这是埃氏筛的常见优化。n可能小于4这样连一对素数都组不出来直接输出0。输入可能有多个测试用例需要循环读取。这道题本身不难属于“送分题”但如果素数表生成错误或者边界没处理好就很容易变成“送命题”。3.5 geohash编码二分思想的工程化落地题目描述回忆版geohash编码常用于将经纬度转换为字符串其中一步是对纬度进行二进制编码。给定一个纬度值x-90到90之间采用如下规则编码初始区间为[-90, 90]取区间中点mid。如果x mid则当前位编码为1同时将区间左端点更新为mid否则当前位编码为0同时将区间右端点更新为mid。重复上述步骤直到生成6位二进制编码。输出这6位二进制编码。思路分析这道题是对二分查找的变形考察。每次循环确定一个二进制位同时把区间缩小一半。循环6次每次根据x与mid的大小关系确定当前位并更新区间。这里有一个值得注意的点题目中的边界条件是“x mid编码为1”还是“x mid编码为1”不同题目可能有不同定义。在写代码时要仔细读题不能想当然。参考代码#include bits/stdc.h using namespace std; int main() { double x; cin x; double left -90.0, right 90.0; int res 0; for (int i 0; i 6; i) { double mid (left right) / 2.0; if (x mid) { res res * 2 1; left mid; } else { res res * 2; right mid; } } for (int i 5; i 0; i--) { cout ((res i) 1); } cout endl; return 0; }复杂度时间复杂度O(1)因为编码长度固定为6位。空间复杂度O(1)。易错点如果直接按“res的二进制位”输出需要注意res的位数不满6位时要在前面补0。上面代码从5到0逐位输出可以保证输出6位。mid的类型要用double不能用int否则精度丢失会导致区间更新错误。区间端点的初始值要写对一个是-90一个是90写反了整套编码就完全错。这道题后面还可以继续扩展成完整的geohash编码包括经度二分和base32转码。如果在面试中遇到能顺带把这两步讲清楚会是不错的加分项。4. 笔试实操心得与避坑指南4.1 时间分配先拿基本分再攻难题我那会儿参加笔试最大的教训就是在第一道题上死磕太久结果后面几道基础题都没时间写。现在回想起来笔试编程题很忌讳“完美主义”。正确的时间分配策略是先把所有题目都读一遍判断难度从最简单的开始做保证会做的题全部拿到分再回头思考难题。这套题里“素数对”和“geohash编码”属于读完题就能写的类型“有趣的数字”属于中等难度“构造回文”和“小Q的歌单”需要一点思考时间。如果按题目顺序死磕很可能卡在某一题上。从易到难推进至少能保证3道题AC这已经能超过很多候选人了。4.2 输入输出与代码提交的易错点在线笔试的输入输出经常坑人常见情况包括输入包含多组数据、每组数据格式不同、输出结果之间需要换行、输出结果有额外空格会不会判错等。我的习惯是第一能用while(cin n)循环读取的一定用循环因为你不确定测试数据到底有几组。第二输出时严格按题目要求不要多输出任何提示文字比如“请输入”这类提示在OJ里会被当作错误输出。第三如果结果需要取模每一步计算都取模不要只在最后取一次。另外特别提醒一点C的运算符优先级很容易踩坑比如 (res i) 1 这里位移的优先级比按位与高所以可以不加括号但为了可读性最好还是加上。这种细节在笔试中不扣分但在代码review里一定会被同事提出来。4.3 设计测试用例把边界当作一等公民我在刷题复盘时发现很多同学写完代码只跑题目给的样例跑通了就提交结果一提交就挂。这是因为题目给的样例通常只覆盖最普通的情况不会帮你覆盖边界。我的建议是养成“边界测试”的习惯。每写完一道题至少测试这几种输入最小规模n1、最大规模n取题面上限、全相等、全不同、递增、递减、随机大数、结果溢出场景。用“构造回文”这道题举例至少要测空串、单字符、全相同字符、已经回文的串、完全逆序的串。用“有趣的数字”举例至少要测所有数字相同、有重复数字且最小差值为0、没有重复数字且最小差值大于0。把这些测试用例跑一遍代码的正确性基本就有保障了。很多同学觉得这是浪费时间但实际上花5分钟测边界比提交后挂掉再花10分钟找原因要划算得多。5. 从2016到今天的题目演进与备考建议5.1 校招笔试的出题趋势从纯算法到场景抽象最近的腾讯校招笔试编程题已经很少直接考“给你一个数组求如何如何”这种纯数学题了更多是把算法包装在业务场景里。比如让你设计一个推荐系统的排序逻辑或者模拟一个消息队列的消费顺序。场景化出题的本质没有变考察的还是同样的算法和数据结构但需要先读懂题意从场景中抽象出数学模型。这不是说2016年的题目就没有价值。恰恰相反基础算法是所有场景题的底座。你现在能把LCS、背包、二分、筛选法吃透到了场景题里照样能看懂题目背后的算法本质。5.2 九年后回头看这套题还能刷吗我的答案是当然能刷而且很适合作为校招笔试的入门训练。原因有三个第一题量适中五道题覆盖了五个常见考点刷一遍不会花太多时间第二难度曲线合理从简单到中等都有适合用来定位自己的薄弱环节第三网上题解和相关讨论非常多刷完以后很容易找到对应的复盘文章形成“做题-对答案-总结”的学习闭环。不少已经上岸的工程师在写面经时都会提到自己当年刷过这套题。它不一定是你拿到offer的决定性因素但一定是你建立笔试信心的重要起点。5.3 系统化备考路线与复盘方法如果你现在才开始准备校招笔试我的建议是不要只盯着某一年的题而是按知识点系统刷。比较稳妥的路线是先刷剑指Offer把高频面试题过一遍然后刷LeetCode Hot 100按数组、链表、树、动态规划、字符串、二分、贪心、数论这些专题逐个攻破最后再用“腾讯2016研发工程师编程题”这类真题卷做模拟检验整体水平。刷题过程中一定要做错题记录写清楚自己当时的错误思路和正确解法。不要追求刷题数量要追求每道题都能讲清楚两个问题为什么这样解是对的还有没有更好的解法。能把一道中等题说到让一个完全不懂的人听明白才说明你是真的掌握了。我自己的体会是面试官其实不指望你把每道题都写出最优解更看重的是你面对一个陌生问题时的分析过程和代码风格。这套2016年的题恰好就能帮你练出这种分析能力。当你把一道题从题意、思路、实现到测试完整走一遍你会发现大厂笔试并没有传说中那么可怕。
