程序员才看得明白的面试圣经

面试圣经...



小编提示：文章很长，可以收藏之后慢慢看哦！

当我最初开始参加编程面试的时候，我所有最心仪的公司都忽视了我。现在回头看那个时候，我发现自己当时去参加面试都完全没做任何准备。虽然已经有许多博客文章和书籍在讲编程面试，但现在的我作为面试官，坐在桌子的另一边，还是能看到许多来参加编程面试的人没做任何准备，或者准备得很糟糕。这也就是为什么我开始写这篇指南的原因，刚毕业时的我、第一次参加面试的我一定非常想有这么一份指南来指引自己。而从现在开始，我自己也会照着这份指南去做。

多年以来，我在好几家公司工作过，所以我的面试技巧得到了很好的磨炼，而且我参与面试的过程也教会了我该说什么、该做哪些准备，以及如何面试。在这篇指南里，你会了解到面试的概况、面试取得成功的六大步骤，以及我在考察数据结构和算法时所考虑的方面。这篇指南无法确保你找到工作，但它能帮助你尽最大可能给面试官留下一个好印象。

声明：本文中的观点完全出自个人视角。

本节概述了硅谷公司的面试过程，仅仅是个情况介绍，大家可以跳过去往后看。

除了直接申请面试以外，一般说来，还有两种途径来获得面试的机会：由现在的雇主推荐，或者通过LinkedIn。虽然前者会快一些、更尊敬一些，但后者很可能是大部分应聘者所走的路径。事实上，每天都有无数的招聘人员趴在LinkedIn上，他们唯一的工作就是寻找和接触有可能换工作的员工，所以一定要保证自己的信息是最新的，而且要多交人脉、多请别人来认可自己的技能，并且要把你所具备的技能、做过的个人项目或者对开源软件所做的贡献加到个人页面里去。



最初的接触一般是通过电子邮件进行的，然后招聘人员会给你打电话，大概了解一下你的技术背景。如果你的技能和他们正在寻找的技能一致，他们就会安排一次电话面试，在电话面试时，你可能就会被要求在一份共享的在线文档里编程。那么你就会知道，这份文档很可能没有任何代码补全和句法高亮的功能。电话面试会持续半小时到45分钟，如果你表现不错，就会被邀请去参加现场面试。现在如果没有电话面试、或者在电话面试之外，你可能还得去参加一个小的编程项目。

现场面试由几次面试组成，总体会持续45分钟到一个小时。这些面试会和电话面试非常像，只是问题会更难——不过能亲眼见到面试官多少算是有所补偿。现场面试数周之后，所有反馈应该都被看过、招聘决定就会做出，招谁不招谁也就定了。如果你没拿到offer，也要明白面试是一个随机的过程，包含运气的成分，不妨把它看作是一次学习的经历。可能你还会想起布莱恩·阿克顿（BrianActon）面试Facebook和Twitter不成、后来成为WhatsApp联合创始人的故事。

理论上讲，用哪种编程语言并不重要，但你面试需要用某种特定语言来完成的工作时除外，比如iPhone开发者或者前端开发者。我强烈建议你用正在面试的公司所使用的一种编程语言来编程（以及练习面试问题）。

编程面试的目的，是为了确定你的编程水平有多高。一般来说，你将被要求用编程来完成一个功能或者方法，但有时候，你会需要编辑一个类的定义，或者设计一系列相关的代码模块。在任何一种情况下，你都要有条不紊地解决问题，并遵循以下六个步骤：首先，要确保你理解了面试官的问题。许多问题都是故意措辞模糊或者模棱两可，这个时候你可以请面试官把问题说清楚，从而确保你真正回答面试官的问题。你的提问同时还有一个好处，就是它能给你自己一些时间，让你的脑子转起来。用一到两个例子来确定问题的限制条件和要求（在现场面试时在白板上完成这个过程，在电话面试时在笔记本上完成）。尝试用中等规模的例子，以便覆盖到一些特殊情况。如果你能想到可能相关的表格，就把它画出来。事实上，把你想到的任何东西都写下来是会有帮助的，因为它能为你提供一个视觉锚点，从而让你在走不通时或者思考过程中随时返回某一个点。把话说清楚，这可能是最重要的一步。要试着让面试尽可能有更多的互动，面试官不知道你在想什么，而让他们参与到你的思考过程里，会让她给你一些有用的提示，防止你偏向错误的方向。你的目标就是要先和面试官确证你的答案，然后再去写代码，而且你考虑答案越清晰、越高效，你得到的即时反馈也就越好。通过应用以下技巧来找到答案：回想一下你遇到的类似问题，再想想它们是如何被解决的，尝试各种不同的算法（分治算法、贪心算法、递归、排序，等等），把问题分解成更小的、可处理的小问题（这样你就能得到相应部分的分数），最后再通览一遍你列出的数据结构，因为有时候，只要想到了正确的数据结构，就能给出正确的答案。当你向面试官问清楚了问题、并向她解释了你的答案之后，就可以开始写代码了。要记住，在共享文档里写代码的时候，你可以复制粘贴、写评论，而且能回过头来完成骨架算法和功能。但在白板上写代码就不一样了，它需要你的头脑很清醒，而且需要你具备管理白板空间的技能。如果足够幸运的话，现在当你开始在白板左上角动笔的时候，应该非常明白你要写些什么东西，而且你要确保在你写答案的时候，没有挡住面试官的视线。花点儿时间把代码写得紧凑而美观一点儿，因为你的代码也会是面试反馈的一部分。在你写代码的时候，要大声解释你在写什么，这会让你的面试官更容易地跟上你的思路。最后，用不同的例子和特殊案例验证一下你的代码，并且要一行一行地过。这会展示你的思考过程，让你检查出小错误，并告诉面试官你的办法是可行的。如果你想得到额外加分的话，甚至可以把单元测试的代码写下来！最后再和面试官聊一下你的答案在空间和时间利用方面的复杂性，然后结束整场面试。

