算法与并发编码

这里是编码练习集合：先闭卷说明模式与不变量，再独立实现，最后用边界用例验证。主练 5 题提供完整 Java 17 实现与追问；30 题清单补足广度。SQL 手写题的主归属在 SQL手写笔试，此处只关联不复制讲解。

知识点回查索引

练习	对应知识点权威讲解
LRU Cache	并发综合：LRU 与限流器
令牌桶	并发综合：LRU 与限流器
生产者消费者	ThreadPoolExecutor、阻塞队列、拒绝策略、锁语义与公平性、AQS 与 Condition
Top K、滑动窗口、数组/二分/DP 等广度题	属通用算法练习，按下方清单的模式与不变量自查；涉及并发的回查上两行

一、数组、哈希与前缀（4 题）

#	题目	关键不变量 / 易错点	时间 / 空间
1	两数之和	哈希存“还差多少”；先查后存，避免同一个元素用两次	O(n) / O(n)
2	字母异位词分组	排序后的字符串或字符计数作为 key；key 必须与字符顺序无关	O(n·k log k) / O(n·k)
3	最长连续序列	只从“没有前驱”的数开始向右扩展；用 set 去重，避免重复扫描	O(n) / O(n)
4	除自身以外数组的乘积	左前缀积 × 右后缀积；不允许用除法，注意 0 和负数	O(n) / O(1) 额外

二、双指针（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
5	三数之和	排序后固定一个数，其余双指针；跳过重复元素，避免重复三元组	O(n²) / O(log n) 排序
6	盛最多水的容器	面积由较短边决定；每次移动较短边，才可能变大	O(n) / O(1)
7	接雨水	双指针维护左右最大高度；或单调栈按层计算	O(n) / O(1)

三、滑动窗口（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
8	无重复字符的最长子串	窗口内无重复；左边界只能右移，不能回退	O(n) / O(字符集)
9	最小覆盖子串	need/window 计数；先扩张到满足，再收缩找最小	O(n) / O(字符集)
10	找到字符串中所有字母异位词	固定长度窗口 + 计数；窗口长度等于模式串长度	O(n) / O(字符集)

四、二分查找（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
11	二分查找	统一区间定义（左闭右开或闭区间）；`mid` 防溢出，边界只收缩不震荡	O(log n) / O(1)
12	搜索旋转排序数组	先判断哪一半有序，再判断目标是否落在有序半边	O(log n) / O(1)
13	查找第一个和最后一个位置	两次二分：lower_bound 与 upper_bound；找不到要返回 [-1,-1]	O(log n) / O(1)

五、栈（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
14	有效的括号	左括号入栈，右括号与栈顶匹配；结束后栈必须为空	O(n) / O(n)
15	每日温度	单调递减栈存下标；当前温度更大时弹出并计算距离	O(n) / O(n)
16	柱状图中最大的矩形	单调递增栈 + 左右哨兵；弹出时用左右边界算宽度	O(n) / O(n)

六、链表（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
17	反转链表	三指针；改指针前先保存 next，返回 prev	O(n) / O(1)
18	合并两个有序链表	哨兵节点 + 双指针；最后接上未走完的剩余部分	O(m+n) / O(1)
19	环形链表 II	快慢指针相遇后，一个指针回到头部同速前进，相遇点即入口	O(n) / O(1)

七、堆与 Top K（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
20	合并 K 个升序链表	小顶堆存各链表头；空链表不入堆；也可两两分治	O(N log k) / O(k)
21	数组中的第 K 个最大元素	快速选择平均 O(n)，最坏 O(n²)；面试要说明退化风险	平均 O(n) / O(1)
22	前 K 个高频元素	先统计频率，再用小顶堆或桶排序；注意频率相同的情况	O(n log k) / O(n)

八、树（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
23	二叉树的层序遍历	队列 BFS；每层先固定 size，再处理该层	O(n) / O(w)
24	验证二叉搜索树	用上下界或中序遍历；不能只比较父子节点	O(n) / O(h)
25	二叉树的最近公共祖先	后序递归；左右子树都找到目标时，当前节点即 LCA	O(n) / O(h)

九、图与搜索（2 题）

#	题目	关键不变量 / 易错点	时间 / 空间
26	岛屿数量	遍历网格，遇到陆地计数并 DFS/BFS 淹没；入队时就标记，避免重复入队	O(mn) / O(mn) 上界
27	课程表	拓扑排序或 DFS 三色标记；有环则无法完成	O(V+E) / O(V+E)

十、动态规划（3 题）

#	题目	关键不变量 / 易错点	时间 / 空间
28	零钱兑换	`dp[amount]` 表示凑出该金额的最少硬币数；初始化 INF，注意无解	O(amount·n) / O(amount)
29	最长递增子序列	O(n²) DP 或 tails + 二分 O(n log n)；tails 不是真实子序列	O(n log n) / O(n)
30	编辑距离	`dp[i][j]` 由插入、删除、替换三种转移；可用滚动数组	O(mn) / O(min(m,n))

30 题可实施规格与答案

以下题号对应上方全清单。字符串题默认 ASCII（除非改题明确要求 Unicode 码点），整数计算使用足够宽的类型；输入非法时先返回参数错误，不把溢出当成算法结果。树示例按层序表示，null 表示空子树，节点身份与节点值分开。验证时先跑所列确定样例，再按每题给出的独立对照方法检查小规模输入。U90 已将 30 题参考实现与独立对照全部实跑（30/30 通过，退出码 0）：入口 python3 labs/coding-practice-u90/run.py，见实验说明。实现级修正两处：searchRange 上界查找不能把 target+1 夹到 Integer.MAX_VALUE（MAX 值自身漏检）；LCA 层序建树的节点下标按实际节点数取（含 null 占位跳过）。

1. 两数之和

题意与约束：给整数数组 a 和 target，返回两个不同下标，使两值之和为目标；保证恰好一组解，2≤n≤100000，值及目标绝对值不超过10⁹。

答案：从左到右查 target-a[i] 是否在“此前值→下标”哈希表中，命中即返回，否则存当前值。先查后存保证不复用自身，复杂度O(n)/O(n)。

边界与验证：[2,7,11,15],9 → [0,1]；[3,3],6 → [0,1]。用双循环枚举不同下标作为独立对照，核对返回下标合法、不同且和正确；覆盖负数与目标为0。

2. 字母异位词分组

题意与约束：输入至多10000个仅含小写英文字母的字符串，每串长0～100，输出按字符多重集合相同分组，组间和组内顺序不限。

答案：每串计算26项频次数组，以含分隔符的完整计数元组为键归组，不能拼接无分隔数字造成碰撞。时间O(总字符数)，空间O(总字符数+26n)。

边界与验证：["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]；两个空串应同组。将各串排序作为另一种键，归一化组内/组间顺序后比较，保留重复字符串数量。

3. 最长连续序列

题意与约束：给无序整数数组，返回最长连续整数集合长度，不要求在原数组中相邻；0≤n≤100000，允许重复及32位极值。

答案：去重到set，仅从没有前驱的值开始向右探测，记录最大长度，每值只被扩展一次，平均O(n)/O(n)。比较前驱/后继时使用long或显式保护MIN/MAX，避免整数回绕。

边界与验证：[100,4,200,1,3,2,2] → 4，[] → 0。将去重值排序并逐段计数作为对照；覆盖MIN、MAX同时存在时不应误连。

4. 除自身以外数组的乘积

题意与约束：给长度2～100000的整数数组，返回每位置除自身外所有值的乘积，禁止除法；约定全部前后缀积与输出均在long范围内。

答案：输出先写左侧前缀积，再从右向左乘滚动后缀积；更新顺序必须先使用后更新后缀。O(n)时间、除输出外O(1)空间。

边界与验证：[1,2,3,4] → [24,12,8,6]，[-1,0,3] → [0,-3,0]，两个0则全0。小数组用逐位置排除自身的乘法枚举对照，覆盖负数与单个0。

5. 三数之和

题意与约束：给长度0～3000整数数组，返回所有和为0的不重复值三元组，同一位置只能使用一次；值绝对值≤10⁹，结果顺序不限。

答案：排序，固定i后在右侧用双指针，和小则left右移，大则right左移；命中跳过相同值，固定值也去重。求和用long，O(n²)时间、排序空间依实现。

边界与验证：[-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]]，[0,0,0,0] → [[0,0,0]]。小数组三重枚举下标，将三元组排序后放set，与输出集合比较。

