当我在热门大型科技公司询问为何算法题是必考环节时，最常见的回答大概是：“我们的规模太大了，万一有人不小心写出个O(n²)的算法导致网站瘫痪，这代价我们可承担不起。”1 有趣的是，尽管我在工作中为公司创造的价值里，有相当一部分正是解决了电话面试级别的算法问题，但我自己却通不过算法面试！说这话时，人们往往以为我是指自己有一半面试都挂了——其实远不止一半。

我曾写过一篇关于面试经历的博客草稿，试读的读者们却评价它过于无聊且重复，因为我挂掉的面试实在太多。他们建议我把失败经历整理成表格，毕竟没人愿意读一篇上万字、通篇都是失败案例的博客（这建议很中肯；我正在制作带表格的版本）。我大概参加过四十来场“正经”的软件面试，通过的也就一两场（严格来说可能为零）2。

下面举几个例子，让大家明白我所说的“电话面试级别的算法问题”具体指什么。

在我曾任职的一家大公司里，有个团队为内部需求编写了一个核心库，实现了可调整大小的数组。每当数组扩容超出底层存储时，该实现会固定增加若干元素，然后将旧数组复制到新分配的稍大数组中。这是教科书式的反面案例——因为这种扩容方式会导致线性时间开销，而非均摊常数时间的扩容。这个例子经典到常被用作演示均摊分析的标准案例。

对于不熟悉大厂电话面试流程的朋友，我经历过的典型电话面试通常包括：

  • 一道“简单”的编程/算法题，前面可能配一道“非常简单的”热身题
  • 一连串“非常简单的”编程/算法题
  • 一堆冷知识（通用型岗位少见，但底层或性能相关岗位并不罕见）

这个数组实现问题被认为非常简单，属于“极简单”类别，要么是“真正”电话面试题的热身，要么与一堆同样简单的问题打包在一起。然而，这个可调整大小的数组在公司所有JVM代码中造成了大约1%的GC压力（它是所有代码中第二大分配来源），同时还消耗了相当一部分CPU。幸运的是，这个可调整大小的数组实现并未作为通用可调整大小数组使用，而是仅由一个半专用包装器实例化，这才使得它“仅”占公司所有GC压力的1%。如果作为面试题提出，团队中绝大多数成员极有可能在面试中正确实现它。我修复这个问题为公司带来的年收入超过了我一生的总收入。

那是第二大分配来源，而第一大分配来源是在同一个核心库中将一对long值转换为字节数组。这似乎是因为有人编写或复制粘贴了一个以字节数组为输入的哈希函数，然后将其修改为接受两个输入，即取两个字节数组并按顺序操作，导致哈希函数接口变为(byte[], byte[])。为了在两个长整型上调用此函数，他们使用了一个广泛使用的实用库中的便捷long转byte[]转换函数。该函数除了分配一个byte[]并将长整型塞入其中外，还会反转长整型的字节序（该函数似乎旨在将long值转换为网络字节序）。

不幸的是，切换到更合适的哈希函数将是一个重大变更，因此我的修复方案是将哈希函数接口改为接受一对长整型而非一对字节数组，并让哈希函数自行处理字节序反转，而不是将其作为独立步骤（由于哈希函数已经在打乱字节顺序，这并未增加额外工作）。消除这些不必要的分配为公司带来的年收入超过了我一生的总收入。

寻找常数因子加速在技术上并非算法问题，但你在算法面试中也会遇到。作为算法问题的后续，我经常被问到“你能让它更快吗？”答案通常涉及进行简单的优化，从而带来常数因子的改进。

我在面试中被问过两次的一个具体例子是：你原本用整数存储ID，但问题中已经暗示这些ID是密集排列的，因此可以用位域来存储它们。位域面试题与现实世界中冗余数组的区别在于：现实中的现有解决方案与预期答案相差甚远，以至于你大概率不会被要求寻找常数级别的速度优化——更可能的情况是，你在面试中就已经被淘汰了。

