后端面试走到第九期聊点不一样的。前面的几期把数组、链表、二叉树的基础题铺得差不多了这一期我想专门挑几类我在模拟面试和实际面试里反复见到、又有明确“区分度”的题目LRU 缓存设计、TopK 高频词、锯齿形层序遍历以及最长递增子序列的二分优化。这四道题代表了四种完全不同的考察方向LRU 是“工程结构设计”TopK 是“海量数据思维”锯齿形层序是“代码基本功”而最长递增子序列则是“动态规划 二分查找”的进阶组合。如果你正在准备后端岗位的算法面试这四道题值得单独写一版自己的模板答案。代码我会给完整可运行的 C 实现配合复杂度分析和面试官常见的追问点一次性讲透。1. 为什么还在更第九期后端面试算法的真实定位1.1 面试官到底在考什么很多同学准备后端面试时容易走两个极端一个极端是死磕 LRU、红黑树手写、跳表实现总觉得面试官是不是要从内存布局开始考另一个极端是觉得后端嘛主要考系统设计、MySQL、Redis 这些算法随便刷刷就行。我个人的看法是后端岗位的算法题重点从来不是“你背了多少题”而是看你有没有完整、严谨、能落地的代码能力。同样是写一个 LRU有的候选人能把双向链表节点的 prev、next 画得明明白白有的候选人写出来连边界条件都理不清。同样的差距在系统设计题里会被放大得更加离谱所以面试官其实是在用算法题做“低成本筛选”。所谓“大厂算法题”本质上是把真实工程问题抽象出来缓存淘汰是内存管理TopK 是日志排名和流量统计二叉树遍历是序列化、解析器、编译器的基本功最长递增子序列是动态规划的经典模型。这些题不是用来难为人的它们背后都有真实的应用场景。1.2 本期四道题的选择逻辑为什么偏偏选这几道因为它们在后端面试里出现频率足够高而且每一道都能展示一个独特的技能点题目核心技能点面试中常见变体LRU 缓存哈希表 双向链表O(1) 操作LFU、MySQL Buffer Pool 的 LRU 改进TopK 高频词堆的运用、比较器、海量数据思路前 K 大、流式 TopK、字典序排序规则锯齿形层序遍历BFS 模板、层数与方向控制按层输出、蛇形遍历、螺旋矩阵最长递增子序列动态规划转贪心 二分最长递减子序列、俄罗斯套娃信封问题你会发现这几类题目几乎不依赖“算法天赋”更依赖“熟练度和严谨度”。这类题非常适合作为刷题模板整理面试前拿出来快速看一遍能减少大量无谓的紧张。2. LRU 缓存设计后端系统设计的入场券2.1 题目原题与考点拆解原题描述通常是这样的请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 如果关键字不存在则插入该组「关键字-值」。 当缓存容量达到上限时它应该在写入新数据之前删除最久未使用的数据值从而为新的数据值留出空间。考点拆解下来就三个O(1) 查找、O(1) 插入、O(1) 删除。单纯数组做不到哈希表能做到 O(1) 查找但做不到 O(1) 删除最久未使用单纯链表能 O(1) 删除但做不到 O(1) 查找。所以必须把哈希表和双向链表结合起来。这个思路本身不难面试中最容易翻车的其实是“迭代器失效”和“节点删除顺序”。2.2 思路推导为什么是哈希表加双向链表先想一个问题如果只用哈希表容量满时要淘汰最早插入或最早访问的元素怎么找到这个元素用一个时间戳记录最后访问时间然后遍历哈希表找最小时间戳可以但时间复杂度是 O(n)完全不合格。那换个思路用一个双向链表保存访问顺序。每次访问某个数据就把它移动到链表头部链表尾部自然就是最久未被访问的数据。淘汰时直接删除链表尾部节点这就是 O(1) 了。但这时候要查找某个 key 对应的节点怎么办还是得遍历链表又退化成 O(n)。所以答案很清楚哈希表负责从 key 找到链表节点双向链表负责维护访问顺序。哈希表里的 value 不直接存数据而是存“链表节点指针”这样才能保证 O(1) 从 key 定位到节点。2.3 代码实现与关键细节直接上我比较常用的一版实现代码量不大但每个细节都有意义#include list #include unordered_map class LRUCache { private: int capacity; std::liststd::pairint, int cacheList; // pairkey, value std::unordered_mapint, std::liststd::pairint, int::iterator cacheMap; public: LRUCache(int capacity) : capacity(capacity) {} int get(int key) { auto it cacheMap.find(key); if (it cacheMap.end()) { return -1; } // 将访问的节点移到链表头部 int value it-second-second; cacheList.erase(it-second); cacheList.push_front({key, value}); cacheMap[key] cacheList.begin(); return value; } void put(int key, int value) { auto it cacheMap.find(key); // 如果 key 已存在先删除旧节点 if (it ! cacheMap.end()) { cacheList.erase(it-second); cacheMap.erase(key); } // 插入到头部 cacheList.push_front({key, value}); cacheMap[key] cacheList.begin(); // 容量超限时淘汰链表尾部节点 if (cacheMap.size() capacity) { auto last cacheList.back(); cacheList.pop_back(); cacheMap.erase(last.first); } } };有几个细节我想专门拎出来说为什么listpairint,int而不是listint因为链表尾部淘汰时需要知道被淘汰节点的 key才能去哈希表里删除对应的映射。如果链表只存 value那删除哈希表记录时就得再遍历哈希表找 key得不偿失。get操作也要更新访问顺序。很多人实现时会漏掉这个导致结果错误。LRU 里的“使用”包括读和写所以 get 时要把对应节点挪到链表头部。为什么cacheMap存的是list的迭代器而不是链表节点的裸指针因为std::list的插入删除不会让既有迭代器失效用迭代器安全又自然。面试里如果想炫技也可以手写双向链表节点用原始指针但我建议标准库用完再说。2.4 get、put 之外的追问“加分点”面试官一般不会只让你写完就算了后面经常会追加几个问题为什么链表用双向而不是单向因为删除节点需要知道前驱节点单向链表只能从头部遍历找前驱做不到 O(1)。为什么不用std::mapmap底层是红黑树本身也能做到 O(log n) 查找和删除但 LRU 要求 O(1)哈希表才满足。capacity 0怎么办这种情况题目通常不会出现但写代码时要有防御意识如果capacity 0任何put都不能真正缓存数据get 永远返回 -1。我一般会加一个成员变量初始化判断避免线程或空容器场景下 crash。如果改成 LFU 该怎么做LFU 需要按“访问频率”淘汰通常用两个哈希表维护“频率 - 链表”再维护一个最小频率变量。这个题目范围会大不少但思路仍然是“哈希表 双向链表”建议当面试试。提示手撕 LRU 时优先保证 erase 和 push_front 的顺序。正确顺序是先 remove 旧节点再 push_front 新节点。如果你先 push_front 再 erase迭代器指向的节点可能已经被改动容易把链表结构搞乱。3. TopK 高频词堆这种数据结构在后端场景的练兵场3.1 题目原题与常见变体TopK 类的题目在后端面试里有多常见不用我多说。最典型的版本是给定一个非空的单词列表返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同单词有相同出现频率按字母顺序排序。注意这里的“如果频率相同按字母顺序排序”这就是典型的“加分细节”。很多候选人会漏掉这个排序规则题目理解就没到位。这种题目在后端场景里对应的就是统计接口调用量最高的 TopK、日志里出现次数最多的错误码 TopK本质上都是一样的。3.2 复杂度账本排序不行堆才行最直觉的做法是什么统计完频率之后把整体排序然后取前 K 个。这个做法的复杂度是 O(n log n)对于 TopK 来说其实有点浪费。为什么因为题目只要“前 K 大”不需要关心 K 名之后的具体排名。对于海量数据——比如 1 亿条日志K 是 100——完整排序意味着要把 1 亿条数据全部排好序但真正用到的只有前 100 条。用堆的做法是维护一个大小为 K 的小根堆遍历所有元素时如果堆还没满就直接入堆如果堆满了就把当前元素和堆顶比较。堆顶是整个堆里“最不应该被保留”的元素——在 TopK 大里堆顶是最小值如果当前元素比堆顶大就替换堆顶否则跳过。最终堆里留下的就是最大的 K 个。复杂度是多少每个元素入堆或调整堆是 O(log K)总复杂度 O(n log K)。当 K 远小于 n 时O(n log K) 比 O(n log n) 好很多。关键是这种做法不需要把所有数据一次性加载到内存一条条读、一条条处理即可天然适合海量数据场景。3.3 代码实现与比较器陷阱这道题的 C 实现里最大的坑其实就是priority_queue的比较器。我直接贴一段可以跑通的完整代码#include queue #include string #include unordered_map #include vector using namespace std; struct Cmp { bool operator()(const pairint, string a, const pairint, string b) const { // 小根堆堆顶是频率最小、字典序最大的元素 if (a.first ! b.first) return a.first b.first; return a.second b.second; } }; vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring, int freq; for (const string w : words) { freq[w]; } priority_queuepairint, string, vectorpairint, string, Cmp pq; for (auto [word, count] : freq) { if (pq.size() k) { pq.push({count, word}); } else if (Cmp()({count, word}, pq.top())) { // 新元素比堆顶更值得保留时替换堆顶 pq.pop(); pq.push({count, word}); } } vectorstring result; while (!pq.empty()) { result.push_back(pq.top().second); pq.pop(); } reverse(result.begin(), result.end()); return result; }这里最关键的是比较器逻辑。C 的priority_queue默认是最大堆也就是说top()返回的是“比较器认为最大的那个元素”。为了把我们想要淘汰的元素放在堆顶比较器必须反着写a.first b.first会让频率小的元素优先级更高即堆顶是当前堆里频率最小的元素。a.second b.second会影响同频单词的顺序。当频率相同时为了让堆顶是“字典序最大”的元素这样淘汰时优先淘汰字典序大的自然就保住了字典序小的比较器要写a.second b.second。很多人在这一步翻车就是因为没搞清楚“比较器返回 true 时a 是被认为优先级更低的那个”。我建议在面试里手写这个比较器之前先在白板上写一行注释“堆顶应该是什么元素”再反推比较器方向。3.4 从 TopK 到海量数据落盘面试官通常还会追加一个场景问题如果这些单词不是存在于内存里而是分散在多个文件、上亿条记录怎么办核心思路是“分而治之 归并”。先对每个文件单独统计频率得到每个文件内部的 TopK然后再把所有文件的 TopK 汇总。汇总时有两种常用做法一种是维护一个全局大小为 K 的堆把所有文件 TopK 里的元素依次入堆另一种是如果单文件统计结果本身很大可以按 hash(word) 分桶将相同单词分到同一个桶里再对每个桶单独做 TopK最后汇总。还有一个容易忽略的点“流式 TopK”。数据不断产生不能全量落盘统计这时候就要用“衰减窗口”或“近似频率”的方案。这已经超出纯算法范围了但面试时能提到这些会很加分。毕竟后端面试主要不是考你能不能默写 priority_queue而是考你会不会在面对海量数据时做合理的取舍。4. 锯齿形层序遍历二叉树遍历的边界感从哪来4.1 题目原题与考点拆解二叉树遍历是面试的基础题但直白的层序遍历大家都会写于是面试官会加一点花样比如锯齿形层序遍历给定一个二叉树返回其节点值的锯齿形层序遍历。 即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。这类题看似只是层序遍历的变体但考察的能力其实很全面BFS 模板是否熟练、层数奇偶怎么处理、空树边界能不能兜住。而且它的代码框架和“按层返回”、“每层平均值”、“每层最大值”等题目完全一致一道题会了相当于会了一串题。4.2 单队列层序遍历的模板先回顾基础版层序遍历的模板。用队列保存当前层的节点每次处理一层之前先看queue.size()把这一层的节点全部取出同时在过程中把下一层的子节点入队。这个“先记录 size再遍历 size 次”的套路是二叉树按层处理的核心。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* que; que.push(root); while (!que.empty()) { int levelSize que.size(); vectorint level; for (int i 0; i levelSize; i) { TreeNode* cur que.front(); que.pop(); level.push_back(cur-val); if (cur-left) que.push(cur-left); if (cur-right) que.push(cur-right); } result.push_back(std::move(level)); } return result; }注意levelSize是在进入 for 循环前就固定好的不要在循环里直接用que.size()作为判断条件否则你在循环里不断入队子节点这个值会一直变完全乱套。4.3 锯齿形的两种实现姿势锯齿形是在按层遍历的基础上增加“方向交替”。我最推荐的一个版本正常按层收集结果然后根据当前层数决定是否反转。vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint result; if (root nullptr) return result; queueTreeNode* que; que.push(root); int level 0; while (!que.empty()) { int levelSize que.size(); vectorint path; for (int i 0; i levelSize; i) { TreeNode* cur que.front(); que.pop(); path.push_back(cur-val); if (cur-left) que.push(cur-left); if (cur-right) que.push(cur-right); } if (level % 2 ! 0) { reverse(path.begin(), path.end()); } result.push_back(std::move(path)); level; } return result; }这种实现的好处是思路直观、不容易漏层。缺点是有一次额外的reverse操作。但是面试时这个“反转”损耗完全不是重点重点是你能不能把方向控制写对。与其去写那种维护双向队列、左右交替取值的复杂版本我更建议先用这个简单版本让自己或者面试官一眼看明白。如果面试官要求不引入 reverse也可以用 deque 来模拟方向。从左到右时在尾部插入节点从右到左时在头部插入节点整体代码稍微绕一点但可以展示你对数据结构的熟练// 用 deque 实现方向交替其实就是路径构造方式的替换 vectorint level; // levelIndex 表示当前层该往哪个方向 if (level % 2 0) { level.push_back(cur-val); } else { level.insert(level.begin(), cur-val); }这个版本不需要对 vector 做整体反转但 insert 到头部本身是 O(n) 的所以两个版本理论上的性能差距没有你想的那么大。4.4 面试追问螺旋矩阵的迁移锯齿形层序遍历做完面试官很可能会顺着问一句“那如果给一个二维矩阵要求螺旋顺序输出呢”这就属于把二叉树遍历框架迁移到矩阵遍历。螺旋矩阵不能按“层”理解但可以按“圈”处理每轮从最外层到最内层分别输出上、右、下、左四条边。四条边的边界条件极其容易搞错这里分享我的小技巧把 (top, bottom, left, right) 四个边界变量写清楚每输出一条边就收缩一次只要left right top bottom就继续循环输出下边和左边之前必须先判断“只有一行”或“只有一列”的情况否则会重复输出元素。螺旋矩阵和锯齿形层序遍历虽然数据结构不同但考察的本质一致控制好方向、控制好边界、不要重复处理元素。这三个要点在后端代码里也随处可见比如矩阵索引计算、分页数据扫描其实都是边界处理。5. 最长递增子序列被问烂却写不对的 DP 进阶题5.1 题目原题与题目坑点给你一个整数数组 nums找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。 例如nums [10,9,2,5,3,7,101,18]最长递增子序列是 [2,3,7,101]长度为 4。这个题厉害的地方在于它只要你输出长度不要你输出序列本身。就因为这个“简化”很多人才会掉进坑里只想着最后几个字符忽略了中间状态的记录。之后还会有一个大坑仔细看题目说的是“子序列”不是“子数组”所以不需要连续。比如[4, 10, 4, 3, 8, 9]最长递增子序列是[4, 8, 9]或[3, 8, 9]长度是 3。如果理解成连续子序列会出现负值错误。5.2 朴素 DP先确保递归思维正确拿到这个题第一步不是背优化代码而是先能够写出朴素 DP。定义dp[i]表示以nums[i]结尾的最长递增子序列长度。那么所有j i且nums[j] nums[i]的位置都可以把nums[i]接到以nums[j]结尾的子序列后面。所以状态转移方程是dp[i] max(dp[j] 1) 对所有满足 j i 且 nums[j] nums[i] 的 j初始每个dp[i]至少是 1因为每个元素本身可以单独作为一个子序列。int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); int ans 1; for (int i 0; 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^2)。面试时先写出这个版本可以明确告诉面试官“这是一个朴素 DPO(n^2) 的复杂度接下来我用贪心加二分优化到 O(n log n)”。这一步非常重要因为面试官能看见你的思考路径而不是直接给你背出来一个优化代码。5.3 贪心加二分的为什么和怎么做O(n^2) 的 DP 在面对n 10^5的数据量时不够看优化思路是不再维护每个位置结尾的最长长度而是维护一个“尽可能小”的序列尾部。这个思路比较抽象我用一个直观解释对于相同长度的递增子序列如果它的尾部元素越小将来越容易在后面接上更多元素。所以我们在扫描数组时维护一个数组tails其中tails[k]表示长度为k1的递增子序列中尾部元素的最小值。每次扫描到一个新元素x在tails中找第一个大于等于x的位置把它替换成x。如果x比tails里所有元素都大就说明它可以接到当前最长的递增子序列后面于是长度加 1。这里用二分查找把查找过程降到 O(log n)整体复杂度变成 O(n log n)。对[10,9,2,5,3,7,101,18]手动推一遍步骤元素 xtails 变化说明110[10]初始29[9]9 10替换第一个≥9的位置32[2]2 9替换45[2, 5]5 2扩展结尾53[2, 3]3 替换第2个元素67[2, 3, 7]7 3扩展结尾7101[2, 3, 7, 101]扩展818[2, 3, 7, 18]18 替换101第 8 步结束后tails长度仍然是 4因此答案是 4。注意这里tails里保存的并不是真正的最长递增子序列只是“对应长度下最小尾部值”。它不能直接还原出完整序列但长度是对的。如果面试题要求还原序列本身这个贪心做法就不够了得用二分 DP 记录前驱数组的方式处理或者用线段树优化 DP复杂度仍然是 O(n log n)。5.4 代码实现与 lower_bound 的边界#include algorithm #include vector using namespace std; int lengthOfLIS(vectorint nums) { vectorint tails; for (int x : nums) { auto it lower_bound(tails.begin(), tails.end(), x); if (it tails.end()) { tails.push_back(x); } else { *it x; } } return tails.size(); }很多人会在这里搞混lower_bound和upper_bound。这个题的“严格递增”性质决定了只有当新元素严格大于当前最大尾部值时才能扩展如果有相等元素要用新元素替换旧元素而不是在它后面接一个相等的值。所以应该使用lower_bound找到第一个 x的位置。如果用upper_bound遇到等于的情况时会把位置推进到大于x的位置可能导致错误扩展最终长度错误。还有个比较隐蔽的细节lower_bound返回的是迭代器it tails.end()表示当前元素比所有已知尾部值都大也就是可以扩展长度。如果it不是结尾就只做替换不增加长度。这样长度就是tails.size()。注意这个优化实际上把“子序列”问题变成了“维护几个候选尾部”的贪心问题。它的正确性证明需要用到一种交换论证——任何更长序列都能与 tails 中某个相同长度的候选替换而不变坏。面试时不要求背严谨证明但至少要说清楚“尾部越小越优”的原因。6. 面试实战中的共性坑与复盘清单6.1 代码层面的高频翻车点速查表这几类题刷多了之后我总结出一个规律大部分人不缺思路缺的是细节。下面的坑都是实实在在在面试里出现过的问题坑点出现题目典型错误正确姿势迭代器失效LRU先 push_front 再 erase 旧节点先 erase 再 push_front或先记录迭代器容量为 0LRU不管 capacity 直接 put判断 capacity 0直接返回比较器方向TopK 堆小根堆实现成频率大的在堆顶明确堆顶是要被淘汰的元素再反推比较器字典序规则TopK 单词忘了同频按字典序题目描述里只要提到排序规则就必须在比较器里体现lower_bound/upper_bound 混用LIS相等元素导致错误扩展严格递增用 lower_bound 找第一个 x层数奇偶方向锯齿形层序第一层反转了建议 level 从 0 开始偶数层不反转空树/空数组全部题没判断 null 就开始取 root 或 nums[0]函数入口优先判空删除时更新哈希表顺序LRUpop_back 之后没删 map 里旧 key先记录尾节点的 key再 pop_back再 erase第八条特别重要。很多初版 LRU 代码里链表节点删了但哈希表里还留着那个 key导致下次 get 时根据迭代器去访问一个已经被删除的节点行为完全不可控。正确的顺序一定是“记录 key - 删除链表节点 - 删除哈希表映射”。6.2 面试过程中的策略性建议有几点基于实际面试过程的建议比代码本身更值得放在心上第一先讲思路再写代码。哪怕思路就是“我建一个哈希表和双向链表”也要在动笔之前说出来。很多面试官不会因为你代码写错直接否定反而更在意你有没有想清楚再动手。边说边写的好处是如果真的写错了面试官还能知道你的原始意图容易给你引导而不是直接下判断。第二一定要大声说出测试用例。写完代码之后主动说“我用几个用例验证一下比如输入空数组、输入只有一个元素、输入全部相等的情况”。这能非常明显地展示你的调试意识。我见过很多候选人代码几乎是对的但忘记验证边界结果面试官一提边界就慌反而把印象分丢了。第三复杂度的计算要脱口而出。LRU 的 get 是 O(1)put 也是 O(1)空间 O(capacity)TopK 是 O(n log K)空间 O(K)锯齿形层序是 O(n)空间 O(n)LIS 优化后是 O(n log n)空间 O(n)。这些数字如果还要现场推导说明刷题量不够面试时很容易被打折评价。第四如果真的不会也要展示思考过程。比如面试官问 LFU你可以说“LFU 比 LRU 多了一个频率维度我会用 freq 哈希表加双向链表来维护每个频率下的访问顺序再用一个最小频率变量记录淘汰目标”。哪怕这个思路不完全正确也远比沉默或直接说不会好得多。最后再分享一点个人经验第九期选到这四道题是刻意为之的。如果你看回这一期的所有代码会发现每道题其实都可以用很基础的 C 语法写完没有用到什么黑魔法。但恰恰是这些基础题目最能体现一个后端开发者的工程素养能不能在动手之前理清思路写代码时有没有注意边界能不能把复杂度和优化点讲清楚。我个人的体会是算法准备到后期做题数量和正确率之间的关联会变得很低。真正拉开差距的是“稳定输出”的能力。同一道题今天能写出隔一周还能不能立刻写出在面试高压下还能不能保持边界条件不出错。这就是为什么我不建议只刷新题难题而是建议每隔一段时间就回到这些核心模板题上重新写一遍。如果你正在准备后端面试不妨把这四道题当成一个自测小套件每道题写完自己计时控制在一道 15 到 20 分钟以内。写完再对照本文里的细节看看哪些地方丢了。这种练法比闷头再刷几百道新题要管用得多。