6. 盛最多水的容器

题意与约束：给2～100000条非负高度竖线，横坐标为下标，任选两线求最大盛水面积；高度≤10⁹，面积返回long，不包含中间线的实体占用。

答案：两端夹逼，面积为距离乘较小高度；移动较短边，因为保留短边而缩小宽度不可能提高面积。两边相等时移动任一端即可，O(n)/O(1)。

边界与验证：[1,8,6,2,5,4,8,3,7] → 49，[0,0] → 0。小数组枚举所有线对算面积，比较long结果，覆盖等高、单调和大面积。

7. 接雨水

题意与约束：给宽度均为1的非负柱高数组，求能存雨水总量；长度0～100000，高度≤10⁹，总量用long。

答案：双指针维护左右已见最高值，处理当前高度较小一侧，其可蓄水由该侧最高值减当前高度决定，再移动。也可先建左右最大值数组，O(n)时间，双指针O(1)额外空间。

边界与验证：[4,2,0,3,2,5] → 9，单调数组和长度不足3均0。逐位置独立扫描左右最大值，累加 max(0,min(L,R)-h[i]) 对照小数组，覆盖平顶盆地。

8. 无重复字符的最长子串

题意与约束：给长度0～100000的ASCII字符串，返回无重复连续子串的最大长度，而非子序列长度。

答案：记录各字符最近下标，left=max(left,last[c]+1)，每轮更新长度与last；左端不能因窗口外旧字符回退。O(n)时间、O(128)空间；完整实现见下方主练题。

边界与验证："abcabcbb" → 3，"abba" → 2，空串0。小串枚举所有子串用集合检查唯一性，比较最大长度，特别测重复字符全相同。

9. 最小覆盖子串

题意与约束：给ASCII串s与t，返回s中覆盖t全部字符及其重复次数的最短连续子串；各长≤100000，t为空或无解时返回空串，同长取最左。

答案：need计数，扩右端直到全部需求满足，再逐步缩左端更新最佳区间；移除导致计数不足时重新扩展。每端最多走n次，O(|s|+|t|)/O(128)。

边界与验证："ADOBECODEBANC","ABC" → "BANC"，"a","aa" → ""，"aa","aa" → "aa"。小串枚举子串并按多重计数判覆盖，按长度/起点选最优对照。

10. 找到所有字母异位词

题意与约束：给小写字母串s与非空p，返回s中长度等于p且字母计数相同的子串起点；长度≤100000，输出递增下标。

答案：维护固定长度|p|的26维计数，右端加字符，窗口过长移左端，计数相等则收录起点。每轮比较26项仍为O(n)时间、O(26)额外空间。

边界与验证："cbaebabacd","abc" → [0,6]，"abab","ab" → [0,1,2]，p长于s返回空。逐个截取窗口并排序，与排序p比较作为独立对照，检查重叠匹配。

11. 二分查找

题意与约束：输入严格递增整数数组与目标，命中返回下标，否则-1；长度0～100000，不允许线性扫描作正式解。

答案：用 [lo,hi)，mid值小于目标则lo=mid+1，否则hi=mid，收敛后检查lo<n且值相等。O(log n)/O(1)，完整lower_bound实现见备用题。

边界与验证：[-1,0,3,5,9,12],9 → 4，目标2返回-1。用线性查找对照空、单元素、两端命中和两端外目标，并检查每步区间严格缩小。

12. 搜索旋转排序数组

题意与约束：严格递增且无重复的数组旋转任意次，查目标下标或-1；长度0～100000。有重复是另一个规格，不能声称仍始终O(log n)。

答案：二分时若左半有序，判断目标是否位于其闭区间，决定舍右或舍左；否则同样判断有序右半。使用一致的闭区间更新，O(log n)/O(1)。

边界与验证：[4,5,6,7,0,1,2],0 → 4，目标3返回-1。对长度≤20的递增数组枚举全部旋转点和所有存在/不存在目标，与线性查找比较。

13. 查找第一个和最后一个位置

题意与约束：给非递减整数数组及target，返回连续相等段的左右端下标；无解返回[-1,-1]，长度≤100000。

答案：分别找首个 >=target 和首个 >target，若lower不存在则无解，否则答案为[lower,upper-1]。不要用target+1替代upper搜索，以免MAX溢出，O(log n)/O(1)。

边界与验证：[5,7,7,8,8,10],8 → [3,4]，空数组无解，全相等返回[0,n-1]。线性扫描收集全部目标位置作为对照，覆盖Integer.MAX_VALUE。

14. 有效的括号

题意与约束：串中仅含()[]{}，长0～100000，判断括号是否类型匹配且正确嵌套；空串有效。

答案：左括号入栈，右括号要求栈非空且弹出相应左括号，遍历完栈为空才有效。O(n)/O(n)，长度奇数可提前失败。

边界与验证："([]){}" → true，"([)]" → false，"]" → false。短串反复删除相邻合法括号对，最终为空则有效，用此方法对照；检查遗漏未闭合左括号。

15. 每日温度

题意与约束：给每日整数温度，返回每天下次出现严格更高温度所需天数，无则0；长度0～100000，允许等温。

答案：递减栈存还未找到更热日期的下标，当前温度严格大于栈顶温度就弹出并写 i-top；当前下标入栈。每下标进出一次，O(n)/O(n)。

边界与验证：[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]，[30,30] → [0,0]。向右逐日扫描首个严格更高值作为小数组对照。

16. 柱状图最大矩形

题意与约束：给宽度1的非负柱高，返回完全包含于柱形中的最大矩形面积；长0～100000，高度≤10⁹，结果用long。

答案：单调递增栈保存下标，遍历追加虚拟0，当前高度更低时弹出h，以当前i和新的栈顶作为两边界算 h*(i-left-1)；栈底虚拟-1。O(n)/O(n)，相等高度按一致策略处理。

边界与验证：[2,1,5,6,2,3] → 10，[2,2] → 4，空0。枚举每个区间并维护最小高度乘宽度对照，覆盖单调增减和全0。

17. 反转链表

题意与约束：输入无环单链表头，原地反转全部next并返回新头；节点数0～100000，值可重复，不创建替代节点。

答案：prev初始null、cur=head，先保存next，令cur.next=prev，再向前推进两个指针，最终返回prev。O(n)/O(1)，完整Java见备用题。

边界与验证：1→2→3 → 3→2→1，null返回null。保存原节点身份列表，反转后按逆序检查同一批节点、无环；反转两次恢复原节点顺序，覆盖单节点。

18. 合并两个有序链表

题意与约束：两条无环、互不共享节点的非递减单链表，重用节点合并并返回头；总节点≤100000，等值时先取左链表保持稳定。

答案：哨兵加尾指针，比较两头选较小节点连接，移动对应头和tail；一边空后连接另一边余段。O(m+n)/O(1)，完整Java见备用题。

边界与验证：[1,2,4],[1,3,4] → [1,1,2,3,4,4]，一条空则返回另一条。把两输入值合并排序作为值对照，再核对输出节点身份集合恰等于输入且无环。

19. 环形链表II

题意与约束：链表next可能成环，返回入环节点身份，无环返回null；至多100000个不同节点，不按相同节点值判环。

答案：快指针每步2、慢每步1，遇null无环；相遇后让一指针回头，两者各步1，再次相遇即入口。由 2d-d=k·环长 推导，O(n)/O(1)。

边界与验证：3→2→0→-4且尾连到值2节点，返回该节点；自环返回自己。用IdentityHashMap记录第一次重复访问节点作对照，覆盖无环和入口为头。

20. 合并K个升序链表

题意与约束：给k条无环、互不共享节点的有序链表，总节点N≤100000，允许空链表；重用全部节点输出非递减链表。

