刘宇波老师leetcode刷题系列
刘宇波老师leetcode刷题系列
1. 算法面试到底是什么鬼?
一提起算法面试，很多同学就会心有余悸。可其实，大多数企业的算法面试，并没有那么可怕。并不是一定要啃完整本《算法导论》，才能玩儿转算法面试；也并不是只有ACM参赛选手，才能笑傲算法面试。恰恰相反，大多数算法面试关注的算法思维，其实很基础。在这一章，和大家聊一聊，算法面试，到底是什么鬼？…
1-1 算法面试不仅仅是正确的回答问题
课程的目标是什么?让大家在面试中的算法问题,有一个合理的思考路径
1-2 算法面试只是面试的一部分
我们需要对一组数据进行排序
快速排序算法O(nlogn)?
我们可以跟面试官讨论
- 这组数据有什么样的特征?
- 有没有可能包含有大量重复的元素?
- 如果有这种可能的话,三路快排是更好的选择
- 是否大部分数据距离它正确的位置更近,是否近乎有效
- 是否数据的取值范围非常有限,比如对学生成绩排序,如果是这样的话,计数排序是更好的选择
对排序有没有额外的要求?
- 是否需要稳定排序
- 如果是的话,归并排序是更好的选择
数据的存储状况是怎样的?
- 是否使用链表存储的?
- 数据的大小是否可以装载内存中?
- 数据量很大,或者内存很小不足以装载在内存里,需要使用外部排序算法
1-3 如何准备算法面试
项目经历和项目中遇到的实际问题
你遇到的印象最深的bug是什么?
面向对象
设计模式
网络相关;安全相关,内存相关,并发相关,系统设计,scalability
关于过去:参与项目至关重要
如何找到项目?
- 实现
- 参与实战课程学习
- 慕课网
- 创建自己的项目
- 自己做小应用:计划表;备忘录;播放器…
- 自己解决小问题:爬虫;数据分析;词频统计…
- "不是项目"的项目:一本优秀的技术书籍的代码整理
- 分享:自己的技术博客;github等等
通过过去了解你的思考行为方式
- 遇到过的最大挑战?
- 犯过的错误?
- 遭遇的失败?
- 最享受的工作内容?
- 遇到冲突的处理方式?
- 做的最与众不同的事?
准备好合适的问题问面试官
- 整个小组的大概运行模式是怎样的
- 整个项目的后续规划是如何的?
- 这个产品中的某个问题是如何解决的?
- 如何会选择某种技术?标准?
- 我对某个技术很感兴趣,在你的小组中我会有怎样的机会深入这种技术?
1-4 如何回答算法面试问题
算法面试的准备范围
- 不要轻视基础算法和数据结构,而只关注"有意思"的题目
- 各种排序算法
- 基础数据结构和算法的实现:如堆,二叉树,图
- 基础数据结构的使用:如链表.栈,队列,哈希表,图,Trie,并查集…
- 基础算法:深度优先;广度优先;二分查找,递归…
- 基础算法思想:递归,分治,回溯搜索,贪心,动态规划
解决算法面试问题的整体思路
-
注意题目中的条件
-
题目中的一些暗示
有一些题目中的条件就是暗示
- 设计一个O(nlogn)的算法
- 无需考虑额外的空间
- 数据规模大概是10000
-
假如一下子没有思路的话
- 自己先测试几个简单的测试用例,试验一下
- 不要忽视暴力算法
-
我们可以看到一个例题,就是leetcode第三题
给定一个字符串，请你找出其中不含有重复字符的 **最长子串** 的长度。
这个题目到我们没有思路的时候,我们可以使用暴力法进行计算,在一个字符串中寻找没有重复字母的最长子串
-
对于字符串s的子串s[i…j]
-
使用O(n^2)的算法遍历i,j,可以的到的最大子串S[i,j];
- 我们再使用O(length((s[i…j]))的算法判断s[i…j]中是否含有重复字母
-
这种算法的时间复杂度为O(n^3),对于n=100的数据
第2章 面试中的复杂度分析
很多同学一提起复杂度分析就头疼，马上想起了《算法导论》中复杂的数学推导。但其实在一般的企业面试中，对复杂度的分析要求并没有那么高，但也是绕不过去的坎儿。在这一章，和大家介绍一下，面试中需要掌握的复杂度分析。…
2-1 究竟什么是大O（Big O）
n表示数据规模,f(n)表示n的一个函数
O(f(n))表示运行算法所需要执行的指令数,和f(n)成正比
| 时间复杂度 | Big O |
|---|---|
| 二分查找法 O(logn) | 所需执行指令数:a*logn |
| 寻找数组中的最大/最小值O(n) | 所需执行指令数:b*n |
| 归并排序算法O(nlogn) | 所需执行指令数:c*nlogn |
| 选择排序法O(n^2) | 所需执行指令数:d*n^2 |
2-2 对数据规模有一个概念
2-3 简单的复杂度分析
2-4 亲自试验自己算法的时间复杂度
2-5 递归算法的复杂度分析
2-6 均摊时间复杂度分析（Amortized Time Analysis）
2-7 避免复杂度的震荡