在第 1 章中，我们讨论了面试的流程。通常一轮面试是从面试官对照简历了解应聘者的项目经历及掌握的技能开始的。在介绍自己的项目经历时，应聘者可以参照STAR模型，着重介绍自己完成的工作（包括基于什么平台、用了哪些技术、实现了哪些算法等），以及最终对项目组的贡献。 接着进入重头戏——技术面试环节。在这一环节中，面试官会从编程语言、数据结构和算法等方面考查应聘者的基础知识是否扎实全面（详见第2章），并且很有可能会要求应聘者编程实现一两个函数。如果碰到的面试题很简单，则应聘者也不能掉以轻心，一定要从基本功能、边界条件和错误处理等方面确保代码的完整性和鲁棒性（详见第3章）。如果碰到的题目很...

7.1 案例一：（面试题67）把字符串转换成整数7.2 案例二：（面试题68）树中两个节点的最低公共祖先

面试是我们展示自己综合素质的时候。除了扎实的编程能力，我们还需要表现自己的沟通能力和学习能力，以及知识迁移能力、抽象建模能力和发散思维能力等方面的综合实力，如图6.5所示。 图6.5  应聘者综合能力的组成 面试官对沟通能力、学习能力的考查贯穿面试的始终。面试官不仅会留意我们回答问题时的言语谈吐，还会关注我们是否能抓住问题的本质从而提出有针对性的问题。通常面试官认为善于提问的人有较好的沟通能力和学习能力。 知识迁移能力能帮助我们轻松地解决很多问题。有些面试官在提问一道难题之前，会问一道相关但比较简单的题目，他希望我们能够从解决简单问题的过程中受到启发，最终解决较...

发散思维的特点是思维活动的多向性和变通性，也就是我们在思考问题时注重运用多思路、多方案、多途径来解决问题。对于同一个问题，我们可以从不同的方向、侧面和层次，采用探索、转换、迁移、组合和分解等方法，提出多种创新的解法。 通过考查发散思维能力，面试官能够了解应聘者探索新思路的激情。面试时面试官故意限制应聘者不能使用常规的思路，此时他在观察应聘者有没有积极的心态，是不是能够主动跳出常规思维的束缚从多角度去思考问题。比如在面试题64“求1+2++n”中，面试官有意限制不能使用乘除法及与循环、条件判断、选择相关的关键字。这个问题应该说是很难的。在难题面前，应聘者是轻言放弃，还是充满激情地寻...

计算机只是一种工具，它被用来解决实际生产生活中的问题。程序员的工作就是把各种现实问题抽象成数学模型并用计算机的编程语言表达出来，因此有些面试官喜欢从日常生活中抽取提炼出问题考查应聘者是否能建立数学模型并解决问题。要想顺利解决这种类型的问题，应聘者除了需要具备扎实的数学基础和编程能力，还需要具有敏锐的洞察力和丰富的想象力。 建模的第一步是选择合理的数据结构来表述问题。实际生产生活中的问题千变万化，而常用的数据结构只有有限的几种。我们在根据问题的特点综合考虑性能、编程难度等因素之后，选择最合适的数据结构来表达问题，也就是建立模型。比如在面试题61“扑克牌中的顺子”中，我们用一个数组表...

所谓学习能力，很重要的一点就是根据已经掌握的知识、技术，能够迅速学习、理解新的技术并运用到实际工作中去。大部分新的技术都不是凭空产生的，而是在已有技术的基础上发展起来的。这就要求我们能够把对已有技术的理解迁移到学习新技术的过程中去，也就是要具备很强的知识迁移能力。以学习编程语言为例，如果全面理解了C++的面向对象的思想，那么学习下一门面向对象的语言Java就不会很难；在深刻理解了Java的垃圾回收机制之后，再去学习另一门托管语言比如C#，也会很容易。 面试官考查应聘者知识迁移能力的一种方法是把经典的问题稍作变换。这时候面试官期待应聘者能够找到和经典问题的联系，并从中受到启发，把解...

随着软件、系统功能越来越复杂，开发团队的规模也随之扩张，开发者、测试者和项目经理之间的沟通交流也变得越来越重要。也正因如此，很多公司在面试的时候都会注意考查应聘者的沟通能力。这就要求应聘者无论是在介绍项目经验还是在介绍解题思路的时候，都需要逻辑清晰明了，语言详略得当，表述的时候重点突出、观点明确。 我们不能把好的沟通能力理解成夸夸其谈。在面试的时候，知之为知之，不知为不知，对于不清楚的知识点，要勇敢承认，千万别不懂装懂。通常当应聘者说自己很懂某一领域的时候，面试官都会跟进几个问题。如果应聘者在不懂装懂，那么面试官迟早会发现，他可能就会觉得应聘者在其他的地方也有浮报虚夸的成分，这将是得不偿...

