算法面试的理想与现实

2020 年 1 月 17 日 极市平台

加入极市专业CV交流群，与6000+来自腾讯，华为，百度，北大，清华，中科院等名企名校视觉开发者互动交流！更有机会与李开复老师等大牛群内互动！

同时提供每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流。关注 极市平台 公众号，回复 加群，立刻申请入群~

来源：CSDN@微信公众号

作者：Dan Luu

大型科技公司通常都主张必须进行算法面试，因为他们的规模过大，无法承受低效代码带来的巨额成本。但一次的算法面试真的能体现一个人真正的实力吗？

每当我问时尚科技大公司的人，算法测试有什么必要时，通常他们都会说： “我们的系统过于庞大，我们不能允许任何人不小心编写某个 O(n^2) 的算法而导致系统宕机。 ”这句话的可笑之处在于：尽管我为这些公司做出的很大一部分贡献就是解决电话面试级别的算法问题，但我还是没办法通过面试！当我说这话的时候，人们常常以为我的意思是我的面试有一半都失败了。实际上我面试失败次数超过了一半。

当我将自己的面试经历写成文章时，有人认为我的文章太无聊了，因为我的很多面试都失败了。他们认为，我应该将这些失败的经历总结成表格，因为没人愿意读一篇长达一万字的文章，而本章本身只是讲述了一系列的失败经历。我大约经历了40次面试，然而可能只通过了1-2次（甚至可以说是零）。

1

为了说明上述我提到的“电话面试级别的算法问题”，我们先来看几个例子。

我曾在一家大公司任职，公司的某个团队编写了一个核心库，实现了可变数组。在每次调整大小时，如果数组的后备存储溢出，那么这个实现就会添加固定数量的元素，并将旧数组复制到新分配的数组中——仅仅是一个稍大一点的数组。这是实现可变数组的经典反例，因为这样做会导致调整数组大小所需的时间呈线性增长（而不是平摊常数）。这是平摊分析中最常提到的一个经典的例子。

可能有些人不熟悉大型科技公司电话面试的算法问题，我遇到过的问题包括：

一个“简单”的编程/算法问题，也许之前还有一个“非常简单”的热身问题。
一系列“非常容易”的编程/算法问题。
一堆脑筋急转弯问题（对于全面的人才来说这种问题很罕见，但是对于低级或与绩效挂钩的职位来说并不罕见）。

他们认为这类数组的实现是非常简单的问题，因此被划分到了“非常容易”的类别，通常在“真正”的电话面试问题中，这只是一个热身问题，后来还有许多类似的简单问题。然而，可变数组在这家公司的所有JVM代码中，造成了大约1%的垃圾回收压力（所有代码中这个可变数组造成的内存分配占第二位），还造成了不可忽视的CPU占用率。幸运的是，他们没有把这个实现当作通用的可变数组使用，只用于了一个半专用的程序，也因此“仅”造成了所有垃圾回收任务的1%。然而，如果面试的时候被问到这个问题，就让人感觉好像它们绝大多数的团队成员都能够在面试中正确地实现这个功能。我能解决这个问题，而且解决这个问题后为我的老板带来的收益比我这辈子赚得钱都多。

这个问题占用的内存分配排在第二位，而排名第一的是将一对 long 值转化为字节数组，这个实现同样来自同一个核心库。似乎他们编写了这个操作的原因是，有人编写（也许是复制粘贴）了一个哈希函数，其输入为一个字节数组，后来又将这个函数修改成：接受两个字节数组，并依次进行操作，因此这个哈希函数的接口为(byte[], byte[])。为了使用两个 long 调用这个函数，他们使用了工具库中的一个非常便利的转换函数，将 long 转换成 byte[]。这个函数除了分配 byte[] 并将 long 填充到其中外，还可以反转 long 的字节（似乎这个函数本来的用途是将 long 值转换成有序的网络字节。）

不幸的是，想把这样一个函数写得更为合理是一项大工程，因此我的解决办法是将哈希函数的接口变更为接受一对 long（而不是一对字节数组），然后让这个函数执行字节反转，而不是将其作为一个单独的步骤执行（因为这个哈希函数已经打乱了字节的顺序，因此不需要额外的工作）。由于去除了这些不必要的资源分配，我的老板因此而获得收益比我这辈子赚得钱都多。

