算法面试导论

认识

1. 面试中的算法问题，通常并不复杂，远远不需要啃完一本《算法导论》。
2. 算法面试更想考察的是你解决问题的思路。

算法面试到底是什么？

不是仅仅给出一个正确答案，而是展示给面试官你思考问题的方式。

“正确”本身是一个相对概念。

把面试的过程看作是和面试官一起探讨一个问题的解决方案，对于问题的细节和应用场景，可以和面试官沟通。 这种沟通本身很重要，它暗示着你思考问题的方式。

举个例子：面试官要求对一组数据排序时，你可以提问：

1. 是否有大量重复数据？如果有，可以用三路快排。
2. 是否大部分数据近乎有序？如果是，可以用插入排序。
3. 是否数据的取值范围非常有限？如果是，可以用计数排序。
4. 是否需要稳定性？如果是，可以用归并排序。
5. 数据存储结构？如果是链表，可以用归并排序。
6. 是否机器内存很小？如果是，可以用外部排序。

除此之外还有代码规范等等。

算法面试只是面试的一部分

根据应聘职位的不同，面试官可能会更关注你的编程能力、项目经验、沟通能力等。

针对项目经历的提问可以检验：

1. 你是否真的参与了项目。
2. 解决实际问题的能力，而这个问题可能恰巧是应聘公司正在遇到的问题。
3. 你是仅完成了功能开发，还是对相关领域有更深层次的理解。

你遇到的印象最深的 BUG 是什么？ 遇到的最大的挑战？ 犯过的错误？ 遭遇的失败？ 最享受的工作内容？ 遇到冲突的处理方式？ 做的最与众不同的事儿？

问面试官： 整个小组的工作流程是怎样的？ 整个项目的后续规划是怎样的？ 产品方向上是怎样的？ 项目在实现产品中遇到了哪些困难？是如何解决的？ 为什么会选择某些技术？ 在项目中，我的角色大概是？

面向对象、设计模式、网络相关、安全相关、内存相关、并发相关、系统设计。

展示过去：参与的项目至关重要。

基础

1. 各种排序算法。
2. 基础数据结构的实现：堆、二叉树、图…
3. 基础数据结构的使用：如链表、栈、队列、哈希表…
4. 基础算法：深度优先、广度优先、二分查找、递归…
5. 基本算法思想：递归、分治、贪心、动态规划、回溯搜索…

高级数据结构被提及的概率很低

红黑树、B-Tree、斐波那契堆、计算几何、数论、FFT等。

上考场

没有思路怎么办？

自己给自己几个测试用例，试验一下。

不要忽视暴力解法，暴力解法通常是思考的起点。

优化算法

1. 寻找对应的算法思路（看看哪些思路跟这个问题有关，可能用得上）。
2. 寻找对应的数据结构（看看哪些数据结构的特性可能简化这个问题）。
3. 空间和时间的交换（哈希表）。
4. 预处理信息（排序）。

写代码环节

1. 极端条件的判断：空数组、空指针、空字符串、数量为0？
2. 代码风格：变量名、注释。
3. 模块化、复用性。