首页 文章详情

前端如何搞定算法面试?(非广告)

前端UpUp | 244 2021-04-08 09:48 0 0 0
UniSMS (合一短信)

点击上方蓝字“TianTianUp”关注我
您的关注意义重大


开篇词:为什么要出这个专栏

市面上关于算法学习的书和专栏很多,其中也不乏一些特别优秀的,比如《数据结构与算法之美》,《算法 4》等等。我为什么还要写这么一个专栏呢?主要有以下几个原因:

  • 市面上精准定位前端岗位的算法面试和学习专栏不多

除了算法岗,不同的工程师岗位考察算法面试的范围和难度差异虽然不大(尤其是 Google 这样的大公司),但侧重仍然会有不同。而市面上资料站多是普适性的,不具有针对性。这些资料前端岗位可以看, 后端岗位可以看,算法岗位依然可以看。

以下分析针对的是「非绝对头部互联网公司」,比如 Google,Facebook。对于这些公司。关于头部公司的算法面试难度,方式,题型等,我会在接下来的《头部公司的算法面试》部分进行讨论。

前面提到了不同岗位的侧重点不尽相同的,比如**前端基本不会问 B 树和 B+ 树等,而后端则很可能会被问到。再比如马拉车算法,AC 自动机算法则更多地出现在比赛中,工程师面试的比较少。**由于职业原因, 前端接触树这种数据结构会更多,因此实际面试也会有所侧重。

另外即使同一种题型,不同的岗位难度也会有所差别,从我的经验来看,「前端岗位各大公司考察的难度普遍在力扣题目的简单和中等左右,而后端岗位则基本都是中等,算法岗位则会多一点 hard 题目。」

社招整体感觉对算法的要求比校招低一些

还有就是不同的公司对算法的要求也不一样,一般而言越是竞争激烈的公司,对基础知识,编程能力要求也越高。而算法就可以很好地体现工程师基础知识和编程能力。如果算法面试运用的足够好,则可以对面试者基础知识掌握程度,沟通能力,取舍能力,思维能力等多个维度进行很好的考察。

因此不同岗位算法面试的大纲是不一样的,要想充分利用自己的复习时间,找到一份适合自己的面试大纲就显得非常重要了,我会在「模块三」对这个问题进行更深层次的讨论。

前端算法面试的难度如何?考察的方向是什么?我想这是很多人想知道的,我会在后面的内容进一步对这个问题进行讲解。

  • 以题目为主线,而不是算法思想和背后的原理

市面上的资料多是以题目为主线,串讲一些经典的,常见的题目。讲题目本身是没有问题的, 我本人不排斥这种方法, 好的题目对刷题的性价比是很高的,我也会在模块四结合一些经典的题目来对前面讲的知识进行串讲,这个部分解决的是如何将我提到的算法思想和技巧应用起来 。但是这种方式很容易出现看完之后如果不主动总结消化,就很容易将知识还给老师的情况。因此我认为中讲解重心应该是「算法思想」,培养大家的算法思维。

我的专栏的特色是从算法思想入手,让大家会一类题,挖掘不同题目背后的联系。这还没完,我还会对不同的类别的题目进行对比分析,让你知道类型题目背后的逻辑。这也是为什么我的专栏和市面上大多数的专栏目录不太一样的原因之一。

  • 不够新,实时性不够。

面试的实时性是很高的。可能这几年市场比较饱和,竞争比较激烈,面试难度就会上升,反之会降低,随着公司的发展面试的标准也会变。另外考察的侧重其实也是会变的,比如之前大家考察算法多是排序,手写树,链表等,甚至不少前端对算法的认识就是各种排序算法以及复杂度和稳定性分析。但是最近几年排序考察的比重在不断降低,算法面试考察的方向更多的是类似力扣和牛客的那种题目。具体来说有搜索类,设计类等。

专栏特色

基于以上三个原因,我写下了这个专栏。本专栏有如下特色:

  • 覆盖市面上前端算法面试大部分题型,并提供完整的学习路线。
  • 教你算法思想,不单单只是会了某一道题,而是掌握一类题。
  • 提供算法模板,帮你更快解题更少出错。
  • 提供实用刷题工具和技巧,让你少走弯路,最大化利用自己的时间。
  • 提供面试技巧,在同样的知识的情况下获得更好的面试反馈。

