Question

面试官：前面两轮面试下来感觉怎么样？

应聘者：感觉还好，只是大脑连续转了两个小时，有点累。

面试官：面试是个体力活，是挺累的。不过程序员这个行当本身也是体力活，没有好的身体还真撑不住。面试中也要看看你们来应聘的体力怎么样。

应聘者：（笑笑并点点头）说得有道理。

面试官：开个玩笑。现在可以开始面试了吧？

应聘者：好的，我准备好了。

面试官：请简要介绍一下你最近的一个项目。

应聘者：我最近完成的项目是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的结论。但为了照顾应聘者的情面，也会问几个简单的问题。虽然这些简单的问题应聘者可能都能答对，但前面的结果已经不会改变。

在这轮面试中，由于该应聘者一开始的表现很好，我才决定加大难度考考他。假如他最后普通树中结点没有指向父结点的指针这个问题没有很好地解决，我会让他回头去写普通树中结点有指向父结点的指针这个问题的代码。只要他的代码写得完整正确，我仍然会让他通过我的这轮面试，尽管我对他的评价可能没有现在这么高。