答案：将各非空头放小顶堆，弹最小接到tail，再把其next放堆，直至堆空。比较器避免整数相减溢出；O(N log k)时间、O(k)空间，完整Java见备用题。

边界与验证：[[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]，k=0返回null。收集全部输入值排序作对照，检查节点数量、身份与无环。

21. 第K个最大元素

题意与约束：无序整数数组a，1≤k≤n≤100000，重复值按各次出现计数，返回排序后从大到小第k项，允许原地修改输入。

答案：快速选择定位升序下标n-k，分区后只搜索包含目标的一侧；随机或三路分区改善重复值表现，平均O(n)、最坏O(n²)。需确定最坏界时可用大小k的小顶堆O(n log k)。

边界与验证：[3,2,3,1,2,4,5,5,6],4 → 4。复制数组排序取n-k作对照，覆盖k=1、k=n、全等和有序输入，分别说明所选解法的复杂度保证。

22. 前K个高频元素

题意与约束：给整数数组及 1≤k≤不同值数，返回频率最高的k个值；同频按数值小者优先以使输出可核验，输入长度≤100000。

答案：哈希计数，维护“最差候选在堆顶”的k堆，频率低更差，同频值大更差；遇更好候选替换，最后按频率降序/值升序输出。O(n+d log k)/O(d+k)，主练实现如同频任意则需调整比较器。

边界与验证：[1,1,1,2,2,3],2 → [1,2]，[2,1],1 → [1]。将完整频次表按上述规则排序取前k作对照；覆盖负数、全等和k=d。

23. 二叉树层序遍历

题意与约束：给最多100000节点的普通二叉树，返回从根到叶逐层、同层从左到右的值列表，空树返回空列表。

答案：队列BFS，每层先固定size，只弹出该数量节点并依次入左、右孩子；O(n)时间，队列O(w)空间，输出另计O(n)，完整Java见备用题。

边界与验证：[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]。用DFS携带深度并先左后右收集作独立对照，覆盖单链与满树。

24. 验证二叉搜索树

题意与约束：普通二叉树节点值为32位整数，判断是否满足每个节点左子树全部严格小于、右子树全部严格大于；不允许重复，空树有效，节点≤100000。

答案：迭代中序遍历，维护前一个实际访问值，必须严格递增；用hasPrev标志避免MIN作哨兵误判。O(n)时间、O(h)栈空间，不只比较父子值。

边界与验证：[5,1,4,null,null,3,6] → false，[2,1,3] → true。另用long开区间上下界递归检查小树作对照，覆盖重复值与MIN/MAX；深树正式实现用迭代避免栈溢出。

25. 二叉树最近公共祖先

题意与约束：普通二叉树、两个实际存在的节点引用p/q，允许p=q，返回同时为两者祖先的最深节点，祖先包含自身；最多100000节点。

答案：后序搜索，当前为p/q直接返回，左右都找到则当前是LCA，否则返回非空一边。O(n)/O(h)，极深树用显式栈；若不保证存在须增加存在性验证，不能照搬此解。

边界与验证：树[3,5,1,6,2,0,8,null,null,7,4]中p=5/q=4返回节点5，p=5/q=1返回3。建立父指针表，比较两条到根路径的共同后缀作对照，覆盖p=q。

26. 岛屿数量

题意与约束：矩形0/1网格，1为陆地，仅上下左右相连，求连通块数；行列各≤1000，允许原地将已访问1改0，空网格返回0。

答案：扫描每格，遇1计数并BFS淹没整个分量，入队时即标记避免重复。O(mn)时间、队列最坏O(mn)空间；不能一般性宣称O(min(m,n))。

边界与验证：["11000","11000","00100","00011"] → 3，["10","01"] → 2。用并查集合并右/下相邻陆地，统计根数作独立对照；测全水、全陆与单行。

27. 课程表

题意与约束：课程编号0～V-1，先修对 [a,b] 表示先修b才能修a，判断能否修完全部；V≤100000、E≤200000，可有重复边与自环。

答案：建b→a邻接表和入度，所有0入度课程入队，每取出一门就减少后继入度；处理数等于V则可完成，否则有环。重复边需在邻接与入度保持一致，O(V+E)/O(V+E)。

边界与验证：V=2,[[1,0]] → true，加[0,1]则false，[[0,0]]也false。小图枚举全部课程排列检查是否存在满足先修的排列作对照，覆盖孤立点。

28. 零钱兑换

题意与约束：无限使用给定正整数硬币，求凑成amount的最少枚数，无解-1；amount为0～10000，硬币至多100种，面额为正数，可重复。

答案：dp[0]=0，其余初始化amount+1，按金额从1向上，对coin≤金额取 min(dp[x],dp[x-coin]+1)。最终INF返回-1；O(amount·种数)/O(amount)，非正面额须拒绝。

边界与验证：[1,2,5],11 → 3，[2],3 → -1，空硬币/amount0返回0。小amount用从0出发每次加一枚硬币的BFS层数作对照，别用贪心处理[1,3,4],6。

29. 最长递增子序列

题意与约束：给长度0～100000整数数组，求严格递增子序列长度，可不连续；重复值不增加长度。

答案：tails[len-1]保存该长度可能的最小末尾值，对每个x二分首个>=x的位置替换，找不到则追加。tails不保证是原数组中的真实子序列；O(n log n)/O(n)。

边界与验证：[10,9,2,5,3,7,101,18] → 4，[2,2] → 1，空0。小数组用 dp[i]=1+max(dp[j],j<i且a[j]<a[i]) 的O(n²)实现对照，覆盖逆序。

30. 编辑距离

题意与约束：两ASCII串各长0～2000，插入、删除、替换单字符的代价都为1，求将word1变为word2的最小总代价；不包含交换操作。

答案：dp[i][j]为两前缀的距离，边界dp[i][0]=i、dp[0][j]=j；字符相同取左上，否则取左、上、左上最小值加1。可滚动两行，O(mn)时间、O(min(m,n))空间。

边界与验证："horse","ros" → 3，"","abc" → 3，相同串0。长度≤4且字母表仅a/b时，用枚举一次编辑操作的BFS搜索到目标作独立对照（将搜索长度限制在两输入最大长度内），并核对对称性与长度差下界。

按主题验收

主题阶段	题目范围	重点	验收
基础线性结构	1～10	哈希、双指针、滑动窗口	能说明窗口/指针移动的条件，并处理重复值和边界
搜索与指针结构	11～19	二分、栈、链表	能定义区间不变量，手写链表操作并覆盖边界
优先级与遍历	20～27	堆、树、图	能选择合适遍历方式，并解释复杂度与 visited 时机
状态转移	28～30	动态规划	能定义状态、边界和转移，并用小样例验证

薄弱题按掌握情况回访：遮住答案重新推导，能解释关键不变量并通过边界用例后，再转向下一类题。

单题记录模板

text

题号/题名：
模式：
第一次是否独立完成：
思路（不看题解写）：
卡点 / bug：
时间 / 空间复杂度：
边界用例：空、单元素、重复、极端值、有序/逆序

验收标准

[ ] 30 题至少 24 题能独立完成，剩余 6 题能讲清思路和复杂度；
[ ] 前 10 题必须手写并通过边界用例；
[ ] 至少 5 题能独立完成“思路 + 代码 + 测试”，并解释复杂度与关键边界；
[ ] 每一类模式能说出适用条件、反例和常见坑；
[ ] 错题按掌握情况回访，不重复犯同一个边界错误。

主练 5 题：完整实现与追问

代码前先确定输入约定、操作不变量与复杂度，完成后检查正常、边界和异常用例。分布式限流还需处理热点、故障降级与跨节点一致性。

Java 17 示例；尚未逐一编译验证，可用 javac --release 17 编译并运行各题自测。

题 1：LRU Cache（HashMap + 手写双向链表）

思路：HashMap 负责 O(1) 定位节点，双向链表负责 O(1) 调整顺序和淘汰。使用两个哨兵节点 head/tail，省去空指针判断。

不变量：

map 中的每个 key 都恰好对应链表中的一个节点，map.size() 等于链表长度且不超过 capacity；
head.next 是最近使用的节点，tail.prev 是最久未使用的节点；
节点中必须同时存 key，淘汰尾节点时才能从 map 中删除。

java

import java.util.HashMap;
import java.util.Map;

/** LRU：HashMap 定位节点 + 双向链表维护访问顺序（head 侧最新，tail 侧最旧）。 */
public class LRUCache {
    private static final class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head = new Node(0, 0); // 哨兵：head.next 为最近使用
    private final Node tail = new Node(0, 0); // 哨兵：tail.prev 为最久未使用

    public LRUCache(int capacity) {
        if (capacity < 0) throw new IllegalArgumentException("capacity < 0");
        this.capacity = capacity;
        this.map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        Node node = map.get(key);
        if (node != null) {           // 已存在：更新值并提升
            node.value = value;
            moveToHead(node);
            return;
        }
        if (map.size() == capacity) { // 满：先淘汰尾部
            Node lru = tail.prev;
            unlink(lru);
            map.remove(lru.key);      // 节点里存 key 才能反查删除
        }
        Node fresh = new Node(key, value);
        addAfterHead(fresh);
        map.put(key, fresh);
    }

    private void moveToHead(Node node) { unlink(node); addAfterHead(node); }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.prev = node.next = null;
    }

    private void addAfterHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    public static void main(String[] args) {
        LRUCache c = new LRUCache(2);
        c.put(1, 1); c.put(2, 2);
        check(c.get(1) == 1);   // 访问 1，顺序变为 1,2
        c.put(3, 3);            // 淘汰 2
        check(c.get(2) == -1);
        c.put(1, 10);           // 更新已有 key
        check(c.get(1) == 10);
        c.put(4, 4);            // 淘汰 3
        check(c.get(3) == -1 && c.get(4) == 4);

        LRUCache one = new LRUCache(1);
        one.put(1, 1); one.put(2, 2);
        check(one.get(1) == -1 && one.get(2) == 2);

        LRUCache zero = new LRUCache(0);
        zero.put(1, 1);
        check(zero.get(1) == -1);
        System.out.println("LRUCache OK");
    }

    static void check(boolean ok) { if (!ok) throw new AssertionError(); }
}

