数据结构与算法¶

面试追问地图¶

算法题除了写出代码，还要主动说明不变量、边界条件、复杂度和可替代方案。

一、数据结构与算法¶

数组 vs 链表¶

数组查询 O(1) 的原因 ：连续内存 + 相同类型，通过 基地址 + 下标 * 元素大小 直接计算内存地址。

通用概念：连续内存带来的局部性让数组在实践中常胜过复杂度更优的链表。

栈 vs 队列¶

• 栈 ：LIFO（后进先出），push/pop 都在栈顶，用于函数调用、表达式求值
• 队列 ：FIFO（先进先出），队尾插入队首删除，用于任务调度、BFS

常见队列类型¶

• 顺序队列 ：连续存储，可能假溢出
• 链式队列 ：链表实现，动态大小
• 循环队列 ：首尾相接，避免假溢出
• 双端队列 ：两端都可插入/删除
• 优先级队列 ：按优先级出队，通常用堆实现

用两个栈实现队列¶

一个栈 stackPush 负责入队，一个栈 stackPop 负责出队。出队时若 stackPop 为空，将 stackPush 全部倒入 stackPop。入队均摊 O(1)，出队均摊 O(1)。

平衡二叉树¶

左右子树高度差不超过 1。目的是避免 BST 退化为链表（O(n)），维持 O(log n) 操作复杂度。

红黑树性质¶

1. 节点红色或黑色
2. 根节点黑色
3. 叶子节点（NIL）黑色
4. 红色节点的子节点必须黑色
5. 根到叶子的每条路径黑色节点数相同

最长路径不超过最短路径 2 倍，增删查 O(log n)。

红黑树 vs AVL 树¶

实际应用：Java TreeMap/TreeSet 用红黑树；epoll 用红黑树保存 socket。

跳表¶

多层有序链表，通过索引加速查找。增删查平均 O(log n)。Redis ZSet 用跳表实现，层高随机化细节与「为什么不用 B+树」见 Redis。

时间轮¶

是什么：环形数组 + 链表，专为海量定时任务设计。数组每格代表一个时间刻度（如 100ms），任务按到期时间取模挂到对应格子的链表上；指针每 tick 前进一格，执行该格到期任务。

为什么这么设计：

超出一轮范围的任务怎么办： - 轮次法（Netty HashedWheelTimer）：任务记 rounds，指针扫到时 rounds > 0 则减一跳过 - 层级时间轮（Kafka）：秒轮转完进分钟轮，像水表刻度，溢出任务降级到上层轮

常见追问 - 精度和空间怎么取舍？→ tick 越小精度越高但空转越多；Kafka 用 DelayQueue 推进层级时间轮，避免空转。 - 实际应用？→ Netty 连接超时检测、Kafka 延迟操作、Dubbo 重试；业务层的订单超时取消方案对比见系统设计。

B+ 树 vs B 树 vs 红黑树¶

B+ 树是数据库索引首选 ：树高更低（磁盘 I/O 少），叶子链表支持高效范围查询。

通用概念：这三者不是三个独立结构，而是同一取舍在不同介质定价下的三个解——树。红黑树的旋转次数摊还后是常数，这正是它在内存里胜过 AVL 的原因。

堆¶

完全二叉树，大顶堆/小顶堆。用数组存储，节点 i 的左右子节点为 2i+1、2i+2。

堆排序 ：建堆 O(n) + 排序 O(n log n)，原地排序但不稳定。

前缀树（Trie）¶

利用公共前缀减少比较次数。根不含字符，每节点子节点字符不同。用于搜索引擎自动补全、拼写检查、路由表最长前缀匹配。

LRU 缓存淘汰¶

哈希表 + 双向链表 。访问时将节点移到链表头部，淘汰时删除尾部节点。插入/查找/删除均 O(1)。

布隆过滤器¶

位数组 + 多个哈希函数。判断元素是否在集合中： - 返回不存在 -> 一定不存在 - 返回存在 -> 可能存在 （有误判率）

时间复杂度 O(k)，k 为哈希函数个数。适用于 IP 黑名单、缓存穿透防护等。

哈希表冲突解决¶

• 链地址法 ：每个桶挂链表，JDK 1.8+ HashMap 链表长度 >= 8 且数组 >= 64 时转红黑树
• 开放寻址法 ：线性探测/二次探测/双重哈希，ThreadLocalMap 用此方式

负载因子 ：元素数/桶数，Java HashMap 默认 0.75

排序算法复杂度¶

快排原理¶

分治策略：选基准 -> partition 分成左右两部分 -> 递归排序。 最坏 O(n^2) ：每次选到最大/最小值（已有序数组），优化：随机选基准或三数取中。

// 快速排序模板
void quickSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int i = l, j = r, pivot = nums[l + (r - l) / 2];  // 三数取中
    while (i <= j) {
        while (nums[i] < pivot) i++;
        while (nums[j] > pivot) j--;
        if (i <= j) { swap(nums, i, j); i++; j--; }
    }
    quickSort(nums, l, j);
    quickSort(nums, i, r);
}

