编程面试的十大算法（适用于软件工程师）

21CTO

资讯 0 2152 2020-07-07 12:04:20

导读：如果你已经获得计算机科学技术或者软件工程学位，并且在找一份工作。请阅读本文关于编程面试的十大算法。

本文旨在帮助寻找软件开发工程师工作的人们。

强调一点，软件工程师的工作职责包括：软件设计，增强以及实施，包括软件系统和应用程序。

你无需记住过多复杂的算法。只要按要求使用合适的库、框架和数据库来开发满足需求的工具即可。

以下搜索算法优化会对工作帮助很大，如果对算法不熟，就只能使用内置库。以下列出一些重要的算法，会帮助你在面试时获取更多的机率。

动态编程

动态编程是通过消除对递归调用的需求，优化隐性函数等策略。当你看到一个递归函数，即其中某段代码的部分被多次调用时，可以使用动态编程来改进现状。通过存储前一个子函数的结果，可以消除递归性，不必产生多次调用。这样可以将时间复杂度从指数时间降低到多项式时间。

动态编程的算法有如下：

1、丑陋数
2、斐波那契数
3、二项式系数
4、置换系数

二进制搜索

顾名思义，搜索算法用于从称为数据结构的给定集合中搜索元素。二进制搜索在提供排序后的元素数组和搜索键时有效。二进制搜索通过选择中间元素并将其与搜索关键字进行比较来实现，如果该关键字小于中间元素的左侧部分，则以相同的方式进行遍历。如果现在比右部分上搜索密钥。二进制搜索的时间复杂度为O（log n），其中n是数组中元素的数量。

排序算法

排序算法用于对数组进行排序，输入中包含需要排序的数据类型。数据集合可以按升序或降序排序。

以下为重要的排序算法。

合并排序

合并排序基于分治算法的原理进行。它是指将问题分解为较小的部分，并一一解决并最终合并在一起的实践。合并排序将数组分为两半，并在两个半部分上调用sort函数，对这两个半部分进行排序，然后使用merge函数合并在一起。合并排序的时间复杂度为O（n log n）。

快速排序

与合并排序一样，快速排序也是基于分治算法，它在排序功能方面与合并排序有所不同。快速排序的工作原理是选择最后一个元素作为中间值，并将其放在中间，左侧数字较小，而右侧数字较大。左侧和右侧再次使用sort函数执行，结果对整个数组进行了排序。快速排序的时间复杂度为O（n ^ 2）。

深度优先搜索

DFS是一种搜索算法，它从节点开始搜索过程，一直向下到最左边分支的最后一个叶子。在到达最左边的叶子之后，算法开始回溯并遍历树的右侧，依此类推。此DFS的问题在于，如果存在一个周期，则可以多次访问某个节点。DFS的时间复杂度为O（V + E），其中V和E分别表示图中的顶点和边数。

广度优先搜索

BFS是一种从根开始的搜索算法。但是，它没有遍历左侧的所有叶子，而是在同一级别上的节点附近搜索。遍历一个层级后，算法将前进到下一个层级，并继续遍历直到找到元素。BFS的时间复杂度与DFS相同，为O（V + E）。

自定义数据结构

有时，典型的预定义数据结构无法完成任务，人们需要更好，更强大的功能。自定义数据结构可以是真实或抽象对象，具体取决于其数据成员的用途。数据成员可以视为属于指定对象的变量。

哈希表

哈希表是一种数据结构，用于存储，访问和修改时间为O（1）的数据。哈希数据结构使用哈希函数将给定值映射到特定键。然后，使用此键快速访问和检索这些值，哈希的执行效率取决于所用哈希函数之类型。

链表

通常，数组的组件或链接的数据结构存储在连续的内存位置中。它会大量占用空间，并且会让某些内存区域不可用（内存崩溃）。为了克服此问题，使用链表数据结构，数据不再是连续存储，而是列表中的每个元素都有一个指向下一元素存储位置的指针。第一个元素被称为头，最后一个元素被称为尾。

学会问问题

软件工程师应该知道的最重要的事情是询问客户。大多数客户无法理解技术人的观点，如果我们不提出任何问题，则可能会因沟通不畅而引发大问题。

小结

掌握了这些基本算法，就可以轻松进行面试。请记住，软件工程师通常不依靠这些算法来完成工作。取而代之的是，它们被用来测试个人对他是否了解代码基础的理解深度。

我们还会在后面的文章再详细讲解这些算法细节。祝你下次面试顺利。