“应聘者能够礼貌平和、不卑不亢地和面试官交流，逻辑清晰、详略得当地介绍自己及项目经历，谈论题目时能够发现问题的细节并向面试官进行询问，这些都是比较好的沟通表现。对自己做的项目能够了解得很深入、对面试题能够快速寻找解决方法是判断应聘者学习能力的一种方法。这两个能力都很重要，基本能够起到一票否决的作用。”——殷焰（支付宝，高级安全测试工程师）“有时候会问一些应聘者不是很熟悉的领域，看应聘者在遇到难题时的反应，在他们回答不出时会有人员提供解答，在解答过程中观察他的沟通能力及求知欲。”——朱麟（交通银行，项目经理）“沟通能力其实在整个面试过程中都在考核，包括询问他过往的经历，也通常会涉及沟通能力。学习...

6.1 面试官谈能力6.2 沟通能力和学习能力6.3 知识迁移能力 面试题53：在排序数组中查找数字 面试题54：二叉搜索树的第k大节点 面试题55：二叉树的深度 面试题56：数组中数字出现的次数 面试题57：和为s的数字 面试题58：翻转字符串 面试题59：队列的最大值6.4 抽象建模能力 面试题60：n个骰子的点数 面试题61：扑克牌中的顺子 面试题62：圆圈中最后剩下的数字 面试题63：股票的最大利润6.5 发散思维能力 面试题64：求1+2+···+n 面试题65：不用加减乘除做加法 面试题66：构建乘...

在编程面试的时候，面试官通常对时间复杂度和空间复杂度都会有要求，并且一般情况下面试官更加关注时间复杂度。 降低时间复杂度的第一种方法是改用更加高效的算法。比如我们用动态规划解答面试题42“连续子数组的最大和”能够把时间复杂度降低到O(n)，利用快速排序的Partition函数也能在O(n)时间内解决面试题39“数组中出现次数超过一半的数字”和面试题40“最小的k个数”。 降低时间复杂度的第二种方法是用空间换取时间。在解决面试题50“第一个只出现一次的字符”的时候，我们用数组实现一个简单的哈希表，于是用O(1)时间就能知道任意字符出现的次数。这种思路可以解决很多同类型...

硬件的发展一直遵循摩尔定律，内存的容量基本上每隔18个月就会翻一番。由于内存的容量增加迅速，在软件开发的过程中我们允许以牺牲一定的空间为代价来优化时间性能，以尽可能地缩短软件的响应时间。这就是我们通常所说的“以空间换时间”。 在面试的时候，如果我们分配少量的辅助空间来保存计算的中间结果以提高时间效率，则通常是可以被接受的。本书中收集的面试题中有不少这种类型的题目，比如在面试题49“丑数”中用一个数组按照从小到大的顺序保存已经求出的丑数；在面试题60“n个骰子的点数”中交替使用两个数组求骰子每个点数出现的次数。 值得注意的是，“以空间换时间”的策略并不一定都是可行的，...

由于每个人都希望软件的响应时间尽量短一些，所以软件公司都很重视软件的时间性能，都会在发布软件之前花不少精力进行时间效率优化。这也就不难理解为什么很多公司的面试官都把代码的时间效率当作一个考查重点。面试官除了考查应聘者的编程能力，还关注应聘者有没有不断优化效率、追求完美的态度和能力。 首先，我们的编程习惯对代码的时间效率有很大影响。比如C/C++程序员要养成采用引用（或指针）传递复杂类型参数的习惯。如果采用值传递的方式，则从形参到实参会产生一次复制操作。这样的复制是多余的操作，我们应该尽量避免。再举个例子，如果用C#做多次字符串的拼接操作，则不要多次用String的+运算符来拼接字...

“通常针对有较长工作经验的应聘者，会问一些关于时间和空间效率的问题，这能够体现一个应聘者较好的编程素质和能力。”——刘景勇（Autodesk，软件工程师）“面试时一般会直接要求空间和时间复杂度，这两者都很重要。”——张珺（百度，高级软件工程师）“我们有很多考查时间和空间效率这方面的问题。通常两者都给应聘者限定，然后让他给出解决方案。”——张晓禹（百度，技术经理）“只要不是特别大的内存开销，时间复杂度比较重要。因为改进时间复杂度对算法的要求更高。”——吴斌（英伟达，图形设计师）“是空间换时间还是时间换空间，这要看具体的题目了。对于普通的应用，一般是空间换时间，因为通常用户更关心速度，而且一般有足...

5.1 面试官谈效率5.2 时间效率 面试题39：数组中出现次数超过一半的数字 面试题40：最小的k个数 面试题41：数据流中的中位数 面试题42：连续子数组的最大和 面试题43：1~n整数中1出现的次数 面试题44：数字序列中某一位的数字 面试题45：把数组排成最小的数 面试题46：把数字翻译成字符串 面试题47：礼物的最大价值 面试题48：最长不含重复字符的子字符串5.3 时间效率与空间效率的平衡 面试题49：丑数 面试题50：第一个只出现一次的字符 面试题51：数组中的逆序对 面试题52：两个链表的第一个...