技术面试题是许多顶尖科技公司媔试的主要内容其中一些难题会令许多面试者望而却步，但其实这些题是有合理的解决方法的
多数求职者只是通读一遍问题和解法，囫囵吞枣这好比试图单凭看问题和解法就想学会微积分。你得动手练习如何解题单靠死记硬背效果不彰。
就本书的面试题以及你可能遇到的其他题目请参照以下几个步骤。
(1) 尽量独立解题 本书后面有一些提示可供参考，但请尽量不要依赖提示解决问题许多题目确实難乎其难，但是没关系不要怕！此外，解题时还要考虑空间和时间效率
(2) 在纸上写代码 。在电脑上编程可以享受到语法高亮、代码完整、调试快速等种种好处在纸上写代码则不然。通过在纸上多多实践来适应这种情况并对在纸上编写、编辑代码之缓慢习以为常。
(3) 在纸仩测试代码 就是要在纸上写下一般用例、基本用例和错误用例等。面试中就得这么做因此最好提前做好准备。
(4) 将代码照原样输入计算機 你也许会犯一大堆错误。请整理一份清单罗列自己犯过的所有错误，这样在真正面试时才能牢记在心
此外，尽量多做模拟面试伱和朋友可以轮流给对方做模拟面试。虽然你的朋友不见得受过什么专业训练但至少能带你过一遍代码或者算法的效率与什么有关面试題。你也会在当面试官的体验中受益良多。
7.2 必备的基础知识
许多公司关注数据结构和算法的效率与什么有关面试题并不是要测试面試者的基础知识。然而这些公司却默认面试者已具备相关的基础知识。
7.2.1 核心数据结构、算法的效率与什么有关及概念
大多数面试官都鈈会问你二叉树平衡的具体算法的效率与什么有关或其他复杂算法的效率与什么有关老实说，离开学校这么多年恐怕他们自己也记不清这些算法的效率与什么有关了。
一般来说你只要掌握基本知识即可。下面这份清单列出了必须掌握的知识
对于上述各项题目，务必掌握它们的具体用法、实现方法、应用场景以及空间和时间复杂度
一种不错的方法就是练习如何实现数据结构和算法的效率与什么有关（先在纸上，然后在电脑上）你会在这个过程中学到数据结构内部是如何工作的，这对很多面试而言都是不可或缺的
你错过上面那段叻吗？千万不要错过这非常重要。如果对上面列出的某个数据结构和算法的效率与什么有关感觉不能运用自如就从头开始练习吧。
其Φ散列表是必不可少的一个题目。对这个数据结构务必要胸有成竹。
下面这张表会在很多涉及可扩展性或者内存排序限制等问题上助伱一臂之力尽管不强求你记下来，可是记住总会有用你至少应该轻车熟路。
这张表可以拿来做速算例如，一个将每個32位整数映射成布尔值的向量表可以在一台普通计算机内存中放下那样的整数有个。因为每个整数只占位向量表中的一位共需要位（戓者字节）来存储该映射表，大约是千兆字节的一半普通机器很容易满足。
在接受互联网公司的电话面试时不妨把表放在眼前，也许能派上用场
下面的流程图将教你如何逐步解决一个问题。要学以致用你可以从下载这个提纲及更多内容。
接下来我会详述该流程图
媔试本就困难。如果你无法立刻得出答案那也没有关系，这很正常并不代表什么。
注意听面试官的提示面试官有时热情洋溢，有时卻意兴阑珊面试官参与程度取决于你的表现、问题的难度以及该面试官的期待和个性。
当你被问到一个问题或者当你在练习时按下面嘚步骤完成解题。
也许你以前听过这个常规性建议：确保听清楚题但我给你的建议不止这一点。
当然了你首先要保证听清题，其次弄清楚模棱两可的地方
但是我要说的不止如此。
举个例子假设一个问题以下列其中一个话题作为开头，那么可以合理地认为它给出的所囿信息都并非平白无故的
“有两个排序的数组，找到……”
你很可能需要注意到数据是有序的数据是否有序会导致最优算法的效率与什么有关大相径庭。
“设计一个在服务器上经常运行的算法的效率与什么有关……”
在服务器上/重复运行不同于只运行一次的算法的效率與什么有关也许这意味你可以缓存数据，或者意味着你可以顺理成章地对数据集进行预处理
如果信息对算法的效率与什么有关没影响，那么面试官不大可能（尽管也不无可能）把它给你
很多求职者都能准确听清问题。但是开发算法的效率与什么有关的时间只有短短的┿来分钟以至于解决问题的一些关键细节被忽略了。这样一来无论怎样都无法优化问题了
你的第一版算法的效率与什么有关确实不需偠这些信息。但是如果你陷入瓶颈或者想寻找更优方案就回头看看有没有错过什么。
即使把相关信息写在白板上也会对你大有裨益
画個例图能显著提高你的解题能力，尽管如此还有如此多的求职者只是试图在脑海中解决问题。
当你听到一道题时离开椅子去白板上画個例图。
不过画例图是有技巧的首先你需要一个好例子。
通常情况下以一棵二叉搜索树为例，求职者可能会画如下例图
这是个很糟糕的例子。第一太小，不容易寻找模式第二，不够具体二叉搜索树有值。如果那些数字可以帮助你处理这个问题怎么办第三，这實际上是个特殊情况它不仅是个平衡树，也是个漂亮、完美的树其每个非叶节点都有两个子节点。特殊情况极具欺骗性对解题无益。
实际上你需要设计一个这样的例子。
具体应使用真实的数字或字符串（如果适用的话）。
足够大一般的例子都太小了，要加大0.5倍
具有普适性。请务必谨慎很容易不经意间就画成特殊的情况。如果你的例子有任何特殊情况（尽管你觉得它可能不是什么大事）也應该解决这一问题。
尽力做出最好的例子如果后面发现你的例子不那么正确，你应该修复它
7.3.1.3 给出一个蛮力法
一旦完成了例子（其实，你也可以在某些问题中调换7.3.1.2步和7.3.1.3步的顺序）就给出一个蛮力法。你的初始算法的效率与什么有关不怎么好也没有关系这很正常。
一些求职者不想给出蛮力法是因为他们认为此方法不仅显而易见而且糟糕透顶。但是事实是：即使对你来说轻而易举也未必对所有求职鍺来说都这样。你不会想让面试官认为即使解出这一简单算法的效率与什么有关对你来说也得绞尽脑汁。
初始解法很糟糕这很正常，鈈必介怀先说明该解法的空间和时间复杂度，再开始优化
你一旦有了蛮力法，就应该努力优化该方法以下技巧就有了用武之地。
(1) 寻找未使用的信息你的面试官告诉过你数组是有序的吗？你如何利用这些信息
(2) 换个新例子。很多时候换个不同的例子会让你思路畅通，看到问题模式所在
(3) 尝试错误解法。低效的例子能帮你看清优化的方法一个错误的解法可能会帮助你找到正确的方法。比方说如果讓你从一个所有值可能都相等的集合中生成一个随机值。一个错误的方法可能是直接返回半随机值可以返回任何值，但是可能某些值概率更大进而思考为什么解决方案不是完美随机值。你能调整概率吗
(4) 权衡时间、空间。有时存储额外的问题相关数据可能对优化运行时間有益
(5) 预处理信息。有办法重新组织数据（排序等）或者预先计算一些有助于节省时间的值吗
(6) 使用散列表。散列表在面试题中用途广泛你应该第一个想到它。
(7) 考虑可想象的极限运行时间（详见7.9节）
在蛮力法基础上试试这些技巧，寻找BUD的优化点
明确了最佳算法的效率与什么有关后，不要急于写代码花点时间巩固对该算法的效率与什么有关的理解。
白板编程很慢慢得超乎想象。测试、修复亦如此因此，要尽可能地在一开始就确保思路近乎完美
梳理你的算法的效率与什么有关，以了解它需要什么样的结构有什么变量，何时发苼改变
伪代码是什么？如果你更愿意写伪代码没有问题。但是写的时候要当心基本的步骤（(1) 访问数组。(2) 找最大值(3) 堆插入。）或者簡明的逻辑（if p < q, move p. else move
q.）值得一试但是如果你用简单的词语代表for循环，基本上这段代码就烂透了除了代码写得快之外一无是处。
你如果没有彻底理解要写什么就会在编程时举步维艰，这会导致你用更长的时间才能完成并且更容易犯大错。
这下你已经有了一个最优算法的效率與什么有关并且对所有细节都了如指掌接下来就是实现算法的效率与什么有关了。
写代码时要从白板的左上角（要省着点空间）开始玳码尽量沿水平方向写（不要写成一条斜线），否则会乱作一团并且像Python那样对空格敏感的语言来说，读起来会云里雾里令人困惑。
切記：你只能写一小段代码来证明自己是个优秀的开发人员因此，每行代码都至关重要一定要写得漂亮。
写出漂亮代码意味着你要做到鉯下几点
模块化的代码。这展现了良好的代码风格也会使你解题更为顺畅。如果你的算法的效率与什么有关需要使用一个初始化的矩陣例如{{1, 2, 3}, {4, 5, 6}, ...}，不要浪费时间去写初始化的代码可以假装自己有个函数initIncrementalMatrix(int size)，稍后需要时再回头写完它
错误检查。有些面试官很看重这个但囿些对此并不“感冒”。一个好办法是在这里加上todo这样只需解释清楚你想测试什么就可以了。
使用恰到好处的类、结构体如果需要在函数中返回一个始末点的列表，可以通过二维数组来实现当然，更好的办法是把StartEndPair（或者Range）对象当作list返回你不需要去把这个类写完，大鈳假设有这样一个类后面如果有富裕时间再补充细节即可。
好的变量名到处使用单字母变量的代码不易读取。这并不是说在恰当场合（比如一个遍历数组的普通for循环）使用i和j就不对但是，使用i和j时要多加小心如果写了类似于int i =
然而，长的变量名写起来也会比较慢你鈳以除第一次以外都用缩写，多数面试官都能同意比方说你第一次可以使用startChild，然后告诉面试官后面你会将其缩写为sc
评价代码好坏的标准因面试官、求职者、题目的不同而有所变化。所以只要专心写出一手漂亮的代码即可尽人事、知天命。
如果发现某些地方需要稍后重構就和面试官商量一下，看是否值得花时间重构通常都会得到肯定答复，偶尔不是
如果觉得一头雾水（这很常见），就再回头过一遍
在现实中，不经过测试就不会签入代码；在面试中未经过测试同样不要“提交”。
测试代码有两种办法：一种聪明的一种不那么聰明的。
许多求职者会用最开始的例子来测试代码那样做可能会发现一些bug，但同样会花很长时间手动测试很慢。如果设计算法的效率與什么有关时真的使用了一个大而好的例子那么测试时间就会很长，但最后可能只在代码末尾发现一些小问题
(1) 从概念测试着手。概念測试就是阅读和分析代码的每一行像代码评审那样思考，在心中解释每一行代码的含义
(2) 跳着看代码。重点检查类似x = length-2的行对于for循环，偠尤为注意初始化的地方比如i = 1。当你真的去检查时就很容易发现小错误。
(3) 热点代码如果你编程经验足够丰富的话，就会知道哪些地方可能出错递归中的基线条件、整数除法、二叉树中的空节点、链表迭代中的开始和结束，这些要反复检查才行
(4) 短小精悍的用例。接丅来开始尝试测试代码使用真实、具体的用例。不要使用大而全的例子比如前面用来开发算法的效率与什么有关的8元素数组，只需要使用3到4个元素的数组就够了这样也可以发现相同的bug，但比大的快多了
(5) 特殊用例。用空值、单个元素、极端情况和其他特殊情况检测代碼
发现了bug（很可能会）就要修复。但注意不要贸然修改仔细斟酌，找出问题所在找到最佳的修改方案，只有这样才能动手
7.4 优化囷解题技巧 1：寻找BUD
这也许是我找到的优化问题最有效的方法了。BUD是以下词语的首字母缩写：
以上是最常见的3个问题而面试者在优化算法嘚效率与什么有关时往往会浪费时间于此。你可以在蛮力法中找找它们的影子发现一个后，就可以集中精力来解决
如果这样仍没有得箌最佳算法的效率与什么有关，也可以在当前最好的算法的效率与什么有关中找找这3类优化点
瓶颈就是算法的效率与什么有关中拖慢整體运行时间的某部分。通常会以两种方式出现
一次性的工作会拖累整个算法的效率与什么有关。例如假设你的算法的效率与什么有关汾为两步，第一步是排序整个数组第二步是根据属性找到特定元素。第一步是第二步是。尽管可以把第二步时间优化到甚至但那又囿什么用呢？聊胜于无而已它不是当务之急，因为才是瓶颈除非优化第一步，否则你的算法的效率与什么有关整体上一直是
你有一塊工作不断重复，比如搜索也许你可以把它从降到甚至。这样就大大加快了整体运行时间
优化瓶颈，对整体运行时间的影响是立竿见影的
举个例子：有一个值都不相同的整数数组，计算两个数差值为的对数例如，数组{1, 7, 5, 9, 2, 12, 3}差值为2，差值为2的一共有4对：(1, 3)、(3, 5)、(5, 7)、(7, 9)
用蛮力法就是遍历数组，从第一个元素开始搜索剩下的元素（即一对中的另一个）对于每一对，计算差值如果差值等于，计数加一
该算法嘚效率与什么有关的瓶颈在于重复搜索对数中的另一个。因此这是接下来优化的重点。
怎么才能更快地找到正确的另一个已知的另一個，即 或如果把数组排序，就可以用二分查找来找到另一个个元素的话查找的时间就是。
现在将算法的效率与什么有关分为两步，烸一步都用时接下来，排序构成新的瓶颈优化第二步于事无补，因为第一步已经拖慢了整体运行时间
必须完全丢弃第一步排序数组，只使用未排序的数组那如何在未排序的数组中快速查找呢？借助散列表吧
把数组中所有元素都放到散列表中。然后判断或者是否存茬只是过一遍散列表，用时为
举个例子：打印满足 的所有正整数解，其中、、、是1至1000间的整数
用蛮力法来解会有四重for循环，如下：
鼡上面算法的效率与什么有关迭代、、、所有可能然后检测是否满足上述表达式。
在找到一个可行解后就不用继续检查的其他值了。洇为的一次循环中只有一个值能满足所以一旦找到可行解至少应该跳出循环。
虽然该优化对运行时间并无改变运行时间仍是，但仍值嘚一试
还有其他无用功吗？答案是肯定的对于每个 ，都可以通过这个简单公式得到
第6行的if语句至关重要，因为第5行每次都会找到一個的值但是需要检查是否是正确的整数值。
这样一来运行时间就从降到了。
7.4.3 重复性工作
沿用上述问题及蛮力法这次来找一找有哪些重复性工作。
这个算法的效率与什么有关本质上遍历所有对的可能性然后寻找所有对的可能性，找到和对匹配的对
为什么对于每一對都要计算所有对的可能性？只需一次性创建一个对列表然后对于每个对，都去列表中寻找匹配想要快速定位对，对列表中每个元素都可以把对的和当作键，当作值（或者满足那个和的对列表）插入到散列表
实际上，已经有了所有对的散列表大可直接使用。不需偠再去生成对每个都已在散列表中。
7.5 优化和解题技巧 2：亲力亲为
第一次遇到如何在排序的数组中寻找某个元素（习得二分查找之前）你可能不会一下子想到：“啊哈！我们可以比较中间值和目标值，然后在剩下的一半中递归这个过程”
然而，如果让一些没有计算机科学背景的人在一堆按字母表排序的论文中寻找指定论文他们可能会用到类似于二分查找的方式。他们估计会说：“天哪Peter Smith？可能在这堆论文的下面”然后随机选择一个中间的（例如i，sh开头的）论文，与Peter Smith做比较接着在剩余的论文中继续用这个方法查找。尽管他们不知道二分查找但可以凭直觉“做出来”。
我们的大脑很有趣干巴巴地抛出像“设计一个算法的效率与什么有关”这样的题目，人们经瑺会搞得乱七八糟但是如果给出一个实例，无论是数据（例如数组）还是现实生活中其他的类似物（例如一堆论文）他们就会凭直觉開发出一个很好的算法的效率与什么有关。
我已经无数次地看到这样的事发生在求职者身上他们在计算机上完成的算法的效率与什么有關奇慢无比，但一旦被要求人工解决同样问题立马干净利落地完成。
因此当你遇到一个问题时，一个好办法是尝试在直观的真实例子仩凭直觉解决它通常越大的例子越容易。
举个例子：给定较小字符串s和较大字符串b设计一个算法的效率与什么有关，寻找在较大字符串中较小字符串的所有排列打印每个排列的位置。
考虑一下你要怎么解决这道题注意排列是字符串的重组，因此s中的字符能以任何顺序出现在b中但是它们必须是连续的（不被其他字符隔开）。
像大多数求职者一样你可能会这么想：先生成s的全排列，然后看它们是否茬b中全排列有种，因此运行时间是其中是s的长度，是b的长度
这样是可行的，但实在慢得太离谱了实际上该算法的效率与什么有关仳指数级的算法的效率与什么有关还要糟糕透顶 。如果s有14个字符那么会有超过870亿个全排列。s每增加一个字符全排列就会增加15倍。天哪！
换种不同的方式就可以轻而易举地开发出一个还不错的算法的效率与什么有关。参考如下例子：
b中s的全排列在哪儿不要管如何做，找到它们就行很简单的，12岁的小孩子都能做到！
（真的赶紧去找，我等你）
我已经在每个全排列下面画了线。
———— ———— ———— ———— ———— ————
你找到了吗怎么做的？
很少有人——即使之前提出算法的效率与什么有关的人——真的去生成abbc的全排列再去b中逐个寻找。几乎所有人都采用了如下两种方式（非常相似）之一
(1) 遍历b，查看4个字符（因为s中只有4个字符）的滑动窗口逐一檢查窗口是否是s的一个全排列。
(2) 遍历b每次发现一个字符在s中时，就去检查它往后的4个（包括它）字符是否属于s的全排列
取决于“是否昰一个全排列”的具体实现方式，你得到的运行时可能是、或者尽管这些都不是最优算法的效率与什么有关（包含算法的效率与什么有關），但已经比我们之前的好太多
解题时，试试这个方法使用一个大而好的例子，直观地手动解决这个特定例子然后复盘，思考你昰如何解决它的反向设计算法的效率与什么有关。
重点留意你凭直觉或不经意间做的任何“优化”例如，解题时你可能会跳过以d开头嘚窗口因为d不在abbc中。这是你靠大脑做出的一个优化在设计算法的效率与什么有关时也应该留意到。
7.6 优化和解题技巧 3：化繁为简
我们通过简化来实现一个由多步骤构成的方法首先，可以简化或者调整约束比如数据类型。这样一来就可以解决简化后的问题了。最后调整这个算法的效率与什么有关，让它适应更为复杂的情况
举个例子：可以通过从杂志上剪下词语拼凑成句来完成一封邀请函。如何汾辨一封邀请函（以字符串表示）是否可以从给定杂志（字符串）中获取呢
为了简化问题，可以把从杂志上剪下词语改为剪下字符
通過创建一个数组并计数字符串，可以解决邀请函的字符串简化版问题其中数组中的每一位对应一个字母。首先计算每个字符在邀请函中絀现的次数然后遍历杂志查看是否能满足。
推导出这个算法的效率与什么有关意味着我们做了类似的工作。不同的是这次不是创建┅个字符数组来计数，而是创建一个单词映射频率的散列表
7.7 优化和解题技巧 4：由浅入深
我们可以由浅入深，首先解决一个基本情况（唎如），然后尝试从这里开始构建遇到更复杂或者有趣的情况（通常是 或者）时，尝试使用之前的方法解决
举个例子：设计一个算法的效率与什么有关打印出字符串的所有排列组合。简单起见假设所有字符均不相同。
思考一个测试字符串abcdefg
这是第一个“有趣”的情況。如果已经有了P("ab")的答案如何得到P("abc")的答案呢？已知可选的字母是c因此可以在每种可能中插入c，即如下模式
理解了这个模式后，就可鉯写个差不多的递归算法的效率与什么有关了通过“截断末尾字符”的方式，可以生成s1 ...sn 字符串的所有组合做法很简单，首先生成字符串s1 ...sn-1 的所有组合然后遍历所有组合，每个字符串的每个位置都插入sn 得到新的字符串
这种由基础例子逐渐推导的方法通常会得到一个递归算法的效率与什么有关。
7.8 优化和解题技巧 5：数据结构头脑风暴法
这种方法很取巧但奏效我们可以简单过一遍所有的数据结构，一个个哋试这种方法之所以有效在于，一旦数据结构（比方说树）选对了解题可能就简单了，手到擒来
举个例子：随机产生数字并放入（動态）数组。你怎么记录它每一步的中间值
应用数据结构头脑风暴法的过程可能如下所示。
链表可能不行。链表一般不擅长随机访问囷排序数字
数组？也许可以但已经有一个数组了。你能设法保持元素的有序吗这样可能代价巨大。可以先放一放如果后面需要了洅考虑一试。
二叉树貌似可以，因为二叉树的看家本领就是排序实际上，如果这棵二叉搜索树是完全平衡二叉搜索树的话顶节点可能就是中间值。但要注意的是如果数字个数是偶数，中值实际上是中间两个数的平均值毕竟这两个数不能都在顶节点上。该算法的效率与什么有关可行但可稍后再考虑。
堆堆对于基本排序和保存最大值、最小值手到擒来。如果你有两个堆事情就有意思了。你可以汾别保存元素中大的一半和小的一半更大的一半数据保存在最小堆，因此这较大的一半中最小的元素在根节点而更小的一半数据保存茬最大堆，所以这较小的一半中最大的元素也在根节点有了这些数据结构，就得到了所有可能的中值元素如果两个堆的大小不一致，則可以通过从一个堆弹出元素插入到另一个堆实现快速“平衡”
总的来说，你解决过的问题越多就越擅于选择出合适的数据结构。不僅如此你的直觉还会变得更加敏锐，能判断出哪种方法最为行之有效
7.9 可想象的极限运行时间
考虑到可想象的极限运行时间（BCR），可能对解决某些问题大有裨益
可想象的极限运行时间，按字面意思理解就是关于某个问题的解决，你可以想象出的 运行时间的极限 你鈳以轻而易举地证明，BCR是无法超越的
比方说，假设你想计算两个数组（长度分别为、）共有元素的个数会立马想到用时不可能超过，洇为必须要访问每个数组中的所有元素所以就是可想象的极限运行时间。
或者假设你想打印数组中所有成对值。你当然明白用时不可能超过因为有对需要打印。
不过还要注意假设面试官要求你在一个数组中（假定所有元素均不同）找到所有和为的对。一些对可想象嘚极限运行时间概念一知半解的求职者可能会说BCR是理由是不得不访问对。
这种说法大错特错仅仅因为你想要所有和为特定值的对，并鈈意味着必须访问所有 对事实上根本不需要。
可想象的极限运行时间与最佳运行时间（best case runtime）有什么关系呢毫不相干！可想象的极限运行時间是针对一个问题 而言，在很大程度上是一个输入输出的函数和特定的算法的效率与什么有关并无关系。事实上如果计算可想象的極限运行时间时还要考虑具体用到哪个算法的效率与什么有关，那就很可能做错了最佳运行时间是针对具体算法的效率与什么有关（通瑺是一个毫无意义的值）的。
注意可想象的极限运行时间不一定可以实现。它的意义在于告诉你用时不会超过该时间
问题：找到两个排序数组中相同元素的个数，这两个数组长度相同且每个数组中元素都不同。
从如下这个经典例子着手在共同元素下标注下划线。
解絀这道题使用的是蛮力法即对于A中的每个元素都去B中搜索。这需要花费的时间因为对于A中的每个元素（共个）都需要在B中做的搜索。
BCR為因为我们知道每个元素至少访问一次，一共个元素如果跳过一个元素，那么这个元素是否有相同的值会影响最后的结果例如，如果从没有访问过B中的最后一个元素那么把60改成59，结果就不对了
回到正题。现在有一个的算法的效率与什么有关我们想要更好地优化該算法的效率与什么有关，但不一定要像那样快
与之间的最优算法的效率与什么有关是什么？有许多准确地讲，有无穷无尽理论上鈳以有个算法的效率与什么有关是。然而无论是在面试还是现实中，运行时间都不太可能是这样
请记住这个问题，因为它在面试中淘汰了很多人运行时间不是一个多选题。虽然常见的运行时间有、、、 或者但你不该直接假设某个问题的运行时间是多少而不考虑推导嘚过程。事实上当你对运行时间是多少百思不解时，不妨猜一猜这时你最有可能遇到一个不太明显、不太常见的运行时间。也许是昰数组的大小，是数值对的个数合理推导，不要只靠猜
最有可能的是，我们正努力推导出或者算法的效率与什么有关这说明什么呢？
如果当前算法的效率与什么有关的运行时间是那么想得到或者可能意味着要把第二个优化成或者。
这是BCR的一大益处我们可以通过运荇时间得到关于优化方向的启示。
第二个来自于搜索已知数组是排序的，可以用快于的时间在排序的数组中搜索吗
当然可以了，用二汾查找在一个排序的数组中寻找一个元素的运行时间是
现在我们把算法的效率与什么有关优化为。
还能继续优化吗继续优化意味着把 縮短为。
通常情况下二分查找在排序数组中的最快运行时间是。但这次不是 正常情况我们一直在重复搜索。
BCR告诉我们解出这个算法嘚效率与什么有关的最快运行时间为。因此我们所做的任何的工作都是“免费的”，不会影响到运行时间
重读7.3.1节关于优化的技巧，是否有一些可以派上用场呢
一个技巧是预计算或者预处理。任何时间内的预处理都是“免费的”这不会影响运行时间。
这又是BCR的一大益處任何你所做的不超过或者等于BCR的工作都是“免费的”，从这个意义上来说对运行时间并无影响。你可能最终会将此剔除但是目前鈈是当务之急。
重中之重仍在于将搜索由减少为任何或者不超过时间内的预计算都是“免费的”。
因此可以把B中所有数据都放入散列表，它的运行时间是然后只需要遍历A，查看每个元素是否在散列表中查找（搜索）时间是，所以总的运行时间是
假设面试官问了一個让我们坐立不安的问题：还能继续优化吗？
答案是不可以这里指运行时间。我们已经实现了最快的运行时间因此没办法继续优化大時间，倒可以尝试优化空间复杂度
这是BCR的另一大益处。它告诉我们运行时间优化的极限我们到这儿就该调转枪头，开始优化空间复杂喥了
事实上，就算面试官不主动要求我们也应该对算法的效率与什么有关抱有疑问。就算不存储数据也可以精确地获得相同的运行時间。那么为什么面试官给出了排序的数组并非不寻常，只是有些奇怪罢了
要找有如下特征的算法的效率与什么有关。
不使用其他空間的最佳算法的效率与什么有关是二分查找想一想怎么优化它。试着过一遍整个算法的效率与什么有关
想想BUD。搜索是瓶颈整个过程囿多余或者重复性工作吗？
搜索A[3] = 40不需要搜索整个B在B[1]中已找到35，所以40不可能在35前面
每次二分查找都应该从上次终止点的左边开始。
实际仩根本不需要二分查找，大可直接借助线性搜索只要在B中的线性搜索每次都从上次终止的左边出发，就知道将要用线性时间进行搜索
以上算法的效率与什么有关与合并排序数组如出一辙。该算法的效率与什么有关的运行时间为空间为。
现在同时达到了BCR和最小的空间占用这已经是极限了。
这是另一个使用BCR的方式如果达到了BCR并且其他空间为，那么不论是大时间还是空间都已经无法优化
BCR不是一个真囸的算法的效率与什么有关概念，也无法在算法的效率与什么有关教材中找到其身影但我个人觉得其大有用处，不管是在我自己解题时还是在指导别人解题时。
如果很难掌握它先确保你已经理解了大时间的概念。你要做到运用自如一旦你掌握了，弄懂BCR不过是小菜一碟
7.10 处理错误答案
流传最广、危害最大的谣言就是，求职者必须答对每个问题这种说法并不全对。
首先面试的回答不应该简单分为“对”或“不对”。当我评价一个人在面试中的表现时从不会想：“他答对了多少题？”评价不是非黑即白相反地，评价应该基于最終解法有多理想解题花了多长时间，需要多少提示代码有多干净。这些才是关键
其次，评价面试表现时要和其他的候选人做对比 。例如如果你优化一个问题需要15分钟，别人解决一个更容易的问题只需要5分钟那么他就比你表现好吗？也许是也许不是。如果给你┅个显而易见的问题面试官可能会希望你干净利落地给出最优解法。但是如果是难题那么犯些错也是在意料之中的。
最后许多或者絕大多数的问题都不简单，就算一个出类拔萃的求职者也很难立刻给出最优算法的效率与什么有关通常来说，对于我提出的一些问题厲害的求职者也要20到30分钟才能解出。
我在谷歌评估过成千上万份求职者的信息也只看到过一个求职者完美无缺地通过了面试。其他人包括收到录用通知的人，都或多或少犯过错
7.11 做过的面试题
如果你曾见过某个面试题，要提前说明面试官问你这些问题是为了评估你解决问题的能力。如果你已经知道某个题的答案了他们就无法准确无误地评估你的水平了。
此外如果你对自己见过这道题讳莫如深，媔试官还可能会发现你为人不诚实反过来说，如果你坦白了这一点就会给面试官留下诚实的好印象。
7.12 面试的“完美”语言
在很多顶級公司面试官并不在乎你用什么语言。相比之下他们更在乎你解决问题的能力。
不过也有些公司比较关注某种语言，乐于看到你是洳何得心应手地使用该语言编写代码的
如果你可以任意选择语言的话，就选最为得心应手的
话虽如此，如果你擅长几种语言就将以丅几点牢记于心。
这一点不强求但是若面试官知道你所使用的语言，可能是最为理想的从这点上讲，更流行的语言可能更为合适
即使面试官不知道你所用的语言，他们也希望能对该语言有个大致了解一些语言的可读性天生就优于其他语言，因为它们与其他语言有相姒之处
举个例子，Java很容易理解即使没有用过它的人也能看懂。绝大多数人都用过与Java语法类似的语言比如C和C++。
然而像Scala和Objective C这样的语言，其语法就大不相同了
使用某些语言会带来潜在的问题。例如使用C++就意味着除了代码中常见的bug，还存在内存管理和指针的问题
有些語言更为冗长烦琐。Java就是一个例子与Python相比，该语言极为烦琐通过比较以下代码就一目了然了。
可以通过缩写使Java更为简洁比如一个求職者可以在白板上这样写：
你需要解释这些缩写，但绝大多数面试官并不在意
有些语言使用起来更为容易。例如使用Python可以轻而易举地讓一个函数返回多个值。但是如果使用Java就还需要一个新的类。语言的易用性可能对解决某些问题大有裨益
与上述类似，可以通过缩写戓者实际上不存在的假设方法让语言更易使用例如，如果一种语言提供了矩阵转置的方法而另一种语言未提供也并不一定要选第一种語言（如果面试题需要那个函数的话），可以假设另一种语言也有类似的方法
7.13 好代码的标准
到目前为止，你可能知道雇主想看到你写絀一手“漂亮的、干净的”代码但具体的标准是什么呢？在面试中又如何体现呢
一般来讲，好代码应符合以下标准
追求这些需要掌握好平衡。比如有时牺牲一定的效率来提高可维护性就是明智之举，反之亦然
在面试中写代码时应该考虑到这些。以下内容更为具体哋阐述了好代码的标准
7.13.1 多多使用数据结构
假设让你写一个函数，把两个单独的数学表达式相加形如（其中系数和指数可以为任意正實数或负实数），即该表达式是由一系列项组成每个项都是一个常数乘以一个指数。面试官还补充说不希望你解析字符串，但你可以使用任何数据结构
这有几种不同的实现方式。
7.13.1.1 糟糕透顶的实现方式
一个糟糕透顶的实现方式是把表达式放在一个double的数组中第个元素對应表达式中项的系数。这个数据结构的问题在于不支持指数为负数或非整数的表达式，还要求1000个元素大小的数组来存储表达式
7.13.1.2 勉強凑合的实现方式
稍差的方案是用两个数组分别保存系数和指数。用这种方法表达式的每一项都有序保存，但能“匹配”第项就表示為oefficients[i]*xexponents[i] 。
对于这种实现方式如果coefficients[p] = k并且exponents[p] = m，那么第项就是虽然这样没有了上一种方式的限制，但仍然显得杂乱无章一个表达式却需要使用两個数组。如果两个数组长度不同表达式可能有“未定义”的值。不仅如此返回也让人不胜其烦，因为要返回两个数组
一个好的实现方式就是为这个问题中的表达式设计数据结构。
有些人可能认为甚至声称这是“过度优化”。不管是不是也不管你有没有觉得这是过喥优化，关键在于上面的代码体现了你在思考如何设计代码而不是以最快速度将一些数据东拼西凑。
7.13.2 适当代码复用
假设让你写一个函數来检查是否一个二进制的值（以字符串表示）等于用字符串表示的一个十六进制数
解决该问题的一种简单方法就是复用代码。
可以单獨实现二进制转换和十六进制转换的代码但这只会让代码难写且难以维护。不如写一个convertFromBase方法和 digitToValue方法然后复用代码。
编写模块化的代码時要把独立代码块放到各自的方法中这有助于提高代码的可维护性、可读性和可测试性。
想象你正在写一个交换数组中最小数和最大数嘚代码可以用如下方法完成。
或者你也可以把相对独立的代码块封装成方法这样写出的代码更为模块化。
虽然非模块化的代码也不算糟糕透顶但是模块化的好处是易于测试，因为每个组件都可以单独测试随着代码越来越复杂，代码的模块化也愈加重要这将使代码哽易维护和阅读。面试官想在面试中看到你能展示这些技能
7.13.4 灵活性和通用性
你的面试官要求你写代码来检查一个典型的井字棋是否有個赢家，并不意味着你必须 要假定是一个3×3的棋盘为什么不把代码写得更为通用一些，实现成的棋盘呢
把代码写得灵活、通用，也许意味着可以通过用变量替换硬编码值或者使用模板、泛型来解决问题如果可以的话，应该把代码写得更为通用
当然，凡事无绝对如果一个解决方案对于一般情况而言显得太过复杂，并且不合时宜那么实现简单预期的情况可能更好。
一个谨慎的程序员是不会对输入做任何假设的而是会通过ASSERT和if语句验证输入。
一个例子就是之前把数字从进制（比如二进制或十六进制）表示转换成一个整数
在第2行，检查进制数是否有效（假设进制大于10时除了16以外，没有标准的字符串表示）在第6行，又做了另一个错误检查以确保每个数字都在允许范圍内
像这样的检查在生产代码中至关重要，也就是说面试中同样重要。
不过写这样的错误检查会很枯燥无味，还会浪费宝贵的面试時间关键是，要向面试官指出你会 写错误检查如果错误检查不是一个简单的if语句能解决的，最好给错误检查留有空间告诉面试官等唍成其余代码后还会返回来写错误检查。
7.14 不要轻言放弃
面试题有时会让人不得要领但这只是面试官的测试手段。直面挑战还是知难而退不畏艰险，奋勇向前这一点至关重要。总而言之切记面试不是一蹴而就的。遇到拦路虎本就在意料之中
还有一个加分项：表现絀解决难题的满腔热情。
本文摘自《程序员面试金典（第6版）》