电话面试值得特别一提，因为这是大多数人失利的地方。之所以会这样，部分原因在于电话面试是招聘过程中第一道真正的关卡，但也有一部分原因在于，这种形式容易造成沟通的错误，而且缺乏可视化线索，所以电话面试是特别严酷的。

电话面试有两大障碍。

第一大障碍是，在电话面试的一开始，双方都能看到的唯一的东西就是一个空白的共享文档。这会让面试者倾向于过度补偿非语言沟通的缺失，从而着急忙慌地在屏幕上进行沟通。令人遗憾的是，这么做很少会有好结果。所以当务之急并不是去关注那个正在盯着你的空白文档，而是要首先理解和评估问题（也就是完成上述六个步骤中的前四个），同时通过尽可能地沉浸到面试中来弥补现实存在感的缺失（要记住，电话的另一头是一位可以很容易就被别的事情[比如查看邮件]分心的面试官）。电话面试的第二大障碍，就是要同时在电脑上打字和在电话上聊天的后勤保障问题。你不必一只手敲代码、一只手打电话，也不必把电话调到扬声器模式，我建议你用电脑上的Google Hangouts接面试电话（你得有一个GoogleVoice号码，而且得在面试前测试一下）。你还可以用耳麦或者耳机来进一步降低不好的接收效果、提高沟通质量。

如果你正在思考为什么软件工程的面试和日常编程不一样，最根本的原因在于：面试是为了测试你在计算机技术方面的基础，所以会非常偏重算法和数据结构，因此你可能需要练习一些面试问题，从而让自己具备解决面试问题的心态。

从短期来看，你所能做的最好的准备工作就是买一块白板，并匹配好回答模式。

当然了，长远来看，我们都会死掉，所以我会把事情搞简单，说一些你绝对应该复习一下的关键概念。

大部分数组和字符串是可互换的，事实上，你遇到的大部分字符串处理的问题，都可以在理解数组的基础上得到解决。记住这一点之后，你应该懂得如何遍历数组，知道如何访问、转换和调换其中的每一个元素，而且要懂得如何对它们进行各种不同的集合运算。和其他算法相比，二分法检索（Binary search）可能会更多地成为面试问题的核心内容（如果你曾经碰到过有分类数组的问题，那么二分法检索有可能应该是你答案的一部分），你绝对必须知道如何使用它。

和数组密切相关的，是排序算法。你不大可能会被要求重复使用一个排序算法，但很可能你至少知道排序是如何在O(nlogn)的时间里完成的就行。不过你应该大概知道归并排序（merge sort）或者快速排序（quicksort）和基数排序（radix sort）的执行细节。

动态数组可以按需重新调整自己的大小，同时依然提供分时平摊的持续时间访问。一种典型的做法是，当在一个全排列数组中增加一个元素的时候，会形成一个新的、更大的数组，而旧数组中的元素也会被复制到新数组里。你应该在面试时做到完成一个动态数组。

如果你拿到一个非数组类问题，但你在答题中需要用到像数组结构这样的数组，不妨少给自己惹麻烦，直接用动态数组吧。

哈希表（Hash tables）是编程时的瑞士军刀，很多不同类型的问题（检查存在、计算频率、排序，等等）都能用哈希表来完美解决。它几乎肯定会出现在你的面试中，而你应该理解它的原理（哈希功能的角色、冲突如何解决、什么时候要调整大小、为什么）以及如何运用它们。

链表问题在C和C++的面试中最常见，因为它们是弄清楚应聘者是否理解指针的一种简单的办法。不过这个点太初级、太基础了，所以不管用哪种语言，你都应该知道该如何从零做起应用它们。而且由于大部分链表问题不过是与人所周知的遍历还有删除和插入相关的问题的变体，所以链表问题准备起来很容易，你没有理由拿不到这部分分数。