再举另一个公司的例子：Bing使用的搜索索引BitFunnel的配置3，是另一个面试级别的算法问题。要完整描述解决方案所需的上下文对这篇博文来说略显冗长，但核心是：需要配置一组布隆过滤器。据我所知，当时采用的方法之一是编写一个黑盒优化函数，通过梯度下降寻找最优解。据说这种方法总会产生一些奇怪的特征，最终输出的配置必然存在非理想特性，只能通过降低底层布隆过滤器的密度来规避——也就是用更多资源（以及金钱）来解决问题。

要设计更优化的方案，可以观察到BitFunnel的基本操作等价于概率相乘。因此对于任何特定配置，只需将若干概率相乘就能预判其性能表现。由于配置空间并不算大，你可以将其嵌入几个for循环中，遍历所有可能的配置空间，然后筛选出最优配置组合。这种方案并不完全准确，因为概率相乘隐含的独立性假设在现实中并不成立，但它之所以能奏效，原理与朴素贝叶斯垃圾邮件过滤刚推出时的成功类似——尽管该算法错误假设邮件中任意两个词的出现概率相互独立。若需要完整解决方案，可以推导出非独立情况下的细节，不过这大概超出了面试的考察范围。

以上只是我临时想到的三个例子。我经常遇到这类问题，能随口说出几十个案例，如果静下心来逐一列举参与过的项目，或许能超过一百个；若算上我知道但由他人（或无人）处理过的案例，肯定超过一百个。无论是本文已提及还是未提及的例子，都具有以下共同特征：

  • 这个例子可以设计成一道面试题。
  • 如果作为面试题，可以预期相关团队中绝大多数（甚至所有人）都能在面试时间内给出正确答案。
  • 修复这个例子所节省的成本，每年都超过我至今一生的总收入。
  • 这个例子存在的时间之久，足以合理推断若非如此，它根本不会被发现。

在这篇文章的开头，我们提到大型科技公司的人常声称必须进行算法面试，因为规模化的低效代价太高。而我的经验是，在我工作过的每一家进行算法面试的公司，这类例子都数不胜数。试图通过在面试中问算法题，来让员工在工作中解决算法问题，这行不通。

原因之一是，尽管大公司努力确保招聘的人能解算法谜题，但它们同时也激励许多（甚至大多数）开发者避免运用这类思维去创造价值。

针对上述例子的三种解决方案中，两种已投入生产，一种尚未实施。这大致是我随机找一个团队提交代码修改（diff）后，若不持续跟进（相比那些我有理由相信会接受的团队、主动求助的团队，或我不断催促直到修复被采纳的团队）的正常成功率。

如果你非常 cynical，甚至可以认为这个成功率已经高得令人意外。当我随机找一个团队时，效率几乎肯定既不在该团队的目标中，也不在其所在组织的目标里。公司很可能花了不少精力激励团队达成目标——否则设定目标有何意义？接受我的代码修改，意味着他们需要测试、集成、部署变更，并承担风险（因为任何部署都有非零风险）。基本上，我是要求团队付出一些努力、承担一些风险，去做一件对他们毫无价值的事。尽管激励机制存在，人们通常还是会接受修改，但他们不太可能主动花自己的空闲时间寻找效率改进（而他们的正常工作时间会用于与团队目标一致的事情）4。

假设有家公司，它不要求开发者必须通过算法测试，但会激励他们使用相对高效的算法。我认为上面三个例子中，没有一个能在未被发现的情况下存活多年，也不可能长期得不到修复。如果某个开发者在一家鼓励代码性能分析的公司工作，他很可能会查看公司计算量最大的库中性能分析里最耗时的部分。这两个例子的“诀窍”并非什么算法魔法，而只是全面审视问题——这正是激励机制可以解决的问题。第三个例子则不那么必然，因为没有标准工具会提示你去关注这个问题。而且人们很容易试图将结果包装成某种魔法——这个例子曾作为核心内容，帮助一篇论文在其领域（信息检索）的顶级会议上获得“最佳论文奖”，但现实是，这个“诀窍”只是应用了高中数学知识，这意味着真正的诀窍是有足够的时间去审视那些可能应用高中数学的地方，从而找到它。

我实际上在一家采用“面试不问算法题，但激励对公司整体有利的行为”策略的公司工作过。在那期间，我只发现了一个几乎符合上述例子标准的修复（如果公司规模更大，它就会满足所有标准，但由于公司规模限制，效率提升带来的价值远小于大公司——虽然当时比我个人收入高得多，但年回报仍低于我至今的终身总收入）。

