这篇文章原文首发于我的Techie面经文章 : 资深面试官眼中的编程算法面试, 纯手打原创, 分享到论坛中和大家一起交流讨论。如果感兴趣其他软件工程师，数据科学面经文章，也可以浏览Techie面经题解系列文章 ，也欢迎大家加入Techie的免费会员 ，获取更多面经干货文章。
如果你希望得到一对一的算法编程面试备考辅导，或者在面经题准备过程中有任何需要解答的知识问题，欢迎报名参加Techie备受好评的软件工程师模拟面试服务 。我会根据目标公司的出题特点和要求，为同学做针对性的算法编程辅导。如果你在编程算法面试备考过程中有任何问题，也欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信, 期待和大家的沟通！
编程算法（Coding interview）一直是科技公司岗位面试的必考项目。我（史强Gabriel）在一线大厂当backend software engineer多年，以面试官的身份参加过近百场coding面试，也辅导过上千名同学准备软件工程师岗位（Software Engineer）和数据工程岗位（Data Engineer, Machine Learning Engineer）面试。在这个过程当中，我看到许多同学对所涉及到的主题和如何被评价不甚清晰。今天，我们会从coding面试所涉及的常见主题、考察形式和评价方式这几个方面来和大家分享，希望能对正在求职备考的朋友们有所帮助。
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
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
本题中，我们有一个包含n个整数的数组，要求找出最长的严格递增子序列的长度。如果我们一个一个元素地去构造这个最长子序列，那么对于原数组当中的每一个元素，我们都有两种选择：
- 把它包含在我们的最终序列中
- 把它从我们的结果中删掉
由于我们构造出来的序列是递增的，因此我们只要记录之前选好的最后一个元素就好了：我们要选的新的元素一定是要比这个元素大的。
据此，我们可以设计如下的递归关系：
假设输入数组用input来表示，n为其长度，i和j为数组下标，LIS(i, j)表示从子数组input[j…n-1]（从j到n-1）中找到的最长严格递增子序列长度，并且该序列第一个元素 > input[i]。
由此我们可以列出以下三种情况：
从上面的代码我们可以看出，其时间复杂度为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++来写一个方法来返回一个字符串当中指定位置的字符，那么可能很多同学会写成：
查看这里原文中的API design程序
注意看这个返回值类型，如果我们传进来的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. 评价
最后我结合自己近十年来在硅谷一线公司做面试官的经验，和大家介绍一下科技公司对编程面试的评价体系。一般来说，面试的评价会从三个大方面进行：设计、实现、交流。
- 设计… 查看这里原文中的算法面试评价细则
以上就是我为同学们总结的算法编程面试的常见考点和注意事项，未来我在Techie还会继续给大家总结更多软件工程面试的知识总结干货文章，欢迎大家加入Techie免费会员，关注我们的内容更新。 也非常欢迎感兴趣的同学报名参加Techie备受好评的软件工程师模拟面试服务 ，我会结合目标公司的出题特点和要求，为同学做针对性的算法编程一对一辅导。 如果你在编程算法面试备考过程中有任何问题，也欢迎扫描下方的二维码或者搜索 TonyCoding20 添加Techie教师团队微信，期待和大家的沟通！