目录

当我们谈论刷题时,到底在刷什么

在上一篇文章 半年零基础到 LeetCode 300 题,我的算法学习方法论 中我们总结了算法与数据结构的学习方法论,提供了一个算法学习的 big picture。然而算法毕竟只是 semantic 的思想,具体还是要落实到 implementation 层面上。

功利一点来说,算法学习的最终目的还是要能够在面试中完成题目,拿到心仪的 offer。那么今天我们就来讨论一下究竟要如何练习,以及我们在刷题时到底在刷什么

1. 为什么要刷题?

我们经常听到『xxx 刷了几百题』的故事,『找工作就是刷题』的说法,因此我们也打开 LeetCode,开始加入刷题大军。然而我们有没有思考过,为什么要刷题呢

面试需要

这一点无可厚非,大部分面试的考察方式 Technical Interview 都是算法题目面试。可是为什么科技公司都喜欢算法面试呢?因为和高考一样,算法面试是一种有效筛选候选人的流程化方式。

那么,科技公司想要招的就是算法题目做的又快又好的做题家吗?当然不是。那么考算法题到底想要考察我们什么呢?

Problem-solving 能力

面试是为了招人,不是高考入学考试,不是考研,是为了招你进去干活,所以需要能够招聘到可以胜任工作的 candidate,需要招一个可以做 teammate 的人。实际日常开发工作中可能算法都不会用多少,但是需要你有严谨的思维逻辑,需要你有比较强的解决问题的能力,能够在规定时间内干完活交工。但是面试那么短的时间,如何衡量你的解决问题的能力?算法题这就有了用武之处,除此之外,技术类设计问题也是解决问题的另一大考量。

算法题目是给定你一个小的 scope,有一个现有的 feature,给定一个 API 的接口,输入和输出要求,需要你设计内部的底层逻辑,能够让这个 API 正常工作,接收输入正确地得到输出。实际面试题目很多也都是实际工作中的场景,比如 Binary Search 找 bug 在哪里,网页浏览器搜索时如何将字符串中空格 encoding,发送数据时如何将 Tree 序列化反序列化等等。

图片

这个过程就需要你分析问题,思考问题,提出方案,并在规定时间内解决问题。如果你表现良好,那么这是一个合格的 candidate。不能说这种方法一定准确,但是却不失为一种比较合理的标准化流程化的筛选方式。

工程设计能力

而设计类问题如 Object-oriented Design (OOD) 面向对象程序设计及系统设计则是在更大的 scope 上考察你,从一个 API 上升到一个 Project 的系统,甚至整个 service 的系统。给定一个业务需求,如何设计整个程序系统,或设计一个内部使用的数据结构,service 系统搭建设计等,这部分考察的其实也是 problem-solving 能力,不过是需要 CS domain knowledge 和相关经验的能力考察,需要有比较好抽象建模能力,分析能力,对技术有所了解。在实际写这种『类算法题』的时候更需要考虑需求 use case 及实际情况,这种时候就非常需要有比较好的整体性工程思维及 tradeoff 能力

归根到底,几轮 45 分钟的面试也无法保证我完全了解你这个人,但是大部分情况下可以保证我不会招错人。哪怕没有那么聪明出众,但是几轮综合考虑显示出你是一个能够胜任这份工作,能够干活的人就够了。

代码基本功底

这点自然是不必说,招你就是为了写代码,规定时间内小代码都写不完,如何 convince 面试官你可以在日常工作中写完代码。同时高压状态下你的 coding style,变量命名,备注习惯等更是把你真实的代码基本功暴露得一览无余。编程写了多久,你的熟练程度,都能从代码看出来。从能写出能用的代码,到写出好看的代码,再到写出高效优雅的代码,那么在面试官心里的评价也自然有了结果。

培养 CS sense 和思维的方式

转专业总会有一个苦恼的点,我没有 CS 本科,也没有上过专业基础课,没有一点 CS sense 怎么办。这个问题我也一直有,毕竟自己真的转专业到 CS 也就一年不到就毕业了,感觉学校都是些高阶理论证明课也没学会什么。但是在刷了一段算法题目后,我发现很多东西都慢慢开始理解,串接起来,逐渐地潜移默化养成了一个更缜密严谨的思维方式。

就像我前一篇文章中所讲的,Recursion 思维不仅存在于算法,Top-down 的思路再生活中比比皆是。如何从 big picture 细化,如何 Top-down 进行规划,如何先得到一个 Minimum Viable Product 再不断 fine-tune 优化,再 dive 到细节。解决问题如此,学习 CS 也更是如此。

数据结构与算法是最 fundamental 的知识,很多知识体系都与之相关,可以延伸扩展。我们本来就没有一个比较扎实的功底,刷算法题其实一定程度上帮助我们在做这件事情。

