本文写作于 2016 年，在小专栏发表。2024 年对其进行整理并迁移至此处博客。
本文并非要讲高深算法，只是从算法面试角度出发，着重分享算法基础知识以及算法面试的总结。倘若将这些基础夯实，那么应付一般开发岗位的算法面试是足够的。
我的面试经历简述如下：2015 年我参与了激烈的互联网秋招。当年校招的头等大事是“阿里缩招”事件。在西溪园区实习了两个月后，我不幸迎来了变化。9 月份回到学校，我开始投递简历。之后陆续获得了腾讯、华为、美团、魅族、360、京东、爱奇艺、完美、猿题库等公司的 offer。我最终选择了魅族的工作机会。在魅族的 Flyme 核心系统组工作了大概半年的时间。之后，我更换了工作，来到了深圳的鹅厂。到现在，差不多已经有一年的鹅厂工作经历了。那年我创作了一篇文章叫“阿里宝宝漫漫求职路”，这篇文章意外地在全网迅速走红。之后，在朋友的提议下，我删除了那篇稿子中的面试相关内容，仅仅留下了自己当年在准备面试时所写下的知识总结。如果感兴趣的话，可以去查看 AndroidInterviews，其中的总结以及我自己博客里的一些读书笔记，基本上已经涵盖了大部分的 Android 基础知识和常见的面试题。非常建议你看下，也许看完了你就是“offer收割机”咯。
下面的内容主要分为三部分：其一，是算法基础知识总结，此部分内容相对较多；其二，是算法面试经验分享，该部分内容与实际算法面试相关；其三，是附加的一些面试经验分享，期望能对大家的求职之路有所助益。
1. 算法基础知识总结
俗话说，“不积累一步半步的行程，就没有办法达到千里之远”。要想在算法面试中取得成功，首先就必须把算法基础打扎实。
三是常见的算法思想，在常见的算法思想中，有递归、分治、贪心、动规等。
很明显，一篇文章无法将所有算法基础知识都整理完备。接下来，我们主要从算法面试的视角出发，逐个谈论这些算法基础知识。许多其他的算法，像图中的算法，以及算法思想，如回溯、分支限界等，都未在本文中予以介绍。
2014 年春季，我在学校修习了算法分析这门课程。在这期间，我断断续续地看了大半本《算法导论》。2014 年夏季，我坐在寝室里，将《Python Algorithms》这本书读完了。后来，我在自己的博客上撰写了关于 Python 数据结构与算法设计的系列文章。这些文章总计约有十几篇。当时，这些文章被微博大 V“Google 谷歌爱好者”转发了，并且还被赐予了一个新的名字，叫做“码农与蛇的故事”。我很喜欢这个名字。当然，更让我高兴的是，当时我的个人博客首次迎来了如此大的访问量。
1.1 常见的数据结构及其实现
大家都知道，数据结构是算法的基础。如果不懂得二叉堆这个数据结构，又怎么能够写出堆排序算法呢？
常见的数据结构包含数组、链表、栈、队列、二叉堆、树、图等。在这些数据结构中，栈和队列的题目时常出现在笔试试卷里。同时，在实际的算法面试中，二叉堆和图被考到的情况很少，经常出现的是数组、链表以及二叉树这几种数据结构类型的题目。
数组是最基础的数据结构，然而能考的内容却极为丰富。比如有最常见的排序算法，还有找数组中第 k 大的数字，以及找两个有序数组的中位数等。
我的面试经历如下：美团的二面遇到了合并排序这一问题；友盟的实习生面试二面遇到了要找出两个有序数组的中位数这一情况。
链表因其独特的结构而成为常考的内容，比如对链表进行反转、对链表元素进行排序、将两个有序链表进行合并、判断链表是否存在环以及如果有环的话环的起始位置在哪里等
[我的面试经历：腾讯实习生笔试题遇到判断链表是否有环]
二叉树具有天然的递归结构，所以它是最适合考查递归思想的数据结构。比如可以用它来判断二叉树是否平衡，也可以用它来判断二叉树是否相同，还可以用它来判断二叉树是否对称等。
我的面试经历中，在神马实习生一面时遇到了要判断二叉树是否是平衡二叉树这个问题。
栈和队列是很重要的数据结构。不过，它们通常只是作为前期的笔试题。栈经常出现的题目是给出一个栈的入栈序列，然后询问下面哪个序列不可能是这个栈的出栈序列。栈和队列作为算法题的数量并不多，常见的情况有：如何用两个栈来实现一个队列；如何利用一个辅助栈来对一个栈中的元素进行排序。
我的面试经历中，有道一面遇到了这样的情况：利用一个辅助栈来对一个栈中的元素进行排序。
一般而言，开发岗位的算法面试不会出题让面试者临时去设计一个数据结构以解决某个问题。在大多数情况下，只是要求面试者能够对常见的数据结构及其实现熟练掌握，并且能够说出这种数据结构的优缺点。
2015 年校招期间，我遇到的最为常见被问到的题目是实现 LRU 缓存。这可以算作是一道经典的数据结构设计类题目。在那之后的面试中，我几乎再也没有见到过其他类似的数据结构设计题。
1.2 算法时间复杂度的计算
在一般的算法面试中，面试官在你给出解法后，通常会询问你这个解法的时间复杂度是多少。如果时间复杂度较高，他就会要求你想出一个更优的解法。因此，平时有必要进行算法时间复杂度的练习。算法的运行时间主要有三种表示符号，其中最常见的是大 O 表示法。算法导论介绍了三种时间复杂度的计算方法。一种是代换法。另一种是递归树法。还有一种是主定理法。
nlgn 阶时间复杂度是随机数字序列的最优排序算法的时间复杂度，例如快速排序等。
这个建议结合具体例子来记忆，以便能快速反应。
下表呈现了主定理法在三种情形下的求值公式。主定理一般能够处理诸如 T(n) = a T(n/b) + f(n)这样的递归形式的问题，也就是把规模为 n 的问题分成 a 个子问题，每个子问题的规模是 n/b，其中 a 和 b 为正常数，划分原问题以及合并结果所耗费的代价由函数 f(n)来描述。
Sign up for Indie Maker Hu
Subscribe
No spam. Unsubscribe anytime.
1.3 常见的算法思想
Induction 即推导；Recursion 为递归；Reduction 是规约；Divide and Conquer 指分治。
这四个思想较为相近，在《Python Algorithms》这本书里均有提及，我将它们放在一起进行介绍。
可以发现，Induction（推导）与 Recursion（递归）是相互对应的。Induction 是从下往上进行推导，就像从 n - 1 推到 n 那样；而 Recursion 是从上往下进行递归，如同从 n 到 n - 1 这般。
仔细分析可以看出，Induction（推导）、Recursion（递归）以及Divide and Conquer（分治）实际上都属于某种特定形式的Reduction（规约）。这意味着它们的本质都是对问题实施规约。
这四个概念存在一个共同的特点，那就是它们都将注意力集中在求出目标解的某一个步骤上。我们只需认真思考这一步骤，其余的部分就能够自动完成。你是不是有点晕了呢？其实，你或许已经对上面提到的几个概念相当熟悉了，只是平日里没有以这样的方式去思考过。接下来，我们以最常见的排序问题为例，来对其中的算法思想进行阐述。
我们怎样对排序问题进行 Reduction 呢？显然，存在着许多种方式：
我们学过的排序算法经过这样的处理后，基本上都变得很清晰了，不是吗？怎么样呢？
为了能够对问题使用归纳法或者递归法，归约法通常是把一个问题转变为另一个或者几个只是规模变小了的相同问题。那么，这样做就一切顺利了吗？
其实不是这样的。有时候我们得考虑 Reduction 或者分治策略的子问题平衡性。对于同一个问题，分治时若采用 T(n)=T(n-1)+T(1)+n 这种解决方案，与采用 T(n)=2T(n/2)+n 这种解决方案，它们的时间复杂度是不一样的，这里就不详细展开讲了。
（2） 贪心
贪心算法的意思是每次都选择当前看起来最好的那个（局部最优解），不会去思考后续的情况，并且一旦做出选择就不能再更改。倘若原问题具备贪心选择性质以及最优子结构，那么最终得到的解就是最优解。
贪心算法与其他算法存在明显区别。动态规划每次会综合所有子问题的解来得到当前的最优解（全局最优解），并非贪心地进行选择。回溯法是尝试选择一条路径，倘若选择错误，能够“反悔”，即回过头重新选择其他路径试试。
说明贪心算法思想最典型的问题是背包问题，大家对这个问题都很熟悉，且该问题有很多变种，常见的有整数背包和部分背包问题。大致情况是这样的：现在要把一些物品装进一个书包里，每样物品都有一定的重量 w 和价值 v，然而书包的承重量是有限的，所以需要做出决策，即怎样选择物品才能使最终的价值达到最大。整数背包意味着一个物品只有拿或不拿这两种情况，例如茶杯或者台灯等。部分背包问题则是指一个物品可以拿其中的一部分，就像一袋子苹果装不下时可以只装半袋子苹果。更加复杂的版本是每个物品都有特定的体积，并且书包也有体积的限制等。
部分背包问题显然可以用贪心法求解。我们先计算每个物品的单位重量价值，接着将这些价值降序排序。然后开始拿物品，若能装下全部该类物品就全部装进去，若不能全部装下则装部分进去，直到书包载重量满为止。这种策略肯定是正确的。
但是，贪心策略不能用于整数背包问题。整数背包问题可分为两种情况：其一，每类物品的数量是有限的，例如仅有 3 个茶杯和 2 个台灯；其二，每类物品的数量是无限的，即你想要多少就有多少。这两种情况都不能运用贪心策略。0 - 1 背包问题属于典型的第一种整数背包问题。通过看算法导论上的这个例子就能明白，在(b)的情况里，尽管物品 1 单位重量的价值是最大的，然而任何包含物品 1 的选择，其价值都没有超过选择物品 2 和物品 3 所得到的最优解 220；而在(c)的情况中，能够达到的最大价值是 240。
贪心算法相对来说比较容易想到。真正困难的在于如何去证明这种贪心策略是正确的，以及贪心算法的内在原理“拟阵”，这些我已经忘得很彻底了。建议去刷一下 LeetCode 上的贪心题，不过在实际的算法面试中，贪心题出现的频率是比较低的。
（3） 动规
动态规划是一个连续决策的过程。每次决策时，我们可能有多种选择，比如在 0 - 1 背包问题中，我们只有拿这个物品和不拿这个物品这两个选择。我们每次都选择最好的那个作为我们的决策。所以，动态规划的时间复杂度与子问题的个数以及子问题的选择个数有关。一般情况下，动态规划算法的时间复杂度是子问题个数与子问题选择个数的乘积。
动态规划有两种实现方式：
而迭代实现则需要考虑计算顺序，且该顺序十分重要，算法在运行过程中要确保当前要计算的问题中的子问题的解已预先求解好。
下面我们以有向无环图的单源最短路径问题为例，来对比动规的两种实现方式。
假设有一个如图所示的图。我们看到的是，这个有向无环图是经过拓扑排序后的结果。从 a 到 f 的最短路径用灰色标明了。
我们有两种思考方式：
从哪里出发呢？我们采用顺向思维。首先假定从 a 点出发到所有其他点的距离均为无穷大。接着，依据拓扑排序的顺序，从 a 点开始出发。随后，更新 a 点能够抵达的其他点的距离，其中包括 b 点和 f 点。b 点的距离变为 2，f 点的距离变为 9。这个有向无环图经过了拓扑排序，按照拓扑顺序访问所有的点（到目标点停止），就能得到 a 点到已访问点的最短距离。也就是说，到达某个点时，就找到了从 a 点到该点的最短距离。拓扑排序保证后面的点不指向前面的点，所以访问到后面的点时，不可能再更新其前面点的最短距离。这种思维方式的代码实现就是迭代版本。
用图来表示计算过程就是下面所示：
“从何处而来？”我们进行逆向思考，目标是到达 f 点，那么从 a 点经过哪个点到达 f 点会更近呢？只能去求解从 a 点出发能够到达的那些点中哪个距离 f 点更近。这里 a 点能够到达 b 点和 f 点，f 点到自身距离是 0，但 a 点到 f 点的距离是 9，可能不是最近的路径，所以还要看 b 点到 f 点有多近。看 b 点到 f 点有多近，就是求解从 b 点出发能够到达的那些点中哪个距离 f 点更近，这样又绕了回来，也就是进行递归，直到我们能够回答从 a 点经过哪个点到 f 点会更近。这种思维方式的代码实现就是递归版本。
用图来表示计算过程就如下图所示：
动规算法在紧张的算法面试时不易被想出来。个人觉得需要多进行练习，接着要学会列出动规的递推公式，还要处理好边界情况，最后选择合适的实现方式来实现它。在实际的算法面试中，如果遇到水平较高的面试官，是有可能出到动规题的，其中最常见的动规题类型有最长公共子序列和最长递增子序列等。
Sign up for Indie Maker Hu
Hi, I'm javayhu, an indie maker who builds in public. I share thoughts and ideas about indie hacking here, and build amazing products people need.
Subscribe
Email sent! Check your inbox to complete your signup.
No spam. Unsubscribe anytime.
2. 算法面试经验分享2.1 关于刷算法题
Github 是程序员的交友社区，而 LeetCode 如同程序员的王者峡谷，这里是程序员提升自身技能的竞技场。在 2015 年秋招之时，LeetCode 大概只有 100 到 200 道题，如今却已有近 700 道题了。你觉得自己的算法水平怎样都没关系，我建议在算法面试准备阶段去刷一些 LeetCode 的题，因为熟能生巧。AndroidInterviews 上有两份 PDF 文档，一份是 C++版本的 LeetCode 题解，一份是 Java 版本的 LeetCode 题解，建议把它们放到手机里，这样就能随时翻看了。国内很多互联网公司的面试官不会亲自出题，很多时候他们会挑选 LeetCode 上中等难度的题目来考核面试者。如果你曾经做过这些题目，那么你就会心中有数、从容应对了。
刷题并非盲目进行刷题。因为题目数量已经很多了，所以建议先去刷高频题，像数组、链表、二叉树等类型的题。如果时间充足，就可以再去刷自己相对薄弱的环节。要是时间不充足，那就直接看题和解答，并且可以反复去看和反复去记。
手写代码之前，要先与面试官进行沟通。要确保自己完全正确地理解了题目的意思。想好思路之后，再开始写代码。否则，噼里啪啦写了一堆没用且有错误的代码，让面试官看到后会留下不好的印象。在线编程和线下手写代码都没有代码提示。所以平时需要多练习手写代码，不能犯明显的基本语法错误。同时要留意代码风格，像代码格式、变量命名、函数命名等方面。必要时要进行防御性编程以及边界值检查等操作。
我在线做题时，未曾仔细查看要求的输出格式，致使有一小段代码白白写了。面试官指出我没看清题目，即便我三道题都写出来了，可表现仍不够完美。
一般算法面试的题目，容易想到一个最直观的解法。不过，最直观的解法往往不是最优的解法。但一定不要连最直观的解法都不说。比如经典的 Two Sums 问题，很明显，列出所有两个数字的组合，看这个组合是否满足条件，也能得到问题的解。只是你心里清楚，这样做时间复杂度太高了。你一定要和面试官进行交流。当你没有直接想出最优解时，可以先说出最直观的暴力解法。在说出最直观解法的这段时间里，你可以慢慢思考是否有其他更优的解法。或者在你说完最直观的解法之后，面试官会问你有没有更好的解法。这样你就相当于给面试官一个台阶，给他一次机会来引导你找到最优的解法，这样他开心，你也开心。
那年华为的面试给我留下了较深印象。面试官看起来像是一位经验丰富的程序员，面容和蔼，是位慈祥的老先生。他首先问的问题是找素数，并且不停地问我“你这个解法还能不能再优化”。与他沟通时会感觉特别舒服，因为老先生不着急，只是希望我能在他的指引下找到更优的解法。做完这道题后，我没能说服他。接着，老先生又出了一道题。这道题给我的感觉像是他自己构思出来的一道实际应用题。我在纸上圈圈画画，标注出几个状态以及状态之间的跳转方式。还没画完，他就接过笔说可以了，然后一边写一边给我讲解这道题的情况。题目已忘却，然而老先生当时给我“讲课”的神态我还有些印象。之后我直接去面华为专家和 HR 了，听说老先生给了我很好的评价。由此可见，倾听与沟通是极为重要的。注：本文中部分图片来自《算法导论》和《Python Algorithms》两本书籍。
Sign up for Indie Maker Hu
Hi, I'm javayhu, an indie maker who builds in public. I share thoughts and ideas about indie hacking here, and build amazing products people need.
Subscribe
Email sent! Check your inbox to complete your signup.
No spam. Unsubscribe anytime.
本文来自作者[xl131]投稿，不代表新福号立场，如若转载，请注明出处：https://xl131.com/jyan/202502-13154.html
评论列表（4条）
我是新福号的签约作者“xl131”！
希望本篇文章《2016年算法面试经验分享：如何打好基础应对互联网公司算法面试》能对你有所帮助！
本站[新福号]内容主要涵盖：生活百科,小常识,生活小窍门,知识分享
本文概览：本文介绍如何准备算法面试，包括算法的基础知识、面试常见问题，以及面试经验总结等，凭借本文你可以轻松拿到“offer收割机”称号。...