理论上说，常数级别的提高速度并不是算法问题，但是算法面试中还是会出现这样的问题。作为后续的算法问题，他们经常问我：“你能提高代码的速度吗？”这些问题的答案往往涉及简单的优化，以及性能改善。

举一个例子说明我在面试中遇到的问题：将ID保存成整数，但是根据题目的语境，你知道这个ID是紧密压缩过的值，因此你可以将这些ID保存成比特。比特的面试问题与现实世界中存在大量冗余的数组实现有所不同，因为在现实世界里这个问题的解决方案与预期的答案相距甚远，因此可能不会有人要求你进行常数级别的提高速度。更可能的是，在走到这一步的时候你的面试很可能已经失败了。

下面这个例子来自另一个公司，BitFunnel （Bing中使用的搜索引擎）的配置问题，这是面试级别的算法问题的例子。

我无法在本文中通过寥寥几笔说清楚这个解决方案，简单来说，你需要配置一组布隆过滤器。方法之一是编写一个黑盒优化函数，通过梯度下降来尝试寻找最佳解决方案。据我所知，这种方法总是会产生一些奇怪的特性，而最终的配置也不会太理想，只能通过降低布隆过滤器的紧密程度（即投入更多资源，也就是更多钱）来解决这个问题。

为了创建更好的解决方案，你会发现 BitFunnel 中的基本操作相当于概率相乘，因此，对于任何特定配置，你只需要将多个概率相乘，即可确定该配置的执行方式。由于配置的空间并不是很大，因此只需要用几个for循环，在可能的配置空间中进行迭代，然后挑选出最佳的配置集合。但这也不完全正确，因为概率相乘假设了一种现实中并不成立的独立性，但这种方法似乎效果还不错，就像朴素贝叶斯垃圾邮件过滤器也假设电子邮件中两个单词的出现概率是独立的。如果你想要完整的解决方案，则需要详细算出非独立的概率，尽管这超出了面试的范围。

以上就是我想到的三个例子，每次在总结最常见的十道面试题时，我总是会想到这些问题，如果我坐下来认真写出每个经历过的面试题，那么可能会超过一百个。就我个人知道的其他人经历过的考题，那么肯定不止一百个。无论是本文提到的例子，还是我未能详尽叙述的例子，这些考题都有以下共性：

这些问题都可以表述成面试问题。
如果表述成面试问题，则你必然希望相关团队中的大多数人（或者所有人）都能够在面试要求的时间内给出正确答案。
因解决这些问题而节省的年成本比我这辈子挣的钱都多。
我们可以合理地假设这些问题已经出现很长一段时间了，否则它们就不会作为面试题了。

2

在本文的开头，我曾提到大型科技公司通常都主张必须进行算法面试，因为他们的规模过大，无法承受低效代码带来的巨额成本。根据我的经验，我工作过的每家公司都有这样的算法面试。为了招到有能力的人来解决工作中的算法问题，仅凭面试中的算法考题是行不通的。

原因之一在于，即使大公司的目的是为了设法确保员工能够解决算法难题，那么这种做法也会激励许多甚至大多数开发人员避免将这种能力变成金钱。

上述例子的三个解决方案中，有两个已用于生产，还有一个没有。如果换一个团队，而且我不固执地坚持下去的话（也就是说，并非是下面的情况之一：假设我有理由相信我的团队会接受我的解决方案；或团队需要我站出来提出解决方案；或者我固执地坚持到底，直到他们采用我的解决方案），我的解决方案得到实际应用的概率也就这么多，即三分之二。

你可以执拗地说这个成功率（三分之二）已经很高了。如果我随便加入了一个团队，那么很有可能效率既不是这个团队的目标，也不是这个组织的目标。这个公司可能已经花费了大量的精力来激励团队实现各自的目标（否则制定目标的意义何在？），如果要求他们接受我的解决方案，那么他们需要测试、集成、部署更改，还需要承担部署风险（因为所有部署的风险都不可能为零）。那就等于说，我在要求团队冒风险做一些对他们来说毫无价值的工作。尽管有时人们也会罔顾激励措施，采用不同的解决方案，但他们不太可能花费大量的业余时间来寻求效率的提高，他们会将正常的工作时间花在与团队目标相符的工作上。

