面经-数据结构相关

整理了面试中常问的数据结构相关的知识点

树

红黑树和AVL树的定义，特点，以及二者区别

AVL树是平衡二叉搜索树，每个节点的左右子树的高度差不超过1，左右子树的高度做差称为平衡因子，平衡因子的取值只可能是 0 +-1 绝对值超过1的就不是平衡二叉树。 红黑树是以 一个数据位标记节点红黑颜色的树，也是二叉搜索树，每次插入和删除节点都要满足一定的着色规则，从而约束红黑树使得根节点到叶子节点的最长路径不超过最短路径的2倍。（每个节点非红即黑，根节点是黑色，每个叶节点是黑色，如果一个节点是红色，其子节点必须是黑，每条路径上黑色节点数目一致）

区别：红黑树是弱平衡二叉树，AVL 树由于平衡条件过于严格，导致每次插入或删除节点都容易使得平衡打破，需要频繁的旋转调整树，导致效率下降。所以在需要频繁插入或删除的应用场景，红黑树速度更快。红黑树插入节点最多旋转两次，删除节点最多旋转三次。

哈夫曼编码

哈夫曼编码是哈夫曼树的一种应用，用于数据的无损压缩。根据序列中字符出现频率，使用0/1来对字符重新编码。是一种不等长前缀编码，出现频率高的字符使用较多位空间编码。具体：

1. 哈夫曼树是一种自底向上构建表示的最优前缀二叉树T
2. 算法以|C|个叶节点（每个叶节点表示一个字符）开始，经过C-1次合并运算产生最终要求的树。
3. 构建步骤 …

map底层为什么用红黑树实现

介绍AVL树定义特点, 介绍红黑树 定义特点

AVL 树是高度平衡的，频繁的插入和删除，会引起频繁的rebalance，导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。所以红黑树在查找，插入删除的性能都是O(logn)，且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。

介绍一下B+树

B+树是一种多路搜索树，主要为磁盘或其他直接存储设备而设计的一种平衡查找树，因为磁盘相对内存而言读写速度慢，使用B+树相对二叉搜索树 每次 减少磁盘读写次数。B+树每个节点可有多个孩子，每个节点中的键值有序排列。所有值都存在叶节点中。相对B树有以下特点：

• 内部节点不存数据，只存键值
• 叶子节点存放数据，且和相邻叶子节点构成有序链表
• 每个节点的最大子树个数M 则键值M 而 B树M M-1
• ….

说一说map和unordered_map的底层实现

​ map 的底层是基于红黑树实现的 因此map内部元素是有序的，且查找速度log(N) 而unordered_map是无序的底层基于 哈希实现，查找更快 接近常数级别，极端情况会O(N)

map和unordered_map优点和缺点

对于map，其底层是基于红黑树实现的，优点如下：

1. 有序性，这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作
2. map的查找、删除、增加等一系列操作时间复杂度稳定，都为logn

unordered_map

1. 内部基于哈希表，以（key,value）对的形式存储，因此空间占用率高
2. 无序
3. Unordered_map的查找、删除、添加的时间复杂度不稳定，平均为O(c)，取决于哈希函数。极端情况下可能为O(n)

回答一下epoll怎么实现的

epoll应用场景： 对于高连接的应用场景。例如 有上百万个用户通过TCP连接至服务器，但是每一时刻只有几十个或几百个TCP活跃（接受TCP包 ，需要内核完成读写文件操作）。那么epoll就是为了在此种场景下高效处理数据连接。在linux内核2.4以前，使用select 或者 poll事件驱动的方式实现。