我认为我只发现一个接近的例子，主要原因是有足够多的人把让公司变得更好视为自己的职责，因此那些直接的高价值修复往往不存在，因为系统通常从一开始就被设计得不容易发现改进点。在少数例外情况下，由于有足够多的人试图为公司做正确的事（而不是被迫遵守与公司整体利益相悖的局部激励），很可能在我遇到问题之前，别人就已经把它修复了。

那家公司面试中的算法/编程部分（初筛加现场面试）比主流科技公司的电话面试还要简单，而且我们基本上不进行系统设计面试。

有一段时间，我们尝试过一道算法类的现场面试题，难度偏难，但仍在大型公司电话面试中可能出现的正常范围内（不过比你在现场面试中预期的要简单一些）。我们后来不再问这道题，因为每一位我们面试的应届毕业生都没能答出来（我们不会给有经验的候选人这种问题）。我们的声望不足以吸引那些能轻松回答这类问题的候选人，因此，如果沿用其他公司都在用的时髦招聘筛选标准，我们根本招不到人。在当今关于面试的讨论中，我们的做法常被称为“降低门槛”，但我不明白，当候选人被聘用的工作几乎（甚至完全）不涉及“跨栏”时，我们为什么要在意他们能跨过多高的栏。而且，在确实需要他们跨栏的情况下，那些栏可能只有两英寸高，轻松就能迈过去。

以实际生产力来衡量，那是我工作过的最具生产力的公司。我认为原因在于文化，过于复杂，无法在这篇文章中完全探讨，但我认为，我们没有用算法测试来筛掉完全合格的候选人，而是假设如果公司文化鼓励人们做正确的事而非只关注局部目标，员工可以在工作中学会这些技能，这起到了帮助作用。

如果其他公司希望员工在工作中解决面试级别的算法问题，或许可以尝试激励员工解决算法问题（在相关情况下）。这可以作为筛选的补充，甚至替代那些要求候选人在白板上写算法题的筛选方式。

附录：我们是如何走到这一步的？

很久以前，面试中常包含“冷知识”问题。现代版本可能如下所示：

  • 什么是MSI？MESI？MOESI？MESIF？MESIF相比MOESI有什么优势？
  • 在析构函数中抛出异常会发生什么？如果是C++11呢？如果顶层析构函数调用的子对象析构函数抛出异常，哪些其他子对象的析构函数会执行？如果在栈展开过程中抛出异常呢？在什么情况下这不会导致std::terminate被调用？

我在上学时就听说过这种做法，甚至在一些“老派”公司里见过。那会儿微软还是业界老大，想复制成功公司的人都会模仿微软。当时最受欢迎的编程博主乔尔·斯波尔斯基（Joel Spolsky）告诉人们，必须采用某种软件实践X，因为微软正在这么做，不学就没法竞争。例如，在那个时代最有影响力的编程博文中，乔尔·斯波尔斯基推崇他所谓的“乔尔测试”，部分理由就是你必须做这些事才能跟上微软这样的公司：

12分是完美，11分可以接受，但10分或更低就有大问题。事实上，大多数软件组织的得分只有2或3分，它们需要严重的帮助，因为像微软这样的公司常年保持12分。

当时流行一种说法：微软会问类似下面的问题（我2001年左右面试微软时，确实被问到了其中一个脑筋急转弯，而算法或编程题一个都没有）：

  • 如果你只有半英寸高，怎么从搅拌机里逃出来？
  • 为什么井盖是圆的？
  • 一个没有窗户的房间里有三盏灯，每盏灯由房间外的开关控制。你在房间外，只能进房间一次。你怎么确定哪个开关控制哪盏灯？

由于我面试时正好赶上这种转变期，被问了不少 trivia 题和脑筋急转弯（包括上面所有那些）。其他一些当时流行、严格来说不算脑筋急转弯的问题，是费米问题。另一个趋势是行为面试，我面试过的几家公司完全采用行为面试，没有任何技术面试。

