资深面试官眼中的编程算法面试

编程算法（Coding interview）一直是科技公司岗位面试的必考项目。我（史强）在一线大厂当backend software engineer多年，以面试官的身份参加过近百场coding面试，也辅导过上千名同学准备软件工程师岗位（Software Engineer）和数据工程岗位（Data Engineer, Machine Learning Engineer）面试。在这个过程当中，我看到许多同学对所涉及到的主题和如何被评价不甚清晰。今天，我们会从coding面试所涉及的常见主题、考察形式和评价方式这几个方面来和大家分享，希望能对正在求职备考的朋友们有所帮助。我在Youtube Channel "Techie科技求职" 里也会持续发布编程算法题精讲视频，欢迎大家关注！

​​如果你希望系统提升编程算法知识和解题能力，或者在参加software engineer岗位面试之前得到个性化专业辅导，欢迎报名参加Techie备受好评的编程算法集训营课程。我会用58+课时的时间，结合120多道算法编程面试真题，为大家总结27类常考面试题型和变种题解法，以最高效的方式为大家搭建完整的算法编程知识体系，提高备考效率。如果你在编程算法面试备考过程中有任何问题，也欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信, 期待和大家的沟通！

1. 主题

我总结coding面试的主题整体分为以下三大类：

• 数据结构
• 算法
• API设计

下面我们结合具体的算法面试例题细致讨论一下这些内容。

1.1. 数据结构

数据结构简单来说就是找一种组织数据的方式使得我们想要的操作能在要求的复杂度内完成。一般来说，考察的重点基本集中在以下五类：

• array
• linked list
• map/set (hashtable based or tree based)
• tree
• graph

在面试中，求职者需要有能力结合问题本身的特点，选择合适的数据结构去解决具体应用问题。下面我们通过设计一个“贪吃蛇游戏”来展示数据结构在具体问题中的应用：

“通过代码来实现贪吃蛇，使得我们可以将其往4个方向移动一步并且我们能够判定现在蛇头是否已经撞到地图边界又或者是自己身体。“

假设蛇是在一个二维地图上移动，那么最直接的representation无疑是 a list of xy 坐标对。这种方式对于我们想要的两种操作也是支持的（假设蛇的身体由n个坐标对组成）：

• 我们可以计算出所有原来的坐标对在移动下的新位置。这个操作是O(n)的。
• 对于新的蛇头位置，我们可以直接做线性查找看看蛇身体中是否已经有一样的坐标对。这个操作也是O(n)的。  

在这个基础上，如果进一步观察，你们就会发现蛇在移动过后只有头部和尾部的位置发生了变化。这种只有在一头一尾上进行变化的操作应该很容易让我们联想到一个支持在O(1)时间复杂度内完成这样操作的线性结构：queue。对于第二个操作，如果我们稍微抽象一下，本质上其实我们想要做这样一件事情：在一个集合中找一个元素（坐标对）是否存在。根据这个操作语义，我们可以联想到要使用hashset来作为这个集合。这样做我们操作的复杂度就会变成O(1)的。总的来说，如果我们同时使用hashset和queue来表示蛇的身体的话，我们两个需要的操作都能达到O(1)的时间复杂度。

通过这个例子我们可以看到，在实际问题中，我们对数据结构的选择不是凭空得到的，而是先分析得到所需操作的语义，然后再用这个语义与我们toolbox中的数据结构所支持的特定操作特点进行match，最终确定解决方案。当然，很多时候我们没有办法找到一个已知的结构去支持所有我们想要的操作，对于这种情况，我们就可以设计一个新的由已知结构进行复合的新结构来满足我们自己的要求，也就是我们在这道贪食蛇题目中的做法。

1.2. 算法

一般来说，编程面试中算法部分的常见考法是：选用常见的algorithm design模式来解决一个问题，这些模式包括：divide and conquer，backtracking，dynamic programming等等。另外一种考法是：修改一些经典的algorithm，比如binary search，Breadth/best/depth first search on graph等，来适配并解决一个问题。

