第7章 两个面试案例 在第一章中，我们讨论了面试的流程。通常一轮面试是从面试官对照着简历了解应聘者的项目经历及掌握的技能开始的。在介绍自己的项目经历时，应聘者可以参照STAR模型，着重介绍自己完成的工作（包括基于什么平台、用了哪些技术、实现了哪些算法等），以及最终对项目组的贡献。 接着进入重头戏技术面试环节。在这一环节中面试官会从编程语言、数据结构和算法等方面考查应聘者的基础知识是否扎实全面（详见第2章），并且很有可能会要求应聘者编程实现一两个函数。如果碰到的面试题很简单，应聘者也不能掉以轻心，一定要从基本功能、边界条件和错误处理等方面确保代码的完整性和鲁棒性（详见第3章）。如果碰到的题目很难，应聘者可以尝试画图让抽象的问题变得形象化，也可以尝试举几个具体的例子去分析隐含的规律，还可以尝试把大的问题分解成两个或者多个小问题再递归地解决小问题。这3种方法能够帮助应聘者形成清晰的思路，从而解决复杂的难题（详见第4章）。很多面试题都不止一种解决方案，应聘者可以从时间复杂度和空间复杂度两个方面选择最优的解法（详见第5章）。在面试过程中，面试官除了关注应聘者的编程能力外，他还会关注应聘者的沟通能力和学习能力，并有可能考查应聘者的知识迁移能力、抽象建模能力和发散思维能力（详见第6章）。 在面试结束前的几分钟，面试官会给应聘者机会问几个最感兴趣的问题。应聘者可以从当前招聘的项目及其团队等方面提出几个问题。不建议应聘者在技术面试的时候向面试官询问薪资情况，或者立即打听面试结果。 接下来是两个典型的面试案例，我们从中可以直观地感受到面试的整个过程。在第一个案例（详见7.1节）中，我们将看到面试过程中很多应聘者都曾犯过的错误；而在第二个案例（详见7.2节）中，我们将看到面试官所认可的表现。我们希望应聘者能够少犯甚至不犯错误，在面试过程中充分表现出自己的综合素质，同时也衷心祝愿每个应聘者都能拿到自己心仪的Offer。 7.1 案例一：（面试题49）把字符串转换成整数 面试官：看你简历上写的是精通C/C++语言，这两门语言你用了几年了？ 应聘者：从大一算起的话，快六、七年了。 面试官：也是C/C++的老程序员了嘛（微笑），那先问一个C++的问题（递给应聘者一张A4纸，上面有一段打印的代码，如下面所示）。你能不能分析一下这段代码的输出？  应聘者：（看了一下代码，略作思考）n1是2，而n2是0。 面试官：为什么？ 应聘者：在构造函数的初始化列表中，n2先被初始化为0，n2的值就是0了。接下来再用n2＋2初始化n1，所以n1的值就是2。 ［注：应聘者这个问题的回答是错误的，详见后面的“面试官点评”］ 面试官：C++是按照在初始化列表中的顺序初始化成员变量的吗？ 应聘者：（一脸困惑）不是这样吗？我不太清楚。 面试官心理： 对成员变量的初始化顺序完全没有概念就号称自己“精通”C++，也太言过其实了。算了，C++就不接着问了，看看你的编程能力。 面试官：没关系，我们换一个题目。能不能介绍一下C语言的库函数中atoi的作用？ 应聘者：atoi用来把一个字符串转换成一个整数。比如输入字符串"123"，它的输出是数字123。 面试官：对的。现在就请你写一个函数StrToInt，实现把字符串转换成整数这个功能。当然，不能使用atoi或者其他类似的库函数。你看有没有问题？ 应聘者：（嘴角出现一丝自信的笑容）没有问题。 应聘者马上开始在白纸上写出了如下代码：  应聘者：（放下笔）我已经写好了。 面试官心理： 我出的题目有这么简单吗？你也太小看我了。 面试官：这么快？（稍微看了看代码）你觉得这代码有没有问题？仔细检查一下看看。 应聘者：（从头开始读代码）哦，不好意思，忘了检查字符串是空指针的情况。 应聘者拿起笔，在原来代码上添加两行新的代码。修改之后的代码如下：  面试官：改好了？（看了一下新的代码）当字符串为空的时候，你的返回是0。如果输入的字符串是"0"的时候，返回是什么？ 应聘者：也是0。 面试官：两种情况都得到返回值0，那么当这个函数的调用者得到返回值0的时候，他怎么知道是哪种情况？ 应聘者：（脸上表情有些困惑）不知道。 面试官：你知道atoi是怎么区分的吗？ 应聘者：（努力回忆，有些慌张）不记得了。 面试官：atoi是通过一个全局变量来区分的。如果是非法输入，返回0并把这个全局变量设为一个特殊标记。如果输入是"0"，则返回0，不会设置全局变量。这样当atoi的调用者得到返回值0的时候，可以通过检查全局变量得知输入究竟是非法输入还是字符串"0"。 应聘者：哦。（拿起笔准备写代码）我马上修改。 面试官：等一下，除了空字符串之外，还有没有可能有其他类型的非法输入？ 应聘者：（陷入思考，额头上出现汗珠）如果字符串中含有'0'到'9'之外的字符，那么这样的输入也是非法的。 面试官：所有'0'到'9'之外的字符都是非法的吗？ 应聘者：加号和减号应该也是合法的输入字符。 面试官：对的。先好好想想，想清楚了再开始写代码。 应聘者思考几分钟之后，写下了如下代码：  面试官：（看到应聘者写完了）能不能简要地解释一下你的代码？ 应聘者：我定义了一个全局变量g\_Status来标记是不是遇到了非法输入。如果输入的字符串指针是空指针，则标记该全局变量然后直接返回。接下来我开始遍历字符串中的所有字符。由于正负号只有可能出现在字符串的第一个字符，我们先处理字符串的第一个字符。如果第一个字符是符号，则标记当前的数字是负数，并在最后确保返回值是负数。在处理后续字符时，当遇到'0'到'9'之外的字符时，终止遍历。如果遇到了数字，则把数值累加上去。 面试官心理： 这段代码已经写得不错，你的编程能力看起来还不错，只是编程的习惯不太好，不会在编码之前想好可能有哪些输入，从而在代码中留下太多的漏洞。这次修改的几个问题都是我已经提醒你的，没有提醒的你自己没有找出一个。 面试官：不错。觉得功能上还有什么遗漏吗？ 应聘者：还有遗漏？（思索良久）要不要考虑溢出？ 面试官：你觉得呢？如果输入的是一个空字符串""，你觉得应该输出什么？ 应聘者：""不是个数字，我想应该是返回0，同时把g\_nStatus设为非法输入。 面试官：那你能分析一下你现在的输出是什么吗？ 应聘者：（紧张，声音有些发抖）好像返回值是0，但没有设置g\_nStatus为非法输入？ 面试官：嗯。我们再考虑一些有意思的输入，比如输入的字符串只有一个正号或者负号，你期待的输出是什么？ 应聘者：如果只有一个正号或者负号，后面没有跟着数字，我想也不是有效的输入。（开始分析代码）我的返回值是0，但不会设置g\_nStatus。 面试官：由于时间也差不多了，已经没有时间给你再做修改了。我的问题问完了，你有什么问题需要问我的吗？ 应聘者：你们公司工资待遇怎么样？ 面试官：你的期望值是多少呢？ 应聘者：我有不少同学的月薪税前超过8000，我不想低于他们。 面试官心理： 我不是HR，别和我谈工资。 面试官：我们公司由人事部门统一确定应届毕业生的工资，所以你的这个问题我不能直接回答，不过你的期望值我倒可以转告HR。 应聘者：好的，谢谢。 面试官：还有其他问题吗？ 应聘者：没有了。 面试官：那这轮面试就到这里结束吧。 面试官点评： 这名应聘者在简历中写他精通C/C++，本来我对他的表现是充满了期待的。但在他回答错了第一个C++的语法题之后，他给我留下的印象就不是很好了。这就是希望越大失望越大吧。实际上，构造函数的初始化列表是C++中经常使用的一个概念。在C++中，成员变量的初始化顺序只与它们在类中声明的顺序有关，而与在初始化列表中的顺序无关。在前面的问题中，n1先于n2被声明，因此n1也会在n2之前被初始化，所以我们先会用n2＋2去初始化n1。由于n2这个时候还没有被初始化，因此它的值是随机的。用此时的n2加上2去初始化n1，n1的值只是一个随机值。接下来再用0初始化n2，因此最终n2的值是0。 接下来是要求应聘者把一个字符串转换成整数，这看起来是道很简单的题目，实现其基本功能，大部分人都能用10行之内的代码解决。可是，当我们要把很多特殊情况即测试用例都考虑进去，却不是一件容易的事情。解决数值转换问题本身不难，但我希望在写转换数值的代码之前，应聘者至少能把空指针NULL、空字符串""、正负号、溢出等方方面面的测试用例都考虑到，并在写代码的时候对这些特殊的输入都定义好合理的输出。当然，这些输出并不一定要和atoi完全保持一致，但必须要有显式的说明，和面试官沟通好。 这个应聘者最大的问题就是还没有养成在写代码之前考虑所有可能的测试用例的习惯，逻辑不够严谨，因此一开始的代码只处理了最基本的数值转换。后来我每次提醒他一处特殊的测试用例之后，他改一处代码。尽管他已经做了两次修改，但仍然有不少很明显的漏洞，特殊输入空字符串""，边界条件比如最大的正整数与最小的负整数等。由于这道题思路本身不难，因此我希望他能把问题考虑得尽可能周到，代码尽量写完整。下面是参考代码：   在前面的代码中，把空字符串""和只有一个正号或者负号的情况都考虑到了。同时正整数的最大值是0x7FFF FFFF，最小的负整数是0x8000 0000，因此我们需要分两种情况来分别判断整数是否发生上溢出或者下溢出。 最后他在提问环节给我留下的印象不是很好。他只有一个问题，是关于薪水方面。是不是反映出他找工作仅仅关心工资？通常只关心工资待遇的员工是非常容易流失的，而且他把期望值设在8000的唯一理由是他有同学的工资超过这个数。他对自己有没有一个定位？ 虽然从他后来改写代码的过程来看，他的编程能力还是不错的，但我担心以他现在的编程习惯，由于没有一个全面的考虑，他写出的代码将会漏洞百出，鲁棒性也得不到保证。总的来说，我的意见是我们不能录取这名应聘者。 源代码： 本题完整的源代码详见49\_StringToInt项目。 测试用例： ● 功能测试（输入的字符串表示正数、负数和0）。 ● 边界值测试（最大的正整数、最小的负整数）。 ● 特殊输入测试（输入字符串为NULL指针、输入字符串为空字符串、输入的字符串中有非数字字符等）。 7.2 案例二：（面试题50）树中两个结点的最低公共祖先 面试官：前面两轮面试下来感觉怎么样？ 应聘者：感觉还好，只是大脑连续转了两个小时，有点累。 面试官：面试是个体力活，是挺累的。不过程序员这个行当本身也是体力活，没有好的身体还真撑不住。面试中也要看看你们来应聘的体力怎么样。 应聘者：（笑笑并点点头）说得有道理。 面试官：开个玩笑。现在可以开始面试了吧？ 应聘者：好的，我准备好了。 面试官：请简要介绍一下你最近的一个项目。 应聘者：我最近完成的项目是Civil 3D（一款基于AutoCAD的土木设计软件）中的Multi-Target。这个Target指的是道路的边缘。之前道路的边缘只能是Civil中的一个数据类型叫Alignment，我的工作是让Civil支持其他类型的数据做道路的边缘，比如AutoCAD中的Polyline等。 面试官：有没有考虑到以后有可能会添加新的数据类型作为道路的边缘？ 应聘者：这个在开发的过程中就发生过。在第二版的需求文档中添加了一种叫做Pipeline的道路边缘。由于我的设计中考虑了扩展性，最后只要添加新的class就行了，几乎不需要对已有的代码做任何修改。 面试官：你是怎么做到的？ 应聘者在白纸上用UML画了一张类型关系图（图略）。 应聘者：（指着图解释）从这张图我们可以看出，一旦需要支持新的道路边缘比如Pipeline，我们只需继承出新的class就可以了，对已有的其他class没有影响。 面试官心理： 对自己的工作讲得很细致、很深入，这个项目的确是你设计和实现的。看得出来，你对面向对象的设计和开发有着较深的理解。 面试官：（点点头）的确是这样的。接下来我们做一个编程题吧。我的题目是输入两个树结点，求它们的最低公共祖先。 应聘者：这树是不是二叉树？ 面试官：是又怎么样，不是又怎么样？ 应聘者：如果是二叉树，并且是二叉搜索树，是可以找到公共结点的。 面试官：那假设是二叉搜索树，你怎么查找呢？ 应聘者：（有些激动，说得很快）二叉搜索树是排序过的，位于左子树的结点都比父结点小，而位于右子树的结点都比父结点大，我们只需要从树的根结点开始和两个输入的结点进行比较。如果当前结点的值比两个结点的值都大，那么最低的共同父结点一定是在当前结点的左子树中，于是下一步遍历当前结点的左子结点。如果当前结点的值比两个结点的值都小，那么最低共同父结点一定在当前结点的右子树中，于是下一步遍历当前结点的右子结点。这样在树中从上到下找到的第一个在两个输入结点的值之间的结点，就是最低的公共祖先。 面试官：看起来你对这个题目很熟悉，是不是以前做过啊？ 应聘者：（面露尴尬）这个……碰巧…… 面试官：（笑）那咱们把题目稍微换一下。如果这棵树不是二叉搜索树，甚至连二叉树都不是，而只是普通的树，又该怎么办呢？ 应聘者：（停下来想了十几秒）树的结点中有没有指向父结点的指针？ 面试官心理： 反应挺快的，而且提的问题针对性很强。你的沟通能力不错。 面试官：为什么需要指向父结点的指针？ 应聘者在白纸上画了一张图，如图7.1所示。  图7.1 树中的结点有指向父结点的指针，用虚线箭头表示 应聘者：（指着自己画的图7.1解释）如果树中的每个结点（除根结点之外）都有一个指向父结点的指针，这个问题可以转换成求两个链表的第一个公共结点。假设树结点中指向父结点的指针是pParent，那么从树的每一个叶结点开始都有一个由指针pParent串起来的链表，这些链表的尾指针都是树的根结点。输入两个结点，那么这两个结点位于两个链表上，它们的最低公共祖先刚好就是这两个链表的第一个公共结点。比如输入的两个结点分别为F和H，那么F在链表F->D->B->A上，而H在链表H->E->B->A上，这两个链表的第一个交点B刚好也是它们的最低公共祖先。 面试官：求两个链表的第一个共同结点这个题目你是不是之前也做过？ 应聘者：（摸摸后脑勺，尴尬地笑笑）这个……又被你发现了…… 面试官心理： 能够把这个题目转换成求两个链表的第一个公共结点，你的知识迁移能力不错。感觉你对数据结构很熟悉，基本上达到录用标准了。不过我很有兴趣看看你的极限在哪里。再加大点难度试试吧。 面试官：（笑）那只好再把题目的要求改变一下了。现在假设这棵树是普通的树，而且树中的结点没有指向父结点的指针。 应聘者：（稍微流露出一丝抓狂的表情，语气中透出失望）好吧，我再想想。 面试官：这个题目也只比前面的两个稍微难一点点，你能搞定的。 应聘者：（静下来思考了两分钟）所谓两个结点的公共祖先，指的是这两个结点都出现在某个结点的子树中。我们可以从根结点开始遍历一棵树，每遍历到一个结点时，判断两个输入结点是不是在它的子树中。如果在子树中，则分别遍历它的所有子结点，并判断两个输入结点是不是在它们的子树中。这样从上到下一直找到的第一个结点，它自己的子树中同时包含两个输入的结点而它的子结点却没有，那么该结点就是最低的公共祖先。 面试官：能不能举个具体的例子说明你的思路？ 应聘者：（一边在纸上画图7.2一边解释）假设还是输入结点F和H。我们先判断A的子树中是否同时包含结点F和H，得到的结果为true。接着我们再先后判断A的两个子结点B和C的子树是不是同时包含F和H，结果是B的结果是true而C的结果是false。接下来我们再判断B的两个子结点D和E，发现这两个结点得到的结果都是false。于是B是最后一个公共祖先，即我们的输出。  图7.2 一棵普通的树，树中的结点没有指向父结点的指针 面试官：听起来不错。很明显，当我们判断以结点A为根的树中是否含有结点F的时候，我们需要对D、E等结点遍历一遍；接下来判断以结点B为根的树中是否含有结点F的时候，我们还是需要对D、E等结点再遍历一遍。这种思路会对同一结点重复遍历很多次。你想想看还有没有更快的算法？ 应聘者：（双肘抵住桌子，双手抱住头顶，苦苦思索两分钟）可以用辅助内存吗？ 面试官：你需要多大的辅助内存？ 应聘者：我的想法是用两个链表分别保存从根结点到输入的两个结点的路径，然后把问题转换成两个链表的最后公共结点。 面试官：（点头，面露赞许）嗯，具体说说。 应聘者：我们首先得到一条从根结点到树中某一结点的路径，这就要求在遍历的时候，有一个辅助内存来保存路径。比如我们用前序遍历的方法来得到从根结点到H的路径的过程是这样的：（1）遍历到A，把A存放到路径中去，路径中只有一个结点A；（2）遍历到B，把B存到路径中去，此时路径为A->B；（3）遍历到D，把D存放到路径中去，此时路径为A->B->D；（4）遍历到F，把F存放到路径中去，此时路径为A->B->D->F；（5）F已经没有子结点了，因此这条路径不可能到达结点H。把F从路径中删除，变成A->B->D；（6）遍历G。和结点F一样，这条路径也不能到达H。遍历完G之后，路径仍然是A->B->D；（7）由于D的所有子结点都遍历过了，不可能到达结点H，因此D不在从A到H的路径中，把D从路径中删除，变成A->B；（8）遍历E，把E加入到路径中，此时路径变成A->B->E，（9）遍历H，已经到达目标结点，A->B->E就是从根结点开始到达H必须经过的路径。 面试官：然后呢？ 应聘者：同样，我们也可以得到从根结点开始到达F必须经过的路径是A->B->D。接着，我们求出这两个路径的最后公共结点，也就是B。B这个结点也是F和H的最低公共祖先。 面试官：这种思路的时间和空间效率是多少？ 应聘者：为了得到从根结点开始到输入的两个结点的两条路径，需要遍历两次树，每遍历一次的时间复杂度是O（n）。得到的两条路径的长度在最差情况时是O（n），通常情况下两条路径的长度是O（logn）。 面试官心理： 显然，你对数据结构的理解比大多数人要深刻得多，期待你的代码。 面试官：（微笑，点头）不错。根据这个思路写出C/C++代码，怎么样？ 应聘者：好的，没问题。 应聘者先后下了三个函数：  应聘者：代码中GetNodePath用来得到从根结点pRoot开始到达结点pNode的路径，这条路径保存在path中。函数LastCommonNode用来得到两个路径path1和path2的最后一个公共结点。函数GetLastCommonParent先调用GetNodePath得到pRoot到达pNode1的路径path1，再得到pRoot到达pNode2的路径path2，接着调用GetLastCommonPath得到path1和path2的最后一个公共结点，即我们要找的最低公共祖先。 面试官：嗯，很好。这轮面试的时间已经很长了，我的问题就到这里。你有什么需要问我的吗？ 应聘者：（略作思考）我想问问关于项目合作的事情。你们项目组和美国总部的同事是怎么合作的？是美国人做好设计，然后交给中国这边做具体实现吗？ 面试官：理论上说中国同事与美国同事之间的合作是平等的，不全是美国说了算。我们中国的团队也有自己的项目经理做产品设计。现在两边的团队都有自己负责的功能。只是我们的团队成员和美国同事比起来，经验还不够，对产品的理解没有美国同事那么深刻。因此当两边意见出现分歧的时候，他们的意见更能得到上层的重视。 应聘者：两边的团队都有哪些沟通的方式？ 面试官：平时做相关工作的同事之间会有大量的E-mail交流。每周二的早上（美国时间是星期一的下午）我们有一个例会，所有同事都会参加。在会上大家会讨论项目的进度、遇到的困难等事项。另外，由于最近我们这边招了不少新员工，美国那边正计划选派一个资深的工程师过来给新员工做培训。 应聘者：那中国这边的员工有机会去美国吗？ 面试官：我们的人力资源部门有一个项目，让新员工在两年之内至少有机会去美国接受一次培训，以熟悉公司总部的文化。只是最近由于大的经济环境不是很好，公司在严格控制差旅费用，因此这个项目的执行受到了一点影响。还有其他问题吗？ 应聘者：（想了一会儿）没有了。 面试官心理： 从最后几个问题可以看出，你对我们的项目和团队很有兴趣。同样，我也希望你能加入我们的团队一起做项目。这轮面试你通过了。 面试官：由于时间关系，这轮面试就到这里，怎么样？ 应聘者：（摸摸额头，微笑中略显疲惫）谢谢。 面试官点评： 求树中两个结点的最低公共祖先，不能说只是一个题目，而应该说是一组题目，不同条件下的题目是完全不一样的。一开始的时候，我有意没有说明树的特点，比如树是不是二叉树、树中的结点是不是有一个指向父结点的指针。我把题目说得模棱两可是希望应聘者能够主动向我提出问题，一步一步弄清我的意图。如果一个应聘者能够在面试过程中主动问出高质量的问题以弄清楚题目的要求，我会觉得他态度积极并且具有较强的沟通能力。 在这轮面试中，该应聘者表现得比较积极主动。一开始听到题目之后，他马上询问我树是不是二叉树。在我答复可以是二叉树之后他立即给出了当树是二叉排序树时的解法。我看出了他之前做过这个问题，于是就把题目的要求设为树只是普通的树而不一定是二叉树。他的反应很快，立即又问我树中的结点有没有指向父结点的指针。在第二个问题得到肯定的答复之后，他把问题转换成求两个链表的第一个公共结点。他这段的表现很好，问的两个问题都很有针对性，表明他对这种类型的问题有很深的理解，给我留下了很好的印象。 通常面试的时候让应聘者写出有指向父结点的指针这种情况的代码也就差不多了，但考虑到他之前做过类似的问题，同时我觉得他反应很快，功底不错，以他的能力应该可以挑战一下更高的难度。于是我接下来把指向父结点的指针去掉，决定再加大难度测试一下他的水平到底有多深。他再一次表现出很快的反应能力，思考了一两分钟之后就想出了一个需要重复遍历一个结点多次的算法。在我提示出还有更快的算法之后，他再次把题目转换成求链表的共同结点的问题。期间在他解释其思路的过程中，可以看出他对树的遍历算法理解得很透彻，接下来写出的代码也很规范。综合这名应聘者在本轮面试中的表现，我强烈建议我们公司录用他。 如果面试官在面试的过程中逐步加大面试题的难度，通常对应聘者来说是件好事，这说明应聘者一开始表现得很好，面试官对他的印象很好，并很有兴趣看看他的水平有多深，于是一步一步加大题目的难度。虽然最后应聘者可能不能很好地解决高难度的问题，但最终仍有可能拿到Offer。与此相反的是，有些应聘者觉得面试的时候很多问题都回答出来了，可最终被拒，觉得难以理解。其实这是因为一开始问的问题他回答得很不好，面试官已经出判断他的能力有限，心里已经默默给出了NO的结论。但为了照顾应聘者的情面，也会问几个简单的问题。虽然这些简单的问题应聘者可能都能答对，但前面的结果已经不会改变。 在这轮面试中，由于该应聘者一开始的表现很好，我才决定加大难度考考他。假如他最后普通树中结点没有指向父结点的指针这个问题没有很好地解决，我会让他回头去写普通树中结点有指向父结点的指针这个问题的代码。只要他的代码写得完整正确，我仍然会让他通过我的这轮面试，尽管我对他的评价可能没有现在这么高。