Java 后端真实面试专题 · 算法手撕篇

中大厂（虾皮、BOSS、天猫、爱奇艺、日志易…）现场会让你手写算法。这一篇是真实面经里出现过的高频手撕题，每题三段： ① 思路（怎么想、复杂度）→ ② 关键代码/拓展（写法要点、变体、最优解）→ ③ 它考你什么 / 用在哪。

年限标签：🟢 3年内　🔴 3年+ ⭐ 手撕题别只背答案，讲清思路 + 复杂度 + 边界，比默写代码更重要。

1. 🔴 一亿个数，找出最大的前 K 个（TopN）

思路：不能全排序（内存放不下、O(nlogn) 浪费）。用小顶堆：维护一个大小为 K 的小顶堆，遍历数据，比堆顶大就替换堆顶。时间 O(n·logK)、空间 O(K)。

关键代码/拓展：

PriorityQueue<Integer> heap = new PriorityQueue<>(); // 小顶堆
for (int x : nums) {
    if (heap.size() < k) heap.offer(x);
    else if (x > heap.peek()) { heap.poll(); heap.offer(x); }
}

数据量超内存：分批/分片读，每片求 TopK，再归并（MapReduce 思想）。
找最小 K 个就用大顶堆，反过来。

它考你什么：海量数据处理思维 + 堆的运用。⭐这是 TopN 经典题，几乎大厂必考。可接到项目"实时热销榜 TopN（Redis ZSet）"。

2. 🔴 手写一个 LRU 缓存

思路：LRU（最近最少使用）要 O(1) 的 get/put。用 HashMap + 双向链表：HashMap 存 key→节点（O(1) 查），双向链表按访问顺序排（最近用的放头、淘汰尾部）。

关键代码/拓展：

get：存在则移到链表头、返回值；put：存在则更新移到头、不存在则插头，超容量删尾。
Java 偷懒写法：继承 LinkedHashMap，重写 removeEldestEntry，构造时 accessOrder=true。

class LRU extends LinkedHashMap<Integer,Integer> {
    int cap;
    LRU(int cap){ super(cap,0.75f,true); this.cap=cap; }
    protected boolean removeEldestEntry(Map.Entry e){ return size()>cap; }
}

面试一般要你手写双向链表版，体现你懂原理。

它考你什么：数据结构组合（哈希 + 链表）。⭐高频，且直接对应 Redis 的 LRU 淘汰策略，能往项目引。

3. 🟢 三个线程交替打印，把数字累加到 100（或交替打印 ABC）

思路：线程间协调顺序——用 synchronized + wait/notifyAll 判断"是否轮到自己"，或用 ReentrantLock + 多个 Condition，或 Semaphore 串起来。

关键代码/拓展：

核心：每个线程循环里判断"当前该不该我做"，不该就 wait，做完唤醒下一个。
变体：交替打印奇偶数、ABC、生产者消费者。

它考你什么：多线程协调/通信（wait-notify、Condition）。⭐能接到"怎么保证多线程有序"这道并发题。

4. 🟢 反转一个链表

思路：双指针迭代——prev、cur，遍历时把 cur.next 指向 prev，逐个反转。时间 O(n)、空间 O(1)。

关键代码/拓展：

ListNode prev = null, cur = head;
while (cur != null) {
    ListNode next = cur.next;
    cur.next = prev; prev = cur; cur = next;
}
return prev;

变体：递归反转、反转部分区间、K 个一组反转。

它考你什么：链表指针操作基本功。最基础的手撕题，一定要写得熟。

5. 🟢 两数之和（给数组和目标，找两个数和为 target）

思路：用 HashMap 边遍历边存——对每个数 x，查 map 里有没有 target - x，有就找到，没有就把 x 存入。时间 O(n)。

关键代码/拓展：

Map<Integer,Integer> map = new HashMap<>();
for (int i=0;i<nums.length;i++){
    if (map.containsKey(target-nums[i])) return new int[]{map.get(target-nums[i]), i};
    map.put(nums[i], i);
}

暴力是 O(n²)，用哈希换空间降到 O(n)——典型"空间换时间"。