select: select的工作流程：创建socket－>绑定端口bind－>监听listen－>accept->write/read。当有客户端连接到来时,select会把该连接的文件描述符放到 fd_set（文件描述符(fd)的集合 相当于数组）,然后select会循环遍历它所监测的 fd_set 内的所有文件描述符，如果没有一个资源可用(即没有一个文件描述符可以进行read/write可以操作)，则select让该进程阻塞的等待，一直等到有资源可用为止。而fd_set是一个类似于数组的数据结构，由于它每次都要遍历整个数组，所以它的效率会随着文件描述符的数量增多而明显的变慢，除此之外在每次遍历这些描述符之前，系统还需要把这些描述符集合从内核copy到用户空间，然后再copy回去，如果此时没有一个描述符有事件发生（例如：read和write）这些copy操作和便利操作都是无用功，可见slect随着连接数量的增多，效率大大降低。可见如果在高并发的场景下select并不适用，况且select默认的最大描述符为1024。

epoll: Linux epoll机制是通过红黑树和双向链表实现的。 首先通过epoll_create()系统调用在内核中创建一个eventpoll类型的句柄，其中包括红黑树根节点和双向链表头节点。然后通过epoll_ctl()系统调用，向epoll对象的红黑树结构中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。最后通过epoll_wait()系统调用判断双向链表是否为空，如果为空则阻塞。当文件描述符状态改变，fd上的回调函数被调用，该函数将fd加入到双向链表中，此时epoll_wait函数被唤醒，返回就绪好的事件。

总结： epoll 的机制感觉就是 充分利用了回调函数。使用一个红黑树 存储当前的所有感兴趣事件 （百万级别 很多休眠），而使用一个双向链表来存储 活跃连接。TCP开始活跃时 系统 在中断中调用事先注册的回调函数向 链表中添加 活跃事件。用户只用通过 epoll_wait() 去链表访问活跃事件的数据和id即可。

请你说一说Top(K)问题

• 直接排序法：直接调用一般的排序算法，对所有元素进行排序，然后去topK，这种方法效率低，对内存需求大，因为进行了很多无意义的排序。
• 基于快速排序的变形：根据快排的思想，每次从待排列的数据中随机选取一个作为 参考数据，将比他大的放在它的右边，小的放左边，分组完成后，如果基准元素右侧的个数n=K，完毕；如果n>K，则重新对左边数据进行一次相同的分组操作；如果基准元素右侧的元素个数n< K，则重新对左边数据进行一次相同的分组操作，此时K=K-n；
• 基于堆排序的思路：首先构建一个含有 K 个元素的小顶堆，每次读入数据和堆顶数据比较，如果小于它直接pass，否则删除堆顶元素并将其入堆。遍历完成后，堆中数据即为TopK
• 分治法：
• Hash 法：对于含有大量重复元素的数据，可以先通过hash法把重复的数去掉。这样可以减小很多的不必要计算

请你说一说C++两种map

unordered_map (Hash) 和 map (红黑树)

请你说一说红黑树的性质还有左右旋转

https://blog.csdn.net/weixin_43939593/article/details/104420724?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159021709219725211930470%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=159021709219725211930470&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2_blogfirst_rank_v1~rank_blog_v1-1-104420724.pc_v1_rank_blog_v1&utm_term=%E7%BA%A2%E9%BB%91%E6%A0%91

堆和栈

说一说你理解的stack overflow

​ 栈溢出概念：栈溢出指的是程序向栈中某个变量中写入的字节数超过了这个变量本身所申请的字节数，因而导致栈中与其相邻的变量的值被改变。

​ 栈溢出得原因：

• 局部数组过大。当函数内部的数组过大时，有可能导致堆栈溢出。局部变量是存储在栈中的，因此这个很好理解。解决这类问题的办法有两个，一是增大栈空间,二是改用动态分配，使用堆（heap）而不是栈（stack）。
• 递归调用的层数太多。递归函数在运行的时候会执行压栈操作。当压栈次数太多时，也会导致堆栈溢出。
• 数组指针越界

### 栈和堆的区别，以及为什么栈要快

区别：

1. 地址生长方向，栈是由高地址向低地址，堆反之
2. 分配方式：栈是系统自动分配内存，有硬件实现，存放局部变量参数等。而堆是人为实现的一种结构，需要手动申请和释放内存。
3. 栈由于其先进后出的特性，不会产生内存碎片
4. 栈高效