复杂度：get/put 时间 O(1)，空间 O(capacity)。

边界用例：容量为 0（put 不生效）、容量为 1（每次 put 新 key 都淘汰）、更新已有 key（值更新且提升为最新、不触发淘汰）、get 也要提升顺序、淘汰后再次访问返回 -1。

追问答案：

为什么不用单向链表？ 删除任意节点需要前驱，单向链表找前驱是 O(n)。
生产中用什么？ LinkedHashMap(capacity, 0.75f, true) 加重写 removeEldestEntry 即可实现 LRU；更推荐 Caffeine（W-TinyLFU，命中率更高，支持过期和统计）。
如何线程安全？ 最简单是方法加 synchronized 或一把 ReentrantLock，但 get 也会修改链表，读写锁无效，全局锁成为瓶颈。优化方向：分段（按 key hash 分 N 个独立 LRU，牺牲全局精确 LRU）；近似 LRU（读操作只记录到缓冲区，异步批量调整顺序，Caffeine 的做法）；Redis 的近似 LRU 是随机采样淘汰。命中统计用 LongAdder 避免热点竞争。
为什么不会丢节点？ unlink 和 addAfterHead 都成对修改前后指针，moveToHead 先摘再插；淘汰时先 unlink 再 map.remove，两处结构同步更新。

题 2：Top K 高频元素（小顶堆 + 桶排序）

思路一（堆）：先统计频次，再维护大小为 k 的小顶堆，堆顶是当前候选中频次最小的，新元素进入后若超过 k 就弹出堆顶。

思路二（桶）：频次的取值范围是 1..n，以频次为下标建桶，从高频桶向低频桶收集 k 个。

java

import java.util.*;

public class TopKFrequent {
    /** 方案一：频次 Map + 容量为 k 的小顶堆，O(n log k) 时间，O(n) 空间。 */
    public static int[] topKByHeap(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        k = Math.min(k, freq.size());
        // 堆顶是当前 k 个里频次最小的；频次相同按值降序出堆，保证结果确定
        PriorityQueue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(
                (a, b) -> !a.getValue().equals(b.getValue())
                        ? Integer.compare(a.getValue(), b.getValue())
                        : Integer.compare(b.getKey(), a.getKey()));
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            heap.offer(e);
            if (heap.size() > k) heap.poll();
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) res[i] = heap.poll().getKey(); // 频次从高到低
        return res;
    }

    /** 方案二：桶排序，下标为频次，O(n) 时间，O(n) 空间。 */
    @SuppressWarnings("unchecked")
    public static int[] topKByBucket(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) return new int[0];
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.merge(x, 1, Integer::sum);
        List<Integer>[] buckets = new List[nums.length + 1]; // 频次最大为 n
        freq.forEach((num, f) -> {
            if (buckets[f] == null) buckets[f] = new ArrayList<>();
            buckets[f].add(num);
        });
        k = Math.min(k, freq.size());
        int[] res = new int[k];
        int idx = 0;
        for (int f = nums.length; f >= 1 && idx < k; f--) {
            if (buckets[f] == null) continue;
            for (int num : buckets[f]) {
                if (idx == k) break;
                res[idx++] = num;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        check(Arrays.equals(topKByHeap(nums, 2), new int[]{1, 2}));
        int[] b = topKByBucket(nums, 2);
        check(b.length == 2 && b[0] == 1 && b[1] == 2);
        check(topKByHeap(nums, 0).length == 0);
        check(topKByHeap(new int[0], 3).length == 0);
        check(topKByHeap(nums, 10).length == 3);   // k 大于不同元素数
        check(topKByBucket(nums, 10).length == 3);
        check(topKByHeap(new int[]{5}, 1)[0] == 5);
        System.out.println("TopKFrequent OK " + Arrays.toString(topKByHeap(new int[]{4, 4, 5, 5, 6}, 2)));
    }

    static void check(boolean ok) { if (!ok) throw new AssertionError(); }
}

复杂度：

方案	时间	空间	适用
小顶堆	O(n log k)	O(n + k)	k 远小于 n、数据可流式处理
桶排序	O(n)	O(n)	n 不太大，可一次性装入内存
全排序	O(n log n)	O(n)	朴素方案，作为对比

边界用例：k=0 或数组为空返回空数组；k 大于不同元素数时返回全部；频次相同时堆方案按值排序保证结果确定（题目没要求时要先和面试官确认）。

追问答案：

为什么是小顶堆不是大顶堆？ 大顶堆要放入全部 m 个不同元素，O(m log m)；小顶堆只保留 k 个，堆顶就是“淘汰门槛”。
还有更快的方法吗？ 快速选择（quickselect）平均 O(n)，最坏 O(n²)。
数据流或数据量超过内存怎么办？ 按 key 哈希分片到多台机器/多个文件，各自求局部 Top K 后归并（同一个 key 只会落在一个分片，所以局部结果可以直接合并）；只需近似结果时用 Count-Min Sketch + 小顶堆，或 Space-Saving 算法，内存固定。滑动时间窗口的热点统计可以按分钟分桶聚合。

题 3：最长无重复子串（滑动窗口）

思路：窗口 [left, right] 内无重复。右指针每前进一步，如果当前字符上次出现的位置在窗口内，就把左边界移到该位置的下一位。

不变量：窗口内无重复字符；left 只增不减（abba 用例专门验证这一点：读到最后的 a 时，其上次位置 0 已在窗口外，不能把 left 拉回 1）。

java

import java.util.HashMap;
import java.util.Map;

