作者:Educative翻译:疯狂的技术宅
https://www.educative.io/blog...
未经允许严禁转载
算法是技术面试的重要组成部分,尤其是在国内外的大厂中。本文将为你介绍在面试中需要了解的常见算法以及提高它们效率的方法(这是面试中常见的问题),最后会为你提供一些练习题。
你需要审视的基本概念是:
一旦掌握了基础知识,就可以开始进入在面试之前应该了解的中间概念;具体来说,本文将向你展示一些关键的算法范例(以及使它们高效的方法),这些范例对于学习解决面试中的编码问题至关重要。
在我们深入研究算法范式之前,应该对计算机程序相对于算法的时间复杂性和效率说些什么——一种被称为“渐近分析”的概念。在面试中,可能不会要求你直接计算算法的复杂度,但可能会要求你计算所编写的算法的复杂度或让你改善一个算法的复杂度。
复杂度是算法效率的近似度量,并且与你编写的每个算法都相有关。这是所有程序员都必须意识到的事情。有两种复杂度:时间和空间。时间复杂度和空间复杂度实质上是算法处理某些输入时将分别花费多少时间和多少空间的近似值。通常要解决以下三个问题:
Big O 是分析算法的首选方法,因为在大多数情况下,平均情况和最佳案例无法洞察算法的效率。
如果你在面试中被要求找到算法的 Big O 复杂性,这是一般的经验法则:
例:找到时间复杂度为 3n³ + 4n + 2的算法的 Big O 复杂度,将其简化为O(n³)。
计算算法的时间复杂度时,你需要采取三个步骤:
这是一个简单的例子,用于测量大小为 n
的 for 循环的时间复杂度。这是一个大小为 n
的循环:
#include <iostream> using namespace std; int main(){ int n = 10; // 0(1) int sum = 0; // 0(1) for (int i=0; i<n; i++) sum+=2; // 0(1) cout << sum; // 0(1) return 0; }
首先,将代码分成多个单独的操作,然后计算执行该代码的次数,如下所示:
在对每个操作执行了多少次进行计数之后,只需将所有这些计数相加即可得出该程序的时间复杂度。
$$ \begin{align} 时间复杂度 & = 1 + 1 + 1 +(n + 1)+ n + n + 1 \\ & = 3 +(n + 1)+ 2n + 1 \\ & => 3n + 5 \end{align} $$
渐进分析的一般技巧:
用于计算算法时间复杂度的有用公式:
算法范式是“构建有效解决问题的通用方法”;换句话说,它们是解决问题的方法、策略或技术,对于每个程序员都是必不可少的。花时间学习这些,因为你很有可能会在面试中用到其中一种或多种算法。
算法范式之所以出色,是因为它们奠定了适合解决各种不同问题的框架,包括:
渐近分析:计算下面给出的代码段的 Big O 复杂度。
int main(){ int n = 10; int sum = 0; float pie = 3.14; for (int i=1; i<n; i+=3){ cout << pie << endl; for (int j=1; j<n; J+=2){ sum += 1; cout << sum << endl; } } }
排序和搜索算法:实现一个函数,该函数接受两个可变长度的排序数组,并找到两个数组的中位数。
图算法:实现一个函数,该函数返回给定级别的无向图的节点数。
贪心算法:假设存在无限数量的 25 美分,10 美分,5 美分和 1 美分硬币,实现一个函数来计算代表 V 美分的硬币数量。
动态规划算法:一个孩子正在上 n 级楼梯,每次可以走 1 步,2 步或 3 步。实现一个函数,计算孩子上楼梯的可能方式。
分治法:给定 2 个有 k 行和 44 个排序列的二维数组,以及一个大小为 $k \times n$ 的空一维输出数组,用分治法将所有元素从 k 个排序数组复制到 $k \times n$ 个输出数组。
如果你要进行技术面试,必须为展示自己对各种算法的了解做好准备,并了解每种算法的复杂度。熟悉上面提到的算法范例(即分治、暴力、贪婪),谚语云:“实践出真知”,所以你需要花时间去练习实现不同的算法,并计算其复杂度,因为开发人员在编码时必须意识到这一点。
你可以采取一些步骤来确保下次面试成功:
熟悉各种算法:不要只记住解决方案。花时间了解构成每种算法的模式以及应该采取的方法。
做功课:练习的次数越多,感觉就会越舒适。
下一步…学习,准备和练习:只是凭借看老的面试题和博客文章来准备面试是不够的,你需要真正的实践经验。