对于第一类考察，一个非常重要的计算思想是recursion(递归)。我们建议求职者一定要把这个思想掌握好，因为许多实际的算法设计(e.g., backtracking)模式都是递归的具体表现形式。动态规划是很多人都觉得的一个痛点，其表现出来的，就是遇到一个新的问题不会找出正确的状态转移关系(e.g., 要设计哪些状态，当前状态是从哪些之前的状态转移过来的等等)。如果递归掌握得好，大家就会发现dynamic programming无非就是没有重复运算的recursion。我们下面用一个例子来阐述recursion和dynamic programming之间的关系：

[Leetcode 300] Longest increasing subsequence 

本题中，我们有一个包含n个整数的数组，要求找出最长的严格递增子序列的长度。如果我们一个一个元素地去构造这个最长子序列，那么对于原数组当中的每一个元素，我们都有两种选择：

• 把它包含在我们的最终序列中
• 把它从我们的结果中删掉

由于我们构造出来的序列是递增的，因此我们只要记录之前选好的最后一个元素就好了：我们要选的新的元素一定是要比这个元素大的。

据此，我们可以设计如下的递归关系： 

假设输入数组用input来表示，n为其长度，i和j为数组下标，LIS(i, j)表示从子数组input[j..n-1]（从j到n-1）中找到的最长严格递增子序列长度，并且该序列第一个元素 > input[i]。

由此我们可以列出以下三种情况： 

Case 1: j >= n 这个表示我们现在处理的是空数组

Case 2: input[i] >= input[j] 这个表示j这个位置的字符不能被选到要构造的序列当中。 

Case 3: input[i] < input[j] 这里表示j这个位置的字符可以被选到要构造的序列当中。

有了这个，我们很容易就得到对应的code（recursion的代码实现一般都可以直接照搬我们的状态函数定义）：

这里的递归算法设计方法属于backtracking，因为我们这个有这个依次做决策这么一个过程。和我们这里这个过程非常相似的有找子集 [Leetcode 78] 以及找子集和 [Leetcode 416]。

这个算法我们不难看出，其时间复杂度为O(2^n)。这个原因在于我们在递归展开的过程当中有着大量的重复运算。如果我们观察一下这个递归现在的状态表示形式，我们可以看到其实我们只有O(n^2)个不同的状态。同时，我们现在状态是二维的，如果我们所有状态画在一个二维表格当中，我们可以发现，要计算(i, j)这个格子，我们要知道其右边的格子(i, j + 1)和其右下方的格子(j, j + 1)的结果。据此，如果我们从右往左，从下往上来依次对这个表格当中的格子进行计算，我们每一个状态就只会运算一次，从而达到我们想要的O(n^2)的时间复杂度。以下是实现代码：

对于第二类考察，即通过修改一些经典的algorithm来适配并解决一个问题，同学们要对经典算法的应用场景和特点熟悉在心。譬如，binary search应用的前提是我们的搜索空间具有某种单调性。举个例子，[Leetcode 278] First Bad Version，我们需要找出第一个不好的软件版本。在这个版本空间中，根据题目描述，我们可以知道有一条清晰的分割线将所有号的版本号和不好的版本号分割开来。基于这个前提，我们的搜索可以使用binary search来加速。

1.3. API设计

大多数情况下，公司不会专门地设置一轮面试来考察API设计。在一些带设计元素的问题（譬如像之前提到的贪吃蛇）里，如果面试官没有给出基本的代码框架，那么表示他们想要看到面试者能不能够自己抽象并定义合适的接口。举个例子，假设我现在要用C++来写一个方法来返回一个字符串当中指定位置的字符，那么可能很多同学会写成：

注意看这个返回值类型，如果我们传进来的index不是一个有效的在字符串当中实际存在的位置，那么我们应该返回什么值比较合适呢？考虑到这种情况，我们需要一个能够optionally返回字符的数据类型。在C++当中，我们一种方式是用char *来作为返回值。因为是指针，所以当我们无法返回字符的时候，我们可以通过返回空指针来表示这种情况。

