后端校招经典笔试题解析：用户喜好、手串与或与加的算法实战

在后端校招的题库里“字节跳动2018校招后端方向第四批”是一套绕不开的经典题。当年题目在牛客网上放出来之后讨论区热度一直很高不是因为它难到让人无从下手而是因为它把区间统计、环形数组、位运算这几个高频考点用非常贴近业务场景的方式串在了一起。哪怕放到现在来看这套题依然值得反复刷很多公司笔试题里都能看到它的影子。这套题适合谁正在准备秋招或春招的后端同学想系统过一遍经典笔试题型的选手以及从客户端、前端转后端、想快速补算法基础的朋友。题目本身不限制语言C、Java、Python都能写我下面用C来讲因为我当年笔试就是用C写的而且C在牛客这种在线评测环境里跑起来最稳不容易因为输入输出效率被卡。1. 这套题为什么值得反复刷1.1 2018年真题的出题风格与难度定位先说整体印象。这套题的题面都不长没有大段背景故事输入输出格式写得比较清楚想读懂题目不需要花太多时间。和现在动辄长篇材料题的笔试比起来反而显得清爽。难度属于中等偏上不是那种完全送分的签到题但也远远没到竞赛难度。它考的东西非常基础二分、贪心、位运算、线性扫描。但每一个基础点里都埋了一个小坑稍不注意就会踩进去。这种出题方式其实很考验基本功也很有大厂风格——不跟你绕弯子就看你对基础知识的掌握扎不扎实。我记得当年很多人考完吐槽“题目我都会就是没时间调完”。这句话其实点出了这套题的一个特点思路不难想但代码写起来要考虑很多边界条件尤其是下标处理和输入输出的细节。如果平时没有养成严谨的编码习惯考场上很容易在“看起来会”的题上翻车。1.2 流传最广的三道题与考点地图这套题里流传最广、讨论度最高的是三道题用户喜好、手串、或与加。它们分别对应三类非常典型的问题模型题目核心考点难度常见错误用户喜好哈希分组、二分查找中等直接暴力遍历导致超时手串环形数组、相邻位置判断中等漏掉首尾相接处的情况或与加位运算、二进制构造简单偏中没有推出 x y 0 的条件从这份考点地图能看出来这套题不考任何高级数据结构不考线段树、不考平衡树、不考图论算法。它考的就是你遇到问题之后能不能把问题抽象成最简单的模型然后用最朴素的算法解决它。后面我会逐题拆解把每道题的思考过程、代码实现和坑点都讲透。2. 用户喜好从暴力到二分一道典型的区间统计题2.1 题目原文与输入输出约定这道题的背景是推荐系统题面大概是这样的系统里有 n 个用户每个用户对某类文章有一个喜好度喜好度用一个整数表示。现在要回答 q 次查询每次查询给定 l、r、k问第 l 个到第 r 个用户中喜好度恰好为 k 的用户有多少个。输入格式第一行一个整数 n表示用户总数第二行 n 个整数依次表示第 1 个到第 n 个用户的喜好度第三行一个整数 q表示查询次数接下来 q 行每行三个整数 l、r、k。输出要求对每次查询输出一行答案。数据范围方面n 和 q 都能到 10 的 5 次方级别。这个数据规模直接决定了暴力解法走不通。2.2 暴力解法为什么过不了最直观的写法是每次查询都在数组里从 l 遍历到 r数一下有几个 a[i] 等于 k。这个思路没有错问题是复杂度。一次查询最坏要遍历 n 个元素q 次查询就是 O(nq) 的复杂度。当 n 和 q 都是 10^5 时总操作次数是 10^10用 C 跑也要几十秒。而在线评测系统一般只给 1 到 2 秒的运行时间所以暴力解法只能拿一小部分分数数据稍微大一点就直接超时。我当年第一次做这道题老实写了暴力结果只过了 30% 左右的 case。后来才意识到这题的考点根本不是“会不会遍历数组”而是“能不能想到用额外结构加速区间统计”。2.3 按喜好值分组加二分定位的 AC 思路既然暴力是遍历区间那我们就想办法不做遍历。观察一下查询的本质给定一个喜好值 k我们要知道在 [l, r] 这个下标范围内有哪些下标对应的位置是 k。顺着这个思路可以做一个预处理把每个喜好值 k 对应的所有用户下标存到一个数组里。比如喜好度为 5 的用户下标有 2、7、9、15那就存成 [2, 7, 9, 15]。这个数组天然是递增的因为我们是按下标顺序依次收集的。这样每次查询就变成了在喜好度 k 对应的下标数组里找到大于等于 l 的第一个位置和小于等于 r 的最后一个位置两个位置之间的元素个数就是答案。在有序数组里做这个操作只需要两次二分查找。配合哈希表整体结构就是 unordered_mapint, vector key 是喜好度value 是所有出现该喜好度的下标列表。查询时用 lower_bound 找第一个不小于 l 的位置用 upper_bound 找第一个大于 r 的位置两个迭代器相减就是 [l, r] 范围内的下标个数。时间复杂度上预处理是 O(n)每次查询是 O(log n)总复杂度 O((n q) log n)完全能在时限内跑完。2.4 参考代码C#include bits/stdc.h using namespace std; int main() { int n; scanf(%d, n); unordered_mapint, vectorint pos; for (int i 1; i n; i) { int val; scanf(%d, val); pos[val].push_back(i); } int q; scanf(%d, q); while (q--) { int l, r, k; scanf(%d%d%d, l, r, k); auto v pos[k]; auto it1 lower_bound(v.begin(), v.end(), l); auto it2 upper_bound(v.begin(), v.end(), r); printf(%d\n, (int)(it2 - it1)); } return 0; }代码很简单但有几个细节要特别留意。首先是下标从 1 开始因为题目里说的是“第 1 个用户到第 n 个用户”所以读入时从 i 1 开始 push_back。其次是如果 pos 里没有 k 这个 keyv 是空 vectorlower_bound 和 upper_bound 返回的都是 begin()相减结果是 0不会出问题。2.5 易错点与我的踩坑记录这道题我踩过的坑主要有两个。第一个是用 cin 和 cout 加 endl 来读输出导致在大数据量下超时。牛客的环境里 cin/cout 默认和 stdio 不同步性能会差不少。我后来养成了习惯笔试环境一律用 scanf/printf或者在一开始写上 ios::sync_with_stdio(false) 和 cin.tie(0)。第二个坑是有人会尝试用前缀和来做区间统计但喜好度的取值范围很大不可能开一个这么大的二维数组。这时候要果断放弃前缀和思路转向哈希加二分。还有一个很容易忽略的点如果要查询的喜好度 k 在 map 里不存在直接写 pos[k] 会自动插入一个空 vector虽然不影响答案但会白白增加一次哈希操作。数据量大时尽量用 find 或者直接引用能省一点是一点。3. 手串环形数组与颜色冲突检测3.1 题目理解与数据组织这道题的背景是装饰手串题面大概是这样的一条手串由 n 颗珠子串成环形每颗珠子上可以涂多种颜色颜色编号从 1 到 c。现在规定任意连续 m 颗珠子里同一种颜色最多只能出现一次否则这种颜色就算不合规。问总共有多少种颜色不合规。输入格式第一行三个整数 n、m、c接下来 n 行第 i 行第一个整数 num_i 表示第 i 颗珠子上颜色的种数后面跟 num_i 个整数表示具体颜色编号。这道题的关键在于我们不能真的去枚举所有长度为 m 的连续区间那样复杂度是 O(n * m)在 n 和 m 都很大的时候会超时。正确做法是换个角度与其看区间不如看同一种颜色的位置分布。对于某一种颜色假设它出现在第 2 颗、第 5 颗、第 9 颗珠子上。只要任意两颗之间的珠子距离小于 m就说明存在某个长度为 m 的连续区间同时包含这两颗珠子那这种颜色就一定不合规。所以问题变成了对每种颜色检查相邻出现位置的距离。3.2 核心判断逻辑为什么要检查首尾数据结构上用 vectorvector pos(c 1)pos[color] 存这个颜色出现的所有珠子编号。读入时按顺序 push所以每个颜色对应的位置数组天然是递增的。判断不合规的逻辑分两步。第一步遍历每种颜色内部的相邻位置。如果 pos[color][i] - pos[color][i - 1] 小于 m说明在普通线性排列下这两个珠子离得太近直接判定不合规。第二步也是最容易漏掉的一步检查首尾。因为手串是环形的最后一颗珠子和第一颗珠子在环上是相邻的。假设某种颜色出现在第 1 颗和第 10 颗珠子上n 10m 3。在线性排列下1 和 10 的距离是 9不小于 m看起来没问题。但这是在环形结构里第 9、第 10、第 1 颗珠子是连续的三个珠子如果这种颜色同时出现在第 10 颗和第 1 颗那它就违规了。所以必须额外检查 first n - last 是否小于 m。这里的 first 是这种颜色第一次出现的位置last 是最后一次出现的位置first n - last 计算的是从 last 绕回 first 的环形距离。这个首尾检查是整道题最大的坑。很多人在普通相邻检查上写了半天都能过唯独漏了这一步提交之后只能拿到一半分数。我当时第一次做也栽在这里调试了好久才发现是环形的问题。3.3 参考代码C#include bits/stdc.h using namespace std; int main() { int n, m, c; scanf(%d%d%d, n, m, c); vectorvectorint pos(c 1); for (int i 1; i n; i) { int num; scanf(%d, num); for (int j 0; j num; j) { int color; scanf(%d, color); pos[color].push_back(i); } } int ans 0; for (int col 1; col c; col) { if (pos[col].size() 1) { continue; } bool bad false; for (int i 1; i (int)pos[col].size(); i) { if (pos[col][i] - pos[col][i - 1] m) { bad true; break; } } if (!bad) { int first pos[col].front(); int last pos[col].back(); if (first n - last m) { bad true; } } if (bad) { ans; } } printf(%d\n, ans); return 0; }整体复杂度是 O(总颜色数)因为每个颜色出现的位置只遍历了一遍总长度等于所有珠子上颜色数量的总和读入时就把信息处理完了。3.4 变式与延伸这道题本质上是一个“检测区间冲突”的问题变式很多。比如改成求最长连续不冲突的子段长度或者在二维平面里检测点之间的距离核心思路都是一样的不要模拟整个区间而是把关注点放在“关键位置”之间的距离上。如果换个思路把环展开成 2n 的长度再用滑动窗口去检测其实也能做但需要处理下标取模的问题代码会复杂不少。笔试现场我推荐还是用记录位置的方式思路更直接代码也不容易出边界错误。4. 或与加位运算里的“填空”问题4.1 从等式到按位约束这道题题目很短给定 x 和 k求第 k 小的 y使得 x y x | y。输入第一行是一个整数 t表示数据组数接下来 t 行每行两个整数 x 和 k。拿到这种题目第一反应是把等式往二进制上想。x y 和 x | y 什么时候相等二进制加法里只有当某一位同时出现两个 1 时才会产生进位。一旦进位加法的结果就和按位或的结果不一样了因为按位或不会进位。所以要让等式成立必须保证 x 和 y 在任何一位上不同时为 1也就是 x y 0。换句话说y 只能使用 x 中为 0 的那些二进制位x 中为 1 的位y 必须为 0。比如 x 5二进制是 101。x 中为 0 的位是第 0 位、第 2 位、第 3 位、第 4 位依此类推。那么 y 可以取 0、1、4、5、8、9……这些数从小到大排列第 k 小的 y 就是我们要求的答案。4.2 第 k 小怎么构造把 k 的二进制填进 x 的空位现在问题变成了如何按从小到大的顺序生成所有满足条件的 y并取出第 k 个。观察一下规律。x 5二进制是 101空位是第 0 位、第 2 位、第 3 位……从小到大排列的可选 y 分别为y 0二进制 0空位都填 0y 1二进制 1第 0 位填 1y 4二进制 100第 2 位填 1y 5二进制 101第 0 位和第 2 位都填 1y 8二进制 1000第 3 位填 1y 9二进制 1001第 0 位和第 3 位填 1。留意一下这些 y 和 k 的对应关系。如果把“第 k 小的 y”里 k 的二进制写出来比如 k1 对应 y1k2 对应 y4k3 对应 y5k4 对应 y8。这里其实是在把 k 的二进制位依次填入 x 的空位。具体做法是从低位到高位扫描 x 的每一个二进制位。如果 x 的这一位是 1说明 y 的这一位只能用 0x 继续右移。如果 x 的这一位是 0说明这是一个空位可以把 k 的最低位填到这个位置然后 k 右移一位。当 k 变成 0 时剩下的空位全部填 0 即可。这就是一个“填空”的过程x 的二进制位决定哪些位置不能用剩下的空位用来安放 k 的二进制位。k 的二进制按从低到高的顺序填入这些空位得到的 y 就是第 k 小的那个。4.3 参考代码C#include bits/stdc.h using namespace std; int main() { int t; scanf(%d, t); while (t--) { long long x, k; scanf(%lld%lld, x, k); long long y 0; long long bit 1; while (k) { if ((x bit) 0) { if (k 1) { y | bit; } k 1; } bit 1; } printf(%lld\n, y); } return 0; }这段代码里bit 每次左移一位相当于从低位到高位逐个检查 x 的二进制位。当 x 的某一位是 0 时才把 k 的最低位移进来。循环结束条件是 k 变成 0此时所有需要填的位都填完了。注意这里要用 long long因为最终构造出来的 y 可能超过 int 的范围。x 本身是 int 范围但空位填到高位之后y 的值可能变得很大。还有一个细节容易让新手犯迷糊这段代码对应的是“第 k 小从 1 开始计数”的版本也就是说第 1 小的 y 是最小的正整数解。如果题目允许 y 0那答案会整体偏移一位。做这道题之前最好先用题目给的样例验证一下自己的下标定义是否跟出题人一致。4.4 位运算题的通用套路这类题其实有套路可循。看到 x y x | y 这种带加法和位运算的等式优先往二进制逐位分析去想把等式条件翻译成“哪些位能为 1、哪些位必须为 0”的约束。如果题目要求第 k 小或第 k 大的结果就思考能不能构造一个“模板”把 k 的二进制填进模板的空位里。类似的问题还有 x - y x ^ y、x y x ^ y 等变体本质上都是判断进位和异或的关系。平时刷题的时候可以把这类题放到一起总结比自己零散地做效率高很多。5. 实战复盘从这套题看校招笔试的得分策略5.1 做题顺序与时间分配我当年考这套题的时候时间是一个小时四道题不算宽裕。我的策略是拿到题先把所有题目快速扫一遍用一两分钟判断每道题的考点和难度然后决定做题顺序。我的顺序是先做或与加因为它条件最直接推出 x y 0 之后就是机械的构造不容易卡壳。然后做手串逻辑也相对清晰只要想到记录位置和首尾检查。最后做用户喜好因为二分和哈希的组合需要多写几行代码放在后面不容易被前面的题干扰。这个顺序不是绝对的但你至少应该做到把最有把握的题先做掉把容易拿的分先拿到手。不要在某一题上死磕超过 20 分钟尤其是当后面还有三道题等着你做的时候。5.2 “暴力先行”的保底策略笔试现场如果思路卡壳有一个很实用的保底策略先把暴力写法提交上去拿一部分分数再慢慢想优化。牛客这类在线评测系统一般是按测试用例给分的暴力解法虽然过不了大数据但小数据能全过能拿到不少保底分。用户喜好那道题如果当时没想到哈希加二分完全可以先写 O(nq) 的暴力提交一版至少保证有分。然后再去思考怎么优化。总比干瞪眼十几分钟最后连暴力都没写出来强。我当时见过很多同学就是因为在某道题上追求完美解法结果卡了半小时没写出来最后整场考试节奏全乱。记住笔试的目标是拿分不是写出最优解展览。5.3 从 2018 真题到今天这组题对现在准备校招的参考价值可能有人会觉得2018 年的题太老了现在笔试难度早就升级了刷这种老题还有意义吗我的看法是恰恰因为它老反而更有参考价值。现在各大厂的校招笔试题题量在减少但单题难度和数据规模都在上升也会掺杂更多工程向的场景题。可万变不离其宗核心考点依然是那些基础的东西二分、位运算、贪心、图论、动态规划。这套 2018 年的题把它最基础的几种模型考了一遍用来做“手感恢复剂”再合适不过。你会发现很多 2025、2026 年还在传的后端面试题清单里依然能看到用户喜好、手串这类题目的变体。只是数据范围变大了背景换成了更复杂的业务但底层解法没变。5.4 给今年准备校招的同学三条建议第一提前适应在线评测环境。牛客网和本地 IDE 最大的区别是输入输出格式、内存限制、编译选项都不一样。别在本地跑通了就以为万事大吉至少提前一周每天在牛客上练题刻意训练自己手写输入输出代码的能力。第二卡题果断跳过。一道题如果 20 分钟还没有清晰思路先标记一下做后面的题。回头如果有时间再想就算想不出来至少保证其他题做完了。第三刷题不能只背代码。每一种解法都要能讲清楚三件事为什么这样做是对的复杂度是多少边界条件在哪里。面试官最喜欢问的就是“你讲讲这道题的思路”如果你只能把代码默写出来但讲不清楚原理反而会扣分。最后再分享一点个人体会。这套题我当年是卡着时间线做完的印象最深的反而是用户喜好那道题——不是因为它难而是因为我当时想到了哈希却没想到用二分硬是写了个平衡树上去。后来被面试官点了一句这道题考的就是你有没有把问题化简的能力。如今回头再看这套题没有一道需要高级数据结构全是基础功。所谓校招笔试考的不是你会多少炫技的东西而是你能不能把最朴素的方法用对、用稳。这套题建议你认真刷刷完你会感谢自己。