← 返回首页 ❓ 面试题库
📑 本篇章节导航 (共7章,点击直达)
一、数组与链表(1-6)二、栈、队列与哈希(7-12)三、树与图(13-20)四、排序与查找(21-27)五、动态规划与贪心(28-35)六、高频面试真题(36-50)附:速查表

Q79 - 数据结构与算法面试实战

共50道题 | 难度分布:★★★★☆平均 | 20K+ Java后端岗位必考

一、数组与链表(1-6)

数组与链表的区别?各自适用场景?

★★★★★

反转链表?检测环?找中间节点?

★★★★★


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

HashMap的底层实现原理?

★★★★★

1. 计算hash:(h = key.hashCode()) ^ (h >>> 16)(扰动函数减少碰撞)。

2. 定位桶:hash & (n-1)(等价于hash % n,n是2的幂)。

3. 桶为空→直接放入。不为空→遍历链表/红黑树。

4. 链表长度≥8且数组长度≥64→树化(TreeNode)。

5. 链表长度≤6→退化回链表。

ArrayList的扩容机制?

★★★★☆

LRU缓存如何实现?

★★★★★

跳表的原理?为什么Redis用跳表而不用红黑树?

★★★★☆


二、栈、队列与哈希(7-12)

栈与队列的应用场景?

★★★★☆

有效的括号?用栈实现队列?用队列实现栈?

★★★★☆

滑动窗口最大值?

★★★★★

1. 新元素入队前,移除队尾所有小于新元素的值(它们不可能成为最大值)。

2. 检查队首是否超出窗口左边界→移除。

3. 窗口形成后,队首即为最大值。

哈希冲突的解决方法?

★★★★★

一致性哈希的原理?虚拟节点的作用?

★★★★★

布隆过滤器的原理?误判率如何控制?

★★★★☆


三、树与图(13-20)

二叉树的前中后序遍历(递归+迭代)?

★★★★★

红黑树的性质?为什么HashMap用红黑树?

★★★★★

1. 节点是红色或黑色。

2. 根节点是黑色。

3. 叶子节点(NIL)是黑色。

4. 红色节点的子节点必须是黑色(不能连续红)。

5. 从任一节点到其叶子的所有路径包含相同数目的黑色节点。

B树与B+树的区别?为什么数据库用B+树?

★★★★★

二叉搜索树的第K小元素?验证BST?

★★★★☆

Trie(前缀树)的原理与应用?

★★★★☆

图的遍历?DFS与BFS?

★★★★☆

最小生成树?Kruskal vs Prim?

★★★☆☆

如何判断有向图是否有环?

★★★★☆


四、排序与查找(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)稳定

快速排序的原理?如何优化?

★★★★★

二分查找的变体?

★★★★★

Top K问题的解法?

★★★★★

归并排序的应用?逆序对计数?

★★★★☆

堆的原理与应用?

★★★★★

搜索引擎的倒排索引原理?

★★★★☆


五、动态规划与贪心(28-35)

动态规划的核心思想?解题步骤?

★★★★★

1. 定义状态(dp数组的含义)。

2. 状态转移方程。

3. 初始条件(base case)。

4. 遍历顺序。

5. 返回结果。

爬楼梯/斐波那契/零钱兑换?

★★★★★

最长递增子序列(LIS)?

★★★★★

最长公共子序列(LCS)?编辑距离?

★★★★☆

背包问题?0-1背包/完全背包?

★★★★★

股票买卖问题(通用解法)?

★★★★★

贪心算法的适用条件?

★★★★☆

回溯算法的模板与应用?

★★★★★


  void backtrack(路径, 选择列表) {
      if (满足结束条件) { 结果.add(路径); return; }
      for (选择 : 选择列表) {
          做选择;
          backtrack(路径, 选择列表);
          撤销选择;
      }
  }

六、高频面试真题(36-50)

两数之和?三数之和?

★★★★★

合并两个有序数组/链表?合并K个有序链表?

★★★★★

二叉树的最近公共祖先?

★★★★★

接雨水问题?

★★★★★

最长无重复子串?

★★★★★

全排列/子集?

★★★★☆

二叉树的序列化与反序列化?

★★★★☆

实现一个线程安全的LRU缓存?

★★★★★


  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保证线程安全。

设计一个限流器(令牌桶/漏桶)?

★★★★★

如何实现一个简单的布隆过滤器?

★★★★☆


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;
    }
}

设计微信红包算法?

★★★★★

路径总和I/II/III?

★★★★☆

大数据排序:100亿条数据排序?

★★★★☆

1. 分片:100亿数据分成1000个文件,每个1000万条。

2. 内排序:每个文件内部排序(快排/归并)。

3. 归并合并:K路归并(优先队列)。

判断链表是否回文?

★★★☆☆

算法面试的综合策略?

★★★★★

1. 确认理解题意(边界条件、数据范围、特殊要求)。

2. 暴力解法(先做出来)。

3. 分析优化方向(时间/空间复杂度)。

4. 写出最优解。

5. 复杂度分析。

6. 测试用例(正常/边界/异常)。


附:速查表

知识点时间复杂度关键技术
HashMapO(1)平均数组+链表+红黑树
跳表O(logN)多层链表,Redis ZSET
B+树O(logN)数据库索引,叶子链表
快排O(n log n)平均分治+pivot
归并排序O(n log n)分治+稳定+外部排序
二分查找O(log n)有序数组,变体多
Top KO(n log K)小顶堆/QuickSelect
DFS/BFSO(V+E)栈/队列
动态规划视状态数状态定义+转移方程
一致性哈希O(log N)哈希环+虚拟节点