Q79 - 数据结构与算法面试实战
共50道题 | 难度分布:★★★★☆平均 | 20K+ Java后端岗位必考
一、数组与链表(1-6)
数组与链表的区别?各自适用场景?
★★★★★
- 数组:连续内存、O(1)随机访问、O(n)插入删除、缓存友好(空间局部性)。
- 链表:非连续内存、O(n)查找、O(1)插入删除(已知位置)、缓存不友好。
- 适用场景:
- 数组:频繁查找、已知大小、多维数据。
- 链表:频繁插入删除、大小不定、实现LRU缓存。
- ArrayList vs LinkedList:
- ArrayList:数组实现,get(i)是O(1),add(i, e)是O(n)。
- LinkedList:双向链表,get(i)是O(n),add/remove是O(1)(已知节点)。
- 实际中ArrayList几乎总是更快(CPU Cache Line预取)。
反转链表?检测环?找中间节点?
★★★★★
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
- 检测环(快慢指针):快指针走两步、慢指针走一步。相遇则有环。
- 找中间节点:快慢指针,快到尾时慢在中间。
- 合并两个有序链表:双指针比较,小的先接入。
HashMap的底层实现原理?
★★★★★
- JDK 1.8:数组 + 链表 + 红黑树。
- 流程:
1. 计算hash:(h = key.hashCode()) ^ (h >>> 16)(扰动函数减少碰撞)。
2. 定位桶:hash & (n-1)(等价于hash % n,n是2的幂)。
3. 桶为空→直接放入。不为空→遍历链表/红黑树。
4. 链表长度≥8且数组长度≥64→树化(TreeNode)。
5. 链表长度≤6→退化回链表。
- 扩容:
- 负载因子0.75,元素数 > capacity * 0.75时扩容为2倍。
- JDK 1.8优化:元素在新数组的位置要么原位置,要么原位置+oldCap。
- 线程不安全:put并发可能导致链表成环(JDK 7头插法)。用ConcurrentHashMap。
ArrayList的扩容机制?
★★★★☆
- 默认初始容量10(首次add时创建)。
- 扩容:newCapacity = oldCapacity + (oldCapacity >> 1) = 1.5倍。
- Arrays.copyOf()拷贝旧数组到新数组。
- 面试要点:预知大小时用new ArrayList<>(1000)避免多次扩容。
LRU缓存如何实现?
★★★★★
- 数据结构:HashMap + 双向链表。
- get(key):HashMap查找→移到链表头部→返回值。O(1)。
- put(key, value):
- 已存在→更新值→移到头部。
- 不存在→新节点加到头部→超容量则删除尾部(最久未使用)。
- Java实现:LinkedHashMap(accessOrder=true)+ removeEldestEntry重写。
- 面试变形:LFU(最不经常使用)→ 两个HashMap + 频率桶。
跳表的原理?为什么Redis用跳表而不用红黑树?
★★★★☆
- 跳表(SkipList):多层有序链表。查找从最高层开始,逐层下降。O(logN)。
- 与平衡树对比:
- 实现简单(比红黑树简单得多)。
- 范围查询高效(链表遍历)。
- 内存占用可控(随机层数,平均1.33个指针/节点)。
- 并发友好(CAS操作链表比树简单)。
- Redis ZSET用跳表原因:实现简单+范围操作高效+并发友好。
二、栈、队列与哈希(7-12)
栈与队列的应用场景?
★★★★☆
- 栈(LIFO):函数调用栈、括号匹配、表达式求值、浏览器前进后退、DFS。
- 队列(FIFO):BFS、任务调度、消息队列、缓冲区。
- 双端队列(Deque):滑动窗口最大值、回文检测。
- 单调栈:下一个更大元素、柱状图最大矩形。
- 优先队列(堆):Top K问题、合并K个有序链表、Dijkstra。
有效的括号?用栈实现队列?用队列实现栈?
★★★★☆
- 有效括号:遇到左括号入栈,遇到右括号检查栈顶是否匹配。
- 栈实现队列:两个栈,一个入队栈、一个出队栈。出队时如果出队栈为空,将入队栈全部倒入。
- 队列实现栈:一个队列,push时先加入队尾,再将前面的元素逐个移到后面。
滑动窗口最大值?
★★★★★
- 单调递减双端队列:队列存索引,保证队首是窗口最大值。
- 步骤:
1. 新元素入队前,移除队尾所有小于新元素的值(它们不可能成为最大值)。
2. 检查队首是否超出窗口左边界→移除。
3. 窗口形成后,队首即为最大值。
- 时间复杂度:O(n)(每个元素最多入队出队各一次)。
哈希冲突的解决方法?
★★★★★
- 链地址法(拉链法):冲突元素用链表存储。JDK HashMap使用。
- 开放寻址法:
- 线性探测:hash+1, hash+2, ... 聚集问题。
- 二次探测:hash+1², hash+2², ...
- 双重哈希:hash1 + i*hash2。
- 再哈希:用另一个哈希函数。
- Java中的选择:
- HashMap:链地址法(链表+红黑树)。
- ThreadLocal:开放寻址法(线性探测)。
- ConcurrentHashMap:链地址法(链表+红黑树+ synchronized+CAS)。
一致性哈希的原理?虚拟节点的作用?
★★★★★
- 传统哈希取模问题:增减节点时大量数据迁移。
- 一致性哈希:
- 哈希环(0~2^32-1),节点和数据都映射到环上。
- 数据顺时针找最近的节点。
- 增减节点只影响相邻节点间的数据。
- 虚拟节点:
- 问题:节点少时分布不均匀(数据倾斜)。
- 解决:每个物理节点对应多个虚拟节点,均匀分布在环上。
- 应用:Redis Cluster(Hash Slot 16384个)、分布式缓存、负载均衡。
布隆过滤器的原理?误判率如何控制?
★★★★☆
- 原理:位数组 + 多个哈希函数。添加元素时多个哈希位置设为1。查询时所有位都为1则可能存在。
- 特性:可能有假阳性(误判存在),但不会有假阴性(不存在的一定不存在)。
- 误判率控制:
- 增大位数组长度。
- 增加哈希函数个数(但太多反而增加误判)。
- 最优哈希函数个数:k = (n/m) × ln2(n=元素数,m=位数组长度)。
- 应用:缓存穿透防护(Redis+布隆过滤器)、爬虫URL去重、邮箱垃圾邮件过滤。
三、树与图(13-20)
二叉树的前中后序遍历(递归+迭代)?
★★★★★
- 递归:简单直接,注意理解访问顺序。
- 迭代(栈模拟):
- 前序:根→左→右。先push右再push左。
- 中序:左→根→右。一路向左入栈,弹出时访问,转向右子树。
- 后序:左→右→根。前序的"根右左"反转。
- 层序遍历(BFS):队列。
红黑树的性质?为什么HashMap用红黑树?
★★★★★
1. 节点是红色或黑色。
2. 根节点是黑色。
3. 叶子节点(NIL)是黑色。
4. 红色节点的子节点必须是黑色(不能连续红)。
5. 从任一节点到其叶子的所有路径包含相同数目的黑色节点。
- 红黑树保证:最长路径不超过最短路径的2倍。O(logN)查找。
- 为什么用红黑树:
- 链表过长(≥8)时查找退化为O(n),红黑树保证O(logN)。
- 比AVL树更适合插入/删除频繁的场景(AVL更严格平衡,旋转更多)。
- TreeMap/TreeSet底层就是红黑树。
B树与B+树的区别?为什么数据库用B+树?
★★★★★
- B树:每个节点都存数据,子节点数=度数。
- B+树:
- 非叶子节点只存键值(索引),不存数据。
- 数据都在叶子节点。
- 叶子节点之间有双向链表连接。
- 为什么数据库用B+树:
- 查询稳定:每次都走到叶子节点,路径长度相同。
- 范围查询高效:叶子链表顺序遍历。
- 一个节点存更多键→树更矮→IO次数更少。
- InnoDB一个页16KB,存数百个键,3层B+树可存2000万+行。
- 面试要点:理解"磁盘IO次数"是关键指标,树越矮IO越少。
二叉搜索树的第K小元素?验证BST?
★★★★☆
- 第K小元素:中序遍历(左→根→右),第K个访问的就是第K小。
- 验证BST:递归检查每个节点的值在(min, max)范围内。
Trie(前缀树)的原理与应用?
★★★★☆
- 原理:多叉树,每条边代表一个字符。从根到某节点的路径组成一个字符串。
- 时间复杂度:插入/查找O(L),L为字符串长度。与数据量无关。
- 应用:自动补全、拼写检查、IP路由表、敏感词过滤。
- 空间优化:基数树(压缩公共前缀)、Double-Array Trie。
图的遍历?DFS与BFS?
★★★★☆
- DFS(深度优先):栈/递归。适合找路径、连通性、拓扑排序。
- BFS(广度优先):队列。适合最短路径(无权图)、层序遍历。
- 拓扑排序:DFS后序逆序或BFS(Kahn算法:入度为0入队)。
- 最短路径:
- 无权图:BFS。
- 正权图:Dijkstra(贪心+优先队列)O(E log V)。
- 负权图:Bellman-Ford O(V×E)。
- 全源:Floyd-Warshall O(V³)。
最小生成树?Kruskal vs Prim?
★★★☆☆
- Kruskal:按边权排序,用并查集判断是否形成环。O(E log E)。适合稀疏图。
- Prim:从任一节点开始,每次选最小权边扩展。O(E log V)。适合稠密图。
- 并查集:路径压缩+按秩合并,查询/合并近乎O(1)。
如何判断有向图是否有环?
★★★★☆
- DFS三色标记法:白色(未访问)→灰色(访问中)→黑色(访问完)。遇到灰色则有环。
- 拓扑排序(Kahn):统计入度,入度为0入队。若最后处理的节点数<V则有环。
- 应用:编译依赖分析、课程安排、任务调度。
四、排序与查找(21-27)
常见排序算法的对比?
★★★★★
| 算法 | 平均 | 最坏 | 空间 | 稳定性 |
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 选择排序 | O(n²) | O(n²) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
| 基数排序 | O(d×n) | O(d×n) | O(n) | 稳定 |
- Java Arrays.sort():
- 基本类型→双轴快排(DualPivotQuicksort)。
- 对象类型→TimSort(归并+插入混合,稳定)。
快速排序的原理?如何优化?
★★★★★
- 原理:选pivot分区(小于pivot在左,大于在右),递归左右两部分。
- 优化:
- 随机化pivot:避免最坏情况(已排序数组)。
- 三数取中:选首、中、尾的中位数作为pivot。
- 小数组切换插入排序(<47个元素)。
- 三路快排:将等于pivot的元素集中到中间,处理大量重复元素。
- 面试要点:理解为什么最坏O(n²)但实践中最快(Cache友好、原地排序)。
二分查找的变体?
★★★★★
- 标准二分:查找目标值。
- 左边界:找到第一个等于target的位置。
- 右边界:找到最后一个等于target的位置。
- 查找第一个大于等于target的。
- 查找最后一个小于等于target的。
- 注意:mid = left + (right - left) / 2 防止溢出。
Top K问题的解法?
★★★★★
- 方法一:小顶堆(大小为K)。遍历所有元素,堆满后比堆顶大则替换。O(n log K)。
- 方法二:快排分区(QuickSelect)。第K大=分区后下标为n-K的元素。平均O(n)。
- 方法三:排序后取前K个。O(n log n)。
- 海量数据(内存放不下):
- 分治:文件分片→每片Top K→合并Top K。
- 堆排序合并。
归并排序的应用?逆序对计数?
★★★★☆
- 归并排序应用:
- 大文件外部排序(无法全部加载到内存)。
- 链表排序(快排不适合链表)。
- 逆序对计数(归并时统计跨左右半部分的逆序对)。
- 逆序对:归并过程中,左半部分元素>右半部分元素时,左半部分剩余元素都与右半部分当前元素构成逆序对。
堆的原理与应用?
★★★★★
- 堆:完全二叉树,用数组存储。
- 大顶堆:父节点≥子节点。arr[i] ≥ arr[2i+1] && arr[i] ≥ arr[2i+2]。
- 小顶堆:父节点≤子节点。
- 核心操作:
- 上浮(sift up):插入后与父节点比较交换。O(log n)。
- 下沉(sift down):删除堆顶后,末尾元素放堆顶,向下调整。O(log n)。
- 应用:优先队列、Top K、堆排序、定时任务调度(Timer/DelayQueue)、Dijkstra。
搜索引擎的倒排索引原理?
★★★★☆
- 正排索引:文档ID→文档内容。
- 倒排索引:词项(Term)→ 包含该词的文档列表(Posting List)。
- 构建过程:文档→分词→Term Dictionary→Posting List。
- 查询过程:用户查询→分词→查倒排索引→交集/并集→排序返回。
- Elasticsearch:
- Term Dictionary用FST(有限状态转换器)存储。
- Posting List用Frame of Reference压缩+Roaring Bitmap。
- 面试要点:理解为什么ES搜索比MySQL LIKE快。
五、动态规划与贪心(28-35)
动态规划的核心思想?解题步骤?
★★★★★
- 核心思想:将问题分解为重叠子问题,记忆化存储避免重复计算。
- 解题步骤:
1. 定义状态(dp数组的含义)。
2. 状态转移方程。
3. 初始条件(base case)。
4. 遍历顺序。
5. 返回结果。
- 关键:找状态转移方程。从结果往前推,考虑最后一步的所有可能。
爬楼梯/斐波那契/零钱兑换?
★★★★★
- 爬楼梯:dp[i] = dp[i-1] + dp[i-2]。
- 斐波那契:同上,空间可优化为O(1)(只保留前两个值)。
- 零钱兑换:dp[i] = min(dp[i-coin] + 1) for all coins。求最少硬币数。
最长递增子序列(LIS)?
★★★★★
- 方法一(DP):dp[i] = max(dp[j]+1) for all j<i且nums[j]<nums[i]。O(n²)。
- 方法二(贪心+二分):维护一个递增数组,每个数用二分找到可替换的位置。O(n log n)。
最长公共子序列(LCS)?编辑距离?
★★★★☆
- LCS:dp[i][j] = 如果s1[i]==s2[j]则dp[i-1][j-1]+1,否则max(dp[i-1][j], dp[i][j-1])。
- 编辑距离:dp[i][j] = min(插入, 删除, 替换)。用于拼写纠错、DNA序列比较。
背包问题?0-1背包/完全背包?
★★★★★
- 0-1背包:每件物品最多用一次。dp[i][w] = max(不选i, 选i)。
- 降维:dp[w]逆序遍历。
- 完全背包:物品可重复使用。dp[w]正序遍历。
- 分组背包:每组只能选一个。
- 面试变形:零钱兑换(完全背包)、分割等和子集(0-1背包)。
股票买卖问题(通用解法)?
★★★★★
- 通用状态定义:dp[i][k][0/1] = 第i天、交易k次、持有/不持有。
- dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+price[i])(不持有=max(延续不持有, 卖出))
- dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-price[i])(持有=max(延续持有, 买入))
- 一次交易(k=1):遍历维护最低价格。
- 无限次交易(k=∞):所有上涨都吃。
- 两次交易(k=2):拆分为两个一次交易。
- 含冷冻期/手续费:状态转移加限制。
贪心算法的适用条件?
★★★★☆
- 适用条件:贪心选择性质 + 最优子结构。
- 经典问题:
- 活动选择:按结束时间排序,选最早结束的。
- 跳跃游戏:维护最远可达位置。
- 区间调度/合并:排序+贪心。
- 哈夫曼编码:优先队列合并最小频率。
- 贪心vs动态规划:贪心不做回溯,选择局部最优。如果局部最优不能保证全局最优则不能用贪心。
回溯算法的模板与应用?
★★★★★
void backtrack(路径, 选择列表) {
if (满足结束条件) { 结果.add(路径); return; }
for (选择 : 选择列表) {
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}
- 经典问题:N皇后、子集、组合、全排列、括号生成、单词搜索。
- 剪枝优化:排序+提前终止、used数组去重。
六、高频面试真题(36-50)
两数之和?三数之和?
★★★★★
- 两数之和:HashMap存值→索引,遍历时查target-nums[i]是否存在。O(n)。
- 三数之和:排序+双指针。固定一个数,左右指针收缩找两数之和。O(n²)。
- 去重:跳过重复的固定数和指针值。
合并两个有序数组/链表?合并K个有序链表?
★★★★★
- 合并两个:双指针比较,小的先接入。
- 合并K个:
- 方法一:优先队列(小顶堆),每次取最小元素。O(N log K)。
- 方法二:分治两两合并。O(N log K)。
二叉树的最近公共祖先?
★★★★★
- 普通二叉树:
- 左右子树都找到→当前节点就是LCA。
- 只在一边找到→返回找到的那边。
- BST:利用大小关系,第一个在p和q之间的节点就是LCA。
接雨水问题?
★★★★★
- 方法一(双指针):左指针和右指针,记录左右最大值。O(n) O(1)。
- 方法二(单调栈):维护递减栈,遇到更高的柱子时计算凹槽面积。
最长无重复子串?
★★★★★
- 滑动窗口 + HashMap/Set:
- 右指针扩展窗口,遇到重复字符时左指针收缩到重复字符之后。
- 记录最大窗口长度。
- O(n)时间。
全排列/子集?
★★★★☆
- 全排列:回溯+used数组标记已使用。
- 子集:每个元素选或不选(回溯)。或迭代:每加一个元素,将已有子集全部复制一份加上新元素。
二叉树的序列化与反序列化?
★★★★☆
- 前序遍历序列化:根→左→右,null用特殊字符(如#)标记。
- 反序列化:按前序重建,遇到#返回null。
实现一个线程安全的LRU缓存?
★★★★★
- 方案一:ConcurrentHashMap + ConcurrentLinkedDeque(粗粒度锁)。
- 方案二:分段锁(Stripe)+ HashMap + 双向链表。
- 方案三:ReadWriteLock保护整体结构。
- Java简化实现:
int capacity;
Map<K, V> map = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > capacity;
}
};
加synchronized或ReentrantLock保证线程安全。
设计一个限流器(令牌桶/漏桶)?
★★★★★
- 令牌桶:
- 以固定速率往桶中放令牌,桶满丢弃。
- 请求消耗令牌,桶空则拒绝。
- 允许突发流量(桶内有积累的令牌)。
- 漏桶:
- 请求进入桶中排队,以固定速率流出处理。
- 不允许突发,流量均匀。
- 实现:AtomicLong记录令牌数/上次补充时间。
- 分布式:Redis + Lua脚本(原子操作)。
如何实现一个简单的布隆过滤器?
★★★★☆
public class BloomFilter {
private BitSet bitSet;
private int bitSize;
private int[] seeds;
public boolean mightContain(String value) {
for (int seed : seeds) {
int hash = hash(value, seed);
if (!bitSet.get(hash % bitSize)) return false;
}
return true;
}
}
设计微信红包算法?
★★★★★
- 二倍均值法:
- 每次抢到的金额 = random(0.01, 剩余金额/剩余人数×2)。
- 保证每个人至少拿到0.01元。
- 最后一人拿剩余全部。
- 要求:金额随机但不过于悬殊。总金额精确。
路径总和I/II/III?
★★★★☆
- I:根到叶子路径和等于target。DFS递归。
- II:找出所有满足条件的路径。DFS+回溯。
- III:任意路径(不要求根到叶子)。前缀和+HashMap。O(n)。
大数据排序:100亿条数据排序?
★★★★☆
1. 分片:100亿数据分成1000个文件,每个1000万条。
2. 内排序:每个文件内部排序(快排/归并)。
3. 归并合并:K路归并(优先队列)。
- MapReduce思想:Map阶段局部排序 → Shuffle → Reduce阶段合并。
- 面试要点:理解内存放不下时的分治策略。
判断链表是否回文?
★★★☆☆
- 方法:快慢指针找中点 → 反转后半部分 → 双指针比较 → 恢复。
- O(n)时间,O(1)空间。
算法面试的综合策略?
★★★★★
1. 确认理解题意(边界条件、数据范围、特殊要求)。
2. 暴力解法(先做出来)。
3. 分析优化方向(时间/空间复杂度)。
4. 写出最优解。
5. 复杂度分析。
6. 测试用例(正常/边界/异常)。
- 复杂度速查:
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
- 10^8次运算≈1秒。n=10^5时O(n²)可能超时。
- Java面试高频数据结构:
- HashMap、ConcurrentHashMap
- ArrayList、LinkedList
- TreeMap(红黑树)
- PriorityQueue(堆)
- LinkedHashMap(LRU)
附:速查表
| 知识点 | 时间复杂度 | 关键技术 |
| HashMap | O(1)平均 | 数组+链表+红黑树 |
| 跳表 | O(logN) | 多层链表,Redis ZSET |
| B+树 | O(logN) | 数据库索引,叶子链表 |
| 快排 | O(n log n)平均 | 分治+pivot |
| 归并排序 | O(n log n) | 分治+稳定+外部排序 |
| 二分查找 | O(log n) | 有序数组,变体多 |
| Top K | O(n log K) | 小顶堆/QuickSelect |
| DFS/BFS | O(V+E) | 栈/队列 |
| 动态规划 | 视状态数 | 状态定义+转移方程 |
| 一致性哈希 | O(log N) | 哈希环+虚拟节点 |