栈高效的原因：栈是操作系统提供的数据结构，计算机底层对栈提供了一系列支持：分配专门的寄存器存储栈的地址，压栈和入栈有专门的指令执行；而堆是由C/C++函数库提供的，机制复杂，需要一些列分配内存、合并内存和释放内存的算法，因此效率较低。

手写代码，两个栈实现一个队列

class Solution
{
    public:
        void push(int node) {
        stack1.push(node);
    }
    int pop() {
        if(stack2.size()!=0){
        int tmp = stack2.top();
        stack2.pop();
        return tmp;
    }
    else{
    while(stack1.size()!=0){
        int tmp = stack1.top();
        stack1.pop();
        stack2.push(tmp);
    }
    return pop();
    }
    }

    private:
    stack<int> stack1;
    stack<int> stack2;
}；

小根堆特点

1. 堆是一个完全二叉树，除最后一层外，其他的都得是满的
2. 小顶堆，父节点总是小于他的左右子节点的值，因此堆顶的元素最小。大顶堆相反。

数组

数组和链表的区别

数组的特点：数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。数组的插入数据和删除数据效率低，插入数据时，这个位置后面的数据在内存中都要向后移。删除数据时，这个数据后面的数据都要往前移动。但数组的随机读取效率很高。因为数组是连续的，知道每一个数据的内存地址，可以直接找到给地址的数据。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。数组需要预留空间，在使用前要先申请占内存的大小，可能会浪费内存空间。并且数组不利于扩展，数组定义的空间不够时要重新定义数组。

链表的特点：链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。不指定大小，扩展方便。链表大小不用定义，数据随意增删。

数组的优缺点：

1. 随机访问性强
2. 查找速度快
3. 插入和删除效率低
4. 数组大小固定，不能动态拓展 可能浪费内存
5. 内存空间要求高，必须有足够的连续内存空间。

链表的优缺点：

1. 插入删除速度快
2. 内存利用率高，不会浪费内存
3. 大小没有固定，拓展很灵活。
4. 不能随机查找，必须从第一个开始遍历，查找效率低

判断有无重复数

​ 一个长度为N的整形数组，数组中每个元素的取值范围是[0,n-1],判断该数组否有重复的数，请说一下你的思路并手写代码

思路： 把每个数放到自己对应序号的位置上，如果其他位置上有和自己对应序号相同的数，那么即为有重复的数值。时间复杂度为O(N),同时为了节省空间复杂度，可以在原数组上进行操作，空间复杂度为O(1)

排序

手写快排的代码

海量数据如何去取最大的k个

• 基础的对所有元素进行排序，效率不高，因为只用求K大 并不需要对所有元素排序
• 快排的变形，选取基准数，左右分区，如果右边比基准数大的个数不等于K，根据与K的大小关系选择是对基准数左半部分or右半部分数递归求K-N or K 大。
• 最小堆法。首先建立一个含有K个元素的最小堆，每次取序列中的元素与堆顶元素比，如果比堆顶元素大，将堆顶元素弹出，改元素入堆，如果小，就说明他肯定不是K大中的一个，跳过。依次遍历到结束，最后堆中的元素就是topK
• 分治法：将所有元素分为N 分，如果每份的元素数量可以放入内存，就分别对每份找出前K大，否则继续分治处理。最后每份挑出了K个，一共有N*K个元素，可以使用快排的变形找出前K个。
• Hash法：对于含有大量重复元素，使用Hash去重，如果剩下元素可以读入内存了，就直接排序，否则可以使用分支法读入内存在处理或者堆法。

快排的时间复杂度最差是多少？什么时候时间最差

元素倒序，O(n^2)

什么是稳定性排序

对于相等的元素，排序前后相对顺序不变

快排算法最差情况推导公式