总之，那时人们需要为模仿微软的面试风格找个理由。当我问别人为什么觉得脑筋急转弯或费米问题好时，他们通常给出的方便理由是：这能看出候选人是否真的会思考，不像那些愚蠢的 trivia 题，只能看出你记住了多少琐事。我们真正需要招聘的是能真正思考的候选人！

回头看，人们现在意识到这并不有效，盲目照搬微软的每个决定并不会让你像微软一样成功，因为微软的成功归结于几个关键因素加上网络效应。所以，模仿他们的面试方式不可能让你变成微软。相反，它只会让你变成一家面试风格像微软、却无法利用微软所利用的网络效应的公司。

对于面试者来说，过去那些脑筋急转弯题目的流程，和现在算法题的流程基本一样——区别只在于，面试前你复习的是《如何移动富士山》而不是《破解编程面试》，为的是积累一堆工作中永远用不上的脑筋急转弯知识，而不是一堆工作中永远用不上的算法知识。

那时候，面试官会专门从《如何移动富士山》这类面试准备书里学题目，然后问给那些从《如何移动富士山》这类书里背过答案的候选人。我和比我小十岁的人聊起这个，他们都觉得这很荒谬——那些题目显然跟工作毫无关系，能否答好更多取决于有没有做过面试准备，而不是工作能力。Hillel Wayne 讨论过如今人们如何设计面试题（我也在几家不同公司亲眼见过），除了那些考察特定专业知识的团队，如今的情况似乎也没什么本质区别。

到现在，我们已经经历了数十年编程面试的流行风潮，每一波事后看来都显得荒唐可笑。要么我们终于找到了有效面试的真正秘诀，并且克服了那些曾让前人不断采用明显荒谬的跟风面试技巧的障碍；要么我们正身处另一波风潮之中，而这波风潮在十年或二十年后的人看来同样可笑。

在不了解面试有效性的前提下，从元层面来看——既然人们获取面试技巧的方式依然如故（从最顶尖的公司那里照搬高级技巧）——如果这还不是跟风，那才真叫奇怪。如果人们正在参考或引用实证研究，或者独立发现了有效的方法，那我倒不会这么惊讶于当前技巧并非跟风。

受 Wesley Aptekar-Cassels 一条评论的启发，上次我找工作时，问了一些人他们如何检验面试流程的有效性，以及如何减少流程中的偏见。我得到的回答（按相似度归类，频率从高到低）如下：

  • 啊？我们不干这个，或者说，我们为什么要干这个？
  • 我们其实不太清楚自己的流程是否有效
  • 我/我们就是知道它有效
  • 我/我们没有偏见
  • 如果存在偏见，我/我们会注意到，但事实上没有
  • 有人研究过或做过调查，但跟我说这事的人，从来没人能说清楚是怎么研究的，或者调查方法是什么

附录：培训

与大多数现实世界的问题一样，当试图弄清楚为什么每年有七位数、八位数甚至九位数级别的面试级算法漏洞等待修复时，你无法指出单一的“根本原因”。相反，存在一种类似刺猬防御的激励错位机制。另一部分原因在于，培训被严重低估了。

我们讨论过，在我工作过的所有公司中，除了一家之外，都存在这样的激励体系：即使简单计算就能发现数千万甚至数亿美元的浪费可以轻松修复，开发者也会觉得不应该花时间关注效率提升。而由于这不受激励，开发者往往缺乏此类经验，导致不熟悉，进而觉得比实际更难。因此，即使一天的工作能带来每年100万美元的节省或利润（据我经验，在大公司相当常见），人们也意识不到这只需一天工作，且只需对开发速度做出很小妥协就能完成。解决后一个问题的方法之一是培训，但获得认可甚至比不在目标范围内的效率提升更难！

举个例子，我曾写过一篇中等长度的教程（4500字，按字数算比本文短，但加上图片可能更长），内容涉及如何发现各种低效问题（如何使用分配或CPU时间分析器，如何针对我们使用的GC进行特定服务的GC调优，如何使用我构建的自动发现JVM或容器配置低效的工具等，基本上都是简单且影响大、易于编写操作手册的内容；如果你在Twitter，可以在http://go/easy-perf阅读）。有几位之前会找我帮忙的人告诉我，他们能自己调试并修复问题；我还间接听说，另外几位我不认识的人也能独立提高服务效率。我估计自己只听到了不到10%的案例，因此我猜测这帮助了数十名工程师，可能还更多。