许多链表问题中都会用到一个小技巧，那就是慢速/快速指针技术。它的简单版含义如下：使用两个指针迭代生成一个列表，其中一个指针在另一个指针的前面。快速模式下的指针可能会是一个位于前面的固定数值（它有助于确定列表有无循环，或者找到列表中的第k个元素），或者也可能会跳过慢速指针经过的多个结点（打个比方，如果快速指针的速度是慢速指针的两倍，那么当它到达列表末尾时，慢速指针将会位于列表的中间）。

请注意，当面试官谈到链表时，他们常常指的是单链表，但你无论如何都应该问清楚。

栈和队列一般会是你用来解题的数据结构的一部分。你应该知道如何用链表和数组两种方式来实现它们。树/二叉树/二叉搜索树（BST）/字典树/堆

你可能不会每天都见到树和图，但你很可能会在面试时遇到它们，所以你要彻底地看一下这些数据结构。

树最一般的定义，是和其他结点没有或者有一个以上关系的结点的集合，但在实践中，当面试官说“树”的时候，他们指的是一种叫二叉树的东西。二叉树是一种树的类型，它的每个结点都至多有两个子树，一般被称为左子树和右子树。

你不应该把二叉树和二叉搜索树混淆起来，后者是一种特殊的二叉树，它的左子树结点上的值都比父结点小，而右子树结点上的值都比父结点大或者相等。二叉搜索树的优点是，如果树的结构相对平衡（向面试官问清楚这个问题），那么查找、插入和删除就可以在O(log n)的时间里完成。二叉搜索树的其他重要属性，就是你跟着所有的左子树走，就能得到这个树上最小的元素，而跟着所有的右子树走，就能得到这个树上最大的元素。请注意，是有办法让树一直保持平衡的，最常用的办法就是红黑树和AVL树。我不会去弄清楚它具体实现的细节，只要知道有这些数据结构就行。

不过你绝对必须知道遍历树（tree traversal）算法：广度优先搜索（breadth-first-search）、深度优先搜索（depth-first-search），以及中序遍历、后序遍历和前序遍历之间的差别。

最后是堆（heaps），它也被称为优先队列，是你应该了解的最后一种数据结构。它们通常都是满足堆属性的二叉树：每个结点的子树的值都比结点本身的值小，或者与它相等。所以根结点的值总是最大的，也就是说你总能找到最大值，但代价就是寻找其他任何一个值所需的时间都是O(n)。插入和删除所需的时间依然是O(logn)。

和树一样，图也是由带子集的结点组成的，但和树不一样的地方在于，这些结点可以有多个父结点，所以可能会形成自环（loop）或者圈（cycle）。除了链接——也被称作边（edges）——之外，两个结点之间可能地有比指针更多的信息，而且可能会有值和权重。边有方向的图被称为有向图，而只有双向指针的图被称为无向图。边上有权重的图被称为加权图。

有三种方法来表示图，但你只要搞清楚邻接矩阵（adjacency matrices）和邻接表（adjacency lists）就行了。你应该了解它们计算的复杂程度、它们需要折衷的地方，以及如何在现实的代码中实现它们。用哪种方法取决于你有的图的类型，比如连接完整的简单图可能用邻接矩阵来实现更好，而稀疏一些的图则可能用邻接表来表示更好。



请注意，如果你是在实现加权图，很可能需要定义一个Edge类。

图论是一个非常宽泛的话题，所以很难知道一个人应该为一场面试去熟悉多少种图论算法，所以我只是列出了我认为可以覆盖90%图论问题的内容：你绝对必须知道该如何遍历一个图（深度优先或者广度优先），以及如何做拓扑排序（topological sorting），你应该知道如何实现迪杰斯特拉（Dijkstra）的最短路径算法（这里有一个制作精巧的视频解释了这一算法），同时也要知道如何实现普里姆（Prim’s）算法。最后，如果你还知道如何实现A*搜索算法（A*searchalgorithm），那就更好了。

要想处理位元，你必须先得知道在二进制补码（two’s complement）标记内部，数字是如何表示的——二进制补码和无格式二进制标记是一样的，只是负数要“进行位元翻转之后再加1”。比如要想得到数字-1，你要从用8位二进制整数表示是00000001的1开始。对每一个位元进行翻转之后的结果是11111110，再加上1就是11111111，也就成了二进制补码中的-1。

左移位运算符“”会把一个位模式向右移，但当向右移动负数时，它的作用在不同

编程语言中也不一样，在Java中，右移位会用符号扩充的办法，用1来填充负数中的空位。

逻辑右移位运算符“>>>”是Java和Javascript中独有的，无论数值是多少，它都用0来填充空位。

设置某一位：可以用按位或运算符（|）。

num |= 1