2010年，工作面试总结（二），知识篇

本文着重于介绍我工作面试中涉及到的一些知识，以及我本人认为可以供大家参考的一些资料。

书籍：

《算法导论》

这本是大部头，很多人都看不完。我本人也并没有看完，它跟了我这么多年，完全是属于常看常新的牛书。每一次看，都发现会有新的收获。比如，以前并不知道求K位数或者中位数有平均为O(n)复杂度的算法。看到了别的地方的参考资料，才知道，原来《算导》上专门有一小节讲这个内容。我基本上是本科比较集中的看了一遍，研一的时候又集中的看了一遍，才算是粗略的看完。但是其实，很多理论性的，以及图论一部分依然还是没有看完。个人推荐，先从简单的开始，挑选比较熟悉的一些偏重与数据结构方面的知识作为起点。这本书的习题非常重要，要是有时间，能够全部做完，那绝对是能够神功在手了。其实，集中把，第二部分（排序），第三部分（数据结构），第四部分（高级设计，我基本主要看动态规划和贪心），第五部分（高级数据结构，B树和二项堆，并差集），第六部分（图算法，最大流部分较难，自己可以看情况掌握）。这些部分可以先从算法本身开始，伪代码全部看懂。因为算法导论讲的很详细，而且有来龙去脉，基本不会有太大难度。数学证明，推荐大家掌握，但是，突击或者第一次，可以选择性的看看。我自己是重复看，才把证明看掉的。第一次看的时候，基本都跳过了。不过，证明和习题是精髓！希望如果有时间，一定要补回来。

《编程之美》《挑战编程》

这本书绝对是将全中国企业，或者说是一部分懒惰的企业面试题库提升了一个档次的一本神书。百度面我师兄的时候，我师兄直接把有一道题的最优解答出来了。但是，那个面试官显然是不知道最优解，一直在引导我师兄答出，这本书里面的第四个解。呵呵。书很不错。全部看一遍并不难。说个不好听的，可以背下来，而且相信我，基本上绝对有用！比如说，n!后面有多少个0。我相信，你们今年面试或者笔试，一定会碰到这道题。《挑战编程》大家可以自行考虑一下吧，这个完全是针对acm竞赛的，不过，看看题也不错。

《编程珠玑》

业界神书嘛。习题全部做完就是了。其实都是些小东西，但是，基本上一步步考察你的解决问题的能力。个人觉得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我当时都是在这本书里面看到的。

《算法技术手册》

这本书貌似出镜不多。书很薄，代码写的非常好，其实基本上全部都是基础算法和数据结构的实现。但是，它牛逼就在于，代码写的太好了，基本上，看一遍，绝对能背下来。面试基础很重要。基本上每个笔试或者面试，都会考一个100行以内的小程序。比如，给定一棵树，以及其中一个节点x，要求出这棵树的中序遍历序列中，x的后续节点，非递归实现。这种题非常简单，但是，真正写对的，其实并不多。

《STL源码剖析》《C标准库》

都不厚。挑着看一遍非常舒服。特别是，看看STL每个数据结构迭代器类型啊，红黑书如何实现啊。C标准库，最常见的，比如strcpy()和memcpy()有什么区别啊。特别是，STL，看过之后，对泛型还是能有一定了解的。

《C专家编程》《Effective c++》《深度探索C++对象模型》

第一本比较简单，可以当八卦书看。后两本其实也没啥好说的，其实都是些业界公认的牛书。我再重复一遍也没什么意义。但是，的确，考察基本上也就都是这么几本书上面的东西。基本上后两本主要侧重看c++对象方面的一些指示，特别是多态相关的。

《具体数学》《组合数学》

这两本其实可以看作修身养性的书。我当时是时间比较充裕的时候看完的。纯突击，大家就可以跳过了。但是，看完真的很有用。比如说，你们就可以跟面试官扯约瑟夫环的构造解了（这道题我觉得80%会遇到），直接推推公式，就不用写模拟代码了。《组合数学》也是，很多笔试一般会有些小智力题。不过，其实一般的题目，不看这本书也可以搞定。所以，这两本仅供参考。大家有兴趣的时候，可以翻翻。

《Linux内核源码剖析》《Linux环境高级编程》……

要是有机会，能看看最好。因为很多公司都会考察Linux相关的知识。最少要会点脚本，一些简单的Linux命令，以及正则表达式什么的。要是能聊聊内核源码或者驱动开发什么的东西，面试官肯定更加喜欢了。

知识：

c & c++

首先要知道c和c++的区别。常考的有const的用法，一些生僻关键字比如extern，static的用法。

结构体与类的差别。类里面的字对齐问题，也就是说一个类到底有多大。以及一个空的类有多大。

虚函数以及多态相关的显然是重点。比如析构函数什么时候需要写成虚函数，构造函数是否可以是虚函数。

int a[10]; a 和 &a的区别。

java

java我并不熟。但是基本上肯定会考一些虚拟机相关的，以及GC等知识。然后，一般招聘的java程序员都会问到很多多线程编程的东西，以及hadoop！这个绝对是重点，淘宝绝对就是问这个的。

操作系统

这个看工作岗位的实际要求。基本的进程线程区别==肯定是会问到的。要是要求高一些，就会问很多多线程编程的问题。一些竞争死锁等基础知识，一些进程调度的算法，最近的kernel好像用的是CFS调度算法。shell编程，如何读取程序堆栈，写一些core dump的读取程序等等的。

数据结构

基本上所有的排序都要会写。与树有关的操作都要会些非递归版本。图一般考的不多。Flood-Fill算法等等。查找中位数。B树和红黑书最好要掌握，不用会写，能扯扯基本就行。KMP，这个很有可能考！而且的确真的不好懂。要是实在不行，背下来吧。哈哈。

网络

这个其实比较基础了。我个人网络方面的知识并不好。但是各种协议的基础，几次握手啊，一些操作系统的api实现到底是单工还是双工用的是TCP还是UDP。我个人网络纯粹靠拼RP。

数据库

数据库非常重要。基本的SQL肯定是要会的。最常见有一道题，inner join和out join的区别。MySQL是重点，基本上很多企业都是问这个。然后，百度扯多了会跟你扯MySQL引擎 的一些东西。这些我就不太懂了。要是能准备的话，或者说的确是做这方面的，就可以着重多准备下。

大规模数据处理

这一块绝对是重点！而且本身不是一个系统的学科分支。但是，基本上几家大公司都会问这方面的。推荐先读读google那几篇论文。Page Rank那一篇，然后Map Reduce好像有几篇吧。Big Table什么的。推荐一个网址。这篇貌似是转载的，我以前找到的源地址现在找不到了。处理这一类问题基本上思路都是，哈希，map reduce以及bit map等等的。对了，推荐看一下外排序以及相关的败者树。这些都是大规模数据处理的一些典型问题。掌握了这些其实也就够了。这块有点屠龙之技的感觉，特别是对于学生，基本没有谁能有机会把这些代码实现出来。但是，没办法，这些公司就是喜欢考。看完那篇博客的，然后再自行查找一些资料，基本就够了。万变不离其中，而且，这些东西，没办法考那么难的。

推荐一个博客吧，作者收集了100+道面试题，并且全部给出了代码。把这个全部看完，基本上很多面试笔试，都是这些原题。

推荐Top Language里面的今天我们思考系列，好几年前的了。看大牛的思考过程，非常有帮助。希望自己能多想想再看答案。注意，google group好像有时被墙。

我把发芽网的题库版块也扫了一遍。

还有好多一时想不起来了。先post出来，有待以后再修改。