如果我花一周时间做“正经”工作而非写教程，我就能拿出具体、可量化价值的东西，轻松放进宣传材料或绩效评估里。但结果我却搞出了这么个虚无缥缈的东西，顶多算点“额外加分”。我并非在抱怨这件事——这完全是我预料之中的结果。但平均而言，公司只会得到它们激励出来的东西。如果公司指望由开发者来提供培训（而不是雇佣专门制作培训材料的人，而这类岗位的经费往往远低于工程岗位），却又不像重视开发工作那样重视培训，那么培训资源短缺就是必然的。

我相信你也能从公共教育材料中看到培训激励不足的现象，这源于教育和培训变现的相对难度。如果你想靠讲解知识赚钱，有几种方法似乎效果不错。如果内容能直接体现明显价值，那么定价“非常高”（短课程收费数百或数千美元）的视频课程似乎可行。企业培训也相当有效——公司花钱请你到现场给30人讲课，你按每人3000美元收费。

如果你想触达（并可能帮助）大量人群，把文字放到网上免费提供效果很好，但变现效果很差。对于技术类话题，我不确定非广告拦截用户群体是否足够庞大到能靠广告变现（而非设置付费墙）。

举个例子，Julia Evans 可以靠她的杂志收入养活自己，据她说过去两年每年收入约10万美元。而企业培训领域做得非常好的人，靠一两天培训课程就能赚到这么多；从我听说的企业演讲费率来看，一些高薪技术演讲者接两次活就能赚到同样数目。这些收入远高于平均水平，尤其是演讲收入，但既然我们在和Julia Evans比较，我认为用高于平均水平的费率来对比并不算不公平。

附录：激励错位的刺猬防御，第三部分

在上述三个例子中，有一个团队的情况是：对我而言，做任何对公司真正有价值的事都毫无收益；而另外两个团队则相反，无论做什么，只要对公司有利，对我个人也有好处。根据我的经验，这在大型公司的团队中非常罕见，但即便在那个团队里，激励机制的匹配度依然相当糟糕。有一次，在获得晋升和加薪后，我计算了自己所做的改动为公司带来的收益与个人加薪的比例，结果发现我的加薪仅占我为公司创造收益的0.03%——这还只计算了那些易于量化且对利润有绝对影响的贡献。我的大部分工作都与工具开发相关，其价值难以量化，但我怀疑实际价值可能远超可量化的部分，因此我实际获得的收益可能不到我所创造边际价值的0.01%。这实际上还高估了我工作的激励程度——从边际角度看，我强烈怀疑自己做的任何事对我个人而言都毫无价值。当年度收益达到1000万或2000万美元后，绩效评估、晋升、加薪等方面基本没有差别。由于努力工作没有额外收益，反而存在风险（可能卷入政治斗争、导致网站宕机等），对我来说，完成“足够”工作量后再多做的边际回报很可能是负值。

有些公司会定期发放高额特别奖金，但我所在的公司并非如此。因此，一旦员工在绩效评估中获得了最高评级，公司就再无任何手段表明它重视额外的工作。从机制设计的角度看，公司实际上是在要求员工在完成“足够”工作量后停止工作。

因此，即便在这个与公司成功相对契合的团队中（相比大多数团队而言），公司的薪酬体系也为团队所能达到的契合度设定了上限。

这种情况还以另一种方式体现。与许多公司常见的情况一样，管理者的加薪预算主要取决于团队人数，然后以零和博弈的方式分配给团队成员。不幸的是，对每个团队成员而言（至少在薪酬方面），团队里几乎全是高效工程师，这意味着在零和加薪游戏中，没有人能获得特别好的结果。团队的人员流动率很低，因为员工喜欢与优秀的同事共事，但公司却在动用其最大的杠杆之一——薪酬——试图促使员工离开团队，加入效率较低的团队。

由于这种设置非常普遍，我听说多家公司的管理者试图留住那些无害但效率低下的员工，以应对这一问题。如果你抽象地问一个人，公司是否想雇佣和留住低效的人，我猜他们会回答“不”。但就公司可以被认为想要什么而言，它想要的是它所激励的东西。