归并排序原理¶

分治：从中间分开 -> 递归排序两半 -> 合并两个有序数组。 最坏 O(n log n)，稳定，需要 O(n) 额外空间。适用于外部排序、链表排序。

// 归并排序模板
void mergeSort(int[] nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(nums, l, mid);
    mergeSort(nums, mid + 1, r);
    int[] temp = new int[r - l + 1];
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r)   temp[k++] = nums[j++];
    System.arraycopy(temp, 0, nums, l, temp.length);
}

堆排序¶

// 堆排序模板（大顶堆 → 升序）
void heapSort(int[] nums) {
    int n = nums.length;
    for (int i = n / 2 - 1; i >= 0; i--) heapify(nums, n, i);  // 建堆
    for (int i = n - 1; i > 0; i--) {
        swap(nums, 0, i);                                       // 堆顶→末尾
        heapify(nums, i, 0);                                    // 调整堆
    }
}
void heapify(int[] nums, int n, int i) {
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && nums[left] > nums[largest]) largest = left;
    if (right < n && nums[right] > nums[largest]) largest = right;
    if (largest != i) { swap(nums, i, largest); heapify(nums, n, largest); }
}

排序稳定性¶

相同关键字的元素在排序后保持原始相对顺序。归并、冒泡、插入稳定；快排、堆排、选择不稳定。

外部排序（大数据排序）¶

1. 部分排序 ：拆分文件，每块内存排序（快排），生成有序"顺段"
2. 归并 ：多路归并合并顺段，借助败者树减少归并层数降低 I/O

Top-K 问题（找最大前 K 个）¶

• K 小 ：最小堆，O(N log K)
• K 大 ：快速选择，平均 O(N)
• 简单方案 ：全排序 O(N log N)

二分查找¶

对有序数组 O(log n) 查找。

常见坑 ： - 防止溢出：mid = left + (right - left) / 2 - 边界写法统一：闭区间 [left, right] 用 left <= right，左闭右开用 left < right - 变体题：第一个等于、最后一个等于、第一个大于等于等

DFS vs BFS¶

二叉树遍历¶

DFS 三种 ：前序（根左右）、中序（左根右，BST 中序=升序）、后序（左右根） BFS 一种 ：层序遍历（队列实现）

链表操作¶

反转链表 ：迭代（三指针 prev/curr/next）或递归。

判断环/找环入口 ：快慢指针。相遇后一个指针回到头部，两指针同步走，再次相遇处即环入口。

动态规划¶

将大问题拆为重叠子问题，记录子问题解避免重复计算。

两个特征 ：最优子结构、重叠子问题。 解题套路 ：定义状态 -> 状态转移方程 -> 初始化 -> 遍历顺序

经典题 ：斐波那契、背包问题、LCS、LIS、编辑距离、打家劫舍、零钱兑换。

贪心 vs 动态规划¶

贪心：每步选当前最优，不保证全局最优（如找零钱特定面值可贪心）。 DP：枚举所有子问题解，一定得到最优解但更慢。

时间/空间复杂度分析¶

常见等级：O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

规则 ：只看最高阶、忽略常数系数、加法取最大、乘法相乘。

二、海量数据问题¶

海量数据问题如何选择方案？¶

先量化四件事：数据规模与单条大小、可用内存、结果要精确还是允许误差、数据能否多遍扫描。然后再选工具，而不是看到“大数据”就回答分库分表。

分治为什么通常按 hash 分片？¶

当全部数据放不进内存时，用 hash(key) % N 写入 N 个文件，使相同 key 必定进入同一文件，再逐个加载统计或判重。N 要按最坏分片而非平均值估算；若热点 key 导致倾斜，可先采样、增加分片数或对热点单独处理。

按范围分片便于有序归并，但要求已知分布，否则边界可能严重不均。分治的代价是额外磁盘 I/O、临时空间和多阶段失败恢复。

Bitmap 和 Bloom Filter 如何取舍？¶

Bitmap 用一个 bit 表示值域中的一个整数，能精确判定、交并集也高效。例如 10 亿以内的非负整数约需 10^9 / 8 字节，即约 119 MiB，不是 1 GB。若 ID 是稀疏 64 位值，可先分桶或使用压缩位图。

Bloom Filter 用多个哈希把元素映射到位数组，空间更省，但“可能存在”包含假阳性；“一定不存在”可信。它适合挡住大部分无效查询，不能单独作为计费、权限等精确判断依据。公式与 Redis 实现见 Redis。

外部排序和 Top-K 有什么区别？¶

外部排序需要输出全局有序结果：把可装入内存的块分别排序写盘，再用小顶堆做多路归并。Top-K 只保留最大的 K 个，扫描数据时维护大小为 K 的小顶堆即可，无需排序所有数据。

若数据分布在多机，每个分片先求局部 Top-K，再对至多 机器数 × K 个候选求全局 Top-K。这个结论适用于按“同一比较规则”取 Top-K；若求全局词频 Top-K，必须先把相同 key 的计数合并，不能直接合并每台机器的局部热门词。