它考你什么：哈希表的运用、把 O(n²) 优化到 O(n) 的意识。

6. 🟢 统计一组数据里出现频率最高的前 N 个

思路：先用 HashMap 统计每个元素的频率，再用小顶堆取频率 Top N（结合了 TopN）。时间 O(n + m·logN)。

关键代码/拓展：

map.entrySet 进堆，堆按频率比较，维护大小 N。
这就是真实面经里"找最常听的 3 首歌""top5 单词"。

它考你什么：哈希统计 + 堆，是 TopN 的变体。

7. 🔴 二叉树的最近公共祖先（LCA）

思路：递归——从根往下找，如果当前节点是 p 或 q 就返回它；递归左右子树，如果左右都返回了非空，说明 p、q 分别在两侧，当前节点就是 LCA；否则返回非空的那一边。

关键代码/拓展：

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;
    return l!=null?l:r;
}

变体：二叉搜索树的 LCA（利用有序性更简单）。

它考你什么：二叉树递归 + 分治思维。

8. 🟢 校验一个字符串/char 数组是否是合法 IPv4 地址

思路：按 . 分成 4 段，校验：① 正好 4 段；② 每段是数字、0~255；③ 没有前导零（"01" 非法）；④ 不为空。

关键代码/拓展：

split("\\.") 后逐段判断（注意 split 末尾空串问题）。
不让用自带 API 时，手动遍历计数点号、逐字符判断。

它考你什么：字符串处理 + 边界考虑（前导零、空段、越界）——边界是这题的坑。

9. 🔴 买可乐：n 元买 n 瓶，2 个空瓶换 1 瓶，n 元能喝几瓶？

思路：模拟——初始 n 瓶，喝完有 n 个空瓶，每 2 个空瓶换 1 瓶继续喝……循环到空瓶不足 2 个。或数学归纳出结果是 2n-1。

关键代码/拓展：

int total=n, empty=n;
while(empty>=2){ int newOne=empty/2; total+=newOne; empty=empty%2+newOne; }

数学法：除最后一瓶外每瓶都能"循环"产生价值，结论 2n-1。
面试官常要"模拟 + 数学"两种解法。

它考你什么：模拟能力 + 找数学规律。

10. 🟢 冒泡排序 / 快速排序手写

标准答：

冒泡：相邻比较交换，每轮把最大的冒到末尾，O(n²)。
快排：选基准、分区（小的左、大的右）、递归，平均 O(nlogn)。

// 快排分区核心
void quickSort(int[] a,int l,int r){
    if(l>=r)return; int p=partition(a,l,r);
    quickSort(a,l,p-1); quickSort(a,p+1,r);
}

拓展：

常见排序复杂度、稳定性要记（归并稳定 O(nlogn)、快排不稳定）。
快排最坏 O(n²)（有序数组），随机选基准优化。

它考你什么：基础排序 + 复杂度。冒泡几乎送分，快排考分治。

11. 🟢 二分查找

思路：有序数组里查目标，每次比中间值、折半缩小范围，O(logn)。

关键代码/拓展：

int l=0,r=n-1;
while(l<=r){ int m=l+(r-l)/2;
    if(a[m]==target)return m;
    else if(a[m]<target)l=m+1; else r=m-1; }
return -1;

坑：mid=l+(r-l)/2 防溢出；边界 <= 还是 < 要想清。
变体：找左/右边界、旋转数组查找。

它考你什么：二分边界处理——最容易写错边界的题。

12. 🔴 约瑟夫环：100 人围圈报数，剔除奇数位，循环到剩一人

思路：可以用队列/链表模拟，也可以数学推导。题里"剔除奇数位"反复进行，最后剩下的是 ≤100 的最大 2 的幂（这类"每轮剔一半"的变体规律）。

关键代码/拓展：

标准约瑟夫环（每数到 m 出局）有递推公式 f(n)=(f(n-1)+m)%n。
用循环链表模拟最直观。

它考你什么：模拟 + 找规律 / 递推。

13. 🔴 36 进制（0-9 a-z）两个数相加

