AI面试-算法结构基础

事实上,目前在中国,几乎只要是技术岗位,100%的人都会在面试中询问算法和数据结构。

[En]

In fact, at present, almost as long as they are technical posts in China, 100% of them will ask about algorithms and data structures in interviews.

两者都可以快速反映候选人的真实水平,如代码量、代码质量、性能、逻辑思维和灵活性。

[En]

Both can quickly reflect the true level of the candidate, such as the amount of code, the quality of the code, performance, logical thinking, and flexibility.

算法结果概述

1 、前言

1.应用范围:机器学习、数据挖掘、自然语言处理、图形学等。

2.求职方面的考点 贪心、分治、动态规划、树、图等。而且考官非常喜欢用算法来验证你的代码水平!

2 、概述

1.定义:简单的说,算法就是解决问题的方式。

2.特点:有穷性、确定性、可行性、有输入&输出。

3 、基础算法:

1.穷举法:求N个数的全部排列、8皇后问题。

2.分而治之:二分查找——减而治之、归并排序——分而治之。

3.贪心:最小生成树——Prim、Kruskal、单元最短路——Dijkstra。

4.动态规划:背包问题、士兵路径。

算法复杂度问题

1 、概述

谈算法不谈复杂度=耍流氓!

硬件的发展是不断的,但算法的扩展是指数的。

[En]

The hardware development is constant, but the expansion of the algorithm is exponential.

在实现之前,估计算法所需的资源:时间和空间。

[En]

Before implementation, estimate the resources required by the algorithm: time and space.

2 、时空复杂度:

1.含义:使用大O记号(最坏情况,忽略系数)。

2.包括:时间复杂度(基本操作次数)、空间复杂度(占用内存字节数)、两者的区别是空间可以再利用、联系是时空互换(Hash表)。

3.举例:

O(1) :基本运算,+,-,*,/,%,寻址。

O(logn) :二分查找。

O(n1/2) :枚举约数。

O(n) :线性查找。

O(n2):朴素最近点对。

O(n3) :Floyd最短路、普通矩阵乘法。

O(nlogn):归并排序。

O(2n) :枚举全部的子集。

O(n!): 枚举全排列。

以上示例摘要:

[En]

Summary of the above examples:

优秀:O(1) < O(logn) < O(n1/2) < O(n) < O(nlogn) 。

可能可以优化:O(n2) < O(n3) < O(2n) < O(n!) 。

4.方法:输入输出、数循环次数、均摊分析。

栈和队列问题

1 、两者的共性和区别

1.共性:存放数据的线性表、空间复杂度O(n)、单次操作时间复杂度O(1) 。

2.区别:队列——先进先出(FIFO),栈——先进后出(FILO)。

2 、操作

入栈/队列、出栈/队列、判断满/空。

3 、实现

1.需要的工具:数组和链表皆可(线性表)、指针(辅助变量):栈顶/底指针、队头/尾指针。

2.关键:出入元素的同时移动指针。

4 、应用

插入语匹配测试和模拟系统栈,由于篇幅比较长,可以在公众号后台回复“申请”获取。

[En]

Parenthesis matching test and simulation system stack, because the length is relatively long, you can reply “application” in the official account background to get.

哈希表问题

1 、哈希表概述

1.定义:存放数据的集合。

2.操作:根据(Key, Value)进行,插入、查找、删除(可以没有)。

3.空间复杂度:O(m)。

4.单次操作时间复杂度:O(1) 。

5.本质:Key的索引。

2 、哈希表例题

1.题目:给出n个[0, m)范围内的整数,去重。

2.解题思路:

①快速排序:期望时间复杂度O(nlogn) ,附加空间复杂度O(1)。

②计数(基数)排序:时间复杂度O(n + m) 、附加空间复杂度O(m)。

3.在思考一下:

若n << m,计数排序的大量空间被浪费。

只需要判断它有没有出现,优化?

[En]

Just need to judge whether it has appeared or not, optimize?

将Key区间[0, m) 映射到[0, p) 。

H(key) = key mod p、若m > p, 多对一的映射方式。

3 、哈希表的实现

1.处理冲突(Key, Value):开放地址法(数组)、拉链法(数组+链表)。

2.负载率:负债率=已有元素大小/ 存储散列大小。

3.哈希函数设计:负载率越低,效率越高,一般负载率小于50%。

4 、哈希表应用

1.题目:设字符串A=’12314123’,求’123’在A中出现的次数。如果不会写KMP又想要O(n),应该怎么处理那?

2.思路:Key(‘123’) = ‘1’ 10^2 +’2′ 10 + ‘3’* 1 = 123。

3.问题:Key相等时Value有可能不同、每次比较Value也是不小的开销,特别是Value可能很大、不考虑Value将产生错误率(错误率换时间)、多重哈希(降低错误率)。

布隆过滤器问题

1 、布隆过滤器概述

1.定义:判断一个字符串是否出现过的数据结构

2.和哈希表的区别:哈希表是空间换时间,而布隆过滤器是错误率换空间。

2 、布隆过滤器的实现

1.由01的数字序列构成

2.插入:多个不同hash函数计算Key,置1

3.查找:有一个为0不可能存在,全为1可能存在

4.空间?

3 、布隆过滤器的评价

1.优点:时间和空间、多个hash函数可并行、交差并(位运算)。

2.缺点:错误率随着负载率上升而上升、无法删除。

Original: https://www.cnblogs.com/Anita9002/p/11218939.html
Author: Anita-ff
Title: AI面试-算法结构基础

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/7634/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

最近整理资源【免费获取】:   👉 程序员最新必读书单  | 👏 互联网各方向面试题下载 | ✌️计算机核心资源汇总