第6章 面试中的各项能力 6.1 面试官谈能力 “应聘者能够礼貌平和、不卑不亢地和面试官交流，逻辑清晰、详略得当地介绍自己及项目经历，谈论题目时能够发现问题的细节并向面试官进行询问，这些都是比较好的沟通表现。对自己做的项目能够了解很深入、对面试题能够快速寻找解决方法是判断应聘者学习能力的一个方法。这两个能力都很重要，基本能够起到一票否决的作用。” ——殷焰（支付宝，高级安全测试工程师） “有时候会问一些应聘者不是很熟悉的领域，看应聘者在遇到难题时的反应，在他们回答不出时会有人员提供解答，在解答过程中观察他的沟通能力及求知欲。” ——朱麟（交通银行，项目经理） “沟通能力其实整个过程都在考核，包括询问他过往的经历，也通常会涉及沟通能力。学习能力是在考查算法或者项目经验过程中，通过提问，尤其是一些他没有接触过的问题来考核的。沟通能力和学习能力很重要，在某种程度上这些都是潜力。如果应聘者沟通能力不行、难以合作，我们不会录取。” ——何幸杰（SAP，高级工程师） “让其介绍过往项目其实就在考查沟通和表达能力。学习能力通过问其看书和关注什么来考查。沟通能力、学习能力对最终面试结果会有一定的影响。对于资深的应聘者，影响要大些。” ——韩伟东（盛大，高级研究员） “应聘者会被问及一些需求不是很明确的问题，解决这些问题需要应聘者和面试官进行沟通，以及在讲解设计思路和代码的过程中也需要和面试官交流互动。沟通及学习能力是面试成绩中关键的考查点。” ——尧敏（淘宝，资深经理） “沟通、学习能力就是看面试者能否清晰、有条理地表达自己，是否会在自己所得到的信息不够的情况下主动发问澄清，能否在得到一些暗示之后迅速做出反应纠正错误。” ——陈黎明（微软，SDE II） 6.2 沟通能力和学习能力 1．沟通能力 随着软件、系统功能越来越复杂，开发团队的规模也随之扩张，开发者、测试者和项目经理之间的沟通交流也变得越来越重要。也正因为此，很多公司在面试的时候都会注意考查应聘者的沟通能力。这就要求应聘者无论是在介绍项目经验还是介绍解题思路的时候，都需要逻辑清晰明了，语言详略得当，表述的时候重点突出、观点明确。 我们不能把好的沟通能力理解成夸夸其谈。在面试的时候，知之为知之，不知为不知，对于不清楚的知识点，要勇敢承认，千万别不懂装懂。通常当应聘者说自己很懂某一领域的时候，面试官都会跟进几个问题。如果应聘者在不懂装懂，面试官迟早会发现，他可能就会觉得应聘者在其他的地方也有浮报虚夸的成分，这将是得不偿失的。 有意向加入外企的应聘者要注意提高自己英文交流的能力。不少外企的面试部分甚至全部采用英语面试，这对英语的要求就很高。我们通过了英语的四六级考试未必能用英语对话。如果觉得自己英语的听说能力还不够好，建议花更多的时间来提高自己的听力。英语面试中最重要的是我们要听懂面试官的问题。通常采用英文面试的面试官自己的英语都比较好，即使我们的发音不够标准，对方一般也能听懂。这和我们能听懂普通话不标准的老外说中文的道理是一样的。但如果面试官的问题没有听明白，那我们就是说得再清楚也无济于事了。 2．学习能力 计算机是一门更新速度很快的学科，每年都有新的技术不断涌现。因此作为这个领域从业人员的软件工程师们需要要具备很强的学习能力，否则时间一长就会跟不上技术进步的步伐。也正是因为这个原因，IT公司在面试的时候，面试官都会重视应聘者的学习能力。只有具备很强的学习能力及学习愿望的人，才能不断完善自己的知识结构，不断学习新的先进技术，让自己的职业生涯保持长久的生命力。 通常面试官有两种办法考查应聘者的学习能力。第一种方法是询问应聘者最近在看什么书或者在做什么项目、从中学到了哪些新技术。面试官可以用这个问题了解应聘者的学习愿望和学习能力。学习能力强的人对各种新技术充满了兴趣，随时学习、吸收新知识，并把知识转换为自己的技能。第二种方法是抛出一个新概念，接下来观察应聘者能不能在较短时间内理解这个新概念并解决相关的问题。本书收集的面试题涉及诸如数组的旋转（面试题8）、二叉树的镜像（面试题19）、丑数（面试题34）、逆序对（面试题36）等新概念。当面试官提出这些新概念的时候，他期待应聘者能够通过思考、提问、再思考的过程，理解它们并最终解决问题。 3．善于学习、沟通的人也善于提问 面试官有一个很重要的任务就是考查应聘者的学习愿望及学习能力。学习能力怎么体现呢？面试官提出一个新概念，应聘者没有听说过它，于是他在已有的理解的基础上提出进一步的问题，得到面试官的答复之后，思考再提问，几个来回之后掌握了这个概念。这个过程能够体现应聘者的学习能力。通常学习能力强的人具有主动积极的态度，对未知的领域有强烈的求知欲望。因此建议应聘者在面试过程中遇到不明白的地方多提问，这样面试官就会觉得你态度积极、求知欲望强烈，会给面试结果加分。 面试小提示： 面试是一个双向交流的过程，面试官可以问应聘者问题，同样应聘者也可以向面试官提问。如果应聘者能够针对面试题主动地提出几个高质量的问题，面试官就会觉得他有很强的沟通能力和学习能力。 举个例子，Google曾经有一道面试题：找出第1500个丑数。很多人都不知道丑数是什么。不知道怎么办？面试官就坐在对面，可以问他。面试官会告诉你只含有2、3、5三个因子的数就是丑数。你听了后，觉得听明白了，但不太确定，于是可以举几个例子并让面试官确认你的理解是不是正确：6、8、10、12都是丑数，但14就不是，对吗？当面试官给出肯定的答复，你就知道自己的理解是对。问题问的是第1500个丑数，与顺序有关。可是哪个数字是第一个丑数呢，1是不是第一个？这个你可能也不能确定，怎么办？还是问面试官，他会告诉你1是或者不是丑数。题目是他出的，他有责任把题目解释清楚。 有些面试官故意一开始不把题目描述清楚，让题目存在一定的二义性。他期待应聘者能够一步步通过提问来弄明白题目的要求。这也是在考查应聘者的沟通能力。为什么要这样考查？因为实际工作也是这样，不是一开始项目需求就定义得很清楚，程序员需要多次与项目经理甚至客户反复沟通才能把需求弄清楚。如果没有一定的沟通能力，当程序员面对一个模糊的客户需求时他就会觉得无从下手。 比如最近很流行的一个面试题，面试官最开始问：如何求树中两个结点的最低公共祖先。此时面试官对题目中的树的特点完全没有给出描述，他希望应聘者在听到问题后会提出几个问题，比如这棵树是二叉树还是普通的树。 如果面试官说是二叉树，应聘者可以继续问该树是不是排序的二叉树。面试官回答是排序的。听到这里，应聘者才能确定思路：从树的根结点出发遍历树，如果当前结点都大于输入的两个结点，则下一步遍历当前结点的左子树；如果当前结点小于输入的两个结点，则下一步遍历当前结点的右子树。一直遍历到当前结点比一个输入结点大而比另一个小的时候，此时当前结点就是符合要求的最低公共祖先。 在应聘者问树是不是二叉树的时候如果面试官回答是任意的树，此时应聘者可以接着提问在树结点中有没有指向父结点的指针。如果面试官给出肯定的回答，也就是树的结点中有指向父结点的指针，此时从输入的结点出发，沿着指向父结点的指针一直到树的根结点，可以看做一个链表，因此这个题目的解法就和求两个链表的第一个公共结点的解法是一样的了。如果面试官给出的是否定的回答，也就是树的结点没有指向父结点的指针，那么我们可以在遍历的时候用一个栈来保存从根结点到当前结点的路径，最终把它转化成求两个路径的最后一个公共结点。详细的解题过程请参考本书的7.2节。 面试官给出不同的条件，这将是3个完全不一样的题目。如果一开始应聘者没有弄清楚面试官的意图就贸然动手解题，那结果很有可能是离题千里。从中我们也可以看出在面试过程中沟通的重要性。当觉得题目的条件、要求不够明确的时候，我们一定要多提问以消除自己的疑惑。 6.3 知识迁移能力 所谓学习能力，很重要的一点就是根据已经掌握的知识、技术，能够迅速学习、理解新的技术并能运用到实际工作中去。大部分新的技术都不是凭空产生的，而是在已有技术的基础上发展起来的。这就要求我们能够把对已有技术的理解迁移到学习新技术的过程中去，也就是要具备很强的知识迁移能力。以学习编程语言为例，如果全面理解了C++的面向对象的思想，那么学习下一门面向对象的语言Java就不会很难。在深刻理解了Java的垃圾回收机制之后，再去学习另外一门托管语言比如C#，也会很容易。 面试官考查知识迁移能力的一个方法是把经典的问题稍作变换。这个时候面试官期待应聘者能够找到和经典问题的联系，并从中受到启发把解决经典问题的思路迁移过来解决新的问题。比如如果遇到面试题38“数字在排序数组中出现的次数”，我们看到“排序数组”就可以想到二分查找算法。通常二分查找算法用来在一个排序数组中查找一个数字。我们可以把二分查找的思想迁移过来稍作变换，用二分查找算法在排序数组中查找重复数字的第一个和最后一个，从而得到数字在数组中出现的次数。 面试官考查知识迁移能力的另一个方法就是先问一个简单的问题，在应聘者解答完这个简单的问题之后再追问一个相关的同时难度也更大的问题。这个时候面试官希望应聘者能够总结前面解决简单问题的经验，把前面的思路、方法迁移过来。比如在面试题40“数组中只出现一次的数字”中，面试官先问一个简单的问题即数组中只有一个数字只出现一次的情况。在应聘者想出用异或的办法找到这个只出现一次的数字之后，他再追问如果数组中有两个数字只出现一次，该怎么找出这两个数字？这个时候应聘者要从前面的思路中得到启发：既然有办法找到数组中只出现一次的一个数字，那当数组中有两个数字只出现一次的时候，我们可以把整个数组一分为二，每个子数组中包含一个只出现一次的数字，这样我们就能在两个子数组中分别找到那两个只出现一次的数字。接下来我们就可以集中精力去想办法把数组一分为二，这样就能找到解决问题的窍门，整个题目的难度系数就降低了不少。 知识迁移能力的一种通俗的说法是“举一反三”的能力。我们在去面试之前，通常都会看一些经典的面试题。然而题目总是做不完的，我们不可能把所有的面试题都准备一遍。因此更重要的是每做一道面试题的时候，都要总结这道题的解法有什么特点，有哪些思路是可以应用到同类型的题目中去的。比如为了解决面试题“翻转单词顺序”，我们先翻转整个句子的所有字符，再分别翻转每个单词中的字符。这样多次翻转字符的思路也可以运用到面试题“左旋转字符串”中（面试题42）。在解决面试题28“字符串的排列”之后，我们发现“八皇后问题”其实归根到底就是数组的排列问题。本书中很多章节在分析了一道题之后，列举了和这道题相关的题目，读者可以通过分析这些题目的相关性来提高举一反三的能力。 面试题38：数字在排序数组中出现的次数 题目：统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。 既然输入的数组是排序的，那么我们很自然地就能想到用二分查找算法。在题目给出的例子中，我们可以先用二分查找算法找到一个3。由于3可能出现多次，因此我们找到的3的左右两边可能都有3，于是我们在找到的3的左右两边顺序扫描，分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O（n）次，所以顺序扫描的时间复杂度是O（n）。因此这种算法的效率和直接从头到尾顺序扫描整个数组统计3出现的次数的方法是一样的。显然，面试官不会满意这个算法，他会提示我们还有更快的算法。 接下来我们思考如何更好地利用二分查找算法。假设我们是统计数字k在排序数组中出现的次数。在前面的算法中时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上，有没有可能用二分查找算法直接找到第一个k及最后一个k呢？ 我们先分析如何用二分查找算法在数组中找到第一个k。二分查找算法总是先拿数组中间的数字和k作比较。如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果中间数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。 基于这个思路，我们可以很容易地写出递归的代码找到排序数组中的第一个k：  在函数GetFirstK中，如果数组中不包含数字k，那么返回-1。如果数组中包含至少一个k，那么返回第一个k在数组中的下标。 我们可以用同样的思路在排序数组中找到最后一个k。如果中间数字比k大，那么k只能出现在数组的前半段。如果中间数字比k小，k就只能出现在数组的后半段。如果中间数字等于k呢？我们需要判断这个k是不是最后一个k，也就是中间数字的下一个数字是不是也等于k。如果下一个数字不是k，则中间数字就是最后一个k了；否则下一轮我们还是要在数组的后半段中去查找。我们同样可以基于递归写出如下代码：  和函数GetFirstK类似，如果数组中不包含数字k，那么GetLastK返回-1；否则返回最后一个k在数组中的下标。 在分别找到第一个k和最后一个k的下标之后，我们就能计算出k在数组中出现的次数了。相应的代码如下：  在上述代码中，GetFirstK和GetLastK都是用二分查找法在数组中查找一个合乎要求的数字，它们的时间复杂度都是O（logn），因此GetNumberOfK的总的时间复杂度也只有O（logn）。 源代码： 本题完整的源代码详见38\_NumberOfK项目。 测试用例： ● 功能测试（数组中包含查找的数字，数组中没有查找的数字，查找的数字在数组中出现一次/多次）。 ● 边界值测试（查找数组中的最大值、最小值，数组中只有一个数字） ● 特殊输入测试（表示数组的指针为NULL指针）。 本题考点： ● 考查应聘者的知识迁移能力。我们都知道二分查找算法可以用来在排序数组中查找一个数字。应聘者如果能够运用知识迁移能力，把问题转换成用二分查找算法查找重复数字的第一个和最后一个，那么这个问题也就解决了一大半。 ● 考查应聘者对二分查找算法的理解程度。这道题实际上是二分查找算法的加强版。只有对二分查找算法有着深刻的理解，应聘者才有可能解决这个问题。 面试题39：二叉树的深度 题目一：输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 二叉树的结点定义如下：  例如，图6.1中的二叉树的深度为4，因为它从根结点到叶结点最长的路径包含4个结点（从根结点1开始，经过结点2和结点5，最终到达叶结点7）。  图6.1 深度为4的二叉树 在本题中面试官给出了一种树的深度的定义，我们可以根据这个定义去得到树的所有路径，也就能得到最长的路径及它的长度。在面试题25“二叉树中和为某一值的路径”中我们详细讨论了如何记录树中的路径。这种思路的代码量比较大，我们可以尝试更加简洁的方法。 我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。比如在图6.1的二叉树中，根结点为1的树有左右两个子树，其左右子树的根结点分别为结点2和3。根结点为2的左子树的深度为3，而根结点为3的右子树的深度为2，因此根结点为1的树的深度就是4。 这个思路用递归的方法很容易实现，只需对遍历的代码稍作修改即可。参考代码如下：  源代码： 本题完整的源代码详见39\_1\_TreeDepth项目。 测试用例： ● 功能测试（输入普通的二叉树，二叉树中所有结点都没有左/右子树）。 ● 特殊输入测试（二叉树只有一个结点，二叉树的头结点为NULL指针）。 只要应聘者对二叉树这一数据结构很熟悉，就能很快写出上面的代码。如果公司对编程能力有较高的要求，面试官可能会追加一个与前面问题相关但难度更大的问题。比如，在应聘者做完上面的问题之后，面试官追问： 题目二：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如，图6.1中的二叉树就是一棵平衡二叉树。 需要重复遍历结点多次的解法，简单但不足以打动面试官 有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一个思路：在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下：  上面的代码固然简洁，但我们也要注意到由于一个结点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入图6.1中的二叉树，我们将首先判断根结点（结点1）是不是平衡的。此时我们往函数TreeDepth输入左子树的根结点（结点2）时，需要遍历结点4、5、7。接下来判断以结点2为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。 每个结点只遍历一次的解法，正是面试官喜欢的 如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。下面是这种思路的参考代码：  我们只需给上面的函数传入二叉树的根结点及一个表示结点深度的整型变量即可：  在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树。 源代码： 本题完整的源代码详见39\_2\_BalancedBinaryTree项目。 测试用例： ● 功能测试（平衡的二叉树，不是平衡的二叉树，二叉树中所有结点都没有左/右子树）。 ● 特殊输入测试（二叉树中只有一个结点，二叉树的头结点为NULL指针）。 本题考点： ● 考查对二叉树的理解及编程能力。这两个题的解法实际都只是树的遍历算法的应用。 ● 考查对新概念的学习能力。面试官提出一个新的概念即树的深度，这就要求我们在较短的时间内理解这个概念并解决相关的问题。这是一种常见的面试题型。能在较短时间内掌握、理解新概念的能力，就是一种学习能力。 ● 考查知识迁移的能力。如果面试官先问如何求二叉树的深度，再问如何判断一棵二叉树是不是平衡的，应聘者应该从求二叉树深度的分析过程中得到启发，找到判断平衡二叉树的突破口。 面试题40：数组中只出现一次的数字 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O（n），空间复杂度是O（1）。 例如输入数组{2,4,3,6,3,2,5,5}，因为只有4、6这两个数字只出现一次，其他数字都出现了两次，所以输出4和6。 这是一个比较难的题目，很少有人能在面试的时候不需要提示一下子想到最好的解决办法。一般当应聘者想了几分钟后还没有思路，面试官会给出一些提示。面试官很有可能会说：你可以先考虑这个数组中只有一个数字只出现一次，其他的都出现了两次，怎么找出这个数字？ 这两个题目都在强调一个（或两个）数字只出现一次，其他的出现两次。这有什么意义呢？我们想到异或运算的一个性质：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。 想明白怎么解决这个简单问题之后，我们再回到原始的问题，看看能不能运用相同的思路。我们试着把原数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果能够这样拆分成两个数组，我们就可以按照前面的办法分别找出两个只出现一次的数字了。 我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于这两个数字肯定不一样，那么异或的结果肯定不为0，也就是说在这个结果数字的二进制表示中至少就有一位为1。我们在结果数字中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。由于我们分组的标准是数字中的某一位是1还是0，那么出现了两次的数字肯定被分配到同一个子数组。因为两个相同的数字的任意一位都是相同的，我们不可能把两个相同的数字分配到两个子数组中去，于是我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其他数字都出现了两次。我们已经知道如何在数组中找出唯一一个只出现一次数字，因此到此为止所有的问题都已经解决了。 举个例子，假设输入数组{2,4,3,6,3,2,5,5}。当我们依次对数组中的每一个数字做异或运算之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别对这两个子数组求异或，就能找出第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。 想清楚整个过程之后再写代码就不难了。下面是参考代码：  在上述代码中，FindFirstBitIs1用来在整数num的二进制表示中找到最右边是1的位，IsBit1的作用是判断在num的二进制表示中从右边数起的indexBit位是不是1。 源代码： 本题完整的源代码详见40\_NumbersAppearOnce项目。 测试用例： 功能测试（数组中多对重复的数字，数组中没有重复的数字） 本题考点： ● 考查知识迁移能力。只有一个数字出现一次这个简单的问题，很多应聘者都能想到解决办法。能不能把解决简单问题的思路迁移到复杂问题上，是应聘者能否通过这轮面试的关键。 ● 考查对二进制和位运算的理解。 面试题41：和为s的两个数字VS和为s的连续正数序列 题目一：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。 例如输入数组{1、2、4、7、11、15}和数字15。由于4＋11＝15，因此输出4和11。 面试的时候，很重要的一点是应聘者要表现出很快的反应能力。只要想到一个方法，应聘者就可以马上告诉面试官，即使这个方法不一定是最好的。比如这个问题，很多人都能立即想到O（n2）的方法，也就是先在数组中固定一个数字，再依次判断数组中其余的n－1个数字与它的和是不是等于s。面试官会告诉我们这不是最好的办法。不过这没有关系，至少面试官知道我们的思维还是比较敏捷的。 接着我们寻找更好的算法。我们先在数组中选择两个数字，如果它们的和等于输入的s，我们就找到了要找的两个数字。如果和小于s呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们可以考虑选择较小的数字后面的数字。因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字s了。同样，当两个数字的和大于输入的数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些。 我们以数组{1、2、4、7、11、15}及期待的和15为例详细分析一下这个过程。首先定义两个指针，第一个指针指向数组的第一个（也是最小的）数字1，第二个指针指向数组的最后一个（也是最大的）数字15。这两个数字的和16大于15，因此我们把第二个指针向前移动一个数字，让它指向11。这个时候两个数字1与11的和是12，小于15。接下来我们把第一个指针向后移动一个数字指向2。此时两个数字2与11的和13，还是小于15。我们再一次向后移动第一个指针，让它指向数字4。数字4、11的和是15，正是我们期待的结果。表6.1总结了在数组{1、2、4、7、11、15}中查找和为15的数对的过程。 表6.1 在数组{1、2、4、7、11、15} 中查找和为15的数对  这一次面试官会首肯我们的思路，于是就可以动手写代码了。下面是一段参考代码：  在上述代码中，ahead为较小的数字的下标，behind为较大的数字的下标。由于数组是排序的，因此较小数字一定位于较大数字的前面，这就是while循环继续的条件是ahead>behind的原因。代码中只有一个while循环从两端向中间扫描数组，因此这种算法的时间复杂度是O（n）。 源代码： 本题完整的源代码详见41\_1\_TwoNumbersWithSum项目。 测试用例： ● 功能测试（数组中存在和为s的两个数，数组中不存在和为s的两个数） ● 特殊输入测试（表示数组的指针为NULL指针） 看到应聘者比较轻松地解决了问题还有时间剩余，有些面试官喜欢追问和前面问题相关但稍微难一些的问题。比如下面的问题就是一个例子： 题目二：输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1＋2＋3＋4＋5＝4＋5＋6＝7＋8＝15，所以结果打印出3个连续序列1～5、4～6和7～8。 有了解决前面问题的经验，我们也考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，bug初始化为2。如果从small到big的序列的和大于s，我们可以从序列中去掉较小的值，也就是增大small的值。如果从small到big的序列的和小于s，我们可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small到（1＋s）/2为止。 以求和为9的所有连续序列为例，我们先把small初始化为1，big初始化为2。此时介于small和big之间的序列是{1,2}，序列的和为3，小于9，所以我们下一步要让序列包含更多的数字。我们把big增加1变成3，此时序列为{1,2,3}。由于序列的和是6，仍然小于9，我们接下来再增加big变成4，介于small和big之间的序列也随之变成{1,2,3,4}。由于序列的和10大于9，我们要删去去序列中的一些数字，于是我们增加small变成2，此时得到的序列是{2,3,4}，序列的和正好是9。我们找到了第一个和为9的连续序列，把它打印出来。接下来我们再增加big，重复前面的过程，可以找到第二个和为9的连续序列{4,5}。可以用表6.2总结整个过程。 表6.2 求取和为9的连续序列的过程  形成了清晰的解题思路之后，我们就可以开始写代码了。下面是这种思路的参考代码：  在前面的代码中，求连续序列的和应用了一个小技巧。通常我们可以用循环求一个连续序列的和，但考虑到每一次操作之后的序列和操作之前的序列相比大部分数字都是一样的，只是增加或者减少了一个数字，因此我们可以在前一个序列的和的基础上求操作之后的序列的和。这样可以减少很多不必要的运算，从而提高代码的效率。 源代码： 本题完整的源代码详见41\_2\_ContinuesSquenceWithSum项目。 测试用例： ● 功能测试（存在和为s的连续序列，如9、100等；不存在和为s的连续序列，如4、0）。 ● 边界值测试（连续序列的最小和3） 本题考点： ● 考查思考复杂问题的思维能力。应聘者如果能够通过一两个具体的例子找到规律，解决这个问题就容易多了。 ● 考查知识迁移的能力。应聘者面对第二个问题的时候，能不能把解决第一个问题的思路应用到新的题目上，是面试官考查知识迁移能力的重要指标。 面试题42：翻转单词顺序 VS左旋转字符串 题目一：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。 这个题目流传甚广，很多公司都多次拿来作面试题，很多应聘者也多次在各种博客或者书籍上看到过通过两次翻转字符串的解法，于是很快就可以跟面试官解释清楚解题思路：第一步翻转句子中所有的字符。比如翻转"I am a student. "中所有的字符得到".tneduts a ma I"，此时不但翻转了句子中单词的顺序，连单词内的字符顺序也被翻转了。第二步再翻转每个单词中字符的顺序，就得到了"student. a am I"。这正是符合题目要求的输出。 这种思路的关键在于实现一个函数以翻转字符串中的一段。下面的函数Reverse可以完成这一功能：  接着我们可以用这个函数先翻转整个句子，再翻转句子中的每个单词。这种思路的参考代码如下：  在英语句子中，单词被空格符号分隔，因此我们可以通过扫描空格来确定每个单词的起始和终止位置。在上述代码的翻转每个单词阶段，指针pBegin指向单词的第一个字符，而pEnd指向单词的最后一个字符。 源代码： 本题完整的源代码详见42\_1\_ReverseWordsInSentence项目。 测试用例： ● 功能测试（句子中有多个单词，句子中只有一个单词）。 ● 特殊输入测试（字符串指针为NULL指针、字符串的内容为空、字符串中只有空格）。 有经验的面试官看到一个应聘者几乎不假思索就能想出一种比较巧妙的算法，就会觉得他之前可能见过这个题目。这个时候很多面试官都会再问一个问题，以考查他是不是真的理解了这种算法。面试官一个常见的考查办法就是问一个类似的但更加难一点的问题。以这道题为例，如果面试官觉得应聘者之前看过这个思路，那他可能再问第二个问题： 题目二：字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如输入字符串"abcdefg"和数字2，该函数将返回左旋转2位得到的结果"cdefgab"。 要找到字符串旋转时每个字符移动的规律，不是一件轻易的事情。那我们是不是可以从解决第一个问题的思路中找到启发？在第一个问题中，如果输入的字符串之中只有两个单词，比如"hello world"，那么翻转这个句子中的单词顺序就得到了"world hello"。比较这两个字符串，我们是不是可以把"world hello"看成是把原始字符串"hello world"的前面若干个字符转移到后面？也就是说这两个问题是非常相似的，我们同样可以通过翻转字符串的办法来解决第二个问题。 以"abcdefg"为例，我们可以把它分为两部分。由于想把它的前两个字符移到后面，我们就把前两个字符分到第一部分，把后面的所有字符都分到第二部分。我们先分别翻转这两部分，于是就得到"bagfedc"。接下来我们再翻转整个字符串，得到的"cdefgab"刚好就是把原始字符串左旋转2位的结果。 通过前面的分析，我们发现只需要调用3次前面的Reverse函数就可以实现字符串的左旋转功能。参考代码如下：  想清楚思路之后再写代码是一件很容易的事情，但我们也不能掉以轻心。面试官在检查与字符串相关的代码时经常会发现两种问题：一是输入空指针NULL时程序会崩溃；二是内存访问越界的问题，也就是试图访问不属于字符串的内存。例如如果输入的n小于0，指针pStr+n指向的内存就不属于字符串。如果我们不排除这种情况，试图访问不属于字符串的内存就会留下严重的内存越界的安全隐患。在前面的代码中，我们添加了两个if判断语句就是为了防止出现这两种问题。 源代码： 本题完整的源代码详见42\_2\_LeftRotateString项目。 测试用例： ● 功能测试（把长度为n的字符串左旋转0个字符、1个字符、2个字符、n－1个字符、n个字符、n＋1个字符）。 ● 特殊输入测试（字符串的指针为NULL指针）。 本题考点： ● 考查知识迁移的能力。当面试的时候遇到第二个问题，而之前我们做过“翻转句子中单词的顺序”这个题目，那如果能够把多次翻转字符串的思路迁移过来，就能很轻易地解决字符串左旋转的问题。 ● 考查对字符串的编程能力。 6.4 抽象建模能力 计算机只是一种工具，它的作用是用来解决实际生产生活中的问题。程序员的工作就是把各种现实问题抽象成数学模型并用计算机的编程语言表达出来，因此有些面试官喜欢从日常生活中抽取提炼出问题考查应聘者是否能建立数学模型并解决问题。要想顺利解决这种类型的问题，应聘者除了需要具备扎实的数学基础和编程能力之外，还需要具有敏锐的洞察力和丰富的想象力。 建模的第一步是选择合理的数据结构来表述问题。实际生产生活中的问题千变万化，而常用的数据结构却只有有限的几种。我们在根据问题的特点综合考虑性能、编程难度等因素之后，选择最合适的数据结构来表达问题，也就是建立模型。比如在面试题44“扑克牌的顺子”中，我们用一个数组表示一副牌，用11、12和13分别表示J、Q、K并且用0表示大小王。在面试题45“圆圈中最后剩下的数字”中，我们可以用一个环形链表模拟一个圆圈。 建模的第二步是分析模型中的内在规律，并用编程语言表述这种规律。我们只有对现实问题进行深入细微的观察分析之后，才能找到模型中的规律，才有可能编程解决问题。例如在本书2.4.2节提到的“青蛙跳台阶”问题中，它内在的规律是斐波那契数列。再比如面试题43“n个骰子的点数”问题，其本质是求数列f（n）＝f（n－1）＋f（n－2）＋f（n－3）＋f（n－4）＋f（n－5）＋f（n－6）。找到这个规律之后，我们就可以分别用递归和循环两种不同的方法去写代码。然而，并不是所有问题的内在规律都是显而易见的。在面试题45“圆圈中最后剩下的数字”中，我们经过严密的数学分析之后才能找到每次从圆圈中删除的数字的规律，从而找到一种不需要辅助环形链表的快速方法来解决问题。 面试题43：n个骰子的点数 题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 玩过麻将的人都知道，骰子一共6个面，每个面上都有一个点数，对应的是1～6之间的一个数字。所以n个骰子的点数和的最小值为n，最大值为6n。另外根据排列组合的知识，我们还知道n个骰子的所有点数的排列数为6n。要解决这个问题，我们需要先统计出每一个点数出现的次数，然后把每一个点数出现的次数除以6n，就能求出每个点数出现的概率。 解法一：基于递归求骰子点数，时间效率不够高 现在我们考虑如何统计每一个点数出现的次数。要想求出n个骰子的点数和，可以先把n个骰子分为两堆：第一堆只有一个，另一个有n－1个。单独的那一个有可能出现从1到6的点数。我们需要计算从1到6的每一种点数和剩下的n－1个骰子来计算点数和。接下来把剩下的n－1个骰子还是分成两堆，第一堆只有一个，第二堆有n－2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n－2个骰子来计算点数和。分析到这里，我们不难发现这是一种递归的思路，递归结束的条件就是最后只剩下一个骰子。 我们可以定义一个长度为6n－n＋1的数组，和为s的点数出现的次数保存到数组第s－n个元素里。基于这种思路，我们可以写出如下代码：  上述思路很简洁，实现起来也容易。但由于是基于递归的实现，它有很多计算是重复的，从而导致当number变大时性能慢得让人不能接受。关于递归的性能讨论，详见本书2.4.2节。 解法二：基于循环求骰子点数，时间性能好 可以换一种思路来解决这个问题。我们可以考虑用两个数组来存储骰子点数的每一个总数出现的次数。在一次循环中，第一个数组中的第n个数字表示骰子和为n出现的次数。在下一循环中，我们加上一个新的骰子，此时和为n的骰子出现的次数应该等于上一次循环中骰子点数和为n－1、n－2、n－3、n－4、n－5与n－6的次数的总和，所以我们把另一个数组的第n个数字设为前一个数组对应的第n－1、n－2、n－3、n－4、n－5与n－6之和。基于这个思路，我们可以写出如下代码：  在上述代码中，我们定义了两个数组pProbabilities\[0\]和pProbabilities\[1\]来存储骰子的点数之和。在一轮循环中，一个数组的第n项等于另一数组的第n－1、n－2、n－3、n－4、n－5以及n－6项的和。在下一轮循环中，我们交换这两个数组（通过改变变量flag实现）再重复这一计算过程。 值得注意的是，上述代码没有在函数里把一个骰子的最大点数硬编码（hard code）为6，而是用一个变量g\_maxValue来表示。这样做的好处是，如果某个厂家生产了其他点数的骰子，我们只需要在代码中修改一个地方，扩展起来很方便。如果在面试的时候我们能对面试官提起对程序扩展性的考虑，一定能给面试官留下很好的印象。 源代码： 本题完整的源代码详见43\_DicesProbability项目。 测试用例： ● 功能测试（1、2、3、4个骰子的各点数的概率）。 ● 特殊输入测试（输入0）。 ● 性能测试（输入较大的数字，比如11）。 本题考点： ● 数学建模的能力。不管采用哪种思路解决问题，我们都要先想到用数组来存放n个骰子的每一个点数出现的次数，并通过分析点数的规律建立模型并最终找到解决方案。 ● 考查对递归和循环的性能的理解。 面试题44：扑克牌的顺子 题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任意数字。 我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大、小王是特殊的数字，我们不妨把它们都定义为0，这样就能和其他扑克牌区分开来了。 接下来我们分析怎样判断5个数字是不是连续的，最直观的方法是把数组排序。值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。如果排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但只要我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}，在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以把它当成2去填补这个空缺。 于是我们需要做3件事情：首先把数组排序，再统计数组中0的个数，最后统计排序之后的数组中相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。 最后，我们还需要注意一点：如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式就是如果一副牌里含有对子，则不可能是顺子。 基于这个思路，我们可以写出如下代码：  为了让代码显得简洁，上述代码调用C的库函数qsort排序。可能有人担心qsort是O（nlogn）的时间复杂度，还不够快。由于扑克牌的值出现在0～13之间，我们可以定义一个长度为14的哈希表，这样在O（n）时间就能完成排序（本书2.4.1节有这种思路的例子）。通常我们认为不同级别的时间复杂度只有当n足够大的时候才有意义。由于本题中数组的长度是固定的，只有5张牌，那么O（n）和O（nlogn）不会有多少区别，我们可以选用简洁易懂的方法来实现算法。 源代码： 本题完整的源代码详见44\_ContinousCards项目。 测试用例： ● 功能测试（抽出的牌中有一个或者多个大、小王，抽出的牌中没有大、小王，抽出的牌中有对子）。 ● 特殊输入测试（输入NULL指针）。 本题考点： 考查抽象建模能力。这个题目要求我们把熟悉的扑克牌转换为数组，把找顺子的过程通过排序、计数等步骤实现。这些都是把生活中的模型用程序语言来表达的例子。 面试题45：圆圈中最后剩下的数字 题目：0,1,…,n－1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈（如图6.2所示），从数字0开始每次删除第3个数字，则删除的前四个数字依次是2、0、4、1，因此最后剩下的数字是3。  图6.2 由0－4这5个数字组成的圆圈 本题就是有名的约瑟夫（Josephuse）环问题。我们介绍两种方法：一种方法是用环形链表模拟圆圈的经典解法，第二种方法是分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字。 经典的解法，用环形链表模拟圆圈 既然题目中有一个数字圆圈，很自然的想法就是用一个数据结构来模拟这个圆圈。在常用的数据结构中，我们很容易想到环形链表。我们可以创建一个总共有n个结点的环形链表，然后每次在这个链表中删除第m个结点。 如果面试官要求我们不能使用标准模板库里的数据容器来模拟环形链表，我们自己实现一个链表也不是很难的事情。如果面试官没有特殊要求，我们就可以用模板库中的std::list来模拟一个环形链表。由于std::list本身并不是一个环形结构，因此每当迭代器（Iterator）扫描到链表末尾的时候，我们要记得把迭代器移到链表的头部，这样就相当于按照顺序在一个圆圈里遍历了。这种思路的代码如下：  如果我们用一两个例子仔细分析上述代码的运行过程，就会发现我们实际上需要在环形链表里重复遍历很多遍。重复的遍历当然对时间效率有负面的影响。这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O（mn）。同时这种思路还需要一个辅助链表来模拟圆圈，其空间复杂度是O（n）。接下来我们试着找到每次被删除的数字有哪些规律，希望能够找到更加高效的算法。 创新的解法，拿到Offer不在话下 首先我们定义一个关于n和m的方程f（n,m），表示每次在n个数字0,1,…,n－1中每次删除第m个数字最后剩下的数字。 在这n个数字中，第一个被删除的数字是（m－1）%n。为了简单起见，我们把（m－1）%n记为k，那么删除k之后剩下的n－1个数字为0,1,…,k－1,k＋1,…,n－1，并且下一次删除从数字k＋1开始计数。相当于在剩下的序列中，k＋1 排在最前面，从而形成k＋1,…,n－1,0,1,…,k－1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列是从0开始的连续序列），因此该函数不同于前面的函数，记为f’（n－1,m）。最初序列最后剩下的数字f（n,m）一定是删除一个数字之后的序列最后剩下的数字，即f（n,m）＝f’（n－1,m）。 接下来我们把剩下的这n－1个数字的序列k＋1,…,n－1,0,1,…,k－1做一个映射，映射的结果是形成一个从0到n－2的序列：  我们把映射定义为p，则p（x）＝（x－k－1）%n。它表示如果映射前的数字是x，那么映射后的数字是（x－k－1）%n。该映射的逆映射是p－1（x）＝（x＋k＋1）%n。 由于映射之后的序列和最初的序列具有同样的形式，即都是从0开始的连续序列，因此仍然可以用函数f来表示，记为f（n－1,m）。根据我们的映射规则，映射之前的序列中最后剩下的数字f’（n－1,m）＝p－1\[f（n－1,m）\]＝\[f（n－1,m）＋k＋1\]%n，把k＝（m－1）%n代入得到f（n,m）＝f’（n－1,m）＝\[f（n－1,m）＋m\]%n。 经过上面复杂的分析，我们终于找到了一个递归公式。要得到n个数字的序列中最后剩下的数字，只需要得到n－1个数字的序列中最后剩下的数字，并以此类推。当n＝1时，也就是序列中开始只有一个数字0，那么很显然最后剩下的数字就是0。我们把这种关系表示为：  这个公式无论用递归还是用循环，都很容易实现。下面是一段基于循环实现的代码：  可以看出，这种思路的分析过程尽管非常复杂，但写出的代码却非常简洁，这就是数学的魅力。最重要的是，这种算法的时间复杂度是O（n），空间复杂度是O（1），因此无论在时间效率还是空间效率上都优于第一种方法。 源代码： 本题完整的源代码详见45\_LastNumberInCircle项目。 测试用例： ● 功能测试（输入的m小于n，比如从最初有5个数字的圆圈删除每次第2、3个数字；输入的m大于或者等于n，比如从最初有6个数字的圆圈删除每次第6、7个数字）。 ● 特殊输入测试（圆圈中有0个数字）。 ● 性能测试（从最初有4000个数字的圆圈中每次删除第997个数字）。 本题考点： ● 考查抽象建模的能力。不管应聘者是用环形链表来模拟圆圈，还是分析被删除数字的规律，都要深刻理解这个问题的特点并编程实现自己的解决方案。 ● 考查对环形链表的理解及应用能力。大部分面试官只要求应聘者基于环形链表的方法解决这个问题。 ● 考查数学功底及逻辑思维能力。少数对算法和数学基础要求很高的公司，面试官会要求应聘者不能使用O（n）的辅助内存，这个时候应聘者就只能静下心来一步步推导出每次删除的数字有哪些规律。 6.5 发散思维能力 发散思维的特点是思维活动的多向性和变通性，也就是我们在思考问题时注重运用多思路、多方案、多途径地解决问题。对于同一个问题，我们可以从不同的方向、侧面和层次，采用探索、转换、迁移、组合和分解等方法，提出多种创新的解法。 通过考查发散思维能力，面试官能够了解应聘者探索新思路的激情。面试时面试官故意限制应聘者不能使用常规的思路，此时他在观察应聘者有没有积极的心态，是不是能够主动跳出常规思维的束缚从多角度去思考问题。比如在面试题46“求1＋2＋…＋n”中，面试官有意限制不能使用乘除法及与循环、条件判断、选择相关的关键字。这个问题应该说是很难的。在难题面前，应聘者是轻言放弃，还是充满激情地寻找新思路、新方法，具有不同心态的应聘者在面试中的表现是大不一样的。 通过考查发散思维，面试官能够了解应聘者的灵活性和变通性。当常规思路遇到阻碍的时候，应聘者能不能及时地从另外的角度用不同的方法去分析问题，这些都能体现应聘者的创造力。在面试题47“不用加减乘除做加法”中，当四则运算被限制使用的时候，应聘者能不能迅速地从二进制和位运算这个方向寻找突破口，都是其思维灵活性的直接体现。 通过考查发散思维，面试官还能了解应聘者知识面的广度和深度。面试实际上是一个厚积薄发的过程。在遇到问题之后，应聘者如果具有宽泛的知识面并且对各领域有较深的理解，那么他就更容易从不同的角度去思考问题。比如我们可以从构造函数、虚函数、函数指针及模板参数的实例化等不同角度去解决面试题46“求1＋2＋…＋n”。只有对C++各方面的特性了如指掌，我们才能在遇到问题的时候将各个知识点信手拈来。同样，如果我们在学习数字电路相关课程的时候对CPU中加法器的原理有深刻的理解，那么自然就会想到从二进制和位运算的角度去思考解决面试题47“不用加减乘除做加法”。 面试题46：求1＋2＋…＋n 题目：求1＋2＋…＋n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 这个问题本身没有太多的实际意义，因为在软件开发中不可能有这么苛刻的限制。但不少面试官认为这是一道不错的能够考查应聘者发散思维能力的题目，而发散思维能够反映出应聘者知识面的宽度，以及对编程相关技术理解的深度。 通常求1＋2＋…＋n除了用公式n（n＋1）/2之外，无外乎循环和递归两种思路。由于已经明确限制for和while的使用，循环已经不能再用了。递归函数也需要用if语句或者条件判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。 解法一：利用构造函数求解 我们仍然围绕循环做文章。循环只是让相同的代码重复执行n遍而已，我们完全可以不用for和while来达到这个效果。比如我们先定义一个类型，接着创建n个该类型的实例，那么这个类型的构造函数将确定会被调用n次。我们可以将与累加相关的代码放到构造函数里。如下代码正是基于这个思路：  解法二：利用虚函数求解 我们同样也可以围绕递归做文章。既然不能在一个函数中判断是不是应该终止递归，那么我们不妨定义两个函数，一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在两个函数里二选一。从二选一我们很自然地想到布尔变量，比如值为ture（1）的时候调用第一个函数，值为false（0）的时候调用第二个函数。那现在的问题是如何把数值变量n转换成布尔值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为false。有了上述分析，我们再来看下面的代码：  这种思路是用虚函数来实现函数的选择。当n不为零时，调用函数B::Sum；当n等于0时，调用函数A::Sum。 解法三：利用函数指针求解 在纯C语言的编程环境中，我们不能使用虚函数，此时可以用函数指针来模拟，这样代码可能还更加直观一些：  解法四：利用模板类型求解 另外我们还可以让编译器帮助完成类似于递归的计算。比如如下代码：  Sum\_Solution4<100>::N就是1＋2＋…＋100的结果。当编译器看到Sum\_Solution4<100>时，就会为模板类Sum \_Solution4以参数100生成该类型的代码。但以100为参数的类型需要得到以99为参数的类型，因为Sum\_Solution4<100>::N＝ Sum \_Solution4 <99>::N＋100。这个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无须生成，递归编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定的常量，不能动态输入，这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n不能太大。 源代码： 本题完整的源代码详见46\_Accumulate项目。 测试用例： ● 功能测试（输入5、10求1＋2＋…＋5和1＋2＋…＋10）。 ● 边界值测试（输入0和1）。 本题考点： ● 考查发散思维能力。当习以为常的方法被限制使用的时候，应聘者是否能发挥创造力，打开思路想出新的办法，是能否通过面试的关键所在。 ● 考查知识面的广度和深度。上面提供的几种解法，涉及构造函数、静态变量、虚拟函数、函数指针、模板类型的实例化等知识点。只有深刻理解了相关的概念，才能在需要的时候信手拈来。这就是厚积薄发的过程。 面试题47：不用加减乘除做加法 题目：写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷四则运算符号。 面试的时候被问到这个问题，很多人在想：四则运算都不能用，那还能用什么啊？可是问题总是要解决的，我们只能打开思路去思考各种可能性。首先我们可以分析人们是如何做十进制的加法的，比如是如何得出5＋17＝22这个结果的。实际上，我们可以分成三步进行：第一步只做各位相加不进位，此时相加的结果是12（个位数5和7相加不要进位是2，十位数0和1相加结果是1）；第二步做进位，5＋7中有进位，进位的值是10；第三步把前面两个结果加起来，12＋10的结果是22，刚好5＋17＝22。 我们一直在想，求两数之和四则运算都不能用，那还能用什么？对数字做运算，除了四则运算之外，也就只剩下位运算了。位运算是针对二进制的，我们就以二进制再来分析一下前面的三步走策略对二进制是不是也适用。 5的二进制是101，17的二进制是10001。还是试着把计算分成三步：第一步各位相加但不计进位，得到的结果是10100（最后一位两个数都是1，相加的结果是二进制的10。这一步不计进位，因此结果仍然是0）；第二步记下进位。在这个例子中只在最后一位相加时产生一个进位，结果是二进制的10；第三步把前两步的结果相加，得到的结果是10110，转换成十进制正好是22。由此可见三步走的策略对二进制也是适用的。 接下来我们试着把二进制的加法用位运算来替代。第一步不考虑进位对每一位相加。0加0、1加1的结果都0，0加1、1加0的结果都是1。我们注意到，这和异或的结果是一样的。对异或而言，0和0、1和1异或的结果是0，而0和1、1和0的异或结果是1。接着考虑第二步进位，对0加0、0加1、1加0而言，都不会产生进位，只有1加1时，会向前产生一个进位。此时我们可以想象成是两个数先做位与运算，然后再向左移动一位。只有两个数都是1的时候，位与得到的结果是1，其余都是0。第三步把前两个步骤的结果相加。第三步相加的过程依然是重复前面两步，直到不产生进位为止。 把这个过程想清楚之后，写出的代码非常简洁。下面是一段基于循环实现的参考代码：  源代码： 本题完整的源代码详见47\_AddTwoNumbers项目。 测试用例： 输入正数、负数和0。 本题考点： ● 考查发散思维能力。当＋、－、×、÷运算符都不能使用时，应聘者能不能打开思路想到用位运算做加法，是能否顺利解决这个问题的关键。 ● 考查对二进制和位运算的理解。 相关问题： 不使用新的变量，交换两个变量的值。比如有两个变量a、b，我们希望交换它们的值。有两种不同的办法：  面试题48：不能被继承的类 题目：用C++设计一个不能被继承的类。 在C#中定义了关键字sealed，被sealed修饰的类不能被继承。在Java中同样也有关键字final表示一个类型不能被继承。在C++中没有类似于sealed和final的关键字，我们只有自己来实现。 常规的解法：把构造函数设为私有函数 很多人都能够想到，在C++中子类的构造函数会自动调用父类的构造函数，子类的析构函数也会自动调用父类的析构函数。要想一个类不能被继承，我们只要把它的构造函数和析构函数都定义为私有函数。那么当一个类试图从它那继承的时候，必然会由于调用构造函数、析构函数而导致编译错误。 可是这个类型的构造函数和析构函数都是私有函数，我们怎样才能得到该类型的实例呢？我们可以通过定义公有的静态函数来创建和释放类的实例。基于这个思路，我们可以写出如下代码：  这个类是不能被继承，但总觉得它和普通的类型有些不一样，使用起来有点不方便。比如我们只能得到位于堆上的实例，而得不到位于栈上的实例。 新奇的解法：利用虚拟继承，能给面试官留下很好的印象 能不能实现一个与一般的类型相比除了不能被继承之外其他用法都一样的类型呢？办法还是有的，不过需要一定的技巧。请看如下代码：  这个SealedClass2使用起来和一般的类型没有区别，我们可以在栈上、也可以在堆上创建实例。尽管类MakeSealed<SealedClass2>的构造函数和析构函数都是私有的，但由于类SealedClass2是它的友元类型，因此在SealedClass2中调用MakeSealed<SealedClass2>的构造函数和析构函数都不会引起编译错误。 但当我们试图从SealedClass2中继承一个类并创建它的实例的时候，却不能通过编译。比如我们从SealedClass2中继承出类型Try：  由于类SealedClass2是从类MakeSealed<SealedClass2>虚继承过来的，在调用Try的构造函数的时候，会跳过SealedClass2而直接调用MakeSealed<SealedClass2>的构造函数。非常遗憾的是，Try不是MakeSealed<SealedClass2>的友元类型，因此不能调用它的私有构造函数。 通过上面的分析，我们发现从SealedClass2继承的类，一旦实例化就会导致编译出错，因此SealedClass2不能被继承，这也就满足了题目的要求。 注：第二种方法的可移植性不好。虽然SealedClass2在Visual Studio中能够编译，但由于GCC中对friend的要求不同于Visual Studio，目前在最新的GCC中还不支持模板参数类型作为友元类型。 源代码： 本题完整的源代码详见48\_SealedClass项目。 本题考点： ● 考查发散思维能力。当要求设计一个不能被继承的类时，应聘者要马上从把构造函数定义为私有函数出发去寻找解题方法。 ● 考查对C++多个概念的理解，比如构造函数、模板、友元等。 6.6 本章小结 面试是我们展示自己综合素质的时候。除了扎实的编程能力，我们还需要表现自己的沟通能力和学习能力，以及知识迁移能力、抽象建模能力和发散思维能力等方面的综合实力（如图6.3所示）。  图6.3 应聘者的综合能力的组成 面试官对沟通能力、学习能力的考查贯穿着面试的始终。面试官不仅会留意我们回答问题时的言语谈吐，还会关注我们是否能抓住问题的本质从而提出有针对性的问题。通常面试官认为善于提问的人有较好的沟通和学习能力。 知识迁移能力能帮助我们轻松地解决很多问题。有些面试官在提问一道难题之前，会问一道相关但比较简单的题目，他希望我们能够从解决简单问题的过程中受到启发，最终解决较为复杂的问题。另外，我们在面试之前可以做一些练习。如果面试的时候碰到类似的题目，就可以应用之前的方法。这要求我们平时要有一定的积累，并且每做完一道题之后都要总结解题方法。 有一类很有意思的面试题是从日常生活中提炼出来的，面试官用这种类型的问题来考查我们抽象建模的能力。为了解决这种类型的问题，我们先用适当的数据结构表述模型，并分析模型中的内在规律确定计算方法。 有些面试官喜欢在面试的时候限制使用常规的思路。这个时候就需要我们充分发挥发散思维的能力，跳出常规思路的束缚，从不同的角度去尝试新的办法。