public class LongestSubstring {
    /** ASCII 版本：数组记录字符最后出现位置，O(n) 时间，O(1)（128）空间。 */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.isEmpty()) return 0;
        int[] last = new int[128];
        java.util.Arrays.fill(last, -1);
        int best = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (c >= 128) throw new IllegalArgumentException("仅支持 ASCII，非 ASCII 请用 codePoint 版本");
            if (last[c] >= left) left = last[c] + 1; // 左边界只前进不后退
            last[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    /** Unicode 版本：按 code point 处理代理对（如 emoji），HashMap 记录位置。 */
    public static int lengthOfLongestSubstringUnicode(String s) {
        if (s == null || s.isEmpty()) return 0;
        int[] cps = s.codePoints().toArray();
        Map<Integer, Integer> last = new HashMap<>();
        int best = 0, left = 0;
        for (int right = 0; right < cps.length; right++) {
            Integer prev = last.put(cps[right], right);
            if (prev != null && prev >= left) left = prev + 1;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        check(lengthOfLongestSubstring("abcabcbb") == 3);
        check(lengthOfLongestSubstring("bbbbb") == 1);
        check(lengthOfLongestSubstring("pwwkew") == 3);
        check(lengthOfLongestSubstring("") == 0);
        check(lengthOfLongestSubstring("abba") == 2);   // 验证左边界不回退
        check(lengthOfLongestSubstring(" ") == 1);
        check(lengthOfLongestSubstringUnicode("a😀b😀") == 3);
        check(lengthOfLongestSubstringUnicode("abba") == 2);
        System.out.println("LongestSubstring OK");
    }

    static void check(boolean ok) { if (!ok) throw new AssertionError(); }
}

复杂度：时间 O(n)，每个字符最多被右指针访问一次；空间 ASCII 版 O(128)，Unicode 版 O(min(n, 字符集大小))。

边界用例：空串、单字符、空格、全相同字符、abba（左边界不回退）、含 emoji 的字符串（charAt 会把代理对拆成两个 char，需要按 code point 处理）。

追问答案：

为什么不用 Set 加 while 收缩？ 也可以，时间仍是 O(n)（每个字符最多进出一次），但记录最后位置可以让 left 直接跳转，常数更小。
如果要求返回子串本身？ 在更新 best 时同时记录 start = left，最后 substring(start, start + best)。
字符集假设怎么说？ 先问输入范围：只含 ASCII 用 int[128]，扩展 ASCII 用 int[256]，任意 Unicode 用 HashMap 加 code point。

题 4A：生产者消费者

方案一：ReentrantLock + 两个 Condition

java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/** 方案一：ReentrantLock + 两个 Condition 的有界缓冲区，支持关闭。 */
public class BoundedBuffer<T> {
    private final Deque<T> queue = new ArrayDeque<>();
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
    private boolean closed = false;

    public BoundedBuffer(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
        this.capacity = capacity;
    }

    /** 阻塞放入；关闭后放入抛异常；响应中断。 */
    public void put(T item) throws InterruptedException {
        if (item == null) throw new NullPointerException();
        lock.lockInterruptibly();
        try {
            while (queue.size() == capacity && !closed) notFull.await(); // while 防虚假唤醒
            if (closed) throw new IllegalStateException("buffer closed");
            queue.addLast(item);
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    /** 阻塞取出；关闭且已取空时返回 null，作为消费者退出信号。 */
    public T take() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (queue.isEmpty() && !closed) notEmpty.await();
            if (queue.isEmpty()) return null; // closed 且无剩余
            T item = queue.removeFirst();
            notFull.signal();
            return item;
        } finally {
            lock.unlock();
        }
    }

    /** 带超时的 offer，生产环境常用于避免无限阻塞。 */
    public boolean offer(T item, long timeout, TimeUnit unit) throws InterruptedException {
        if (item == null) throw new NullPointerException();
        long nanos = unit.toNanos(timeout);
        lock.lockInterruptibly();
        try {
            while (queue.size() == capacity && !closed) {
                if (nanos <= 0) return false;
                nanos = notFull.awaitNanos(nanos);
            }
            if (closed) return false;
            queue.addLast(item);
            notEmpty.signal();
            return true;
        } finally {
            lock.unlock();
        }
    }

    public void close() {
        lock.lock();
        try {
            closed = true;
            notEmpty.signalAll(); // 唤醒所有等待者让其退出
            notFull.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public static void main(String[] args) throws Exception {
        BoundedBuffer<Integer> buf = new BoundedBuffer<>(4);
        int producers = 3, perProducer = 1000, consumers = 2;
        AtomicInteger consumed = new AtomicInteger();
        AtomicInteger sum = new AtomicInteger();
        Thread[] ps = new Thread[producers];
        Thread[] cs = new Thread[consumers];
        for (int i = 0; i < producers; i++) {
            ps[i] = new Thread(() -> {
                try {
                    for (int j = 1; j <= perProducer; j++) buf.put(j);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
            ps[i].start();
        }
        for (int i = 0; i < consumers; i++) {
            cs[i] = new Thread(() -> {
                try {
                    Integer v;
                    while ((v = buf.take()) != null) { // 处理放在锁外
                        consumed.incrementAndGet();
                        sum.addAndGet(v);
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
            cs[i].start();
        }
        for (Thread p : ps) p.join();
        buf.close();
        for (Thread c : cs) c.join();
        int expectedSum = producers * perProducer * (perProducer + 1) / 2;
        if (consumed.get() != producers * perProducer || sum.get() != expectedSum) throw new AssertionError();
        System.out.println("BoundedBuffer OK consumed=" + consumed.get());
    }
}

要点：

notFull、notEmpty 两个条件队列，生产者只唤醒消费者，消费者只唤醒生产者，避免 synchronized + notifyAll 唤醒同类线程的无效竞争；
条件检查必须用 while：存在虚假唤醒，并且被唤醒后条件可能已被其他线程抢先改变；
lockInterruptibly() 和 await() 都响应中断，捕获后恢复中断标志 Thread.currentThread().interrupt()；
关闭语义：close() 后生产者不能再放入，消费者取完剩余元素后拿到 null 退出，signalAll 唤醒所有等待者；
业务处理（如远程调用）必须在 take() 返回后、锁外执行。

方案二：BlockingQueue + 毒丸关闭

java

import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

/** 方案二：BlockingQueue + 毒丸（Poison Pill）关闭。生产代码优先选这一种。 */
public class BlockingQueueDemo {
    private static final Integer POISON = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(16);
        int producers = 2, consumers = 3, perProducer = 500;
        AtomicInteger consumed = new AtomicInteger();
        ExecutorService pool = Executors.newFixedThreadPool(producers + consumers);
        CountDownLatch producersDone = new CountDownLatch(producers);

        for (int i = 0; i < producers; i++) {
            pool.submit(() -> {
                try {
                    for (int j = 0; j < perProducer; j++) {
                        // 用带超时的 offer 暴露背压，而不是无限阻塞
                        if (!queue.offer(j, 1, TimeUnit.SECONDS)) {
                            throw new IllegalStateException("queue full too long");
                        }
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                } finally {
                    producersDone.countDown();
                }
            });
        }
        for (int i = 0; i < consumers; i++) {
            pool.submit(() -> {
                try {
                    while (true) {
                        Integer v = queue.take();
                        if (POISON.equals(v)) break; // 每个消费者吃一颗毒丸后退出
                        consumed.incrementAndGet();
                    }
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }
        producersDone.await();
        for (int i = 0; i < consumers; i++) queue.put(POISON); // 生产完再投毒丸，保证不丢数据
        pool.shutdown();
        if (!pool.awaitTermination(5, TimeUnit.SECONDS)) pool.shutdownNow();
        if (consumed.get() != producers * perProducer) throw new AssertionError(consumed.get());
        System.out.println("BlockingQueueDemo OK consumed=" + consumed.get());
    }
}

两种方案对比：生产代码优先用 ArrayBlockingQueue/LinkedBlockingQueue，JDK 实现经过充分验证（ArrayBlockingQueue 内部就是一把 ReentrantLock 加 notEmpty/notFull 两个 Condition，LinkedBlockingQueue 用 putLock/takeLock 两把锁提高并发）。手写版用于展示对 AQS 条件队列的理解。毒丸要在所有生产者结束后投递，数量等于消费者数，否则会有消费者永远阻塞或数据未消费完就退出。

复杂度：put/take 均摊 O(1)；空间 O(capacity)。

追问答案：

为什么不用 if？ 虚假唤醒；以及多消费者时，A 被唤醒前元素已被 B 取走，if 会导致对空队列 removeFirst 抛异常。
signal 和 signalAll 怎么选？ 每次只放入/取出一个元素时 signal 足够且更高效；关闭时状态对所有等待者都变了，必须 signalAll。
队列满了怎么办？ 阻塞（背压）、超时 offer 失败后降级、丢弃或落盘；线程池的拒绝策略是同一类问题。

题 4B：线程安全令牌桶

思路：不启动后台线程定时加令牌，而是在每次获取时按“距上次补充的时间差 × 速率”惰性补充，上限为容量。capacity 决定突发量，rate 决定长期平均速率。

java

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.LongSupplier;

/**
 * 线程安全令牌桶：惰性补充（按时间差计算），不需要后台定时线程。
 * capacity 控制突发量，ratePerSecond 控制平均速率。
 */
public class TokenBucket {
    private final long capacity;
    private final double tokensPerNano;
    private final LongSupplier clock;          // 可注入，便于单测
    private final ReentrantLock lock = new ReentrantLock();
    private double tokens;
    private long lastRefillNanos;

    public TokenBucket(long capacity, double ratePerSecond) {
        this(capacity, ratePerSecond, System::nanoTime);
    }

    TokenBucket(long capacity, double ratePerSecond, LongSupplier clock) {
        if (capacity <= 0 || ratePerSecond <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        this.tokensPerNano = ratePerSecond / TimeUnit.SECONDS.toNanos(1);
        this.clock = clock;
        this.tokens = capacity;                // 初始满桶，允许启动突发
        this.lastRefillNanos = clock.getAsLong();
    }

    public boolean tryAcquire() { return tryAcquire(1); }

    public boolean tryAcquire(int permits) {
        if (permits <= 0 || permits > capacity) throw new IllegalArgumentException("permits");
        lock.lock();
        try {
            refill();
            if (tokens >= permits) {
                tokens -= permits;
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    private void refill() {
        long now = clock.getAsLong();          // nanoTime 单调，不受系统时间回拨影响
        long elapsed = now - lastRefillNanos;
        if (elapsed > 0) {
            tokens = Math.min(capacity, tokens + elapsed * tokensPerNano);
            lastRefillNanos = now;
        }
    }

    public static void main(String[] args) throws Exception {
        AtomicLong fake = new AtomicLong(0);
        TokenBucket b = new TokenBucket(5, 10, fake::get); // 突发 5，平均 10/s
        int ok = 0;
        for (int i = 0; i < 10; i++) if (b.tryAcquire()) ok++;
        if (ok != 5) throw new AssertionError("burst " + ok);
        fake.addAndGet(TimeUnit.MILLISECONDS.toNanos(100));  // 100ms 补 1 个
        if (!b.tryAcquire() || b.tryAcquire()) throw new AssertionError("refill");
        fake.addAndGet(TimeUnit.SECONDS.toNanos(10));        // 长时间空闲也不超过容量
        ok = 0;
        for (int i = 0; i < 10; i++) if (b.tryAcquire()) ok++;
        if (ok != 5) throw new AssertionError("cap " + ok);

        // 并发：固定时钟下 8 线程争抢，成功数必须恰好等于容量
        AtomicLong frozen = new AtomicLong(0);
        TokenBucket cb = new TokenBucket(100, 1, frozen::get);
        AtomicInteger success = new AtomicInteger();
        Thread[] ts = new Thread[8];
        for (int i = 0; i < ts.length; i++) {
            ts[i] = new Thread(() -> { for (int j = 0; j < 1000; j++) if (cb.tryAcquire()) success.incrementAndGet(); });
            ts[i].start();
        }
        for (Thread t : ts) t.join();
        if (success.get() != 100) throw new AssertionError("concurrent " + success.get());
        System.out.println("TokenBucket OK");
    }
}

复杂度：tryAcquire O(1)，空间 O(1)。

边界用例：初始满桶允许突发 capacity 个；空闲很久后令牌不超过容量；permits 大于容量直接拒绝（否则永远拿不到）；并发 8 线程争抢，在时钟冻结时成功数必须精确等于容量。

追问答案：

为什么用 System.nanoTime()？ 单调递增，不受 NTP 校时或人工改系统时间影响；currentTimeMillis 回拨会导致补充为负或爆发。测试时注入假时钟。
为什么加锁而不用 CAS？ 状态有两个字段（tokens、lastRefill），需要一起原子更新；可以把二者打包进一个不可变对象用 AtomicReference CAS 重试，低竞争时性能更好，高竞争时自旋浪费 CPU。单机 QPS 在百万以下时，一把锁的开销通常可以接受。
令牌桶和漏桶、滑动窗口的区别？ 令牌桶允许突发、限制平均速率；漏桶以恒定速率流出、平滑流量，不允许突发；固定窗口有边界突刺问题，滑动窗口更精确但内存开销更大。Guava RateLimiter 是令牌桶的变体（SmoothBursty/SmoothWarmingUp），支持预热。
分布式限流怎么做？ 用 Redis + Lua 脚本把“读取、补充、扣减”放在一次原子执行中，时间用 Redis 的 TIME 避免各机器时钟不一致；热点 key 可按“总配额/实例数”下发到本地令牌桶，牺牲一些精确性换取性能；Redis 故障时要决定 fail-open（放行，保可用）还是 fail-closed（拒绝，保下游），通常按接口重要性配置，并配合本地限流兜底。

备用题单参考实现

以下各题合并在一个可编译文件中，main 中包含自测用例。

题目	思路	时间 / 空间	易错点
反转链表	三指针迭代：先存 next，再反转指针	O(n) / O(1)	断链前未保存 next；返回 prev 而不是 cur
合并两个有序链表	哨兵节点 + 双指针，剩余部分直接接上	O(m+n) / O(1)	忘记接上剩余链表
合并区间	按左端点排序，当前区间与下一个重叠则扩展右端点	O(n log n) / O(n)	相接 `[1,4],[4,5]` 是否合并要确认；右端点取 max
二叉树层序遍历	队列 BFS，每层先固定 `size`	O(n) / O(w)	循环中直接用 `q.size()` 导致层混乱
二分查找第一个满足条件的位置	左闭右开 `[lo, hi)`，`pred(mid)` 为真收缩右边界	O(log n) / O(1)	`mid` 溢出；死循环（`lo = mid` 而不是 `mid + 1`）
最近公共祖先	后序递归：左右子树都找到则当前为 LCA	O(n) / O(h)	二叉搜索树可以用值比较做到 O(h)
岛屿数量	遍历网格，遇到陆地计数并 BFS 淹没	O(mn) / O(mn) 上界	入队时标记而不是出队时标记，否则重复入队；DFS 深递归可能栈溢出
合并 K 个有序链表	小顶堆存各链表头，弹出最小后压入其 next	O(N log k) / O(k)	空链表不能入堆；也可两两分治合并
延迟任务调度器	`DelayQueue` + 单个调度线程，到期任务交给执行线程池	入队 O(log n)	调度线程中直接执行任务会被慢任务阻塞；同时到期按序号保证 FIFO；关闭时中断调度线程

java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.IntPredicate;

public class Backup {
    static class ListNode {
        int val; ListNode next;
        ListNode(int val) { this.val = val; }
    }
    static class TreeNode {
        int val; TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    // 1. 反转链表：迭代，O(n)/O(1)
    static ListNode reverse(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next; // 先保存后继，防止断链
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // 2. 合并两个有序链表：哨兵节点，O(m+n)/O(1)
    static ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; } // <= 保持稳定
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;
        return dummy.next;
    }

    // 3. 合并区间：按左端点排序后线性合并，O(n log n)
    static int[][] mergeIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return new int[0][];
        int[][] arr = intervals.clone();
        Arrays.sort(arr, Comparator.comparingInt(x -> x[0]));
        List<int[]> res = new ArrayList<>();
        int[] cur = arr[0].clone();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i][0] <= cur[1]) cur[1] = Math.max(cur[1], arr[i][1]); // 相接也合并
            else { res.add(cur); cur = arr[i].clone(); }
        }
        res.add(cur);
        return res.toArray(new int[0][]);
    }

    // 4. 二叉树层序遍历：队列 + 每层 size，O(n)
    static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Deque<TreeNode> q = new ArrayDeque<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();          // 固定本层节点数
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode n = q.poll();
                level.add(n.val);
                if (n.left != null) q.offer(n.left);
                if (n.right != null) q.offer(n.right);
            }
            res.add(level);
        }
        return res;
    }

    // 5. 二分：在 [lo, hi) 中找第一个满足 pred 的位置（pred 单调 false...true），无则返回 hi
    static int firstTrue(int lo, int hi, IntPredicate pred) {
        while (lo < hi) {
            int mid = lo + ((hi - lo) >>> 1); // 防溢出
            if (pred.test(mid)) hi = mid; else lo = mid + 1;
        }
        return lo;
    }
    static int lowerBound(int[] a, int target) {
        return firstTrue(0, a.length, i -> a[i] >= target);
    }

    // 6. 最近公共祖先（普通二叉树）：后序递归，O(n)
    static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lca(root.left, p, q), r = lca(root.right, p, q);
        if (l != null && r != null) return root; // p、q 分居两侧
        return l != null ? l : r;
    }

    // 7. 岛屿数量：BFS 避免深递归栈溢出，O(m*n)
    static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int m = grid.length, n = grid[0].length, count = 0;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '1') continue;
                count++;
                grid[i][j] = '0';         // 入队即标记，防重复入队
                Deque<int[]> q = new ArrayDeque<>();
                q.offer(new int[]{i, j});
                while (!q.isEmpty()) {
                    int[] c = q.poll();
                    for (int[] d : dirs) {
                        int x = c[0] + d[0], y = c[1] + d[1];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                            grid[x][y] = '0';
                            q.offer(new int[]{x, y});
                        }
                    }
                }
            }
        }
        return count;
    }

    // 8. 合并 K 个有序链表：小顶堆，O(N log k)
    static ListNode mergeK(ListNode[] lists) {
        if (lists == null) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x.val));
        for (ListNode l : lists) if (l != null) pq.offer(l);
        ListNode dummy = new ListNode(0), tail = dummy;
        while (!pq.isEmpty()) {
            ListNode n = pq.poll();
            tail.next = n;
            tail = n;
            if (n.next != null) pq.offer(n.next);
        }
        return dummy.next;
    }

    // 9. 简化延迟任务调度器：DelayQueue + 单个工作线程，支持关闭
    static final class DelayScheduler implements AutoCloseable {
        private static final class Task implements Delayed {
            final long triggerNanos; final Runnable action; final long seq;
            Task(long triggerNanos, Runnable action, long seq) {
                this.triggerNanos = triggerNanos; this.action = action; this.seq = seq;
            }
            @Override public long getDelay(TimeUnit unit) {
                return unit.convert(triggerNanos - System.nanoTime(), TimeUnit.NANOSECONDS);
            }
            @Override public int compareTo(Delayed o) {
                Task t = (Task) o;
                int c = Long.compare(triggerNanos, t.triggerNanos);
                return c != 0 ? c : Long.compare(seq, t.seq); // 同时到期按提交顺序
            }
        }
        private final DelayQueue<Task> queue = new DelayQueue<>();
        private final AtomicInteger seq = new AtomicInteger();
        private final ExecutorService executor;   // 业务执行与调度线程分离
        private final Thread worker;
        private volatile boolean running = true;

        DelayScheduler(ExecutorService executor) {
            this.executor = executor;
            this.worker = new Thread(this::loop, "delay-scheduler");
            this.worker.start();
        }
        void schedule(Runnable action, long delay, TimeUnit unit) {
            if (!running) throw new IllegalStateException("closed");
            queue.put(new Task(System.nanoTime() + unit.toNanos(delay), action, seq.getAndIncrement()));
        }
        private void loop() {
            while (running) {
                try {
                    Task t = queue.take();         // 阻塞到最早任务到期
                    executor.execute(() -> {
                        try { t.action.run(); }
                        catch (RuntimeException e) { System.err.println("task failed: " + e); }
                    });
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    return;
                }
            }
        }
        @Override public void close() throws InterruptedException {
            running = false;
            worker.interrupt();
            worker.join();
            executor.shutdown();
            executor.awaitTermination(1, TimeUnit.SECONDS);
        }
    }

    // ---------- 测试 ----------
    static ListNode build(int... v) {
        ListNode d = new ListNode(0), t = d;
        for (int x : v) { t.next = new ListNode(x); t = t.next; }
        return d.next;
    }
    static String str(ListNode h) {
        StringBuilder sb = new StringBuilder();
        for (; h != null; h = h.next) sb.append(h.val).append(h.next != null ? "," : "");
        return sb.toString();
    }
    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) throws Exception {
        check(str(reverse(build(1, 2, 3))).equals("3,2,1"), "reverse");
        check(reverse(null) == null, "reverse null");
        check(str(mergeTwo(build(1, 3, 5), build(2, 4))).equals("1,2,3,4,5"), "merge2");
        check(str(mergeTwo(null, build(1))).equals("1"), "merge2 null");
        check(Arrays.deepToString(mergeIntervals(new int[][]{{8, 10}, {1, 3}, {2, 6}, {15, 18}}))
                .equals("[[1, 6], [8, 10], [15, 18]]"), "intervals");
        check(mergeIntervals(new int[][]{{1, 4}, {4, 5}}).length == 1, "intervals touch");

        TreeNode r = new TreeNode(3); r.left = new TreeNode(9); r.right = new TreeNode(20);
        r.right.left = new TreeNode(15); r.right.right = new TreeNode(7);
        check(levelOrder(r).toString().equals("[[3], [9, 20], [15, 7]]"), "level");
        check(levelOrder(null).isEmpty(), "level null");

        int[] a = {1, 2, 2, 2, 5};
        check(lowerBound(a, 2) == 1 && lowerBound(a, 6) == 5 && lowerBound(a, 0) == 0, "bs");
        check(lowerBound(new int[0], 1) == 0, "bs empty");

        check(lca(r, r.right.left, r.right.right) == r.right, "lca");
        check(lca(r, r.left, r.right.right) == r, "lca root");

        char[][] g = {"11000".toCharArray(), "11000".toCharArray(), "00100".toCharArray(), "00011".toCharArray()};
        check(numIslands(g) == 3, "islands");

        check(str(mergeK(new ListNode[]{build(1, 4, 5), build(1, 3, 4), null, build(2, 6)}))
                .equals("1,1,2,3,4,4,5,6"), "mergeK");
        check(mergeK(new ListNode[0]) == null, "mergeK empty");

        List<Integer> order = Collections.synchronizedList(new ArrayList<>());
        CountDownLatch latch = new CountDownLatch(3);
        try (DelayScheduler s = new DelayScheduler(Executors.newSingleThreadExecutor())) {
            s.schedule(() -> { order.add(3); latch.countDown(); }, 150, TimeUnit.MILLISECONDS);
            s.schedule(() -> { order.add(1); latch.countDown(); }, 10, TimeUnit.MILLISECONDS);
            s.schedule(() -> { order.add(2); latch.countDown(); }, 80, TimeUnit.MILLISECONDS);
            check(latch.await(2, TimeUnit.SECONDS), "delay timeout");
        }
        check(order.equals(List.of(1, 2, 3)), "delay order " + order);
        System.out.println("Backup OK");
    }
}

延迟队列追问：

单机 DelayQueue 的问题？ 任务在内存中，重启丢失；数量大时堆操作 O(log n) 和内存占用都是问题。
海量定时任务？ 时间轮（Netty HashedWheelTimer、Kafka 分层时间轮），插入和删除 O(1)，精度取决于 tick。
分布式、可持久化延迟任务？ Redis ZSet（score 为触发时间，ZRANGEBYSCORE + Lua 原子领取）、RocketMQ 延迟消息/定时消息、数据库任务表 + 扫描（WHERE status='PENDING' AND trigger_at<=now() 加索引和租约领取）。都要处理重复触发，执行方需幂等。

面试官通用追问参考答案

为什么选这个数据结构？ 从操作需求推导：需要 O(1) 查找用哈希，需要有序或 O(1) 删除任意节点用双向链表，需要动态取最值用堆，需要先进先出用队列。先说需要哪些操作及其频率，再说结构。
不变量是什么？ 每题用一句话说清：LRU 是“map 与链表一一对应且头新尾旧”；滑窗是“窗口内无重复且 left 不回退”；堆是“堆内恰好是当前最高频的 k 个”；有界队列是“0 ≤ size ≤ capacity，且只在持锁时修改”。
最坏复杂度是多少？ HashMap 查询平均 O(1)；即使桶已树化，同 hash 且无法按有效 Comparable 顺序定位时，查询仍可能退化到 O(n)。快速选择平均 O(n)、最坏 O(n²)。说明输入假设，区分平均复杂度与最坏界。
输入为空或容量为 0 怎么办？ 先和面试官确认约定：返回空结果、抛 IllegalArgumentException 还是视为合法。上面的代码中，LRU 容量 0 视为合法但不缓存，有界队列容量 0 视为非法。
如何写单元测试？ 按正常、边界、异常三类写 JUnit 5 用例；并发代码用 CountDownLatch 同时启动多线程，断言总量守恒（如生产总数 = 消费总数、令牌发放数 = 容量）；涉及时间的注入可控时钟，避免 sleep 导致测试不稳定。
并发调用会出现什么问题？ LRU：HashMap 并发写导致数据丢失，链表指针被并发修改导致断链或环；令牌桶：不加锁会超发；生产者消费者：if 检查导致越界。解决方法见各题。
内存不足时如何降级？ 缓存设上限并淘汰；用软引用或堆外缓存需谨慎；大数据量改流式或分片处理（Top K 分片）；有界队列满时拒绝或落盘，而不是无界堆积导致 OOM。
能否用 JDK 容器简化？ LRU 用 LinkedHashMap、Top K 用 PriorityQueue、生产者消费者用 BlockingQueue、限流用 Guava RateLimiter、延迟任务用 ScheduledThreadPoolExecutor。手写是为了展示原理，生产中优先用成熟实现。
为什么你的实现不会死循环/丢节点？ 二分：每轮区间严格缩小（lo = mid + 1 或 hi = mid，且 mid < hi）；滑窗：right 每轮加一，必然结束；链表：修改指针前保存后继，成对更新 prev/next；等待循环：每次唤醒都重新检查条件，关闭时 signalAll。
生产场景还需要哪些监控和保护？ 缓存：命中率、淘汰数、容量；队列：长度、等待时间、拒绝次数；限流：通过/拒绝数、按 key 维度的热点；线程：活跃数、阻塞数。保护：容量上限、超时、拒绝策略、熔断和告警。

参考实现

上方主练 5 题与备用题参考实现即原题解全文。

附加 5 个 Java 并发/设计题

这 5 题不占 30 题名额；部分实现见上方主练 5 题参考实现：

手写 LRU（HashMap + 双向链表，或 LinkedHashMap）；
生产者消费者（有界队列 + 条件变量/阻塞队列）；
两个线程交替打印（锁 + 条件变量，注意虚假唤醒）；
简单令牌桶（线程安全、时间源可注入）；
单例或线程安全计数器（说明可见性、原子性和锁边界）。

常见失败模式

只写代码不跑边界用例，面试时在空输入或重复元素上挂掉；
不分析复杂度，或把平均复杂度当最坏复杂度；
背题解，换一个条件就不会；
反复做已经会的题，回避图、DP、堆等薄弱模式；
不记录 bug，导致同一个越界或死循环反复出现；
没有先讲思路就写代码，卡住后无法自救。

与知识点的关系

编码练习是知识点的训练视图：每题的"关键不变量"在对应主题正文有权威讲解，本页不复制第二份讲解。SQL 手写题见 SQL手写笔试；错题按掌握情况进入错题与复盘。

算法与并发编码 ​

知识点回查索引 ​

一、数组、哈希与前缀（4 题） ​

二、双指针（3 题） ​

三、滑动窗口（3 题） ​

四、二分查找（3 题） ​

五、栈（3 题） ​

六、链表（3 题） ​

七、堆与 Top K（3 题） ​

八、树（3 题） ​

九、图与搜索（2 题） ​

十、动态规划（3 题） ​

30 题可实施规格与答案 ​

1. 两数之和 ​

2. 字母异位词分组 ​

3. 最长连续序列 ​

4. 除自身以外数组的乘积 ​

5. 三数之和 ​

6. 盛最多水的容器 ​

7. 接雨水 ​

8. 无重复字符的最长子串 ​

9. 最小覆盖子串 ​

10. 找到所有字母异位词 ​

11. 二分查找 ​

12. 搜索旋转排序数组 ​

13. 查找第一个和最后一个位置 ​

14. 有效的括号 ​

15. 每日温度 ​

16. 柱状图最大矩形 ​

17. 反转链表 ​

18. 合并两个有序链表 ​

19. 环形链表II ​

20. 合并K个升序链表 ​

21. 第K个最大元素 ​

22. 前K个高频元素 ​

23. 二叉树层序遍历 ​

24. 验证二叉搜索树 ​

25. 二叉树最近公共祖先 ​

26. 岛屿数量 ​

27. 课程表 ​

28. 零钱兑换 ​

29. 最长递增子序列 ​

30. 编辑距离 ​

按主题验收 ​

单题记录模板 ​

验收标准 ​

主练 5 题：完整实现与追问 ​

题 1：LRU Cache（HashMap + 手写双向链表） ​

题 2：Top K 高频元素（小顶堆 + 桶排序） ​

题 3：最长无重复子串（滑动窗口） ​

题 4A：生产者消费者 ​

方案一：ReentrantLock + 两个 Condition ​

方案二：BlockingQueue + 毒丸关闭 ​

题 4B：线程安全令牌桶 ​

备用题单参考实现 ​

面试官通用追问参考答案 ​

参考实现 ​

附加 5 个 Java 并发/设计题 ​

常见失败模式 ​

与知识点的关系 ​

算法与并发编码

知识点回查索引

一、数组、哈希与前缀（4 题）

二、双指针（3 题）

三、滑动窗口（3 题）

四、二分查找（3 题）

五、栈（3 题）

六、链表（3 题）

七、堆与 Top K（3 题）

八、树（3 题）

九、图与搜索（2 题）

十、动态规划（3 题）

30 题可实施规格与答案

1. 两数之和

2. 字母异位词分组

3. 最长连续序列

4. 除自身以外数组的乘积

5. 三数之和

6. 盛最多水的容器

7. 接雨水

8. 无重复字符的最长子串

9. 最小覆盖子串

10. 找到所有字母异位词

11. 二分查找

12. 搜索旋转排序数组

13. 查找第一个和最后一个位置

14. 有效的括号

15. 每日温度

16. 柱状图最大矩形

17. 反转链表

18. 合并两个有序链表

19. 环形链表II

20. 合并K个升序链表

21. 第K个最大元素

22. 前K个高频元素

23. 二叉树层序遍历

24. 验证二叉搜索树

25. 二叉树最近公共祖先

26. 岛屿数量

27. 课程表

28. 零钱兑换

29. 最长递增子序列

30. 编辑距离

按主题验收

单题记录模板

验收标准

主练 5 题：完整实现与追问

题 1：LRU Cache（HashMap + 手写双向链表）

题 2：Top K 高频元素（小顶堆 + 桶排序）

题 3：最长无重复子串（滑动窗口）

题 4A：生产者消费者

方案一：ReentrantLock + 两个 Condition

方案二：BlockingQueue + 毒丸关闭

题 4B：线程安全令牌桶

备用题单参考实现

面试官通用追问参考答案

参考实现

附加 5 个 Java 并发/设计题

常见失败模式

与知识点的关系