8 个面试应对算法题小技巧!

大家好,春招正处在重要阶段,今天就跟大家分享一些在处理算法题时的技巧和方法,尤其是在面试或者是比赛的时候应付难题的技巧。说不定就可以在关键时刻起到作用。

冷静

首先要说的就是冷静,越是一些重要的节点,越是要冷静。一旦心里慌乱,手足无措,基本上大脑也就不转了,别说超常发挥了,就连正常发挥都不可能。

面试是一个非常容易紧张的场合,即使我参加过数十次面试,也依然免不了会紧张,尤其是一些充满挑战的面试。比如说久负盛名的公司,或者是全英文的面试等等。所以会紧张是正常现象,大佬们也不例外。

在面试之前发现自己紧张,千万不要和这种情绪对抗,想要让自己不紧张,这是很难做到的,而且反而越在意越容易更紧张。我常用的做法是放平心态,发现自己紧张之后,我会告诉自己这是一种正常现象,不给它过多的关注。过一会之后, 不刻意关注这件事,反而会慢慢放松下来。

同样遇到难题的时候也一样,遇到面试官的问题发现没有准备,或者是一时间没有头绪,也难免心慌。这个时候千万要稳住心神,让自己冷静下来。在面试里遇到难题和没有准备的问题也是正常现象,事先可以做一些心理准备和心理建设,这样有助于冷静下来。

大脑思考和个人的发挥都需要一个冷静的环境,这一点非常重要,几乎可以说胜过所有技巧。

挖掘题意

心态建设好了之后,首先要做的是确认题意,保证自己没有理解错,思考了半天,结果发现是题目看错了这种低级错误非常要命。并且确认题意的同时也是一种拖延时间,可以争取更多思考的时间。

确认完了题意之后,我们还可以继续挖掘题意。很多时候出于种种原因,面试官不会给出所有的信息,最常见的就是数据的范围、数组的长度等等。有的时候题目看着很难,但可能范围很小。有的时候能够挖掘出一些潜在信息,比如谷歌面试有一题求 N 个数的前 K 大。你不问,就是这个题面,如果你仔细问, 面试官会告诉你,N 是一个无限大的数据流,而 K 很小。显然这是一个非常关键的信息。

在这个环节我们需要确保两件事,第一我们对题目的理解是正确的,第二,尽可能挖掘出题目中潜在的信息。

分析难点

挖掘完题目意思之后,接下来要做的就是分析难点。

我们觉得一道题目难,比想不出解法更可怕的是无从下手。无从下手时无论如何绞尽脑汁,往往都是无效思考,还是很难做出题目。所以我们要拒绝无效思考,尽量做有效思考。题目难,想不出解法可以,至少得先搞清楚难点在哪里,是什么问题困扰住了我们。

那怎么才能找到难点呢?最常用的套路就是从暴力解法入手,我们先想想最简单的办法,看看最简单的方法当中藏着哪些问题。比如说是复杂度太大了?还是说情况太过复杂,很难简单地枚举?

找到了难点,就有了突破困难找到解法的可能。这里面也有技巧,最常用的技巧就是回到题意本身。很多问题的关键就藏在题意里,我们在对题目含义做进一步分析之后往往总能有所发现。

除了回到题目本身之外,还有其他一些技巧,我们一一来介绍。

正推反推

一般来说,针对题目的解法可以分成两种,一种是正面突破的正推,即针对问题本身进行求解。另外一种是反推,即不直接回答问题,而是构造一种满足题意的情况解决问题。

我们在思考问题的时候可以灵活应用这两种方法,常见的算法当中,像是搜索都是正推的思路。我们正面搜索所有可能性,找到符合条件的解。而动态规划比较侧重反推,我们不是直接枚举可能性,而是通过维护状态的方式寻找局部最优解。状态可以理解成一个人工构造出来的情况,是一种对问题的巧妙解构。

总之,当我们正面强攻遇到困难时不妨思考一下反向突破,直接枚举不行,我们有没有办法构造答案?构造答案比较困难,能不能搜索?

从简单 case 入手

有的时候一个问题过于复杂,我们直接思考某种通项往往不太容易,这个时候可以尝试一下构造一个规模最小的问题,对这个问题进行分析。

虽然规模最小的问题不能囊括所有可能性,但往往可以用来验证和排除一些解法。如果一个方法连最简单的 case 也通过不了,那么显然是错误的。而反过来,如果我们从最简单的 case 上想到了解法,如果进一步证明了它能够覆盖其他所有的情况,那么它就是正解。

而在算法领域当中,证明往往不必那么严谨,有时候甚至可以进行一定程度的猜测或预估。

很多时候与其在面试的时候干想,不如踏踏实实在草稿纸上构造几个简单的 case 研究,往往就能灵光乍现,找到一些方法。

复杂度入手

在刷 LeetCode 的过程当中,有一个非常关键的信息就是数据的范围,因为通过数据范围我们可以推测出正解大概的复杂度范围,这可以过滤掉大量的无用方法。

比如一个类似搜索的问题,如果我们分析一下发现复杂度太大,那么很自然地就可以往动态规划上思考。因为比搜索更快的方法非常有限,动态规划是最常用的一个。

遇到 可以想想排序、线段树、树状数组等数据结构,或者是类似归并排序的分治算法。

套用算法

最后是利用之前累积的经验,这里的经验主要有两种用途。第一是套用一些类似的问题,比如遇到三数之和,你之前做过两数之和的话,就可以套用一下思路,看看能不能将三数之和问题转化成两数之和应用。再比如经典的动态规划背包九讲,如果你认真研究过所有的背包问题,那么凡是动态规划的问题都可以尝试往背包问题上套用。

第二个用途是算法套用,如果你大概知道哪些算法可以解决大概哪一类问题,那么可以直接尝试套用算法。比如遇到动态更新求区间的问题就可以尝试思考线段树,遇到字符串问题可以试试 KMP、后缀树组、Trie 树,遇到求最大最小值的问题,可以思考动态规划、贪心。

有的时候拿算法套问题比从问题反推算法要简单,实际上这也是高手常用的方法。

边界情况

最后是别忘了注意一些边界情况,很多时候我们想出了方法但往往忘了边界情况,这在面试当中是一个很大的扣分项,面试官会因此觉得我们思维不缜密,这会推翻我们之前解出问题带来的好印象。

所以想出了解法是不够的,不要因此满足,别着急分享。再多思考一些边界情况,或者是举一些极端的例子,看看算法能不能覆盖。

如果发现不能覆盖,及时止损,寻找新的方法,如果能覆盖,也要仔细考虑清楚。并且把这些边界的情况也告知面试官知晓,证明我们思维的严密性。

关于这个问题就先聊到这里,当然面试的时候技巧并不只有提到的这些,如果大家还有什么其他的方法,不妨在下方给留言,感谢大家的阅读。

发表评论

后才能评论