前端算法面试的题型和难度如何?

由于不同的公司,甚至同一家公司不同时间都算法面试的要求都是不一样的,因此我的建议是你可以先去了解一下自己心仪公司的算法面试难度和方向。据我所知, 拼多多,头条,vivo 算法面试的比重会稍微高一点,难度对标力扣的简单和中等题目类型,大部分是原题或者换皮题。而阿里巴巴,有赞问的编程题会更多,比如给你两个版本号,让你判断哪一个是更新的,比如 3.2.1 和 3.3.3,由于 3.3.3 的第二位比 3.2.1 的第二位大,因此 3.3.3 这个版本更新,这个其实在我们日常做工程中是比较实用的一个功能,但是难度不大,考察的是思维严密程度和基础编程能力。

前端算法题的难度实际上并不高,大家不要太担心算法太难学不会。我多次出去面试的经验以及网上的数据都可以说明这一点,甚至一个简单的链表和动态规划都可以让面试官对我留下深刻的映像(公司前端规模都是上百号的)。通过我的经验以及网上的各种面经和题库我还发现,关于前端面试中的算法不仅难度在简单和中等左右,并且中等的题目类型也是搜索和动态规划偏多。这告诉我们前端同学准备算法面试应该在这两个模块投入更多时间。

接下来,结合我个人以及从广大网友的亲身面试经验来看下各大公司对前端算法的考察方向和难度。

我个人面试的公司有阿里,头条,网易等大公司,也有 GrowingIO,e 签宝,曹操专车,大搜车,贝贝集团等互联网独角兽公司。这其中有的公司甚至压根没有算法面试。

我这里列举我出去面试被问到的部分算法题目。

  1. 不借助四则运算实现两数相加
  2. 爬楼梯变种
  3. 链表反转
  4. 链表倒数第 k 个节点(要求 one pass)
  5. 硬币找零
  6. 用 int32 序列化 和 反序列化 IPV4
  7. 质数筛选

可以看出,从题目范围看,基本都是力扣原题。从题目难度来看,基本是简单和中等,实际上除了硬币找零是中等难度,其他都是简单。从题型来看,有两个动态规划(2 和 5),两个双指针(3 和 4),两个位运算(1 和 6)和 一个数学。

私底下不断有朋友和我交流各个公司的面试题。有的是碰到了不会的面试题来问我有没有好的思路。有的则是恰好面试碰到了原题来我这里“还愿”。从广大网友的面试经历上看,前端岗位面试的题目类型“搜索”, “暴力优化” 和“双指针”,题目难度也主要是简单和中等。这和我的面试经历的重合度还是蛮高的。这里的搜索主要是 DFS,BFS,动态规划和回溯。“暴力优化” 指的是 剪枝,滑动窗口,双指针,单调栈。这三种题型基本占据了 70% 以上的比例,这三个题型同样也是本专栏的主要内容。

以网易 2021 校招的题目为例,我们实际地看下算法笔试题目的类型和难度:

第一题:

小易今天读了一篇英文文章,他现在想从里面找出一个单词作为这篇文章的关键词。一个单词可以作为个关键词当且仅当它在这篇文章中出现的频率不低于 1%,现在他想知道有多少个不同的单词可以作为关键词。

这个题目比较简单,只要掌握基础的数据结构即可解决。我们只需要统计每一个单词的出现次数和总的单词数即可,这种做法的时间和空间复杂度为 ,其中  为 文章的字符总数。

图 1

第二题(2020 年也是这个题):

在一次聚会上,教授们被要求写下他们认可哪位教授的研究成果(也可以写自己,且可能出现重复)。已知,如果教授 A 认可 教授 B,且教授 B 认可教授 C,那么可认为 教授 A 认可 教授 C。现在我们想知道有多少对教授是两两相互认可的?

