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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

云栖号资讯小哥 2020-07-27 13:48:00 浏览543
展开阅读全文

云栖号资讯:【点击查看更多行业资讯
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!


您刚刚从大学获得计算机科学或软件工程学位,并且正在寻找职业。您还记得自己喜欢单身汉编写代码,并与好友一起做过一些很棒的项目,然后决定要成为一名开发人员。

您开始准备工作面试,却无法弄清楚记住哪些算法对于评分工作很重要。如果您处于这样的位置,并且足够快地进行面试,那么本文将帮助您记住求职面试可能需要的所有编码算法。

软件工程师的基本工作描述包括设计,增强和实施系统和应用程序。

为此,软件工程师无需记住许多复杂的算法。相反,要求他们使用工作库,框架和数据库的组合来创建满足其软件需求的工具。

根据软件工程领域的专家介绍,了解一些高级搜索算法在优化它们时会有所帮助,否则,您更有可能使用内置库。话虽如此,这里列出了一些重要的算法,在进行面试时您应该具有一些基本的知识。

动态编程

动态编程是通过消除对递归调用的需求来优化隐性函数的策略。每当我们看到一个递归函数,其中某个代码的某个部分被多次调用时,可以通过使用动态编程来大大改进。通过存储前一个子函数的结果,可以消除递归性,从而不必多次调用它们。这样可以将时间复杂度从指数时间降低到多项式时间。属于动态编程类别的算法示例如下:

二进制搜索

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

排序算法

排序算法用于对数组进行排序,输入中包含需要排序的数据类型。数据集可以按升序或降序排序。以下是一些要记住的重要排序算法。

合并排序

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

快速排序

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

深度优先搜索

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

广度优先搜索

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

自定义数据结构

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

哈希表

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

链表

通常,数组的组件或任何链接的数据结构存储在连续的内存位置中。这将占用空间,并且某些内存块不可访问(也就是说,如果内存不足)。为了克服这个问题,使用了链表数据结构,其中的数据不是连续存储的,而是列表中的每个项目都有一个指向下一个元素的存储位置的指针。第一个元素被称为头,最后一个元素被称为尾。

问问题

软件工程师应该知道的最重要的事情是询问客户。大多数客户无法理解他们的观点,如果开发人员不提出任何问题,则可能由于沟通不畅而引起问题。这样,您将能够理解他们正在努力实现的核心问题,而不仅仅是他们面临的困难。

结论

有了这些基本算法的知识,就可以轻松进行面试。请记住,软件工程师通常不依靠这些算法来完成工作。取而代之的是,它们被用来测试个人对他是否了解代码工作的理解。如此说来,祝您下次面试顺利。

【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live

立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK

原文发布时间:2020-07-23
本文作者:爱码农
本文来自:“cocoachina”,了解相关信息可以关注“cocoachina”

网友评论

登录后评论
0/500
评论
云栖号资讯小哥
+ 关注