数据结构与算法
1. 1 亿个 IP 地址，如何去取 Top3
首先，将 1 亿个 IP 地址按照哈希函数的值分成 1024 个桶，每个桶里面存储的是对应哈希值的 IP 地址。然后，对于每个桶，统计出现次数最多的 IP 地址。最后，将这 1024 个桶中出现次数最多的 IP 地址进行排序，取出前三个即可。
2. 七大排序时间复杂度与稳定性
七大排序算法的时间复杂度和稳定性如下：
| 排序算法 | 时间复杂度 | 稳定性 |
|---|---|---|
冒泡排序 | O(n^2) | 稳定 |
选择排序 | O(n^2) | 不稳定 |
插入排序 | O(n^2) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | 不稳定 |
快速排序 | O(nlogn)~O(n^2) | 不稳定 |
归并排序 | O(nlogn) | 稳定 |
堆排序 | O(nlogn) | 不稳定 |
3. 快速排序、归并排序、堆排序
快速排序：快速排序是一种基于分治思想的高效排序算法。它的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
归并排序：归并排序是一种基于分治思想的高效排序算法。它的基本思想是将待排元素分成大小大致相等的两个子集合，分别对这两个子集合进行递归处理，直到子集合中只有一个元素为止，然后将两个子集合合并成一个有序序列。
堆排序：堆排序是一种基于堆结构的高效排序算法。它的基本思想是将待排元素构造成一个堆，然后依次取出堆顶元素（最大或最小），再将剩余元素重新构造成一个堆，重复上述操作直到所有元素都被取出。
4. 令牌桶算法原理
令牌桶算法是一种流量整形算法，它可以平滑地限制数据的传输速率。令牌桶算法的原理是系统会以一个恒定的速率往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
5. 红黑树、avl 的复杂度
红黑树和 AVL 树都是常用的平衡二叉树，它们的时间复杂度都是 O(logn)。红黑树的算法时间复杂度和 AVL 相同，但统计性能比 AVL 树更高，所以在插入和删除中所做的后期维护操作肯定会比 AVL 树要耗时好多，但是它们的查找效率都是 O(logn)
6. 红黑树简介
红黑树是一种自平衡的二叉搜索树，它在计算机科学中被广泛应用。它的名称来自于树中节点的颜色，每个节点要么是红色，要么是黑色。红黑树具有以下特性：
根节点是黑色的。
每个叶子节点 (NIL 节点，空节点) 都是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的。
从任意节点到其每个叶子节点的路径上包含相同数量的黑色节点。
任意节点到其后代的所有叶子节点的简单路径上，均包含相同数量的黑色节点。
这些特性保证了红黑树的平衡性，使得它的高度始终保持在可接受的范围内。红黑树的高度是 O(logn)，其中 n 是树中节点的数量。
红黑树的自平衡性是通过在插入和删除操作后进行调整来实现的。插入和删除操作可能会破坏红黑树的特性，但通过一系列的旋转和重新着色操作，可以保持红黑树的平衡性。
红黑树在许多领域都有广泛的应用，特别是在需要高效地进行插入、删除和搜索操作的场景中。它的时间复杂度在平均和最坏情况下都是 O(log n)，使得它成为一种非常有效的数据结构。
7. 哈希查找时间复杂度
哈希查找的时间复杂度通常被认为是 O(1)。这是因为哈希表利用哈希函数将键映射到数组的特定位置，使得对于任意给定的键，可以通过哈希函数快速计算出其对应的存储位置。在平均情况下，哈希表的搜索、插入和删除操作的时间复杂度都是 O(1)。然而，在最坏情况下，如果发生大量的哈希冲突，哈希表的性能会退化成 O(n)。
8. 快排为什么不稳定
当快速排序中的枢纽元与其他元素进行交换时，可能会改变相同键值的元素的相对顺序。例如，如果有两个相同的元素 A 和 B，且 A 在 B 的前面，但在排序过程中，A 被移动到了 B 的后面，那么相同键值的元素的相对顺序就发生了改变。这就是快速排序不稳定的一个例子。
9. 红黑树属性
节点颜色：每个节点要么是红色，要么是黑色。
根节点颜色：根节点必须是黑色。
叶子节点颜色：叶子节点 (NIL节点或空节点) 都是黑色。
颜色约束：红色节点的子节点必须是黑色。换句话说，不能有两个连续的红色节点。
黑高度：从根节点到任意叶子节点的路径上，经过的黑色节点数量相同。
10. 跳表原理
跳表基于链表实现，通过在原始链表的基础上建立多层索引来加速查找操作。跳表的原理是通过每两个节点抽出一个节点，建立索引层，从而减少查找路径，降低查找时间复杂度。具体原理如下：
遍历有序链表时，需要从头节点开始逐个节点遍历，直到找到目标节点。这种遍历方式的时间复杂度是 O(n)。
跳表的思想是每两个节点抽出一个节点，建立第一层索引。第一层索引的节点个数是原始链表节点个数的一半。
在第一层索引的基础上，再每两个节点抽出一个节点，建立第二层索引。第二层索引的节点个数是第一层索引节点个数的一半。
以此类推，建立多层索引，直到达到某个条件（如节点个数小于等于2）为止。
当需要查找数据时，从最高层索引开始，逐层向下查找，直到找到目标节点或者找不到为止。
在每一层索引中，通过比较节点的值，确定下一步的查找方向，可以快速缩小查找范围。
如果在某一层索引中找到目标节点，则返回该节点；如果在最底层索引中仍然找不到目标节点，则表示数据不存在。
跳表的查询时间复杂度是 O(log(n))，其中 n 是原始链表的节点个数。跳表的插入和删除操作也可以通过类似的方式进行实现，时间复杂度也是 O(log(n))。跳表的优势在于可以在不使用平衡树的情况下，实现高效的查找、插入和删除操作。
Last updated