一般的快排中的基准元素选取的为 最左边或者最右边的元素。 当选取最左边元素作为基准，而序列原本又是正序的时候，每次左右分拨都要挨个交换位置，就和冒泡排序类似；所以O(n^2) 反之当选取最右边基准…倒序…..； 当元素都相同时

所以可以随机选择基准元素，降低出现最坏情况的概率

稳定排序哪几种

插入法，冒泡排序，归并排序，计数排序，基数排序，桶排序

哈希

hash表的实现，包括STL中的哈希桶长度常数

主要包含两部分，一是Hash函数构造由key的值使用Hash函数处理的得到地址。另一个是处理Hash冲突

前者构造Hash的方法主要有 直接地址法，平方取中法，除留余数法 后者的方法有：开放地址法，链地址法，再Hash法，建立公共溢出区等方法

使用链地址法不一定必须满足 桶的个数为质数….？

解决hash冲突的方法

​ 当不同经过hash产生相同的地址时，即差生hash冲突。此时解决的方法有如下：

• 开放地址：所谓开放地址，就是当hash过后 地址重复了之后，按照一定的规律从当前地址往其他地方搜索表中的空内存区 （Hi = H(key + di)）。根据寻址扩展的规律分为如下。产生新地址的方法能覆盖所有表区，免得内存浪费。再读取时，如果在Hash的地址找不到对应的元素，那么就按照指定的寻址方式往其他内存寻找元素对比key，找到表尾也没找到说明不存在。
  1. 线性探查：di = c x i 就是地址线性往后递增 （注意对表长取余了 所以会循环 可以覆盖所有区域）
  2. 二次探查： di = + - i^2 就是平方规律分别向前和向后探测
  3. 伪随机探测：di 是一组伪随机数
• 链地址：向指定地址插入Hash值时，如果该地址已有元素，桶内使用链表存储新增的数据。那么在读取的时候也是遍历链表找到对应的key的内容。
• 公共溢出区：建立一个公共溢出区域，把hash冲突的元素都放在该溢出区里。查找时，如果发现hash表中对应桶里存在其他元素，还需要在公共溢出区里再次进行查找。
• 再hash：再散列法其实很简单，就是再使用哈希函数去散列一个输入的时候，输出是同一个位置就再次散列，直至不发生冲突位置。每次冲突都要重新计算散列，计算时间增加。

image-20201117201021698

哈希表的桶个数为什么是质数

哈希表的桶个数使用质数，可以最大程度减少冲突概率，使哈希后的数据分布的更加均匀。如果使用合数，可能会造成很多数据分布会集中在某些点上，从而影响哈希表效率。 例如常用的Hash函数是标准的求模函数，质数的因数只有1和它本身，合数不止。例如 6 和 7 ，当Hash数是2/3的时候，6%2 = 6%3=0 也就是经过取模Hash后 Key=2/3在同一个地址了。

为什么Hash表的容量是2的幂次方

JDK 里面实际不是用取模 而是 位运算与；一方面 使用与操作替代取模，提升计算效率； n&(capacity-1) 9%8==1，只有2的幂才能有此性质。同时 为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列。因为如果capacity是奇数的话，与capacity-1相与最后一位一定是0，则不能充分利用hash表的空间。

hash表如何rehash 怎么处理其中保存的资源

Hash表中有个负载因子，代表 存储数据长度 / 表的长度。负载因子越大，查找复杂度就越大。每次往表中装载数据要保证负载因子 < 1否则就需要rehash，保证可以装载成功。rehash过程类似数组扩容，开辟一个新的原桶数组的两倍大的空间，并把原本的桶的数组中的元素全部重新Hash到新的Hash桶数组中。

动态规划

手写代码：最长公共连续子序列

手写代码：求一个字符串最长回文子串

手写代码：查找最长回文子串

链表

手写代码，如何合并两个有序链表

手写代码：反转链表

手写代码：判断链表是否为回文

什么是单向链表

判断两个单向链表是否相交

高级算法

加密方法有那些

### LRU缓存

洗牌算法