这是一个典型的图的搜索的题目,此问题可以转化为在一个有向图中求强连通分量,然后统计所有强连通分量中去重的边数目。而关于强连通分量的算法主要有 osaraju 算法,Tarjan 算法和 Gabow 算法,这道题可以使用这三种算法的任意一种简化版即可。然而这种题目在前端算法面试中出现的比例相对比较低。

图 2

第三题:

牛牛有一块 2 * n 的空白瓷砖,并且有 1 * 2 和 2 * 3 两种类型的地毯(地毯可以旋转)。现在他想满足以下条件:

- 瓷砖需要被铺满
- 地毯之间没有重叠
- 地毯不能铺出瓷砖外

求一共有多少种铺地毯的方案,由于结果可能很大,因此你需要返回结果取模 10007。

这是一个爬楼梯的变种题。

由于铺 2 * n 的空白瓷砖就相当于:

  1. 先铺  的空白瓷砖,然后铺一块  的地毯。
  2. 先铺  的空白瓷砖,然后铺一块  的地毯。
  3. 先铺  的空白瓷砖,然后铺一块  的地毯(相当于  的瓷砖旋转一下)。

图 3

因此铺 2 * n 的空白瓷砖的总方案数就是这三种情况之和。如果用 f(n) 表示 2 * n 的空白瓷砖一种有多少种铺地毯的方案的话,那么状态转移方程就是 f(n) = f(n - 1) + f(n - 2) + f(n - 3)

第四题:

有三种难度的睡目难度分别为 Easy,Medium,Hard。现在你总共有 E + EM + M + MH + H 道题。

各个字符串的含义如下:

- E 表示有 E 道题目难度为 Easy.
- EM 表示有 M 道题目难度可以为 Easy 或 Medium.
- M 表示有 M 道题目难度为 Medium。
- MH 表示有 MH 道越目难度可以为 Medium 或 Hard,
- H 表示有 H 道题目难度为 Hard,

你要用这些题目出尽可能多的模拟赛,为了保证题目质,且含有一定的区分度,每场模拟赛要包含 Easy,Medium,Hard 三种难度的题目各一道。求你.多能出多少场模拟赛.

使用 f(E, EM, M, MH, H) 对原问题进行抽象。

这道题可以使用暴力枚举搜索, 这种时间复杂度是指数。

图 4

伪代码:

function t(E, EM, M, MH, H{
  if (E < 1 && EM < 1return 0;
  if (EM < 1 && M < 1 && MH < 1return 0;
  if (H < 1return 0;
  return 1 + max(六种情况);
}

我们也可以枚举所有的题目组合,这种时间复杂度是多项式。而实际上,只有 EM 和 MH 可以表示多种题目,我们不妨假设 EM 中有 i 道 简单,那么中等就是 EM - i,同理 MH 也是一样的,因此所有的可能其实就是  种,也就是说只需要枚举  即可,时间复杂度为 

图 5

代码:

function t(E, EM, M, MH, H{
  let ans = 0;
  for (let i = 0; i <= EM; i++) {
    for (j = 0; j <= MH; j++) {
      ans = Math.max(ans, Math.min(E + i, M + EM - i + j, H + MH - j));
    }
  }
  return ans;
}

可以看出这四道题有「两个是搜索题,一个是简单的数据结构题目,一个是图论」。这不是一个巧合,实际上搜索题目确实是重点题型。我个人还总结了大量公司的真题,基本都是“搜索”, “暴力优化” 和“双指针”,这类题目的比重差不多可以到 70%。除此之外会有一些数学题,设计题等,不过比重不大。而像线段树,KMP,马拉车,跳表就等属于比较冷门的题,以及一些其他岗位常有的题目比如并查集等,在前端面试基本不会出现,大家可以根据自己的情况合理安排复习时间。

头部公司的算法面试

最后我补充一下注重算法的大公司对算法面试的要求。以 Google 为例, 通常会有四个编程面试,并至少有一个是系统设计面试。我们来看下:

他们大多会要求你先在白板上写出设计方案,伪代码,然后对算法复杂度进行分析。同时面试官会不断提问(或者提示)你让你写出更优的解决方案。如果有多个问题,一般也是难度层层递进,有的直接会是上一题的 follow up。一种 follow up 是题目条件限制的变化,比如上一题我问的是两数和,下一题可能就是三数和,再下一题可能是 k 数和这样。另一种是算法性能的优化,让你尝试写出时间复杂度,空间复杂度更优的解法。比如求最长公共前缀,如果你用暴力法解决出来了,通常会让你用二分或者分治再次解决。

另一种是生活中的场景题(就是我前面提到的设计题),而不是具体的算法题目。比如经典的《如何设计 Twitter》,《实现短链接系统》,《设计 Google Docs》等。这需要你对问题进行抽象为算法模型, 然后用代码来解决。这种题目, 需要反复和面试官去沟通和确认细节。难度的话大概是中等和困难,大多是力扣等 OJ 平台问题的变种题(原题的概率极低=-)。但正如我上面所说,真的不是你做出来就行了,而是你需要对这类问题吃透才能过关。

还有一种是改错或者优化题目。给你一个有 bug 或者写的很烂的代码,让你优化。考察的是编码风格,debug 能力。

就题型来说,也会比其他公司的稍微广泛一些, 可能会涉及到 Dijkstra 和 A* 等等。

这里有一个寻路算法可视化网站,有助于帮助大家理解这些算法。https://clementmihailescu.github.io/Pathfinding-Visualizer/#

面试结束后,通常面试官都会写下一份报告,其中不仅包含了面试过程所有细节和讨论,甚至包括每个部分花费了多少时间,有没有提示,以及提示之后的反应,招聘委员负责根据这些报告进行决策。

为了满足大多数人的学习和面试需求, 本专栏不会覆盖太多困难难度的题目,也不会深入不太热门的算法类型。不过这里推荐一份我认为不错的学习资料 Coding Interview University。这个指南使用大部分头部公司,包括但不限于 Google,Facebook,Uber,Amazon,Airbnb。

总结

我们的专栏不讲编程题, 比如我前面提到的版本号匹配。编程题考察的就是我的基础编程能力,一般都是给你描述一个算法步骤,让你用代码来描述出来。而我们的专栏侧重的是经典的算法思想和高频面试题,这点大家需要注意。

对于算法面试我们总结一下:前端算法面试思想上注意考察“搜索”, “暴力优化” 和“双指针”。另外数据结构基础上,树,队列,栈的理解和应用。而递归的使用也是重点,这也不能理解,毕竟 DOM , VDOM,省市区级联选择器等都是树,而树本身就是一种递归的数据结构,使用递归来对树进行搜索是非常符合直觉的。队列和栈在前端出现的也非常多,比如消息队列,浏览器的历史记录等。链表在前端日常开发也有出现的机会,远到 react 的 fiber ,近到原型链都是链表的应用,数据结构与算法在前端领域的应用可以参考我之前写的专题。

以下是专栏的模块安排:

  • 模块一讲解的基础知识。包括基础的数据结构,复杂度分析,以及基础的排序算法。另外还有一个非常好用的技巧 - 递归。这都是学习后面内容的基础。
  • 模块二是算法思想。包括搜索(深度优先遍历,广度优先遍历,回溯),暴力优化(剪枝,前缀树,,滑动窗口,单调栈,双指针),动态规划,分治以及贪心。
  • 模块三是学习路线。我应该先刷什么类型的题目?是按类型还是按顺序?有哪些不得不刷的经典题?这部分给你答案。
  • 模块四是高频大厂面试题解析。主要是将前面讲的内容融会贯通,即如何将前面学的思想用到实际题目中去。
  • 模块五是刷题方法和工具。这个是帮助大家提供刷题效率的,让你用更短的时间,获得更好的效果。
  • 最后是彩蛋: 一些算法面试小技巧。在同样的知识水平前提下, 如何获得更好的表现?让我来告诉你!

END



如果觉得这篇文章还不错
点击下面卡片关注我
来个【分享、点赞、在看】三连支持一下吧

   “分享、点赞在看” 支持一波  

good-icon 0
favorite-icon 0
收藏
回复数量: 0
    暂无评论~~
    Ctrl+Enter