大家好，我是阿秀。
去年在求职的时候，阿秀大概投递过90多家公司，线上面试了超过40场，最后也顺利拿到了抖音SP的offer，一眨眼都已经工作大半年了。
以前跟大家分享过计算机求职面试过程中需要注意的一些小细节，我把自己在求职面试中的经验汇总成了6000+的心得，详见下文
考虑到最近金三银四快开始了，阿秀会继续跟大家分享一些互联网求职相关的经验和总结。
今天就分享下国内互联网面试必考的手撕算法心得吧，本文很干货，建议一些有着求职需要的小伙伴收藏起来，以后可能就看不到了。
1、手撕算法心得
在面试过程中，面试官常常会给出几道算法问题，需要面试者提供思路或写下代码。
在大多数公司的面试中，这一部分的表现都非常重要，而对一些外企来说，这部分的表现是具有决定性的（甚至是唯一重要的表现）。
对于这部分的准备，首推LeetCode、牛客等网站，对于一些重视算法问题的公司如字节、阿里以及国外的微软、HULU等，不仅考的多，而且还挺难，需要有较多的训练量。
而另一些不是很重视这类问题的公司，则刷一些常见的题目就很可能撞到原题了，而且难度一般不大。
因此，根据个人target公司的不同，可以有不同的准备方式，下面将列举一些其他在面试中我认为比较关键的点。
2、一个非常简单的例子
这里先给出一个非常简单的问题，下面的关键点将结合这个问题来阐述。
该问题为，计算一棵二叉树的高度，这是一道很经典的题，简单的实现如下：
int getHeightOfBinaryTree(TreeNode* root) { if (!root) return 0; int left_height = getHeightOfBinaryTree(root->left); int right_height = getHeightOfBinaryTree(root->right); return max(left_height, right_height) + 1; }
3、练习白板编程
面试的编程部分往往是白板编程：面试官要么要求在一个类似于Google Doc的地方写代码，要么就是干脆在白纸上写代码。
这种情况下coding的体验与平时使用IDE的体验是完全不同的。
以Google Doc为例，许多人一开始甚至很难写出能编译的代码，更别说一遍写出bug-free的代码了。
同时，没了IDE，debug的难度也会大大增加，而在白纸上写代码的难度则还要更进一步。
适应白板编程的方法也很简单，只需要足量的练习即可。
就像卖油翁说的：“无他，唯手熟尔！”
4、问清题目
问清题目至关重要。
如果你对面试官的编程问题理解得不清晰，那你应该立刻问一些能帮助你理解的问题。
例如：数据范围是多少？这个数组的大小范围是多少？能不能给个样例？如果输入是这个，那输出应该是什么等等。在上面这个简单的问题中，可以问的一个问题是，二叉树的高度是什么（据我所知，高度的定义并非所有教材都一致）？
许多面试官在面试的时候，会故意先抛出一个模糊的问题。实际上，
他们希望面试者能够经过一些询问理解问题。在这个过程中，面试者能够展现出自己对问题的分析能力以及沟通的能力。
前者的重要性参见《编程珠玑》这本书的第一章：明确问题，战役就成功了90%；后者的重要性在于，问清题目的这个交流过程与面试者入职之后与同事讨论问题的形式非常类似。
显而易见，一个能够很难沟通的面试者也很难成为一个很好沟通的同事。
如果没有问清题目，那会发生什么事情呢？
在最坏情况下，面试者可能会花大量时间去解决一个完全错误的问题，面试结果也可想而知。
或者运气好些，碰到了一个比较nice的面试官，给一些提示告诉面试者已经进入误区了，但这样不仅会浪费不少珍贵的面试时间，更会降低面试官对面试者的评价。
我在面一家公司的时候，面试官给我出了一个题，这个题听上去比较困难，需要用到动态规划才能实现。我当时想，在面试开始阶段就给出一道比较困难的题，这对我来说也太不友好了！
于是我询问了一句”数据的范围是什么呢？“
面试官告诉我，数组的范围都是0-10的整数。
这样的话，这个问题就变成了一个只需要6行代码就可以解决的贪心问题。
如果我没有问清这个问题的话，面试的难度显然大大增加，说不定要花上多几倍的时间去coding。
5、与面试官确认函数签名
确认了题目之后，我认为合理的做法是先和面试官确认函数签名，也即输入是什么参数，输出是什么参数等等。这一步的代价很低，而且相当重要，重要的事情要说三遍。
相当重要！相当重要！相当重要！
第一，这可以告诉面试官，你对函数签名的设计相当重视，而这一点在实际应用中很有价值。
第二，这可以进一步帮你确认自己理解了题意。
一个合理的函数签名可能就类似于LeetCode题目里的函数签名，上面代码中的签名就是一个比较合理的签名。
6、设计简单的测试样例
写完了函数签名之后，可以针对函数签名简单地设计一组测试样例（如果面试官之前给了样例的话，也可以直接用面试官给的样例作为测试样例）。
设计测试样例地主要有三个目的：一是进一步帮助确认自己对题意的理解没有出偏差；二是告诉面试官自己对测试十分重视；三是提醒自己编码完成的时候测试自己的程序。
7、与面试官确认思路
在自己有了一个思路之后，一定要和面试官确认这个思路是否合理。
你可以给面试官解释你的思路为什么合理，面试官可能会和你讨论其中的一些要点。这样做有几点好处：
第一，在解释的过程中，你的思路也会变得更加清晰（面试官充当小黄鸭）。
第二，这也展现出你对沟通的重视性。
第三，可能也是最重要的一点是，如果你的思路不正确，nice的面试官会提示你甚至直接指出错误所在，这样你至少不会在一个错误的思路上耽误太多时间。
切忌有了思路之后，不与面试官交流直接写代码，尤其需要指出的是，如果你的思路对数据有什么假设，或者需要修改输入数据，那一定要和面试官确认这样的做法是合理的。
如果你认为这个问题与某个经典的问题思路一致，或者可以用到某个经典的算法，那么就直接点出来。
例如计算二叉树的高度，实际上是一个后序遍历，那么可以直接点出来。
8、抓住面试官给的提示
有的时候一道题难度比较大，候选人一时想不到最优的思路，或者目前提出的思路是错误的，那合格的面试官可能会给一些提示帮助候选人思考，这时候候选人一定要抓住面试官给的提示。
以上文给的例子为例，如果候选人想不到思路，那面试官可能会提示：“你觉得一棵树的高度与它的左右子树的高度可能有什么样的关系？”这就提示候选人可以用递归的方式来解决问题。
抓住提示是很重要的：一方面，面试官给的提示很可能可以帮助你想到正确/最优的思路；另一方面，这其实也是双方能够进行不错的沟通的体现。
9、确认边界处理
在开始写代码以前或者是写代码的过程中，一定要思考代码的边界条件。
最典型的边界条件有：数据是否会溢出？指针是否可能为空？链表是不是可能存在环？数组的长度是不是零？输入的数据会不会完全不符合题意的要求？
在示例中，边界条件就是当结点指针为空时，高度应该是0。
当你察觉到边界条件存在时，就可以询问面试官处理方式，或者直接告诉面试官你认为什么样的处理方式是合理的。对边界条件的处理在开发软件时也异常重要。
忽视了一个边界条件，就会对程序鲁棒性造成极大的影响，可能直接造成巨大经济损失甚至是人员伤亡。
10、代码中使用可读性高的变量名和函数名
在写代码的时候，尽量使用可读性较高的函数名和变量名。
例如，要计算二叉树的深度，函数签名可以为int getHeightOfBinaryTree(TreeNode* root)入参就叫root（而非node）。递归时，左子树的高度的变量名可以叫left_height 。诸如此类。
这样操作的主要目的也是让面试官看到你良好的编码习惯。
11、写代码过程中保持与面试官交流
实现算法的过程中，切忌闷头狂写而不与面试官交流。
实际上，在写一些关键代码的时候，你完全可以告诉面试官你在实现什么功能。
同样如前例计算二叉树深度，那你就可以告诉面试官，int left_height = getHeightOfBinaryTree(root->left) 是在计算左子树的高度（良好的函数名和变量名其实也让这行代码不言自明），而int root_height= max(left_height, right_height) + 1 则是根据左子树和右子树的高度计算当前根节点的高度。
当然了，在这个简单的示例中，交流或许显得不是那么重要，但是在一些复杂的问题中交流可能会非常重要。
例如，示例的follow-up是请不用递归实现同样的功能，或者更进一步，请用常数空间实现同样的功能。
在这样的问题中（代码可能长达数十行），交流就至关重要了。
面试官需要和你交流来理解你的思路与状态，你同样需要交流来理清思路，这种写代码过程中的交流也是正式工作时非常重要的能力。
当然了，这样的交流也不必过于频繁，否则也可能影响自己的编码状态。
12、写完代码后主动测试
在你写完代码之后，不要急着告诉面试官你已经写完了。
最好先手动跑一个/数个简单的样例。注意跑这个样例的过程要让面试官可以看见并轻易地理解，这常常是需要一些练习的。
主动测试的好处有很多：
第一，这告诉面试官你很重视测试，而测试在实际生产中是非常非常重要的。
第二，一个简单的样例常常可以找出不少类似于typo这样的小错误。
第三，如果你的样例给得不错，那你甚至能够借助这个样例找到程序中的bug并纠正它，这总是要好过面试官发现并告诉你程序中存在着bug。
主动测试时，你也可以确认你的程序可以很好地处理边界数据。
我自己在面一家外企的时候，主动测试的习惯就给我带了很大的回报。
当时我写了一段不算复杂的程序（约20行左右），可是因为情绪紧张，程序中包含了一个相对隐蔽的bug。
写完之后，我习惯性地跑了一个简单的样例，这花了我大约3分钟的时间，但却让我注意到了那个bug。
我赶紧修复了这个bug，到了面试的提问环节，我问面试官本场面试中我表现最好的一点是什么。他告诉我：”是你通过一个样例发现了你的bug。实际上，在你写出了那段代码的时候我就注意到了这个bug，当时我在犹豫要不要提醒你。而你随即开始了测试并找到了这个bug。“
这场面试的结果是，在面试结束半小时左右我就收到了通过面试的消息，这应该就是于无声处听惊雷了。
13、主动给出算法的复杂度
在写完代码之后，应当主动分析自己算法的时间与空间复杂度，一方面，这样可以展示自己扎实的算法基础，另一方面，这也可以告诉面试官自己有这方面的意识。
当然了，如果复杂度分析的有误，那这个分析也可能会成为一个减分项，这个看你自己的平常时的积累了。
14、讨论算法的trade-off
有些时候，题目的解法可能存在一些trade-off。
最常见的就是时间-空间的trade-off，当然有时也会有一些其他的trade-off。
如果意识到了这道题目存在trade-off，那么可以主动地与面试官聊trade-off，让他/她知道你的思考过程与选择。
这就是一个很大的加分点。