刷题是为了学习巩固数据结构算法

我一直觉得不能本末倒置,『不要为了刷题而去刷题』。我们想多刷题,做到面试原题等面试直接秒杀,这固然没有问题。但是并没有那么多好运气落在你头上,很多时候题目可能你没有做过,或者做过忘了,或者面试官改了题目,有更难的 follow-up,那么题海战术就没那么有效了。

我还记得我刚来美国时候学开车的时候,师兄带我学开车。我从来没开过车,所以刚开始学习时候特别小心好学。第一个晚上后,我觉得自己已经开得比较不错了,有点小骄傲。第二个晚上的时候基本开得很好了,我说我要不去考路考吧。师兄说『你考了路考然后呢?练车是为了能够正常出行,能够自己开车在村里生活,考驾照只是一个证明而已。趁着我最近还能带你,我坐副驾你多带我在村里逛逛,能够正常出行我就回去忙了』。突然觉得自己有点急功近利,最后又练了 2 个晚上去超市到处逛逛后才去考了驾照。

刷题感觉也是如此。学车是为了掌握这门技能,并不是说没有驾照就不会开车。刷题的原因是因为我们不熟悉数据结构与算法,因此需要学习和巩固,算法题目刚好是一个可以练习巩固同时可以增加代码经验的过程,整个过程是为了提高自己的思维能力和算法逻辑,而不是为了过面试而背题。车技好了驾照考试想挂都难,算法能力提高了面试也只是一个检验。真正以后想要走多远,理解有多深,需要这个过程扎实学习打好基础。

讲了这么多务虚的东西,我们下面来实际讨论下刷题到底在刷什么,以及该怎么刷。

2. 刷题到底在刷什么?

上面我们谈到了 Problem-sovling 的能力,我们实际练习过程中也是需要自己刻意练习这些能力,这样在面试时才不会紧张或第一次被问到而发懵。面试过程中和算法一起贯穿其中的,其实比算法能力更重要的是 communication skills,这也是我们一般练习时所忽视的。

Clarification

我在 LinkedIn 上和一些 SDE 聊天,给我的第一个建议就是,一定要做好 clarification。他们表示最烦遇到的 candidate 上来就直接写代码,要么是几分钟将题目秒了的 LeetCoder,要么是不怎么会做也不知道问什么,无论哪一种都很尴尬。

面试不是一个考试,是一个双向的过程。其实将面试理解为面试官想要来找一个合适的队友,因此 45 分钟和你一起来模拟实际工作场景遇到的一个问题,一起讨论,tradeoff 将题目做出来的过程,就没有那么紧张了。大部分面试官也是希望你能够拿到 offer 的,因此也会愿意去给 hint 帮助你,如果你都不去问不去交流就自己放弃了这个机会。如果一上来都不 calrify 问题就上来三下五除二,面试官当然有理由怀疑你做过题目或背了答案,旁边打开了 LeetCode 答案。

因此适当交流,问清题目需求和 assumptions,可能的 corner case,input 的特点,data type,甚至可以 rephrase 一下自己的理解,既是给自己争取思考的时间,同时也在 show off 你的逻辑分析能力。和面试官有来有回,了解清楚想要优化什么,空间还是时间,了解面试官想要的 solution,再开始 dive deep。

Think loud

面试过程中闷头写代码也是非常 red flag 的行为。就像前文所说,这是相互交流双向的过程,因此闷头直接写完代码就和让面试官现场看一个自动 typing 的 LeetCode discussion 一样索然无味,而且完全有理由怀疑你是抄的答案。

因此在写代码前,和面试官 go through 你的思考,如何思考这个题目。提出 high-level 的 solution,搞清楚大方向,再思考如何从 brute force 的解法来入手,不断优化。根据面试官的沟通反馈,决定到底是优化哪一方面,或者有没有雷区,做 tradeoff,最终得到 optimal solution。实际面试中面试官有的时候也不一定要求写出最优解,但是中间这个思考的过程就是展示自己的时刻。如果我们只是为了写出代码,反而错过了给面试官留下印象的时刻。

Document your trajectory

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-remind1.png
我的做题笔记

在 think loud 的过程中我们可能会越讲越嗨,但是后面写题目代码时可能因为某一节忘记,或代码过于复杂最终 lost 了,导致写题目时越写越懵逼,再加之时间紧张,越懵逼越紧张,最后就凉了。我们实际学习中,讨论题目时也往往会这样,刚刚明明想明白了,突然就忘记了。

因此我个人的建议是在 show your trjectory 时同时 document your steps。好记性不如烂笔头,在讲解思路时可以先用 comment 记录下自己的关键步骤,每一步的梗概,讨论时提到的细节,或者需要后续优化讨论的点。这样即使我们讨论完,回去时仍然还是有一个比较清晰的文档帮助我们完成 implementation。题目复杂时甚至可以做一点 demo,这样自己写的时候也会有迹可循

