算法面试

过程和思路很重要。

对一组数据进行排序

这组数据有什么特征?

如果

如果有很多重复的数据

三路快排是比较好的选择。

如果没有很多重复的数据,那么普通的快速排序就可以。

大部分数据距离它正确的位置很近

比如银行的业务流水订单排序,大部分是有序的,这个时候使用插入排序比较好。

数据的取值范围很有限

比如对学生成绩进行排序,用计数排序比较好。

问面试官

是否需要稳定的排序?

数据的存储状况?是否是随机存储的

数据量大不大?是内排序还是外排序比较好?

常见复杂度大概能解决什么量级的问题

第2章

时间复杂度分析

二分查找

二分查找的时间复杂度为 $log N​$,因为每次搜索,问题规模就变为原来的一半。一共需要 $log_2 N​$ 次,问题规模就会变成1,就实现了查找。所以时间复杂度是 $log N​$。

不是两层循环就一定是 $O(n^2)$,要看清楚循环的结束条件和增加条件。两层循环也可能是 $O(NlogN)$ 级别的。

不是有递归的算法就是 $O(NlogN)$

递归深度乘以每次递归的时间复杂度。

均摊复杂度分析

添加元素的时候resize

比如 Vector 等数据类型要涉及到 resize 操作,resize操作的时间复杂度是比较大的,但是因为resize是操作很多数据才会产生一次resize,所以resize的时间复杂度是平均分到每次插入操作当中的。

删除元素的时候resize

在临界点连续添加和删除元素,会产生复杂度的震荡。

解决方法:等到删除元素直到剩下的元素为 capacity 的四分之一的时候再进行 resize。

数组问题

数组的问题最常见

排序:选择排序;插入排序;归并排序;快速排序

查找:二分查找法

数据结构:栈;队列、堆

二分查找

起初就定义好寻找范围是开区间还是闭区间。