前几天西法参加了《前端早早聊》第 24 界的分享。我的分享主题是《如何搞定不同公司的算法面试?》 这是这次分享的文字版,供大家查看。如果大家需要分享的原版 ppt,也可以到我的公众号《脑洞前端》中回复早早聊获取。
正文
本次分享我们会按照如下顺序进行:
- 第一部分是前端算法面试都考什么?(其实这部分内容不同公司差异不大,我列举的是总体公司的大部分面试考察点,差不多可以覆盖 90% )
- 第二部分是不同公司算法面试有何区别?(由于不同公司的算法难度和侧重不尽相同,有时候甚至是天差地别,因此我们有必要对不同类型公司的算法面试进行区分)
- 第三部分是如何准备算法面试?(知道了算法面试的考察内容和不同公司的面试特点,就可以根据自己心仪的公司对号入座了。那学习的顺序是什么,重点又是什么?这部分告诉你)
- 第四部分是中等难度算法题实战(通过一个具体的例子,带大家看一下,解决一道具体的算法题背后的思路究竟是如何的,我是如何和已有的知识建立建立的,希望能给大家一点点启发)
- 最后一部分是我的工具与方法论(这部分是我一直在使用的一些工具和方法论,个人觉得不错,这里分享给大家)
为什么是我?
- 我从 17 年开始研究算法面试题,到现在已经接近 4 年了。可以说经验算是比较丰富的了。
- 另外我本人刷了大概 2000 道左右的算法题。就大家比较熟悉的力扣平台而言,我几乎将他们所有的树,链表,堆,二分,动态规划等刷完了。除此之外,我也会刷一些其他 OJ 平台,比如牛客,Binary-Search 等等。在刷题过程中总结了大量的经验和套路。
- 除此之外,我也经常在力扣上分享自己的刷题心得以及题解。当力扣刚推出等级系统的时候,我就已经是满级作者了。除了在力扣上分享经验,我还在其他渠道进行分享,比如 公众号和 Github 。Github 上关于刷题的项目已经超过 4w star 了,非常感谢大家的认可。
- 另外在算法面试这个点上,我已经做了三期的算法面试培训了,累计有 1000 多人参加,很多人拿到大厂 offer 也会过来还愿。
- 最后一点我觉得最重要。 由于我本人是前端,也参加了无数的面试,包括面试别人和被别人面试。从面试官的角度我能知道广大求职者的面试状态,从求职者的角度,我能知道各个公司的考察形式和内容。这一来一回,一正一反,使得我对算法面试更加了解。当然除了我本人亲自面试的经验,我还经常和其他公司的朋友以及群友交流面试题目,他们提供面试真题,我提供免费的算法题目指导。通过这样的过程,我积累了相当可观数目的算法面试真题。使得我对很多公司的面试情况更加了解。
一点点说明
为了方便描述,我将公司分成四个梯队。
- T1:世界头部公司,比如 Google, Amazon, Facebook 等
- T2:国内头部公司,比如 BAT ,头条 ,美团等
- T3:其他中大型公司,比如滴滴,有赞等
- T4:小微公司(这类不在我们的论述范围,因此它们几乎没有算法题)
右边是一个金字塔图,表示的意思是 T4 公司是最多的,其次是 T3,T2,T1。
前端算法面试都考什么?
接下来开始我们本次分享的第一个主要内容 - 《前端算法面试都考什么?》
有的人可能会问,我的这个前端算法面试考点数据来源是哪?有事实依据么?这里我说一句。 这里的考察知识点的数据来源就是我前面做自我介绍时候提到的“亲身经历+好友反馈“。
我从大的方向,将考察点分成了两类。第一类是数据结构与算法基础知识。
数据结构与算法基础知识
这部分,我又做了一个小小的细分,将其分为两个小点。
- 各种数据结构的特性与基本操作。比如数组,队列,栈,链表,树,图等。对于前端,尤其需要掌握的栈和树。这是因为前端使用到栈和树的地方实在太多了。比如 DOM 树(虚拟 DOM 树),树形选择器,浏览器执行栈,浏览器历史记录栈等等。另外题目上围绕栈和树的题目也相当多,从最简单直接的树形数据结构转化复杂一点的数据结构解析,基本就是栈+DFS 都可以搞定,而做 DFS 的时候通常都围绕树型结构进行递归求解的。所以这两个数据结构对前端非常重要。面试频率非常高,这里我敲一下重点,希望大家认真对待这部分。
- 复杂度分析。复杂度分析是学习数据结构与算法的基础,也是核心。我建议大家一定要先学会分析算法的复杂度再去学习具体算法。这部分内容包括时间复杂度和空间复杂度分析,其中每一种复杂度都有最好,最坏以及均摊复杂度。而一般我们使用最坏复杂度比较多,而我写的新书《lucifer 的算法之路》中的全部复杂度也全部都是最坏复杂度,而且这部分内容是在全书的最开始,可见其重要性。另外分析复杂度除了分析迭代,也要会分析递归,递归栈的空间开销经常被大家所忽略,这点值得引起大家的注意。
OK,以上是第一个考点:《数据结构与算法基础知识》,接下来我们来看第二个考点。
算法思想(90%考点)
第二类是算法思想,需要大家在掌握了上面内容基础上再来学习。
这里我列举了五个考点,它们分别是:
- 搜索(BFS,DFS,回溯,二分等)
- 暴力优化(双指针,单调栈,前缀和等)
- 动态规划
- 分治
- 贪心
以上内容覆盖了前端算法面试的 90% 考点。一些比较“冷门”的知识比如二分图,跳表,蓄水池抽样算法等考察频率很低,我就没有列出来。
我希望大家集中精力将重心投入到这 90% 考点中。其他知识点大家可以根据自己的情况学习(比如你想进 T1 或者其他学的差不多了想精进)。
不同公司算法面试有何区别?
接下来,我们来看下本次分享的核心主题 - 《不同公司算法面试有何区别?》
首先我声明一点:即使是同样的公司,同样的岗位不同时期题型和难度都不一定相同。因此以下内容仅表示历史数据,不表示之后的情况。如果大家想获取第一手的不同公司算法面试情况,可以在本次演讲结束后关注我的个人公众号。
前面我们已经对不同公司进行了一个简单的分类,那么这里就直接根据前面的分类进行逐一讲解,比较一下不同公司的算法面试有什么不同。
T1
难度和题型
首先我们来看下 T1 级别的公司。 T1 级别的公司算法面试题难度几乎没有上限,可能会超出普通 OJ 平台的难度,且题目非常灵活,他们经常会时不时原创题库, 因此碰不到原题或者类似题是很正常的。
还有一点有必要和大家强调从一下。 很多人觉得社招算法难度比校招要大,这是不对的。 一般而言,校招会更看重基础,这是因为校招的人通常项目经验都比较欠缺。而算法就是这些基础中非常重要的一项。社招的话,国内公司还是以项目经验和解决问题能力为主,对于算法的要求通常比校招的要求低。因此大家不要觉得校招的算法都这么难,那我社招岂不是更难? 不要有这样的想法。
T1 公司题型也更加广泛,除了上面列举的 90% 考点,还会有一些图论,前缀树,KMP 等其他公司不太会问到的“冷门”知识。虽然 T1 公司很多题目也可以在网上找到原题。不过区别于 T2,T3,他们的出题形式会更加有关联,循序进阶,且会伴随着一些 follow up。
比如第一道题是两数和,第二道题可能就是三数和,甚至是 k 数和。另外还会提出一些进阶要求,比如要求不借助额外空间等。
而且 T1 通常会定期扩充原创题库,这是其他 T2, T3 级别公司(尤其是 T3)很难做到的。
这些题库的题目经过一段时间也会逐步扩散到网上,进而又变成了大家所谓的“网上的原题”。
面试形式
T1 公司之前很多是白板面试,即让你在一块白板上书写。白板书写对你的调试能力, api 了解能力,甚至代码组织能力都有很高的要求。不过最近 T1 公司基本都改成了视频面试的形式,而不是传统的 onsite,因此白板也变成了云编辑器。
T1 公司通常要求思路正确,代码 bug free(有时候也会要求你不经过提示的情况下一次通过),一般也对复杂度有一定要求。不仅需要你能够正确地分析出算法的复杂度,还需要对算法进行改进以达到尽可能优的复杂度。
前面我已经提到了,复杂度分析是基础中的基础,这部分大家注意一下。
面试完成后会有一份完整的面试报告,记录了你每一道题的回答情况甚至用时情况。面试委员会会根据这份面试报告来决定面试是否通过以具体的定级之类的。
一个典型的 t1 公司算法面试流程
接下来,我们来看下《一个典型的 t1 公司算法面试流程》。
- 面试官:我把题目贴到了屏幕左侧,你可以在右侧编辑器中进行作答了。我现在给你放第一题。
- 求职者:OK。(看了一会)题目的意思是不是。。。(复述题目,确保理解正确,询问限制条件,比如数据规模)
- 面试官:(回答求职者的问题)
- 求职者:我的思路是。。。,这种做法的时间复杂度为。。。空间复杂度为 。。。
- (如果面试官觉得没有问题,你就可以开始写代码了。写代码的时候要边写边交流)
- 面试官:你可以对你的算法进行优化么?(如果求职者给的算法不是最优解)
- (面试官会在求职者做题的时候记录求职者的回答情况以及每一部分所花费的时间)
- 最后将几道题(一般是 2 - 4 道)的回答情况汇总到面试报告中
如上是我模拟的一个典型的教科书般的面试流程,大家可以参考这位求职者的回答。
其中核心点就在于:
- 复述题目,确保理解正确,询问限制条件,比如数据规模
- 先讲思路,再写代码。讲思路后记得用复杂度对算法进行评估。
- 如何可能,继续优化你的代码。
T2
难度和题型
T2 公司难度基本不会超过中等,且题目比较固定(就是一些 OJ 原题或者稍微改改)。以我的经历来说,我面试了很多国内顶尖公司,比如头条,阿里,腾讯等。只有腾讯遇到了 hard,还不让你用 hard 解法就能过关(用了 hard 解法反而可能不够,这个和面试官有关,建议你先用最笨的解法,有必要再优化)。
另外从其他朋友的反馈来看,前端岗位算法面试难度为困难的题目很少,且题目比较固定,比如 LRU,分组反转链表等。(可能是公司题库就那几道困难题目?)
题型上来看,前面提到的算法思想基本都可以完全覆盖,很少会有一些刁钻的题目。并且面试的题目大部分都是可以在网上找到原题或者类似的题。这也是 T2 和 T1 的一个显著区别。
这里要提一下校招的笔试题。校招的笔试题大家都觉得是新题, 其实不然,以我这么久和校招题目打交道的过程来看。题目基本都是换皮,而且是那种换了个说法而已的换皮。
面试形式
T2 公司通常是采用云编辑器和本地编辑器的考察形式。比如头条大多数使用的是牛客的编辑器,阿里有些用的是内部开发的伯乐系统,这两个公司通常需要你在云端编辑器完成。再比如腾讯就使用的是腾讯文档,但是允许你在自己的本地编辑器中写代码。这一点还是非常人性化的。
T2 公司对算法题目的要求通常是思路正确,bug free。(不一定一次通过,通常给你几次机会,具体几次视题目难度而定。比如简单题可能就不给你错的机会,困难题允许你错一次或者可以给提示这样)
面试完成后会有一份面试报告,这部分面试报告通常不会像 T1 公司的那样完整,一般只是记录了你最终完成的代码。
需要注意的是你的每一次面试都会记录下来,之后当你再次参加他们公司的面试,有时候也会参考之前的面试记录(通常只会参考最近半年或者一年的面试记录,毕竟每个人都会成长的)。
一个典型的 t2 公司算法面试流程
t2 公司面试流程和 t1 公司有很大的相似性。
虽然考察的形式是差不多的,也就是说非常形似。不过 t2 公司的算法面试题的难度和数量一般会比 t1 的低一些,t1 公司的面试报告也会更加详细一些。
T3
难度和题型
T3 级别的公司难度绝大多数不会超过中等,且基本都是网上非常常见的面试题。如果你想通过这些公司的算法面试,你可以选择完全放弃困难题目。没错,网上常见的困难题也没有必要做了。并且基本上只需要刷我提到的算法思想部分,然后将网上的面经遇到的题目练习一下就差不多够了。
考察形式
考察形式上也通过是让你说思路或者写出伪代码。通常要求思路正确,由于通常是说思路和伪代码,因此也不要求 bug free。
T3 公司面试完成后会有一份简短的面试反馈,一般是对面试人能力的大体概括。这个面试报告可能是在招聘系统中直接给出,也可能是口头的。
一个典型的 t3 公司算法面试流程
t3 公司流程就和 t1 ,t2 有很大差别了。它们有时候根本就没有算法题。如果有的话,通常也是一个加分项。面试的难度也会更低,并且碰上原题的概率会很大,毕竟不是所有公司都有自己的题库的。就连 t2 公司的题库也使用了一些外部题目。
还有一点我发现的一个有意思的点是: T3 公司通常你做出来就行了,不太会让你去优化。比如,我有一次参加一个 T3 公司的面试,它们给我出了一个括号匹配(力扣简单难度)。我先用栈完成了,心想面试官肯定会让我优化成 $O(1)$ 空间。结果是没有,并且面试官对我很满意,觉得我写的很快。
实际上这不是巧合,我的经验告诉我。如果你的算法性能不是差到离谱,只要能做出来就行。什么叫差到离谱?比如两数和,你用 $O(n^2)$ 做出来,这就是离谱。
最后我给一个汇总性的对比表格方便大家查看。
大家可以通过这个表感受不同类型公司算法面试的区别。
我该如何准备算法面试?
前面已经对各种不同的公司从多个维度进行了详细对比。接下来给大家一点实操建议。即如何准备算法面试。
这部分我总结了四点,在这里分享给大家。
1. 先学习数据结构与算法基础知识。
第一个我要给大家的建议是:先学习数据结构与算法基础知识。
我发现很多同学喜欢一下子就钻到刷题中去,他们甚至连复杂度分析以及各种数据结构的特点都还不清楚。
这是万万不可取的做法。一定要注意,做题只是巩固知识的手段,如果你根本没有知识,或者知识不足,那么做题是几乎没有任何效果的。
具体的基础知识内容可以参考我后面要讲的学习路线图。
- 01.数组,栈,队列
- 02.链表
- 03.树
- 04.哈希表
- 05.双指针
- 06.图(加餐)
- 模拟和枚举
- 前缀和与差分
- 如何衡量算法的性能
- 各种排序
2. 找到你心仪的公司,通过多种渠道了解其出题风格和难度
挑选出你心仪的几家公司,看看他们属于 T 几,先有一些大体的映象和心理准备。接下来,你需要从多个渠道了解它们算法题目的类型和难度。我提供几个渠道给大家:
- 牛客网讨论区
- 力扣讨论区
- 一亩三分地
- 社群和好友
- 如果你愿意的话,也可以直接来咨询我。我会尽可能帮助你的
之后你要做的就是根据上面步骤总结的信息针对性刷题,这样可以使你的效率最大化。
3. 不依赖自己顺手的编辑器
平时练习的过程中大家可能习惯了自己顺手的 IDE。比如自己本地的 IDE 或者平台提供的 IDE。
笔试的时候很多情况下是没有条件让你这么做的,所以大家在面试前需要自己适应一下脱离 IDE 写代码。
一个不顺手的 IDE 确实会让你的效率大大降低,比如没有智能提示,没有语法高亮,缺乏良好的格式化,很多快捷键不支持等。当你没有这些良好的条件的时候,会加大你面试的紧张情绪,进而影响你的发挥。因此不依赖你自己顺手的编辑器是一个相当重要的点。
4. 重点突破搜索类和动态规划
最后一个,我觉得或许是对大家最有用的一个建议了,这部分再次划重点。(这是本次分享的第二个重点了。还记得第一个重点么?第一个重点是两个数据结构,栈和树)
回忆一下前面我提到的五种占比 90%的算法思想:
- 搜索(BFS,DFS,回溯,二分等)
- 暴力优化(双指针,单调栈,前缀和等)
- 动态规划
- 分治
- 贪心
前端算法面试 90% 的题目都不超过这几项,尤其是非 T1 公司。
如果要从从这五项再说重点的话,我推荐大家刷:
- 搜索
- 动态规划
而搜索的话,又以树为主。其中的原因我在前面也进行了分析,这里就不赘述了。
至于动态规划,大家也应该着重准备。比如很多公司特别喜欢考察的背包问题,爬楼梯问题,这些都是动态规划。悄悄告诉你,这些问题我本人也都在实际面试中遇到过,可见面试频率还是蛮高的,值得大家重点投入。
而如果你面试国外的公司的话,除了谷歌据说考察动态规划的很少。
举个栗子
接下来上干货,带大家来解决一道算法题。
我们以力扣上的 402. 移掉 K 位数字 为例,讲解一下如何思考一道题目的解法。
之所以要选这道题是因为:
- 难度适中。 没有很难,但也绝对不简单。
- 这题很经典,搞懂这道题你可以 AC 好多道题,我在后面的 PPT 给大家都列好了,大家等会可以看下。另外这道题的题解让我收获了几千的点赞和收藏,可见质量还是不错的。
我们来看一下这道题。
题目描述
1 | 给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。 |
前置知识
- 数学
- 栈
思路
这道题让我们从一个字符串数字中删除 k 个数字,使得剩下的数最小。也就说,我们要保持原来的数字的相对位置不变。
以题目中的 num = 1432219, k = 3
为例,我们需要返回一个长度为 4 的字符串,问题在于: 我们怎么才能求出这四个位置依次是什么呢?
(图 1)
暴力法的话,我们需要枚举C_n^(n - k)
种序列(其中 n 为数字长度),并逐个比较最大。这个时间复杂度是指数级别的,必须进行优化。
一个思路是:
- 从左到右遍历
- 对于每一个遍历到的元素,我们决定是丢弃还是保留
问题的关键是:我们怎么知道,一个元素是应该保留还是丢弃呢?
这里有一个前置知识:对于两个数 123a456 和 123b456,如果 a > b, 那么数字 123a456 大于 数字 123b456,否则数字 123a456 小于等于数字 123b456。也就说,两个相同位数的数字大小关系取决于第一个不同的数的大小。
因此我们的思路就是:
- 从左到右遍历
- 对于遍历到的元素,我们选择保留。
- 但是我们可以选择性丢弃前面相邻的元素。
- 丢弃与否的依据如上面的前置知识中阐述中的方法。
以题目中的 num = 1432219, k = 3
为例的图解过程如下:
(图 2)
由于没有左侧相邻元素,因此没办法丢弃。
(图 3)
由于 4 比左侧相邻的 1 大。如果选择丢弃左侧的 1,那么会使得剩下的数字更大(开头的数从 1 变成了 4)。因此我们仍然选择不丢弃。
(图 4)
由于 3 比左侧相邻的 4 小。 如果选择丢弃左侧的 4,那么会使得剩下的数字更小(开头的数从 4 变成了 3)。因此我们选择丢弃。
那我们要继续丢弃 1 么?不用,因为这样会造成数字更大(从 1xxx 变成了 3xxx)。
。。。
后面的思路类似,我就不继续分析啦。
然而需要注意的是,如果给定的数字是一个单调递增的数字,那么我们的算法会永远选择不丢弃。这个题目中要求的,我们要永远确保丢弃 k 个矛盾。
一个简单的思路就是:
- 每次丢弃一次,k 减去 1。当 k 减到 0 ,我们可以提前终止遍历。
- 而当遍历完成,如果 k 仍然大于 0。不妨假设最终还剩下 x 个需要丢弃,那么我们需要选择删除末尾 x 个元素。
上面的思路可行,但是稍显复杂。
(图 5)
我们需要把思路逆转过来。刚才我的关注点一直是丢弃,题目要求我们丢弃 k 个。反过来说,不就是让我们保留 $n - k$ 个元素么?其中 n 为数字长度。 那么我们只需要按照上面的方法遍历完成之后,再截取前n - k个元素即可。
按照上面的思路,我们来选择数据结构。由于我们需要保留和丢弃相邻的元素,因此使用栈这种在一端进行添加和删除的数据结构是再合适不过了,我们来看下代码实现。
代码
代码支持: Python3, JS
Pythopn3 Code:
1 | class Solution(object): |
JS Code:
1 | var removeKdigits = function (num, k) { |
复杂度分析
令 n 为数字长度。
- 时间复杂度:虽然内层还有一个 while 循环,但是由于每个数字最多仅会入栈出栈一次,因此时间复杂度仍然为 $O(n)$。
- 空间复杂度:我们使用了额外的栈来存储数字,因此空间复杂度为 $O(n)$。
提示: 如果题目改成求删除 k 个字符之后的最大数,我们只需要将 stack[-1] > digit 中的大于号改成小于号即可。
相关题目
大家做完这个题,就可以 AC 下面几个题啦~
- 去除重复字母(困难)
- 拼接最大数(困难)
- 不同字符的最小子序列(中等)
我的工具与方法论
最后是我的工具和方法论,主要介绍一下我学习路上的一些好用的工具,以及我是如何刷题的经验分享。
学习路线
这里我给出一个适合前端同学的一个算法学习路线。
- 复杂度分析:如何衡量算法的性能?
- 基础的数据结构:线性数据结构 (数组,链表,栈,队列,哈希表)
- 基础的数据结构:非线性数据结构 (树 和 图)
- 排序算法:经典排序算法
- 递归: 一种”高级“的思维技巧
- 暴力搜索篇: 回溯,BFS, DFS
- 暴力优化篇:剪枝,滑动窗口,双指针,单调栈
- 高级搜索篇:二分法与位运算
- 动态规划篇:记忆化搜索与动态规划
- 分治:大事化小,小事化了
- 贪心:简单高效但”不靠谱“的算法
- 逆向思考
大家可以根据自己的实际情况从不同阶段开始。如果你是刚开始接触算法,我建议你从头开始跟着这个学习路线坚持下去,我相信一定会有突然间成长的一天。
多做总结,多写题解
大家在学习的过程这一定要及时总结和复习,而写题解就是总结和复习很好的一个途径。我本人写的题解数量已经有几百篇了。通过写题解能够加深我对算法的理解能力。下一次碰到相同或者类似的题目,则可以从大脑中提取更多信息。
使用 anki 管理知识
前面提到了要及时复习。而 anki 就是一个帮助你管理复习计划的软件。它是一个能够根据遗忘周期来自动制定复习计划的软件。我在前期学习算法的时候制作了一部分的复习卡片,它们帮助了我度过了学习算法最艰难的入门期。
等到你刷了足够数量的题目了,就不需要它们了。但是在前期,它确实可以有效地帮助到你。
刷题插件 leetcode-cheatsheet
最后提一下我自己制作的一个刷题插件,现在有几千个人在用了。通过它可以帮助你更有效率刷题和写题解。
- 他提供了学习路线可以帮助你理清不同专题的基本题型和套路。
- 他提供了代码模板可以帮助你快速写出 bug free 的代码。
- 他提供了数据结构可视化和题解模板则可以帮你快速写出格式良好的题解。
- 他提供了复杂度速查, 这是一个帮助你快速判断算法是否可行的参考工具。
推荐一本好书给大家
最后推荐一本书大家。《算法第四版》- 一本非常适合初中级选手的算法学习书籍。
这本书给了我很多帮助,少走了一些弯路。这里推荐给大家,希望也可以帮助到正在学习算法的你。这本书我买了好多本,不仅自己看,还送给了我的朋友和学员。
这本书只是让你入门,以及学习一些经典算法。仅靠这个去参加比赛或者 T1 面试是不够的。大家还需要准备一些别的资料。不过我觉得入门是最难的,相信你入门之后就可以自己去挑选学习资料了。比如 oi wiki。
关注我
我本人最近也在写一个关于前端算法面试的专栏,目前正在寻找合作平台,如果你是平台方可以微信联系我。如果你对内容感兴趣可以订阅我的公众号《脑洞前端》,第一时间消息会在公众号同步大家。
另外我的 《91 天学算法》第四期已经快要开始了,现在还没有开始报名哦,活动介绍:https://leetcode-solution.cn/91。开始报名时间大概是 2021.5.1 - 2021.6.1 之间。具体时间请关注我的公众号《力扣加加》,第一时间获取最新消息。
以上就是本次分享的全部内容了,大家有什么问题的话都可以提,我会尽量回答。