Proof read and test

写完代码时并没有完事,面试官急切地问你是否写完了可能是他发现了一个 bug 而你浑然不知。不要将指出错误的机会留给对方,如果自己找到 bug 并修复了错误,那么说明你是一个有经验的 candidate。但是由对方发现,可能面试 feedback 里的就是粗心不扎实不熟练等等。

因此在写完后一定要做 proof read,检查一遍是否是自己想要表达的 semantic,是否有 typo,调用函数时传参是否正确,有没有缺少 return statement,有没有逻辑问题

最后主动用 test case 来 demo 你的 code,看是否可以正确输出。如果你在 demo 时找到了自己的 bug,那么你赚到了。同时 test 也是一个好的 engineer 素养,也更能 show off 自己扎实 skills。

Analysis and optimzation

算法写完后很多人可能就松了一口气,可是这并没完,要趁胜追击。

主动去分析时间复杂度和空间复杂度,可以边分析边做一些 document,并 proof 你的 complexity analysis

根据时间复杂度,可以提供后续的优化,以及自己主动可以展示一些自己的思考,算法的 tradeoff。如果这道题你之前做过,完全可以展示出自己的深度。再根据面试官的沟通,决定后续的分析及操作等。

OK。那么问题来了,这些我该如何练习呢?我的方法是记录做题笔记。

3. 做题笔记练习

我的题目都在 Notion 进行记录,复习和总结。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-table1.png
我的笔记库

每道题都有标签分类,以及掌握程度,根据记忆曲线计算下一层 review 得时间,重复次数等等。由于 Notion 可以创建 template,因此可以节省很多时间。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-template1.png
Notion customized template

那么做题笔记记录什么?

做题思路

做题笔记中记录自己如何 think out 这个题目,比较难,比较重要的题目第一次做可以记录详细一点,这样下次复习得时候你会节省很多功夫。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-note12.png
Reconstruct Binary Tree 笔记

Notion 支持各种语法高亮,Latex,颜色设置,因此做代码笔记非常方便。同时要记录一下自己刚看到题目时如何进行 clarification,强迫自己去思考 Corner case,有考虑到哪些 case,哪些没考虑到。

答案代码

代码自然是不必说,随手的事。不过我想说的是注意一些细节的 comment,往往复习时这些点会卡很久,而且面试需要重点注意。代码 local 局部的批注会比笔记更加 handy 一些。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-code2.png
细节的 comment

做题边练习讲解

在自己练习时,我后期就开始刻意让自己每次都 mock 在面试一样,先讲思路并 document 我的思路批注,如下图。之后再限时 implement 代码,压力下的训练会更有成效。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int shortestDistance(int[][] grid) {
    // corner case
  
  	// for for loop -> bfs on each cell to update dist
		for for {
      	bfs();
    }
    // after updated, find the shortest distance
}

// bfs to start from one building to find distance to each land
private boolean bfs() {
    // assumption: valid
  	boolean[][] visited;
		Queue<>;

    while (!queue.isEmpty()) {
        // for each level
      	// update cost, mark visited, add neighbor
    }
    // post process for pruning
  	for for {
      	// exclude not reachable building
    }
}

刻意训练分类讨论的能力

小时候学数学时经常各种分类讨论,长大后反而不怎么用。算法题中的 case 讨论真的是非常有帮助,当你分析时了解了所有的 case,那么你写代码就只是写作文一样。我觉得代码能力和算法能力是分开的,会做和会写还是有不小区别,因此要针对自己情况,选择弱项强化,不能有短板。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-cases1.png
分类讨论

最终看着这些分析,写代码就和将汉语翻译为英文一样,没什么区别。

一图胜千言

很多时候的死磕,脑海中打架,都不如画图来得简单直接。可能因为自己以前 research 时经常纠结示意图,感觉很多时候一张图可以将思路说得明明白白,复杂度分析都变得简单了起来。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-graph21.jpeg
DESK Recursion Tree

复杂度分析及推导

复杂度分析非常重要,最关键的是你怎么得到的这个复杂度结果。分析清楚时间和空间复杂度,比较重要的题目一题多解了解各个算法的优缺点,trade off 了然于胸,才是做透了这类题目。

https://cdn.jsdelivr.net/gh/mustpic/imghost/img/1-time1.png
时间复杂度分析

4. Summary

本文分享了刷题和找工作过程中自己的一些思考和准备技巧,希望对你有所帮助。如果有帮助的话,欢迎分享给更多的人。

欢迎关注我的微信公众号『董小染』。

/images/qrcode.png