相关链接

感谢 Leah Hanson、Heath Borders、Lifan Zeng、Justin Findlay、Kevin Burke、@chordowl、Peter Alexander、Niels Olson、Kris Shamloo、Chip Thien、Yuri Vishnevsky 和 Solomon Boulos 提供的评论、修正和讨论。

  1. 首先，大多数模仿谷歌面试流程的公司并没有那么大的规模。但即使对于有规模的公司来说，大多数人的工作并不涉及设计高难度的算法（也许在 2003 年左右的谷歌是这样，但根据我在三家大型科技公司的观察，大多数人的工作对算法的要求相当低）。[返回]
  2. “真正”一词加了引号，因为我曾多次因面试流程之外的原因通过面试。也许我有非常强的内部推荐，足以覆盖我的面试表现；也许有人读过我的博客，根据我的写作认为我能胜任合理的工作；也许有人通过前同事得到了我的背景推荐；或者有人读过我的一些开源代码，并以此而非白板编程题来评判我（据我所知，最后这种情况只发生过一两次）。在我明显未能通过技术面试却仍获得工作邀请的情况下，我通常会询问原因，因此我收集了这些来自他人的理由。

可以说为零的原因是，唯一一次我毫无准备地参加“真正”的软件面试是在谷歌，但那只是因为分配给我的面试官搞错了方向——我面试的是硬件岗位，却被软件团队的人面试，所以我经历的基本上是标准的软件面试，只不过其中一位面试官问了我一些关于状态机和缓存一致性的问题（大概是这类）。当他们意识到搞错了方向后，我又接受了一次硬件工程师的电话面试，以确保我不是在2005年至2013年期间在一家硬件初创公司工作时完全在装样子。有可能我软件部分面试没通过，基本上是靠后续的电话筛选才被录用的。

请注意，这仅指软件方面——实际上我在硬件面试中表现相当不错。到了现在，我对硬件已经很生疏了，可能需要在真正的硬件岗位上花不少时间重新上手，但面试对我来说是小菜一碟。一个很了解我的人认为，这是因为“我说话像个硬件工程师”，既会说一些让硬件人员觉得我很专业的话，也会说一些在大多数程序员听来极其愚蠢的话，这更多是关乎行话而非实际知识或技能。

[返回] 3. 这个问题在电话筛选中比你想的要难一些，但在现场面试中并不算过分（尽管我有个朋友曾在谷歌的电话面试中遇到过谷歌Code Jam世界总决赛的问题，所以根据你遇到的面试官，你可能会遇到同样难或更难的问题）。

顺便提一下，如果你好奇我朋友当时遇到那个问题是怎么处理的——其实他们恰好知道答案，因为之前在 Google Code Jam 中见过并尝试过这道题。虽然当时没做对，但后来为了好玩自己琢磨出来了。不过，我朋友认为把这道题作为电话面试题不太合理，于是请求面试官换一道题。面试官拒绝了，结果我朋友就没通过电话面试。当时，我怀疑全世界能在电话面试中答对这道题的人不超过几百个，而这些人中绝大多数大概都会意识到这是个荒谬的面试题。面试失败后，我朋友找了将近六个月的工作，才终于通过了一家初创公司的面试，并在那里构建了多个核心系统（无论是从业务影响还是工程难度来看）。那家公司后来以百亿美元级别上市，我朋友至今仍在职——公司明白要替换这个人有多难，因此对他非常优待。而其他面试过他的公司，甚至没有一家愿意录用他，他当时找工作确实很艰难。

[返回] 4. 除了那些会导致服务崩溃的严重架构问题外，我观察到团队解决效率问题最常见的方式就是申请更多容量。有些公司会尝试用某种方式制衡这种情况（例如，我听说在 Facebook，许多负责效率改进的团队隶属于容量部门，这样如果发现某个团队存在极端低效且拒绝改进的情况，他们就有权阻止容量申请），但我个人没有在能有效解决这个问题的环境中工作过。谷歌曾有一个旨在解决此问题的系统，其中一项措施是将人员编制与计算资源视为可互换的，但我听说后来因为某些原因又回退到了更传统的系统。[返回]