上面的这个例子虽然简单，但是我认为基本上反映了面试官想要看到的：能够根据需求来合理设计出具有良好语义的接口。进一步，如果面试官来挑战你的设计，你需要能够有根据地证明自己的设计。如果能够给出不同方案的设计并且能清晰地指出他们之间的优缺点，那这个就更好了。很多同学在面试的准备当中会忽略这点，但是这其实正是你们之后工作的时候需要做到的。

2. 形式

前面我们细致介绍了编程面试的三个常见内容主题，下面我们简单梳理一下编程面试的形式：

• 白板. 如果假设是physically面对面试官，同学们有可能在白板上手写代码。这里我建议同学们可以将白板分为两个区域：一块用来正式写code，一块用来画图和分析。这样做的好处是在写code的时候可以容易refer back你之前分析得到的重点，同时这个版面也会相对整洁。
• Online. 如果是virtually面对面试官，同学们基本都是在一线在线coding platform在完成coding。一般这里又可以继续细分： 
  • 平台只提供文本编辑以及语法高亮功能。这里需要同学们对于一些常用的所选语言中的builtin functions有所熟悉。
  • 平台提供测试数据和实际运行代码的能力。这种形式可参考leetcode。
• Pair programming. 这种一般来说相对少见，你和面试官会一起合作完成一个小project。同样的，同学们需要注意做好交流，将问题分析清楚，确认自己和面试官在问题需求上的理解是一致的后再开始具体设计与实现。
• Take home assignments. 这种形式与school project类似，就是同学们在指定时间内完成一个任务。这里同学们要注意自己的代码规范（譬如有对定义的接口有良好的注释，变量命名规范，等等）。

3. 评价

最后我结合自己近十年来在硅谷一线公司做面试官的经验，和大家介绍一下科技公司对编程面试的评价体系。一般来说，面试的评价会从三个大方面进行：设计、实现、交流。

• 设计。对于设计的考察，面试官会看同学们给出的解决方案是否是完备的，有效率的。对于一个问题，除非同学事先见过并且思考过，否则面试官不会期待同学一次性地给出完美的方案。如果同学们能够结合面试官的指引或者通过自己的观察，对自己给出的方案进行多次迭代优化，那么就是非常加分的。要做到好的设计，同学们切记不要过早陷入实现的细节当中去。我认为一个有效地方法是多问自己几个why：为什么我要选择这个数据结构？为什么我的API要写成这样？其他的方案是什么？等等。当你思考这些问题的时候，你很可能会发现你认为的初始实现有着需要改进的地方。另外，对于coding面试，我建议同学们可以在一开始就思考如何测试你的算法。这会强迫你对问题要进行深入地观察，否则，你将不能设计出足够强的测试用例来覆盖可能存在的不同的逻辑情况。在面试当中能给出不同的好的测试用例并能够说明对应设计理由，这也是非常加分的行为。
• 实现。对实现的考察会直接在同学们给出的code里得到体现。这里主要表现为对于所用语言的构造和内置utility是否进行合理使用。譬如，在面向对象的语言中用class来表达一个concept是比较合适的。如果同学没有对于一个指定问题设计实现一个class，那么这就是负面的招聘信号。所以，同学们不能只知道刷算法题，也需要做一些real world projects（有一些实战项目经历就更好了）。
• 交流。对交流的考察主要是看同学们是否能相对清晰地表达所想的算法或者high level设计并且能够在被challenge的时候有力地defend themselves。这就是为什么我们平常在Techie给同学们指定编程面试备考方案时，非常注重大家讲题能力的训练，以及对常见数据结构、算法的深刻理解。对于这部分的训练，贴近实战的模拟面试也是很好的帮自己查漏补缺的方法。

以上就是我为同学们总结的算法编程面试的常见考点和注意事项，未来我在Techie还会继续给大家总结更多软件工程面试的知识总结干货文章，欢迎大家加入Techie免费会员，关注我们的内容更新。同时，也非常欢迎感兴趣的同学报名参加Techie备受好评的编程算法集训营课程，我会用58+课时的时间，结合120多道算法编程面试真题，为大家总结27类常考面试题型和变种题解法，以最高效的方式为大家搭建完整的算法编程知识体系，提高备考效率。如果你在编程算法面试备考过程中有任何问题，也欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信，期待和大家的沟通！