应对Java工程师面试中的算法部分,需要学习的重点,非重点章节

这个问题我以前回答过，但我找了一圈，怎么也找不到了，再回答一次。

首先强调一点的是，因为算法面试不是一个标准化的考试，所以没有一个规范的“考纲”，各个厂子的不同部门的不同时期的不同面试有可能存在偏差，比如最极端的例子，我听我的学生说过在美国 google 面试遇到网络流的问题。但网络流绝对不是重点。

（不过整体我认为，遇到这种很“极端”的问题，如果你能解决，肯定是加分；但不能解决，面试官应该也很清楚是正常的，不太会减分。当然另外一种情况就是其实部门或者企业没有想着招人，所以就是劝退的。什么手写红黑树都属于这一类。）

==========

下面就属于我认为的重点和非重点：

1）线性查找（重点）

2）选择排序，插入排序，冒泡排序 （重点）

3）动态数组，栈，队列（重点）

4）链表（重点）

5）归并排序，快速排序 （重点）

6）二分查找（重点）

7）二分搜索树（普通的 BST）（重点）

8）堆（重点） 

堆排序，尤其是 O(n) 的heapify （一般）

9）希尔排序（非重点）

但是各种排序算法的稳定性（重点）

10）线段树（非重点，可以先跳过去）

11）Trie （一般）

12）并查集 （一般）

13）AVL 树和红黑树

具体的实现可以不管。在强调，具体实现可以不管，遇到面试让你手写红黑树，你反过来让面试官手写一个给你看。

但是基本的概念要清楚，比如什么叫平衡树，不平衡有什么问题，红黑树不是严格的平衡树，而是达到了黑节点的平衡；红黑树统计意义上性能更优，Java 的 TreeMap 和 TreeSet 底层是红黑树，等等这些东东。

14）哈希表 （一般）

也是，基本概念需要了解。

15）SQRT 分解。非重点，跳过。

16）非比较排序，非重点，可以跳过

17）模式匹配（RK 和 KMP），非重点，可以跳过

18）随机算法部分还没有更新，我主要想将 Knuth Shuffle 和蓄水池抽样两个算法，这两个算法我划分为一般。这两个算法都不难，你要是有需要可以先找其他资料看一下。

==========

图论算法部分：

我单独出过一个课程介绍图论算法：https://coding.imooc.com/class/370.html

在这门课程中：

前七章：重点

第十三章的拓扑排序：重点

九章的哈密尔顿，十一章的最小生成树，十二章的有权图最短路径，我划分为一般。这几部分都是很“标准”的算法，理论上计算机专业的同学应该可以“无碍”的写出来。如果有时间就学习一下。

其他部分：桥，割点，欧拉路径，又想吐的 SCC，网络流，都是非重点，可以跳过。

==========

上面的部分主要集中在经典算法和数据结构（包括相应的应用）上，但是算法面试有可能考察很多算法设计领域的内容。关于算法设计，我之前出过一个课程，但是相对有些老，且视频是使用 C++ 讲解的，我就不推荐了。

整体关于算法设计，我的推荐是：在力扣上刷题。再刷题的过程中，遇到问题，再去有针对性的学习。可以参考我的这篇文章：https://www.imooc.com/article/317697

===========

最后，因为我看你的描述，你准备面试属于社招，强调一下：

1）社招对算法的要求可能并没有那么高（也看厂子和国家），所以请根据自己的实际情况调整；

2）面试绝不仅仅是算法，切记。

提前祝拿到好 offer。加油！：）