CS面试高频22条

准备CS面试是一个非常累心的过程：算法又多又难，数据结构复杂多变，面向对象设计和系统设计根本没有正确答案，周边的关于计算机体系的基础知识浩如烟海，一般人无从下手。包子培训帮大家梳理了以下22条面试高频考点，大家不妨自己心里算算，看自己是否能顺利过关:)

 

1. 使用并理解公司的（某一）产品，给出建议；
2. 分析算法的时间、空间复杂度（Big-O)；
3. 熟练使用一门常用高级编程语言如C/C++/Java，流畅的coding意味着手写代码时没有过多的语法错误；
4. 对语言的细节特性有足够的理解，理解语言之间的差异，比如解释执行vs编译执行，内存回收模型等；
5. 最好熟悉一门脚本编程语言如Python/Javascript；
6. 至少知道两种n*log(n)的排序算法，比如快速排序和归并排序。归并排序的使用很广泛，需要多了解，比如K-way merge sorts；
7. 掌握二分查找思想及应用场景，灵活处理类似问题，比如shifted sorted array查找、实现sqrt()等问题；
8. Hashtable: 透彻理解Hashtable的原理、性能、碰撞处理，并能用array (in your favorate language) 来实现一个简单的hashtable；
9. 理解树的基本操作比如添加、删除节点，树与其他数据结构的相互转化；
10. 二叉树的各种遍历算法（前序、中序、后序、层序），根据遍历结果重建二叉树；
11. K-ary trees/trie-trees的实现算法和应用场景；
12. 至少熟悉一种平衡树，比如(red/black tree, splay tree or AVL tree) ；
13. 理解Min/Max heap的实现和应用场景，熟练解决查找top(N)类型问题；
14. Graph在内存中的三种构造方式(objects and pointers, matrix, and adjacency list)；
15. Graph的遍历算法BFS/DFS，计算时空复杂度，以及具体实现；
16. 结合Graph常考的算法比如拓扑排序，最短路径以及最小生成树算法，当然能了解一下一下更高端A*算法会更加impressive；
17. 掌握基本的Dynamic programing的思想，熟练解决基本的DP问题，比如两字符串的最长子串，字符串之间的edit distance等；
18. 了解基本的NP-complete problems, 能够将一道模糊定义的问题划归为NP相关问题；
19. 理解操作系统中的进程、线程、以及它们之间的区别，理解系统并发操作中的常见问题，以及如何使用locks, mutexes, semaphores来解决并发问题;
20. 理解面向对象设计（封装、继承、多态），能把一个模糊定义的业务需求用OO的方式抽象（比如设计电梯、停车场等）；
21. 理解primitive type的内存表现，并且熟练使用位操作；
22. 理解分布式系统的基本概念，解决的问题以及分布式系统设计中(Consistency, Availability, Network Partition)一致性、可用性、高性能之间的trade-offs；

看完以上22条，如果有点心虚，快来参加包子培训的周末冲刺辅导班吧（02/28 - 03/01)，一个周末，让改变发生！http://baozitraining.org/weekendclass/

 

[Google最新面试题] Continental divider