算法是比较复杂又基础的学科烸个学编程的人都会学习大量的算法。而根据统计以下这18个问题是面试中最容易遇到的,本文给出了一些基本答案供算法方向工程师戓对此感兴趣的程序员面试问什么参考。
1)请简单解释算法是什么
算法是一个定义良好的计算过程,它将一些值作为输入并产生相应的輸出值简单来说,它是将输入转换为输出的一系列计算步骤
2)解释什么是快速排序算法?
快速排序算法能够快速排序列表或查询它基于分割交换排序的原则,这种类型的算法占用空间较小它将待排序列表分为三个主要部分:
-
枢轴元素Pivot(选定的比较值)
3)解释算法的時间复杂度?
算法的时间复杂度表示程序运行完成所需的总时间它通常用大O表示法来表示。
4)请问用于时间复杂度的符号类型是什么
鼡于时间复杂度的符号类型包括:
-
Big Oh:它表示小于或等于目标多项式
-
Big Omega:它表示大于或等于目标多项式
-
Big Theta:它表示与目标多项式相等
-
Little Oh:它表示小於目标多项式
5)解释二分法检索如何工作?
在二分法检索中我们先确定数组的中间位置,然后将要查找的值与数组中间位置的值进行比較若小于数组中间值,则要查找的值应位于该中间值之前依此类推,不断缩小查找范围直至得到最终结果。
6)解释是否可以使用二汾法检索链表
由于随机访问在链表中是不可接受的,所以不可能到达O(1)时间的中间元素因此,对于链表来说二分法检索是不可以嘚(对顺序链表或排序后的链表是可以用的)。
7)解释什么是堆排序
堆排序可以看成是选择排序的改进,它可以定义为基于比较的排序算法它将其输入划分为未排序和排序的区域,通过不断消除最小元素并将其移动到排序区域来收缩未排序区域
Skip list数据结构化的方法,它尣许算法在符号表或字典中搜索、删除和插入元素在Skip list中,每个元素由一个节点表示搜索函数返回与key相关的值的内容。插入操作将指定嘚键与新值相关联删除操作可删除指定的键。
9)解释插入排序算法的空间复杂度是多少
插入排序是一种就地排序算法,这意味着它不需要额外的或仅需要少量的存储空间对于插入排序,它只需要将单个列表元素存储在初始数据的外侧从而使空间复杂度为O(1)。
10)解釋什么是“哈希算法”它们用于什么?
“哈希算法”是一个哈希函数它使用任意长度的字符串,并将其减少为唯一的固定长度字符串它用于密码有效性、消息和数据完整性以及许多其他加密系统。
11)解释如何查找链表是否有循环
要知道链表是否有循环,我们将采用兩个指针的方法如果保留两个指针,并且在处理两个节点之后增加一个指针并且在处理每个节点之后,遇到指针指向同一个节点的情況这只有在链表有循环时才会发生。
12)解释加密算法的工作原理
加密是将明文转换为称为“密文”的密码格式的过程。要转换文本算法使用一系列被称为“键”的位来进行计算。密钥越大创建密文的潜在模式数越多。大多数加密算法使用长度约为64到128位的固定输入块而有些则使用流方法。
13)列出一些常用的加密算法
一些常用的加密算法是:
14)解释一个算法的最佳情况和最坏情况之间有什么区别?
·最佳情况:算法的最佳情况解释为算法执行最佳的数据排列。例如,我们进行二分法检索如果目标值位于正在搜索的数据中心,则这就昰最佳情况最佳情况时间复杂度为0。
·最差情况:给定算法的最差输入参考。例如快速排序,如果选择关键值的子列表的最大或最小元素则会导致最差情况出现,这将导致时间复杂度快速退化到O(n2)
15)解释什么是基数排序算法?
基数排序又称“桶子法”是通过比较数芓将其分配到不同的“桶里”来排序元素的。它是线性排序算法之一
16)解释什么是递归算法?
递归算法是一个解决复杂问题的方法将問题分解成较小的子问题,直到分解的足够小可以轻松解决问题为止。通常它涉及一个调用自身的函数。
17)提到递归算法的三个定律昰什么
所有递归算法必须遵循三个规律
-
递归算法必须有一个基点
-
递归算法必须有一个趋向基点的状态变化过程
18)解释什么是冒泡排序算法?
冒泡排序算法也称为下沉排序在这种类型的排序中,要排序的列表的相邻元素之间互相比较如果它们按顺序排列错误,将交换值並以正确的顺序排列直到最终结果“浮”出水面。