思路：和"字符串大数相加"一样——从末尾对齐逐位相加、处理进位，只是逢 36 进 1，字符和数值要互转（0-9→0~~9，a-z→10~~35）。

关键代码/拓展：

用一个函数做 char↔int 转换，逐位加 + 进位，结果反转。
变体：二进制/十进制大数相加、字符串相乘。

它考你什么：进制转换 + 大数模拟 + 进位处理。

14. 🟢 删除链表中值为 n 的节点

思路：用**虚拟头节点（dummy）**简化头节点删除的边界，遍历时 prev.next = cur.next 跳过目标节点。

关键代码/拓展：

ListNode dummy=new ListNode(0); dummy.next=head;
ListNode prev=dummy;
while(prev.next!=null){
    if(prev.next.val==n) prev.next=prev.next.next;
    else prev=prev.next;
}
return dummy.next;

dummy 头节点是链表题去边界的通用技巧。

它考你什么：链表操作 + 虚拟头节点技巧。

15. 🟢 一个数组包含 0-9，统计每个数字出现的次数

思路：用一个长度 10 的计数数组，遍历一遍 count[num]++。O(n) 时间、O(1) 空间（桶计数）。

关键代码/拓展：

这是"计数排序"的思想，值域小时用桶/计数数组最快。
扩展：字符统计用 int[26]/int[128]。

它考你什么：计数/桶思想，值域有限时空间换时间。

16. 🔴 给一亿个数找最大 100 个，用数组还是链表？为什么？

思路：用数组（构建堆）。原因：数组随机访问 O(1)、内存连续、缓存友好，堆操作要频繁按下标访问；链表随机访问 O(n)、有指针开销，不适合。

拓展：

这题是 TopN + "数据结构选型"的结合，考你理解数组和链表的本质差异。

它考你什么：数据结构选型的判断力——不只是会写，还要会选。

17. 🟢 判断一个链表是否有环 / 找环入口

思路：快慢指针——慢指针走一步、快指针走两步，相遇说明有环。找入口：相遇后，一个指针回到头、和慢指针同速走，再次相遇点就是环入口。

关键代码/拓展：

ListNode slow=head,fast=head;
while(fast!=null&&fast.next!=null){
    slow=slow.next; fast=fast.next.next;
    if(slow==fast) return true; }
return false;

快慢指针还能求中点、求倒数第 k 个。

它考你什么：双指针技巧（快慢指针）。

18. 🟢 实现一个生产者-消费者模型

思路：用阻塞队列 BlockingQueue 最简单——生产者 put（满了阻塞）、消费者 take（空了阻塞），队列内部已处理同步。手写则用 synchronized + wait/notify 或 ReentrantLock + Condition。

关键代码/拓展：

BlockingQueue 是首选，体现"用对工具"。
手写版考 wait/notify 的正确使用（while 判断、notifyAll）。

它考你什么：并发协调 + 阻塞队列。⭐能接到项目"用阻塞队列做缓冲削峰"。

给学员的手撕题心法

先说思路再写代码：讲清解法、复杂度、边界，面试官就知道你会了——很多时候思路对了代码细节面试官不苛求。
必背的几道：反转链表、两数之和、二分、快排、TopN（堆）、LRU、快慢指针——这几道覆盖大部分场景。
边界是高频扣分点：空输入、单元素、越界、链表头节点、二分的 <=，写完口头过一遍边界。
数据结构选型也是考点：TopN 用堆、O(1) 查用哈希、有序查找用二分、缓存用哈希+链表。

你能答到第几层？

思路 + 代码 + 边界 + 复杂度都能讲清：中大厂手撕这关你能过。
有思路写不利索：多动手写几遍，手撕靠肌肉记忆。
没思路：先把上面"必背的几道"练熟，覆盖 80% 场景。

这是面试专题的「算法手撕篇」，网站上还有并发、MySQL、Redis、Spring、微服务、消息队列、JVM、安全认证、Java基础、计基与Linux、设计模式、项目场景等系统整理。 🌐 更多真实面试专题与资料：smallredtech.com 💬 想系统学 / 简历与辅导咨询，加微信：Ahongbb666（备注「面试题」）