笔试面试算法总结

笔试面试算法总结

笔试算法问题总结 算法

1. 算法的几个特征是什么。

2. 算法复杂性的定义。大O、θ、?、小o分别表示的含义。

3. 递归算法的定义、递归算法的两要素。

4. 分治算法的思想，经典的分治算法(全排列、二分搜索、归并排序、快速排序、线性时间选择、最接近点对问题)。

5. 动态规划算法解题框架，动态规划算法的两个要素是什么？ ___方法是什么？

6. 经典的动态规划问题(矩阵连乘问题、最长公共子序列问题、0-1背包问题)。

7. 贪心算法的思想，贪心算法的两个要素。

8. 经典的贪心问题(活动安排问题、背包问题、装载问题、哈夫曼编码、单源最短路径、最小生成树问题)。

9. 回溯法的思想，回溯法中有哪两种典型的模型。

10. 经典的回溯算法(n后问题、0-1背包问题、旅行售货商问题)。

11. 分支限界法思想，有哪两种分支限界法。

12. 经典的分支限界算法(0-1背包问题、旅行售货商问题)。

数据结构

1. 数据结构的定义。

2. 栈的两个应用：括号匹配和表达式的计算。是怎么应用的？表达式计算用的是哪种表达方式？有什么好处?

3. 字符串匹配算法：朴素的匹配算法、KMP 算法 。

4. 二叉树前序、中序、后序递归遍历算法。二叉树前序非递归遍历算法。

5. 堆 ，建堆算法，堆的插入和删除算法，堆排序 。

6. 哈希 。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？

7. 二叉搜索树的搜索、插入、删除。时间复杂度。

8. 二叉平衡树的插入结点的原理 ，有哪几种旋转方式？分别适用于哪种情况。分析二叉平衡树的时间复杂度。

9. 红黑树的定义，红黑树的性能分析和与二叉平衡树的比较 。

10. 图有哪些储存表示。

11. 链表插入排序、链表归并排序。

12. 常见的有哪几种排序算法，试比较其时间复杂度，以及是否稳定，及各自使用的情形。

13. 常用分配排序有哪几种？ 基数排序的定义，分类及原理。

14. 外部排序的过程。

15. B树、B+树、Trie的概念及用途，添加删除结点的原理。

面试算法总结xx-04-16 18:21 | #2楼

【一】 时间受限

大部分的面试题，都是对时间复杂度有所要求的，如果有涉及，“最快”一类的字样，毫无疑问，先上时空原理，用空间来换时间。Hash，大数组，一些辅助性的空间，都是首选。在我的面试经历中，有无数次用到过Hash和大数组的。不过，通常这不会是面试官想听的唯一解法，他们紧接着十有八-九是会说“如果只有xx-xx空间呢？”。说此类方法只是为自己争取更多的时间，并且体现思考的完整性，简而言之，装B用。。。

eg1.1：求一个char（8bit）中，二进制1的个数，越快越好。 -- 《编程之美》

编程之美上提供了五种方法，（1）使用除法操作 （2）使用位操作 （3）在位操作的基础上改进，算法的复杂度只于1的个数有关 （4）使用分支操作 （5）查表法。

第2种方法用的是位运算，比第一种方法高效很多。第3种方法非常有技巧。第4，5两种方法其实是用空间换时间，但是如果是一个int（32bit），那么这两种方法就不适用了。方法3的代码

int Count(BYTE v) {

int num = 0;

while( v ) {

v &= ( v - 1 ); num++; } }

eg1.2：有一个整数数组A[N]，让你不用除法，求另一个数组B[N]，其中B[i] = A[0]*A[1] ... * A[N-1] / A[i]，期望复杂度是O(N)。 -- TopLanguage