假设有一家公司的目标不是为了确保开发人员可以通过算法测验，而是为了激励开发人员使用相对高效的算法。我不认为在这种情形下上述三个问题会被遗留至今，经过了这么多年，还未能得到解决。再假设有一家公司在评测代码时会观察调用频率最高的代码，以寻找计算最繁重的那一部分库。在这两种假设下，“窍门”不涉及任何算法问题，只需要多看就行了，完全可以通过激励措施解决。第三个例子并非不可避免的，因为没有标准的工具可以告诉你问题所在。然而，你也可以将结果归结为某种算法问题，因为这个例子正是了IR领域获得过“最佳论文奖”的某篇论文的核心部分，但实际上这个“技巧”只用到了高中数学，这意味着真正的技巧是，只要有足够的时间，利用高中数学的方法就能解决。

在我工作过的公司中，的确有一家“不会在面试中问算法问题，他们更加重视那些对公司发展有利的方面”。在这家公司工作期间，我发现只有一个解决方案似乎可以满足上述例子（如果这家公司规模更大，则可以满足所有条件，但是由于这家公司的规模有限，所以提高效率并没有那么重要，虽然我付出了很多心血，但为公司带来的年收益并不会超过我这辈子挣的钱）。

我认为，我只找到了这么一个例子的主要原因在于，很多人认为他们的工作就是让公司变得越来越好，所以能够直接带来高价值的解决方案根本不存在，因为系统就是这样设计的，想找到改进的方面并不容易。虽然例外的情况很少，但是确实有人会努力做正确的事情，而不是被迫罔顾公司整体的利益而向眼前的利益屈服，这些人可能会抢在我之前就已经解决掉了这些算法问题。

这家公司的算法/编程部分面试比较容易，比主流技术大公司的电话面试容易多了，而且我们基本上没有进行系统设计面试。

有一阵子，我们尝试了一下现场算法面试，虽然很难，但是在大公司的电话面试中其实很常见。后来我们取消了这些面试题，因为我们面试过的毕业生中，没人能答出这些问题（我们没有给经验丰富的候选人这样的问题）。可能是我们公司的名声不够大，来我们公司面试的人都未能答出这些问题，所以我们根本无法像别家公司那样，通过时髦的方法过滤候选人。在当代关于面试的讨论中，我们的做法通常被称为“降低标准”，但是我想不明白既然我们的工作所需的门槛很低（有时甚至没有）的时候，为什么我们要把门槛设得那么高。而且，在有些情况下，虽然你想设置门槛，但门槛只有2寸高，人家可以轻松地迈过去。

从实际的生产力来看，这家公司是我工作过的公司中生产力最高的一家。我认为，其中的原因是文化上的，而且太复杂，无法在本文中进行全面探讨，但我认为我们的讨论有帮助性，因为我们了解到我们无法通过算法测验筛选出完美的候选人，而且我们假设如果我们的文化是做正确的事，而不是专注于眼前的目标，那么人们就会在工作中承担相应的工作。

如果有些公司希望人们在工作中解决面试级别的算法问题，那么他们可以通过激励措施达成这一目标。为此，我们需要付出额外的努力或想别的办法，而不是仅凭在白板上解决算法问题过滤面试者。

原文： https://danluu.com/algorithms-interviews/

新年假期，极市将为大家分享计算机视觉顶会 ICCV 2019 大会现场报告系列视频，欢迎前往B站【极市平台】观看，春节也学习，极市不断更，快来打卡点赞吧~

https://www.bilibili.com/video/av83388150

-End-

*延伸阅读

CV细分方向交流群

添加极市小助手微信（ID : cv-mart），备注：研究方向-姓名-学校/公司-城市（如：目标检测-小极-北大-深圳），即可申请加入目标检测、目标跟踪、人脸、工业检测、医学影像、三维&SLAM、图像分割等极市技术交流群（已经添加小助手的好友直接私信），更有每月大咖直播分享、真实项目需求对接、干货资讯汇总，行业技术交流，一起来让思想之光照的更远吧~