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


 
code-review-tools.png


 
本文旨在帮助寻找软件开发工程师工作的人们。
 
强调一点,软件工程师的工作职责包括:软件设计,增强以及实施,包括软件系统和应用程序。
 
你无需记住过多复杂的算法。只要按要求使用合适的库、框架和数据库来开发满足需求的工具即可。
 
以下搜索算法优化会对工作帮助很大,如果对算法不熟,就只能使用内置库。以下列出一些重要的算法,会帮助你在面试时获取更多的机率。
 
动态编程
 
动态编程是通过消除对递归调用的需求,优化隐性函数等策略。当你看到一个递归函数,即其中某段代码的部分被多次调用时,可以使用动态编程来改进现状。通过存储前一个子函数的结果,可以消除递归性,不必产生多次调用。这样可以将时间复杂度从指数时间降低到多项式时间。
 
动态编程的算法有如下:
 
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)的数据。哈希数据结构使用哈希函数将给定值映射到特定键。然后,使用此键快速访问和检索这些值,哈希的执行效率取决于所用哈希函数之类型。
 
链表
 
通常,数组的组件或链接的数据结构存储在连续的内存位置中。它会大量占用空间,并且会让某些内存区域不可用(内存崩溃)。为了克服此问题,使用链表数据结构,数据不再是连续存储,而是列表中的每个元素都有一个指向下一元素存储位置的指针。第一个元素被称为头,最后一个元素被称为尾。
 
学会问问题
 
软件工程师应该知道的最重要的事情是询问客户。大多数客户无法理解技术人的观点,如果我们不提出任何问题,则可能会因沟通不畅而引发大问题。
 
小结
 
掌握了这些基本算法,就可以轻松进行面试。请记住,软件工程师通常不依靠这些算法来完成工作。取而代之的是,它们被用来测试个人对他是否了解代码基础的理解深度。
 
我们还会在后面的文章再详细讲解这些算法细节。祝你下次面试顺利。
 
 
 

作者:老夏