本次分享我们会按照如下顺序进行:
为了方便描述,我将公司分成四个梯队。
右边是一个金字塔图,表示的意思是 T4 公司是最多的,其次是 T3,T2,T1。
接下来开始我们本次分享的第一个主要内容 - 《前端算法面试都考什么?》
有的人可能会问,我的这个前端算法面试考点数据来源是哪?有事实依据么?这里我说一句。这里的考察知识点的数据来源就是我前面做自我介绍时候提到的“亲身经历+好友反馈“。
我从大的方向,将考察点分成了两类。第一类是数据结构与算法「基础知识」。
这部分,我又做了一个小小的细分,将其分为两个小点。
OK,以上是第一个考点:《数据结构与算法基础知识》,接下来我们来看第二个考点。
第二类是算法思想,需要大家在掌握了上面内容基础上再来学习。
这里我列举了五个考点,它们分别是:
以上内容覆盖了前端算法面试的 90% 考点。一些比较“冷门”的知识比如二分图,跳表,蓄水池抽样算法等考察频率很低,我就没有列出来。
我希望大家集中精力将重心投入到这 90% 考点中。其他知识点大家可以根据自己的情况学习(比如你想进 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 公司算法面试流程》。
如上是我模拟的一个「典型的教科书般的面试流程」,大家可以参考这位求职者的回答。
其中核心点就在于:
T2 公司难度基本不会超过中等,且题目比较固定(就是一些 OJ 原题或者稍微改改)。以我的经历来说,我面试了很多国内顶尖公司,比如头条,阿里,腾讯等。只有腾讯遇到了 hard,还不让你用 hard 解法就能过关(用了 hard 解法反而可能不够,这个和面试官有关,建议你先用最笨的解法,有必要再优化)。
另外从其他朋友的反馈来看,前端岗位算法面试难度为困难的题目很少,且题目比较固定,比如 LRU,分组反转链表等。(可能是公司题库就那几道困难题目?)
题型上来看,前面提到的算法思想基本都可以完全覆盖,很少会有一些刁钻的题目。并且面试的题目大部分都是可以在网上找到原题或者类似的题。这也是 「T2 和 T1 的一个显著区别」。
这里要提一下校招的笔试题。校招的笔试题大家都觉得是新题, 其实不然,以我这么久和校招题目打交道的过程来看。题目基本都是换皮,而且是那种「换了个说法而已的换皮」。
T2 公司通常是采用云编辑器和本地编辑器的考察形式。比如头条大多数使用的是牛客的编辑器,阿里有些用的是内部开发的伯乐系统,这两个公司通常需要你在云端编辑器完成。再比如腾讯就使用的是腾讯文档,但是允许你在自己的本地编辑器中写代码。这一点还是非常人性化的。
T2 公司对算法题目的要求通常是思路正确,bug free。(不一定一次通过,通常给你几次机会,「具体几次视题目难度而定」。比如简单题可能就不给你错的机会,困难题允许你错一次或者可以给提示这样)
面试完成后会有一份面试报告,这部分面试报告通常不会像 T1 公司的那样完整,一般「只是记录了你最终完成的代码。」
需要注意的是你的每一次面试都会记录下来,之后当你再次参加他们公司的面试,有时候也会参考之前的面试记录(通常只会参考最近半年或者一年的面试记录,毕竟每个人都会成长的)。
t2 公司面试流程和 t1 公司有很大的相似性。
虽然考察的形式是差不多的,也就是说非常形似。不过 t2 公司的算法面试题的「难度和数量一般会比 t1 的低一些」,t1 公司的面试报告也会更加详细一些。
T3 级别的公司难度绝大多数不会超过中等,且基本都是网上非常常见的面试题。如果你想通过这些公司的算法面试,你可以「选择完全放弃困难题目」。没错,网上常见的困难题也没有必要做了。并且基本上只需要刷我提到的算法思想部分,然后将网上的面经遇到的题目练习一下就差不多够了。
考察形式上也通过是让你说思路或者写出伪代码。通常要求思路正确,由于通常是说思路和伪代码,因此也不要求 bug free。
T3 公司面试完成后会有一份简短的面试反馈,一般是对面试人能力的大体概括。这个面试报告可能是在招聘系统中直接给出,也可能是口头的。
t3 公司流程就和 t1 ,t2 有很大差别了。它们有时候根本就没有算法题。如果有的话,通常也是一个「加分项」。面试的难度也会更低,并且碰上原题的概率会很大,毕竟不是所有公司都有自己的题库的。「就连 t2 公司的题库也使用了一些外部题目。」
还有一点我发现的一个有意思的点是:T3 公司通常你做出来就行了,不太会让你去优化。比如,我有一次参加一个 T3 公司的面试,它们给我出了一个括号匹配(力扣简单难度)。我先用栈完成了,心想面试官肯定会让我优化成
空间。结果是没有,并且面试官对我很满意,觉得我写的很快。
实际上这不是巧合,我的经验告诉我。如果你的算法性能不是差到离谱,只要能做出来就行。什么叫差到离谱?比如两数和,你用
做出来,这就是离谱。
最后我给一个汇总性的对比表格方便大家查看。
大家可以通过这个表感受不同类型公司算法面试的区别。
前面已经对各种不同的公司从多个维度进行了详细对比。接下来给大家一点实操建议。即如何准备算法面试。
这部分我总结了四点,在这里分享给大家。
第一个我要给大家的建议是:先学习数据结构与算法基础知识。
我发现很多同学喜欢一下子就钻到刷题中去,他们甚至连复杂度分析以及各种数据结构的特点都还不清楚。
这是万万不可取的做法。一定要注意,做题只是巩固知识的手段,如果你根本没有知识,或者知识不足,那么做题是「几乎没有任何效果」的。
具体的基础知识内容可以参考我后面要讲的学习路线图。
挑选出你心仪的几家公司,看看他们属于 T 几,先有一些大体的映象和心理准备。接下来,你需要从多个渠道了解它们算法题目的类型和难度。我提供几个渠道给大家:
之后你要做的就是根据上面步骤总结的信息针对性刷题,这样可以使你的效率最大化。
平时练习的过程中大家可能习惯了自己顺手的 IDE。比如自己本地的 IDE 或者平台提供的 IDE。
笔试的时候很多情况下是没有条件让你这么做的,所以大家在面试前需要自己适应一下脱离 IDE 写代码。
一个不顺手的 IDE 确实会让你的效率大大降低,比如没有智能提示,没有语法高亮,缺乏良好的格式化,很多快捷键不支持等。当你没有这些良好的条件的时候,会加大你面试的紧张情绪,进而影响你的发挥。因此「不依赖你自己顺手的编辑器」是一个相当重要的点。
最后一个,我觉得或许是对大家最有用的一个建议了,这部分「再次划重点。」(这是本次分享的第二个重点了。还记得第一个重点么?第一个重点是两个数据结构,栈和树)
回忆一下前面我提到的「五种」占比 90%的算法思想:
前端算法面试 90% 的题目都不超过这几项,尤其是非 T1 公司。
如果要从从这五项再说重点的话,我推荐大家刷:
而搜索的话,又以树为主。其中的原因我在前面也进行了分析,这里就不赘述了。
至于动态规划,大家也应该着重准备。比如很多公司特别喜欢考察的背包问题,爬楼梯问题,这些都是动态规划。悄悄告诉你,这些问题我本人也都「在实际面试中遇到过」,可见面试频率还是蛮高的,值得大家重点投入。
❝而如果你面试国外的公司的话,除了谷歌据说考察动态规划的很少。 ❞
接下来上干货,带大家来解决一道算法题。
我们以力扣上的 402. 移掉 K 位数字 为例,讲解一下如何思考一道题目的解法。
之所以要选这道题是因为:
我们来看一下这道题。
给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字,剩余为空就是0。
这道题让我们从一个字符串数字中删除 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 个。反过来说,不就是让我们保留
个元素么?其中 n 为数字长度。那么我们只需要按照上面的方法遍历完成之后,再截取前「n - k」个元素即可。
按照上面的思路,我们来选择数据结构。由于我们需要「保留」和「丢弃相邻」的元素,因此使用栈这种在一端进行添加和删除的数据结构是再合适不过了,我们来看下代码实现。
代码支持:Python3, JS
Pythopn3 Code:
class Solution(object):
def removeKdigits(self, num, k):
stack = []
remain = len(num) - k
for digit in num:
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 为了类似 "10200" /n 这种 case 过不了,需要移除前导0。 另外为了防止将 0 全部移除,我们需要判空
return ''.join(stack[:remain]).lstrip('0') or '0'
JS Code:
var removeKdigits = function (num, k) {
const stack = [];
const remain = num.length - k;
for (const digit of num) {
while (k && stack && stack[stack.length - 1] > digit) {
stack.pop();
k -= 1;
}
stack.push(digit);
}
return stack.slice(0, remain).join("").replace(/^0+/, "") || "0";
};
「复杂度分析」
令 n 为数字长度。
。
。
❝提示:如果题目改成求删除 k 个字符之后的最大数,我们只需要将 stack[-1] > digit 中的大于号改成小于号即可。 ❞
大家做完这个题,就可以 AC 下面几个题啦~
最后是我的工具和方法论,主要介绍一下我学习路上的一些好用的工具,以及我是如何刷题的经验分享。
这里我给出一个适合前端同学的一个算法学习路线。
大家可以根据自己的实际情况从不同阶段开始。如果你是刚开始接触算法,我建议你从头开始跟着这个学习路线坚持下去,「我相信一定会有突然间成长的一天」。
大家在学习的过程这一定要及时总结和复习,而写题解就是总结和复习很好的一个途径。我本人写的题解数量已经有「几百篇」了。通过写题解能够加深我对算法的理解能力。下一次碰到相同或者类似的题目,则可以「从大脑中提取更多信息」。
前面提到了要及时复习。而 anki 就是一个帮助你管理复习计划的软件。它是一个能够根据遗忘周期来自动制定复习计划的软件。我在「前期」学习算法的时候制作了一部分的复习卡片,它们帮助了我度过了学习算法最艰难的入门期。
等到你刷了足够数量的题目了,就不需要它们了。但是在前期,它确实可以有效地帮助到你。
最后提一下我自己制作的一个刷题插件,现在有几千个人在用了。通过它可以帮助你更有效率刷题和写题解。
最后推荐一本书大家。《算法第四版》- 一本非常适合初中级选手的算法学习书籍。
这本书给了我很多帮助,少走了一些弯路。这里推荐给大家,希望也可以帮助到正在学习算法的你。这本书我买了好多本,不仅自己看,还送给了我的朋友和学员。
这本书只是让你入门,以及学习一些经典算法。仅靠这个去参加比赛或者 T1 面试是不够的。大家还需要准备一些别的资料。不过我觉得入门是最难的,相信你入门之后就可以自己去挑选学习资料了。比如 oi wiki。
我本人最近也在写一个关于前端算法面试的专栏,目前正在寻找合作平台,如果你是平台方可以微信联系我。如果你对内容感兴趣可以订阅我的公众号《脑洞前端》,第一时间消息会在公众号同步大家。
另外我的 《91 天学算法》第四期已经开始了,活动介绍:https://leetcode-solution.cn/91。
91 天学算法目录
91 天学算法先导篇讲义
91 天学算法基础篇讲义
以上就是本次分享的全部内容了,大家有什么问题的话都可以提,我会尽量回答。