讲师: liuyubobobo
第一章 算法面试到底是什么鬼
1-1
在面对一个算法题时, 面试官有时候看重的并不是你能否在有限的时间内解出来, 更看重的是你 是否有一个合理的思考路径, 要把算法面试的过程看做是和面试官一起探讨一个问题的解决方案, 对于问题的细节和应用环境, 可以和面试官沟通(不要提问太多, 可以自己提出假设, 自己解答), 在沟通的过程中, 一步一步深入到问题的细节, 并完善自己的假设. 这种沟通是非常重要的, 它暗示了你的思考问题的方式.
举例来说: 如果我们被要求对一组数据进行排序:
直接用快排?(这不是一个好的答案)
提问: 这组数据有着什么样的特征?
例如: 有没有可能包含有大量的重复元素?(如果是的, 那么三路快排是更好的选择, 在很多语言的标准库中, 实现排序的基本算法就是三路快排)
又例如: 是否大部分数据距离它的正确位置很近? 是否近乎有序? 如快递订单排序. (如果是的话, 则插入排序更好)
又例如: 是否数据的取值范围有限? 比如对学生成绩排序. (如果是, 那么计数排序更好)
又例如: 是否需要稳定排序? (若是, 则归并更好)
又例如: 数据的存储状况(数据结构)是怎么样的? 如果使用的是链表, 则不能进行随机存取, 就无法使用快排, 而应该使用归并排序.
又例如, 如果数据量很大, 内存放不下, 那么久必须使用外部排序算法
其他主要注意的地方: 对问题的独到见解, 优化, 代码规范, 容错率.
对于算法面试, 人难亦难, 因此不要轻言放弃, 关键在于你所表达出的解决问题的思路. 甚至可以通过表达解题思路的方向, 得出结论: 这个问题的解决方案, 应该在哪个领域, 我可以通过查阅或者进一步学习解决问题.
1-2
注意算法面试只是技术面试的一部分, 其中一个优秀不代表另一个也优秀
重点考察项目经历和项目中遇到的问题, 从这些可以看出你对于技术的态度是怎么样的
如: 你遇到过的印象最深刻的bug是什么? 你有说如何处理这个bug的? 这个问题没有参考答案, 因人而异, 却很容易看出一个人的真实水平是怎样的, 也可以看出你在技术领域的深度, 因此, 建议对这类问题有所准备.
近年来喜欢考察的点: 系统设计(scalability), 即系统在面对大规模设计时遇到的一些常见问题, 关于这些问题也有一些常见的思路和解决思路, 建议提前准备.(这些问题不属于算法面试的内容, 因此本课程不会过多介绍, 建议自己查阅相关资料进行整理)
不能只准备算法的面试, 也要根据自己所申请职位的不同, 对专业领域的知识熟练掌握, 这很重要
项目很重要, 最好能好好准备, 并且对于简历上出现的项目一定要非常熟悉
不是 “项目” 的项目: 一本优秀书籍的代码整理, 个人技术博客等.
通过过去了解你的行为方式:
- 遇到的最大挑战?
- 犯过哪些致命的错误?
- 遭遇的失败?
- 最享受的工作内容?
- 遇到冲突的处理方式?
- 做的最与众不同的事?
对于以上问题, 最后提前准备, 并且最好与自己的实际项目或者应聘的岗位相挂钩, 回答不要太过笼统, 最好能举出具体的事例(可信度更高), 能反映出你的一些个人素质和性格(对公司有利的).
准备好合适的问题问面试官. 这些问题可以反映出你关心的是什么. 如
- 整个小组的大概运行模式是怎么样的?
- 整个项目的后序规划是怎么样的?
- 贵公司中某个产品的某个问题是如何解决的?
- 贵公司为什么会选择某些技术或标准? 具体的考量是怎么样的?
- 我对某个技术很感兴趣, 在贵公司的小组中我会有怎么样的机会深入这种技术?
1-3
准备算法面试不需要啃完一本《算法导论》
对于学习, 我们不能要求一步到位, 很多书, 很多知识, 我们都是要阅读, 理解很多遍, 慢慢的熟练, 直到内化到自己的血液中. 学习切记完美主义
高级数据结构和算法被提及的概率较低(但是对于某些特殊岗位, 这些算法也有可能是必考题). 如: 红黑树, 计算几何, B-Tree, 数论, 斐波那契堆, FFT(傅里叶变换)
远远不需要达到ACM竞赛的水平
算法面试的准备范围: 不要轻视基础算法和数据结构, 而只关注 “有意思” 的题目. 基础算法大致有:
- 各种排序算法
- 基础数据结构和算法的实现: 如堆, 二叉树, 图, …
- 基础数据结构的使用: 如链表, 栈, 队列, 哈希表, 图, Trie, 并查, …
- 基础算法: 深度优先, 广度优先, 二分查找, 递归
- 基本算法思想: 递归, 分治, 回溯搜索, 贪心, 动态规划
在进行实际时, 一味的刷题, 过度的在意正确与否, 而不去考虑题目背后的算法思想, 往往效率很低.(好像自己做了很多题, 但实际上收货并不大 )
1-4 解法算法面试问题的整体思路
注意题目中的条件:
有一些题目的条件本身就是暗示, 如:
- 有序数组
- 设计指定复杂度的算法, 如 $O(nlogn)$, 那么就要考虑分治或者排序
- 无需考虑额外空间, 那么就要考虑申请额外的空间
- 数据规模大概是10000, 对于此, 那么 $O(n^2)$ 是可以接受的
当没有思路的时候:
- 自己给自己几个简单的测试用例, 试验一下
- 不要忽视暴力解法, 暴力解法通常是思考的起点
- 优化算法: 常见的算法思路, 常见的数据结构
- 空间和时间的交换(哈希)
- 对数据进行预处理(排序)
- 在复杂度的瓶颈处寻找答案
在实际编写时, 要注意对极端条件的判断:
- 数组为空? 字符串为空? 数量为0? 指针为
nullptr? - 变量名, 模块化, 复用性, 这些可以给面试官留下好印象
对于基本问题, 如实现堆, 二叉树等, 要做到可以白板变成.
第二章 面试中的复杂度分析
2-1 大 O 记法
大 O 记法: $n$ 表示数据规模, $O(f(n))$ 表示运行算法所需要执行的指令数, 和 $f(n)$ 成正比.
$O(n^2)$ 不一定比 $O(n)$ 快, 如: $10000\times n$ 和 $10\times n^2$
在学术界, 严格的讲, $O(f(n))$ 表示算法执行的上界. 但是在业界, 我们就用其表示算法执行的下界. (如归并排序, 在数据量不同时, 有时是 $O(nlogn)$, 有时是 $O(n^2)$, 但是, 在面试时, 我们就说是 $O(nlogn)$ 就可以)
虽然算法复杂度是用例相关的, 但是在面试中, 我们更在意的是平均的时间复杂度. 不会扣得特别细.(心里有数即可)
2-2 数据规模的概念
对 $10^5$ 的数据进行选择排序, 结果计算机假死? (这很正常, $O(n^2)$ 算法需要 $10^10$ 次操作, 这大概需要几十秒, 而这会使得程序内存超限.)
如果要想在 1s 之内解决问题:
- $O(n^2)$ 的算法可以处理大约 $10^4$ 级别的数据.
- $O(n)$ 的算法可以处理大约 $10^8$ 级别的数据.(例如, 如果面试官说数据规模为一千万, 那么不用想, 我们的算法复杂度必须为 $O(n)$)
- $O(nlogn)$ 的算法可以处理大约 $10^7$ 级别的数据.(以上是对简单的操作而言, 如果单次的操作较复杂, 那么可以对上面的级别再低估一点, 如缩小10倍一般就没问题了)
空间复杂度: 需要注意的是递归空间的占用, 递归了多少次, 其占用的空间复杂度就大致为多少.
2-3 常见的复杂度分析
注意循环语句的坏境.
注意下面双重循环的复杂度, 并不是 $O(n^2)$. 因为外层循环不是 $O(n)$, 而是 $O(logn)$.1
2
3
4
5void hello(int n){
for(int sz = 1; sz < n; sz += sz)
for(int i = 1; i < n; i++)
cout<<"hello"<<endl;
}
2-4 复杂度试验
自以为写出了一个 $O(nlogn)$ 的算法, 但实际上是 $O(n^2)$ 的算法. (复杂度前面的常数有可能差距很大)
实验, 观察趋势. 每次将数据规模提高两倍, 看时间的变化.