算法手撕面试题精选
Java 后端真实面试专题 · 算法手撕篇
手撕题真正考的不是“背过哪道 LeetCode”，而是能不能把问题拆成不变量、选择合适的数据结构，并在边界条件下写出可验证的代码。下面每题按“标准答（思路与原理）→ 代码/复杂度 → 拓展（边界与追问）→ 往项目引”展开。
年限标签：
🟢 3年内🔴 3年+说明：示例代码以 Java 17 语法为主；面试时先说假设（例如
k是否允许为 0、删除一个还是全部），再开始写代码。
1. 🔴 一亿个数，找出最大的前 K 个（TopN）
标准答：
不能把一亿个数全部排序：完整排序是 O(N logN)，还要求数据可同时放进内存。维护一个容量为 K 的小顶堆即可。堆中始终保存“目前见过的前 K 大”，堆顶是这 K 个数里最小的一个；新数只有比堆顶大才值得替换。这个不变量使每个元素只需 O(logK) 调整。
代码与复杂度：
static List<Integer> topK(int[] nums, int k) {
if (nums == null || k <= 0) return List.of();
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int x : nums) {
if (minHeap.size() < k) {
minHeap.offer(x);
} else if (x > minHeap.peek()) {
minHeap.poll();
minHeap.offer(x);
}
}
List<Integer> result = new ArrayList<>(minHeap);
result.sort(Comparator.reverseOrder()); // 需要有序输出时再排，成本 O(K logK)
return result;
}
时间复杂度 O(N logK)，堆空间 O(K)；若只需要“是否进入 TopK”，不必再排序结果。数据超过内存时按文件块读取，每块求 TopK 后再把各块结果合并，最终仍只需保留 K 个数。数值可能超过 int 时用 long，k > N 时返回实际读到的全部数据。
拓展：重复值是否保留取决于题意；要取“不同的 TopK”需先去重或在堆中维护计数。面试官常追问为什么不用大顶堆：求最大 K 用小顶堆，求最小 K 才用大顶堆。还可能问如何估算内存：堆元素、对象头和装箱开销都要算，生产代码优先用原始类型或分片文件。
往项目引：排行榜、日志中最高耗时请求、实时销量 TopN 都可用同一思路；Redis 的 ZSet 适合在线增量排名，离线大文件则用分片 + 堆。回答时把“数据规模、实时性、是否允许近似”说清，不要只报一个堆。
2. 🔴 手写一个 LRU 缓存
标准答：
LRU 要求 get 和 put 平均 O(1)，单独用队列会在删除任意节点时退化为 O(N)。组合 HashMap + 双向链表：Map 负责 key 到节点的定位，链表从头到尾表示“最近使用到最久未使用”。每次命中、更新或插入都把节点移动到头部，超容量删除尾部节点。用两个哨兵节点可以消除头尾判空分支。
代码与复杂度：
final class LruCache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> map = new HashMap<>();
private final Node<K, V> head = new Node<>(null, null);
private final Node<K, V> tail = new Node<>(null, null);
LruCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity;
head.next = tail; tail.prev = head;
}
synchronized V get(K key) {
Node<K, V> n = map.get(key);
if (n == null) return null;
moveToHead(n); return n.value;
}
synchronized void put(K key, V value) {
Node<K, V> n = map.get(key);
if (n != null) { n.value = value; moveToHead(n); return; }
n = new Node<>(key, value); map.put(key, n); addFirst(n);
if (map.size() > capacity) {
Node<K, V> old = tail.prev; remove(old); map.remove(old.key);
}
}
private void moveToHead(Node<K,V> n) { remove(n); addFirst(n); }
private void addFirst(Node<K,V> n) { n.next=head.next; n.prev=head; head.next.prev=n; head.next=n; }
private void remove(Node<K,V> n) { n.prev.next=n.next; n.next.prev=n.prev; }
private static final class Node<K,V> { K key; V value; Node<K,V> prev,next; Node(K k,V v){key=k;value=v;} }
}
每次操作平均 O(1)，空间 O(capacity)。Java 标准库也可以用 LinkedHashMap 的 accessOrder=true 快速实现，但面试手写版要说清链表不变量。上例用 synchronized 只是说明线程安全边界；高并发场景应考虑分段锁、Caffeine 或直接使用成熟实现，不能把一个全局锁的 LRU 当成无锁缓存。
拓展：容量为 0 应拒绝或明确“不缓存”；null 值要区分“未命中”和“命中但值为 null”；是否需要 TTL、最大权重、统计命中率是产品约束，不属于纯 LRU。还要问并发读写、序列化、缓存穿透和淘汰回调如何处理。
往项目引：本地热点配置、RPC 元数据、短期用户会话可用 LRU；分布式缓存则使用 Redis 的淘汰策略并在应用层处理失效。讲项目时说明为什么选择容量淘汰而非 TTL，以及缓存未命中时的回源和保护措施。
3. 🟢 三个线程交替打印，把数字累加到 100（或交替打印 ABC）
标准答：
把“轮到谁”抽象成共享状态 turn，线程只在自己的轮次执行。等待必须放在 while 中而非 if：线程可能被虚假唤醒，也可能被其他线程唤醒但轮次仍不属于自己。打印或累加后更新 turn，再 notifyAll 唤醒其他线程。Semaphore 或 Condition 可以表达同样的令牌传递。
final class Alternator {
private final Object monitor = new Object();
private int turn = 0;
private int value = 1;
void print(int mine, String text, int threadCount, int limit) throws InterruptedException {
if (threadCount <= 0 || mine < 0 || mine >= threadCount) {
throw new IllegalArgumentException("invalid thread turn");
}
while (true) {
synchronized (monitor) {
while (value <= limit && turn != mine) monitor.wait();
if (value > limit) { monitor.notifyAll(); return; }
System.out.println(text + value++);
turn = (turn + 1) % threadCount;
monitor.notifyAll();
}
}
}
}
// new Thread(() -> run(alternator, 0, "A"), "A").start(); ...
这里的共享状态修改和条件检查在同一把锁内，因而不会出现两个线程同时打印。复杂度是每个数字一次临界区，空间 O(1)；InterruptedException 应恢复中断标志或交给上层处理，不能静默吞掉。
拓展：线程数为 0、限制值小于 1、打印任务抛异常时都要定义行为。notify 可能只唤醒不合适的线程，条件复杂时用 notifyAll 更稳；若要求严格吞吐而非教学演示，可用 Semaphore(1) 链式传递。面试官也会追问如何避免忙等：等待条件用 wait/Condition，不要 while 空转。
往项目引：批处理分阶段（读取→校验→写入）可用队列或信号量控制顺序；但业务代码优先使用 ExecutorService、CompletableFuture 或并发容器，不要为“有序”手写脆弱的线程协调。
4. 🟢 反转一个链表
标准答：遍历时必须先保存 cur.next，再把 cur.next 指向 prev，最后整体向前移动。核心不变量是：prev 已经是反转好的前缀，cur 是尚未处理的第一个节点。空链表和单节点自然落在同一套逻辑里。
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;
}
static final class ListNode { int val; ListNode next; ListNode(int v){ val=v; } }
时间 O(N)、额外空间 O(1)。递归写法更短，但递归深度是 O(N)，长链表可能栈溢出；面试中先写迭代版，再说明递归版的 head.next.next = head 和断开 head.next。
拓展：要确认是否原地修改、是否只反转 [left,right] 区间、是否按 K 个一组反转。若链表可能有环，普通反转可能无限循环，应先检测环或限制步数。写完可用空、单节点、两节点和重复值四组用例验证。
往项目引：链表在 Java 业务代码中不如数组/集合常见，但连接池空闲节点、哈希桶链和自定义队列会遇到同样的指针操作；关键是维护链表不变量并保证异常路径不丢节点。
5. 🟢 两数之和（给数组和目标，找两个数和为 target）
标准答：遍历到 x 时，所需的另一个数是 target - x。把已遍历元素放入 Map，先查后放，能够正确处理同一个值出现两次的情况。相比双重循环，哈希把时间从 O(N²) 降到平均 O(N)，代价是 O(N) 额外空间。
static int[] twoSum(int[] nums, int target) {
if (nums == null) return new int[0];
Map<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
Integer j = index.get(need);
if (j != null) return new int[]{j, i};
index.put(nums[i], i);
}
return new int[0];
}
若整数可能溢出，先转 long 计算差值；若要求返回所有不重复组合，可先排序再用双指针，并跳过相同值。题目若明确数组有序，双指针空间可降到 O(1)；若只判断存在性，还可以用布尔桶（值域有限时）。
拓展：没有解时返回空结果还是抛异常必须先约定；同一元素不能重复使用；负数、重复数、空数组都要测试。面试官常追问哈希冲突和最坏复杂度：理想平均 O(1)，极端冲突会退化，因此要说明 Java 8 桶树化和合适的容量。
往项目引：优惠券组合、差额匹配、日志中配对事件都可使用“边遍历边索引”的模式。生产接口还要校验输入长度和上限，避免把无界请求直接放进 Map。
6. 🟢 统计一组数据里出现频率最高的前 N 个
标准答：第一遍用 Map 统计频率，第二遍对 m 个不同元素维护容量为 k 的小顶堆。堆顶是当前 TopK 中频率最低者，遍历完后堆内就是答案，复杂度 O(N + m logK)，比把全部元素按频率排序的 O(m logm) 更省。
static List<String> frequentTopK(List<String> words, int k) {
if (words == null || k <= 0) return List.of();
Map<String, Integer> count = new HashMap<>();
for (String w : words) count.merge(w, 1, Integer::sum);
PriorityQueue<Map.Entry<String,Integer>> heap = new PriorityQueue<>(
Comparator.<Map.Entry<String,Integer>>comparingInt(Map.Entry::getValue)
.thenComparing(Map.Entry::getKey, Comparator.reverseOrder()));
for (var e : count.entrySet()) {
heap.offer(e);
if (heap.size() > k) heap.poll();
}
List<String> result = new ArrayList<>(heap.stream().map(Map.Entry::getKey).toList());
result.sort(Comparator.comparingInt((String w) -> count.get(w)).reversed()
.thenComparing(Comparator.naturalOrder()));
return result;
}
要先约定并列频率的次序（字典序、首次出现顺序或任意），否则不同实现输出不同并不代表算法错。流式数据不能无限保留计数时，可用 Count-Min Sketch 做近似，但要明确误差和内存换取关系。
拓展：k > m 返回全部不同元素；大小写、空字符串和停用词是否归一化属于业务规则；频率可能超过 int 时用 long。还会追问为什么堆比较器要反向处理并列值，以及如何分片统计后合并：先合并各片频率，再做一次 TopK。
往项目引：热门搜索词、错误码排行、用户行为 TopN 都是同一模板；实时排行榜可把计数放 Redis，离线报表则用 MapReduce 聚合。重点说明最终一致还是近似统计，以及榜单刷新周期。
7. 🔴 二叉树的最近公共祖先（LCA）
标准答：后序递归返回“当前子树里找到的 p 或 q（或已确定的 LCA）”。当前节点等于 p/q 时直接返回；左右子树都非空说明 p、q 分居两侧，当前节点就是 LCA；只有一侧非空则向上返回那一侧。
static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lca(root.left, p, q);
TreeNode right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
static final class TreeNode { int val; TreeNode left,right; TreeNode(int v){val=v;} }
时间 O(N)、递归空间 O(H)。上式默认 p、q 一定存在；若题目不保证，应额外统计找到的节点数，只有找到两个才返回结果。二叉搜索树可利用大小关系从根迭代到分叉点，平均更快；多次查询则可预处理父指针、Euler Tour 或倍增表。
拓展：p=q 时答案通常是 p，但要先确认定义；树退化成链时递归深度达到 N；节点值重复时必须比较节点引用或唯一 id，不能只比较 val。面试官常追问“只找到一个节点怎么办”，这是递归模板最容易遗漏的前提。
往项目引：组织树、类目树、权限树查共同上级时可用相同思想；真实接口还要限制树深、校验节点归属租户，并对不存在节点返回明确错误。
8. 🟢 校验一个字符串/char 数组是否是合法 IPv4 地址
标准答：严格 IPv4 由四段十进制数字组成，每段范围 0..255，多位段不能有前导零。直接 split("\\.") 容易漏掉末尾空段，且 Integer.parseInt 对超长数字可能抛异常；面试中可以手动扫描，遇到点号结束一段并立即校验。
static boolean isIpv4(String s) {
if (s == null || s.isEmpty()) return false;
int parts = 0, value = 0, digits = 0;
for (int i = 0; i <= s.length(); i++) {
char c = i < s.length() ? s.charAt(i) : '.'; // 哨兵收尾
if (c == '.') {
if (digits == 0 || value > 255) return false;
if (digits > 1 && s.charAt(i - digits) == '0') return false;
parts++; value = 0; digits = 0;
} else if (c >= '0' && c <= '9') {
if (++digits > 3) return false;
value = value * 10 + (c - '0');
} else return false;
}
return parts == 4;
}
复杂度 O(L)、空间 O(1)。上例不接受首尾空格；若协议允许，应在调用方明确 trim，不要验证函数偷偷改变语义。1.2.3.04、1..2.3、256.0.0.1、空串都应为 false；IPv6 是另一套规则，不能用同一函数“放宽”处理。
拓展：char 数组为空、包含非 ASCII 数字、超过三位、末尾点号都是常见坑。若要求返回错误位置，可把布尔值改成结果对象携带段号和原因。
往项目引：白名单、代理头校验和网络配置录入都要做严格解析；安全场景不能只用正则“看起来像 IP”，还要防止解析器之间对前导零和十六进制的解释不一致。
9. 🔴 买可乐：n 元买 n 瓶，2 个空瓶换 1 瓶，n 元能喝几瓶？
标准答：初始买 n 瓶并得到 n 个空瓶；每次用两个空瓶换一瓶，喝完后空瓶数增加一瓶。循环模拟最不容易误读题意。若允许“借一个空瓶并在最后归还”，数学结论为 2n-1；若不允许借瓶，n=1 只能喝 1 瓶，所以一定要先问清规则。
static long cola(long money) {
if (money <= 0) return 0;
long total = money, empty = money;
while (empty >= 2) {
long exchanged = empty / 2;
total += exchanged;
empty = empty % 2 + exchanged;
}
return total;
}
每轮空瓶数约减半，循环 O(log n)，结果使用 long 可避免大输入溢出。一般化为“b 个空瓶换 1 瓶”时，不能直接套 2n-1；可用递推或模拟，并明确是否允许借瓶、是否有多种包装。
拓展：n<=0、兑换比例为 1、兑换规则变化、空瓶不能跨轮使用都要说明。面试官常让你证明公式：每额外喝一瓶净消耗一个空瓶，初始 n 个空瓶最多再换 n-1 瓶，因此总数 2n-1（允许借瓶时）。
往项目引：积分兑换、优惠券裂变、资源回收等“消耗若干换一个”的规则可以用同一递推模型；业务代码要把兑换记录落库或幂等化，不能只依赖内存循环。
10. 🟢 冒泡排序 / 快速排序手写
标准答：冒泡每轮把当前最大值交换到右端，若一轮无交换可提前结束；快排选基准并把数组分成“<= 基准”和“>= 基准”两段，再递归处理。分区时要保持指针不越界，重复值多时应避免无止境移动。
static void bubbleSort(int[] a) {
if (a == null || a.length < 2) return;
for (int end = a.length - 1; end > 0; end--) {
boolean swapped = false;
for (int i = 0; i < end; i++) if (a[i] > a[i+1]) {
int t=a[i]; a[i]=a[i+1]; a[i+1]=t; swapped=true;
}
if (!swapped) return;
}
}
static void quickSort(int[] a, int l, int r) {
if (a == null || a.length < 2 || l >= r) return;
int i=l, j=r, pivot=a[l + (r-l)/2];
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) { int t=a[i]; a[i++]=a[j]; a[j--]=t; }
}
if (l < j) quickSort(a,l,j);
if (i < r) quickSort(a,i,r);
}
冒泡平均/最坏 O(N²)、最好（带提前退出）O(N)，快排平均 O(N logN)、最坏 O(N²)，递归栈平均 O(logN)。有序输入可让固定基准快排退化，随机基准或三数取中可缓解；生产中直接使用经过优化的 Arrays.sort，不要为了“手写”替代标准库。
拓展：空数组、重复值、负数和整型极值；是否稳定、是否原地、是否允许额外内存。归并排序稳定但需要 O(N) 空间，堆排序 O(N logN) 且原地但不稳定，这些取舍比背复杂度表更重要。
往项目引：批量导入前对小数据排序、按优先级整理任务时可选择排序算法；大数据应让数据库 ORDER BY 或外部排序承担，先评估数据量和内存。
11. 🟢 二分查找
标准答：二分的关键不是“取中间”，而是定义区间不变量。闭区间 [l,r] 中若目标不存在，循环结束时 l=r+1；每次比较后丢弃一半区间。mid = l + (r-l)/2 可避免 l+r 溢出。
static int lowerBound(int[] a, int target) { // 第一个 >= target
if (a == null || a.length == 0) return 0;
int l=0, r=a.length;
while (l < r) {
int m = l + (r-l)/2;
if (a[m] < target) l=m+1; else r=m;
}
return l; // 可能等于 a.length
}
static int binarySearch(int[] a, int target) {
if (a == null || a.length == 0) return -1;
int p = lowerBound(a, target);
return p < a.length && a[p] == target ? p : -1;
}
查找任意值是 O(logN)、空间 O(1)；找左/右边界分别使用 lowerBound(target) 和 lowerBound(target+1)-1，注意 target+1 也可能溢出，可改用 long。旋转数组、按答案二分（例如最小可行容量）都要重新定义“可行性单调”。
拓展：空数组、重复值、目标小于最小值或大于最大值；while (l <= r) 与 while (l < r) 必须和区间定义配套。面试官常让你证明循环一定收敛：每轮都严格缩小未决区间，不能写成 l=m/r=m 导致死循环。
往项目引：时间线、版本号、分段配置和有序 ID 查询常用二分；若数据在数据库里，先确认索引和排序是否真的存在，不能把无序分页结果拿来二分。
12. 🔴 约瑟夫环：100 人围圈报数，剔除奇数位，循环到剩一人
标准答：这道题有两个容易混淆的版本：固定每数到 m 出局的标准约瑟夫环，以及“每轮删除当前奇数位”的淘汰赛。必须先问清每轮从谁开始报数、删除后从谁继续。对不明确的版本，先给可验证的模拟，再给公式，避免直接背“最大 2 的幂”。
static int survivorByOddElimination(int n) {
if (n <= 0) throw new IllegalArgumentException("n must be positive");
if (n == 1) return 1;
List<Integer> people = new ArrayList<>();
for (int i=1;i<=n;i++) people.add(i);
while (people.size() > 1) {
List<Integer> next = new ArrayList<>();
for (int i=0;i<people.size();i++) {
// 从当前列表第 1 位开始报数，删除奇数号
if ((i + 1) % 2 == 0) next.add(people.get(i));
}
people = next;
}
return people.get(0);
}
static int josephus(int n, int m) { // 固定 m 报数，返回 0-based 位置
int f=0;
for (int size=2; size<=n; size++) f=(f+m)%size;
return f;
}
链表/队列模拟的时间通常 O(N²)，适合解释规则；标准固定步长版本用递推 f(1)=0, f(n)=(f(n-1)+m)%n，时间 O(N)、空间 O(1)。奇数位版本的结果取决于起点和是否旋转，不能脱离定义下结论。
拓展：n=1、偶数/奇数、删除后起点变化、编号从 0 还是 1；如果要求输出每轮淘汰顺序，返回列表而不是只返回 survivor。还要注意 m 很大时用取模避免计数器溢出。
往项目引：轮询调度、分片分配和环形队列会用到“按步长移动并删除”的思想；生产代码应优先使用成熟队列，并为公平性、重启恢复和重复分配设计持久化状态。
13. 🔴 36 进制（0-9 a-z）两个数相加
标准答：从两个字符串末尾向前逐位相加，sum = digitA + digitB + carry，结果位为 sum % 36，进位为 sum / 36。输入可有不同长度，因此缺位按 0 处理。不要先转 long，否则大数会溢出。
static String addBase36(String a, String b) {
if (a == null || b == null || a.isEmpty() || b.isEmpty())
throw new IllegalArgumentException("empty number");
int i=a.length()-1, j=b.length()-1, carry=0;
StringBuilder out = new StringBuilder(Math.max(a.length(), b.length())+1);
while (i>=0 || j>=0 || carry!=0) {
int x = i>=0 ? digit(a.charAt(i--)) : 0;
int y = j>=0 ? digit(b.charAt(j--)) : 0;
int sum=x+y+carry; out.append(valueChar(sum%36)); carry=sum/36;
}
return out.reverse().toString();
}
static int digit(char c) {
if (c>='0'&&c<='9') return c-'0';
if (c>='a'&&c<='z') return c-'a'+10;
if (c>='A'&&c<='Z') return c-'A'+10;
throw new IllegalArgumentException("invalid base36 digit: "+c);
}
static char valueChar(int v) { return v<10 ? (char)('0'+v) : (char)('a'+v-10); }
复杂度 O(max(lenA,lenB))，额外空间同结果长度。是否允许大写、前导零和负数要先约定；若支持负数，应先拆符号、比较绝对值后做减法。每一位都要校验 <36，不能把 Character.digit(c,36) 的 -1 忽略。
拓展：0+0、进位产生新最高位、一个字符串全是前导零、非法字符和超长输入。面试官可能要求改成任意进制 2..36，只需把 36 抽成参数并校验范围。
往项目引：短链 ID、分布式流水号和大整数配置可用进制字符串降低长度；若用于排序，要说明字典序与数值序并不总一致，不能直接拿字符串比较大小。
14. 🟢 删除链表中值为 n 的节点
标准答：使用虚拟头节点 dummy，统一处理头节点、连续目标节点和空链表。遍历 prev.next：命中就跳过，不命中才移动 prev，这样连续重复值不会漏删。题目若只要求删除第一个，命中后立即返回即可。
static ListNode removeAll(ListNode head, int value) {
ListNode dummy = new ListNode(0); dummy.next=head;
ListNode prev=dummy;
while (prev.next != null) {
if (prev.next.val == value) prev.next=prev.next.next;
else prev=prev.next;
}
return dummy.next;
}
时间 O(N)、额外空间 O(1)。如果节点还被其他结构引用，原地删除只改变链表链接，不会让外部引用自动失效；并发读写时要加同步或采用不可变链表，不能把单线程指针代码直接用于共享结构。
拓展：目标在头、尾、全部节点、没有命中、连续命中；删除一个还是全部必须先确认。还可追问“如何保留相对顺序”（本算法天然保留）和“如何按谓词删除”（把值比较替换成 Predicate<ListNode>）。
往项目引：过滤待处理任务、移除失效节点、维护内存队列时常用 dummy 技巧；持久化列表则应使用带版本的条件更新，防止并发删除覆盖别人新增的数据。
15. 🟢 一个数组包含 0-9，统计每个数字出现的次数
标准答：值域只有 10 个，直接用固定长度的 long[10] 做桶计数，比 HashMap 少了哈希和对象开销。遍历一次，检查输入确实在 0..9 后递增对应桶。
static long[] countDigits(int[] nums) {
long[] count = new long[10];
if (nums == null) return count;
for (int x : nums) {
if (x < 0 || x > 9) throw new IllegalArgumentException("digit: "+x);
count[x]++;
}
return count;
}
时间 O(N)、额外空间 O(1)（相对于固定值域）。如果题目说的是“统计整数里每个十进制数字”，需要逐个取模处理负号和 0；如果是字符文本，要明确 Unicode 数字与 ASCII '0'..'9' 的区别。
拓展：空数组、负数、超出值域、计数可能超过 int；可用 long[10]。值域变大或稀疏时再换 Map，不能机械地说计数数组永远更好。
往项目引：状态码、评分档位、固定枚举统计都适合桶；报表接口要避免把用户传入的巨大值域直接作为数组长度，防止内存攻击。
16. 🔴 给一亿个数找最大 100 个，用数组还是链表？为什么？
标准答：如果实现固定容量的小顶堆，选数组（或 PriorityQueue 的数组实现）。堆通过 parent=(i-1)/2、left=2*i+1 频繁随机访问，数组连续、缓存友好，且每个元素没有 next 指针开销。链表随机访问是 O(N)，无法高效维护堆。
static void offerTop100(long x, long[] heap, int[] sizeRef) {
if (heap == null || sizeRef == null || heap.length == 0) return;
if (sizeRef[0] < 0 || sizeRef[0] > heap.length) {
throw new IllegalArgumentException("invalid heap size");
}
int size=sizeRef[0];
if (size < heap.length) { heap[size]=x; siftUp(heap,size++); sizeRef[0]=size; return; }
if (x <= heap[0]) return;
heap[0]=x; siftDown(heap,0,heap.length);
}
static void siftUp(long[] h,int i){ while(i>0){int p=(i-1)/2;if(h[p]<=h[i])break;swap(h,p,i);i=p;} }
static void siftDown(long[] h,int i,int n){ for(;;){int l=i*2+1,r=l+1,b=i;if(l<n&&h[l]<h[b])b=l;if(r<n&&h[r]<h[b])b=r;if(b==i)return;swap(h,i,b);i=b;} }
static void swap(long[] h,int i,int j){long t=h[i];h[i]=h[j];h[j]=t;}
数组并不代表要把一亿个数全放进内存；输入仍应流式读取，数组只保存 100 个候选。面试官若问“链表什么时候更好”，可回答：频繁在已知节点位置插入/删除且不需要随机访问时链表有优势，但现代 CPU 下还要考虑缓存局部性和分配成本。
拓展：固定容量、重复值、long 极值、输入为空；如果要求保留原始顺序，堆只负责筛选，输出时还要额外记录序号或二次排序。
往项目引：批处理选择容器时先看访问模式，再看内存和 GC；不要因为“链表插入 O(1)”就用于需要按下标或堆序访问的热点路径。
17. 🟢 判断一个链表是否有环 / 找环入口
标准答：快指针每次走两步，慢指针每次走一步。无环时快指针先到 null；有环时相对速度为 1，必在环内相遇。相遇后让一个指针回到头部，两者每次走一步，下一次相遇就是入口：设头到入口为 a，入口到相遇为 b，环长为 L，相遇时 2(a+b)=a+b+kL，可推出 a=kL-b。
static ListNode cycleEntry(ListNode head) {
ListNode slow=head, fast=head;
while (fast != null && fast.next != null) {
slow=slow.next; fast=fast.next.next;
if (slow == fast) {
ListNode p=head;
while (p != slow) { p=p.next; slow=slow.next; }
return p;
}
}
return null;
}
时间 O(N)、空间 O(1)，不修改链表。若要判断“环长度”可在相遇点再绕一圈计数；若要判断两个链表相交，要先区分有环/无环情况。
拓展：空链表、自环、环在第二个节点、两条链表共享环；比较必须用节点引用 ==，不能用值相等。面试官常追问为什么一定相遇，回答相对速度和有限环长度即可。
往项目引：依赖关系检测、任务链路和自定义迭代器都可用快慢指针发现循环；对外部输入构造的链表还应限制节点数，避免恶意超长遍历。
18. 🟢 实现一个生产者-消费者模型
标准答：生产者把任务放入有界队列，队列满时阻塞生产者；消费者取出任务，队列空时阻塞消费者。优先使用 BlockingQueue，因为它已正确处理可见性、等待/唤醒和中断；手写 wait/notify 时必须用 while 检查条件。
BlockingQueue<Task> queue = new ArrayBlockingQueue<>(1000);
ExecutorService pool = Executors.newFixedThreadPool(4);
for (int i = 0; i < 4; i++) {
pool.submit(() -> {
try {
while (!Thread.currentThread().isInterrupted()) {
Task task = queue.take();
try { handle(task); }
catch (Exception ex) { recordFailure(task, ex); }
}
} catch (InterruptedException ex) {
Thread.currentThread().interrupt(); // 让线程池知道这是正常停机
}
});
}
// 生产端：queue.put(task)；停机时先停止生产，再等待队列消费完并 shutdown
有界队列是关键：无界队列会把压力转成堆内存增长，最终 OOM。关闭时可用“毒丸”或 shutdown + 中断，任务处理要有幂等键，失败要区分可重试和不可重试。吞吐受最慢环节限制，盲目增加消费者可能把数据库连接池打满。
拓展：队列满如何拒绝/降级、消费者异常如何恢复、消息顺序是否重要、是否允许丢弃低优先级任务。notify/notifyAll、公平锁、批量拉取和背压都是常见追问。
往项目引：图片处理、导入校验、异步通知等耗时任务可先用进程内有界队列；跨实例或需持久化时升级为 MQ，并补上确认、重试、死信和监控。不要把进程内队列当成可靠消息系统。
给学员的手撕题心法
- 先复述约束：输入规模、是否有序、是否允许修改原数据、返回一个还是全部结果。
- 写不变量：例如堆保存当前 TopK、二分区间始终包含答案、快慢指针的相对距离。
- 代码后过边界：空输入、单元素、重复值、极值、溢出、异常和中断。
- 报复杂度并说明取舍：时间、额外空间、最坏情况，以及为什么没有选择另一种数据结构。
- 最后接项目：说明同一思想对应的缓存、榜单、任务队列或数据校验场景；没有真实经历就说“可这样落地”，不要编造线上数字。
你能答到第几层？
- 能讲清不变量、复杂度、边界并写出核心代码，说明基本功过关。
- 能比较两种方案、解释最坏情况和失败处理，才算真正理解。
- 能把算法映射到项目约束，并用测试或监控验证，才是面试官期待的工程答案。
这是面试专题的「算法手撕篇」。网站上还有并发、MySQL、Redis、Spring、微服务、消息队列、JVM、安全认证、Java 基础、计算机基础与 Linux、设计模式、项目场景等系统整理。
更多 Java 面试专题：smallredtech.com
简历与辅导咨询，加微信：Ahongbb666（备注「面试题」）