字节跳动Java开发面试题及参考答案（数据结构算法-手撕面试题）

怎么判断两个链表是否相交？怎么优化？

判断两个链表是否相交可以采用多种方法。

一种方法是使用双指针。首先分别遍历两个链表，得到两个链表的长度。然后让长链表的指针先走两个链表长度差的步数。之后，同时移动两个链表的指针，每次比较两个指针是否指向相同的节点。如果指向相同节点，那么这两个链表相交；如果直到指针都走到链表末尾还没有相同节点，那么这两个链表不相交。

  // ListNode 定义static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public boolean isIntersect(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return false;}// 1. 计算两个链表的长度int lenA = getLength(headA);int lenB = getLength(headB);// 2. 让较长的链表先走一段距离，使得两个链表剩余部分长度相同while (lenA > lenB) {headA = headA.next;lenA--;}while (lenB > lenA) {headB = headB.next;lenB--;}// 3. 同时遍历两个链表，检查是否相交while (headA != null && headB != null) {if (headA == headB) {return true; // 相交}headA = headA.next;headB = headB.next;}return false; // 不相交}// 计算链表的长度private int getLength(ListNode head) {int length = 0;while (head != null) {length++;head = head.next;}return length;}

例如，有链表 A 长度为 m，链表 B 长度为 n（假设 m > n）。先让链表 A 的指针先走 m - n 步，然后同时移动 A 和 B 的指针。这种方法的时间复杂度是 O (m + n)，因为需要遍历两个链表来获取长度，然后再同时遍历一部分。

优化的方法可以是使用哈希表。遍历一个链表，将链表中的节点存入哈希表。然后遍历另一个链表，每次检查节点是否在哈希表中。如果在，那么两个链表相交；如果遍历完第二个链表都没有发现相同节点，那么两个链表不相交。这种方法的时间复杂度也是 O (m + n)，但是在平均情况下，哈希表的查找速度很快，可以更快地判断是否相交。

import java.util.HashSet;public class Solution2 {// ListNode 定义static class ListNode {int val;ListNode next;ListNode(int x) { val = x; }}public boolean isIntersect(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return false;}// 使用哈希集合来存储链表A的所有节点HashSet<ListNode> nodeSet = new HashSet<>();// 遍历链表A并将所有节点添加到哈希集合中ListNode currA = headA;while (currA != null) {nodeSet.add(currA);currA = currA.next;}// 遍历链表B，并检查是否存在与链表A中的节点相同的节点ListNode currB = headB;while (currB != null) {if (nodeSet.contains(currB)) {return true; // 相交}currB = currB.next;}return false; // 不相交}public static void main(String[] args) {// 创建测试用例ListNode headA = new ListNode(1);headA.next = new ListNode(2);headA.next.next = new ListNode(3);headA.next.next.next = new ListNode(4);headA.next.next.next.next = new ListNode(5);ListNode headB = new ListNode(6);headB.next = new ListNode(7);headB.next.next = headA.next.next; // 相交节点是节点 3Solution2 solution = new Solution2();System.out.println(solution.isIntersect(headA, headB));  // 输出 true}
}

求一个字符串中最长不重复子串的长度

这是一个常见的面试题，要求找到字符串中最长的不重复子串的长度。我们可以使用 滑动窗口 和 哈希集合 的方法来有效地解决这个问题。

思路：

1. 滑动窗口：我们通过维护一个窗口来追踪当前不重复的子串。窗口的左边和右边分别由两个指针表示，我们通过右指针来扩展窗口，左指针则会根据需要收缩窗口。
2. 哈希集合：为了高效检查一个字符是否已经在当前窗口中，我们可以使用哈希集合来存储窗口中的字符。
3. 当我们遇到重复字符时，左指针会移动到重复字符之后的位置，确保窗口内的字符不重复。

具体步骤：

• 初始化一个空的哈希集合，用于存储当前窗口内的字符。
• 使用两个指针：left 和 right。right 用于扩展窗口，left 用于收缩窗口。
• 如果当前字符（s[right]）不在哈希集合中，表示没有重复字符，将其加入集合，并更新最大长度。
• 如果当前字符已经在集合中，移动 left 指针，直到窗口中的字符没有重复。
• 每次移动 right 指针时，更新当前窗口的最大长度。

时间复杂度：

• 时间复杂度是 O(n)，其中 n 是字符串的长度。因为每个字符最多只会被访问两次（一次通过右指针，另一次通过左指针）。

空间复杂度：

• 空间复杂度是 O(min(n, m))，其中 n 是字符串的长度，m 是字符集的大小（对于英语字符集而言，m 通常是常数 256）。

Java 代码实现：

import java.util.HashSet;public class LongestUniqueSubstring {public static int lengthOfLongestSubstring(String s) {// 用一个哈希集合来记录当前窗口内的字符HashSet<Character> set = new HashSet<>();int left = 0;  // 滑动窗口的左指针int maxLength = 0;  // 记录最长子串的长度// 遍历字符串for (int right = 0; right < s.length(); right++) {// 当右指针指向的字符已经在集合中，收缩窗口while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;}// 将当前字符加入集合set.add(s.charAt(right));// 更新最大长度maxLength = Math.max(maxLength, right - left + 1);}return maxLength;}public static void main(String[] args) {String s = "abcabcbb";System.out.println("The length of the longest substring without repeating characters is: " + lengthOfLongestSubstring(s));  // Output: 3 ("abc")}
}

 反转字符串的单词：如何在原字符串上翻转字符串（如将 "i am student" 翻转为 "student am i"），要求空间复杂度为 O (1)？

要在空间复杂度为 O (1) 的情况下翻转原字符串，可以通过多次翻转子串来实现。

首先，将整个字符串进行翻转。例如，对于字符串 "i am student"，翻转后得到 "tneduts ma i"。可以通过双指针的方法来实现，一个指针指向字符串的开头，另一个指针指向字符串的末尾，然后交换两个指针所指向的字符，并且向中间移动指针，直到两个指针相遇。

接着，对每个单词进行翻转。在翻转后的字符串 "tneduts ma i" 中，我们需要将单词翻转回正确的顺序。可以通过再次使用双指针的方式，找到每个单词的开始和结束位置，然后对每个单词进行翻转。例如，找到第一个单词的开始位置是 0，结束位置是 6（索引从 0 开始），将这个单词 "tneduts" 翻转回 "student"。

以下是一个简单的 Java 实现代码：

class StringReverser {public static void reverseString(char[] s) {int left = 0;int right = s.length - 1;// 翻转整个字符串while (left < right) {char temp = s[left];s[left] = s[right];s[right] = temp;left++;right--;}int start = 0;for (int i = 0; i <= s.length; i++) {if (i == s.length || s[i] == ' ') {int end = i - 1;// 翻转每个单词while (start < end) {char tempWord = s[start];s[start] = s[end];s[end] = tempWord;start++;end--;}start = i + 1;}}}
}

可以通过以下方式调用这个方法：

public class Main {public static void main(String[] args) {char[] str = "i am student".toCharArray();StringReverser.reverseString(str);System.out.println(new String(str));}
}

这样就可以在原字符串上，以空间复杂度为 O (1) 的方式翻转字符串。这种方法主要是巧妙地利用了字符数组的原地操作，通过多次双指针的交换来达到翻转的目的。

说说如何维护堆？大根堆和小根堆的插入删除维护？

堆是一种特殊的完全二叉树数据结构，常用于高效地实现优先队列等应用场景，维护堆主要涉及到插入和删除操作时保持其相应特性，以下是具体介绍。

堆的维护基础

无论是大根堆还是小根堆，都要基于完全二叉树的性质，即除了最后一层节点外，其他层节点数都是满的，最后一层节点从左到右依次排列。并且大根堆要求每个节点的值都大于或等于它的子节点的值，小根堆则要求每个节点的值都小于或等于它的子节点的值。

大根堆插入操作维护

当向大根堆插入一个新元素时，首先将这个元素添加到完全二叉树的最后一个位置（按照层次遍历顺序的最后一个节点处）。然后，为了维持大根堆的特性，需要进行向上调整（也叫上浮操作）。从新插入的节点开始，与其父节点比较，如果新节点的值大于父节点的值，就交换它们的位置，接着继续向上和新的父节点比较，重复这个过程，直到新节点的值小于等于父节点的值或者到达根节点位置。

例如，有一个大根堆为 [9, 7, 5, 3, 1]，现在要插入元素 8。先将 8 添加到最后得到 [9, 7, 5, 3, 1, 8]，然后 8 和它的父节点 5 比较，8 大于 5，交换它们位置得到 [9, 7, 8, 3, 1, 5]，接着 8 再和 7 比较，8 大于 7，再交换得到 [9, 8, 7, 3, 1, 5]，此时 8 小于 9，不再调整，大根堆维护完成。

大根堆删除操作维护

删除大根堆的根节点（通常是优先级最高的元素，也就是堆顶元素）时，先将堆顶元素和最后一个元素交换位置，然后删除原来的最后一个元素（也就是现在的堆顶元素）。这样做之后，为了保持大根堆特性，需要从堆顶开始向下调整（也叫下沉操作）。将堆顶元素和它较大的子节点比较，如果堆顶元素小于较大子节点的值，就交换它们的位置，然后继续向下和新的子节点比较，重复这个过程，直到堆顶元素大于等于它的子节点的值或者到达叶子节点位置。

比如大根堆 [9, 8, 7, 3, 1, 5]，删除堆顶 9 后，把最后一个元素 5 放到堆顶得到 [5, 8, 7, 3, 1]，然后 5 和它较大的子节点 8 比较，5 小于 8，交换得到 [8, 5, 7, 3, 1]，接着 8 和 7 比较，符合要求，不再调整，大根堆维护成功。

小根堆插入操作维护

小根堆插入新元素的初始步骤和大根堆一样，也是先添加到完全二叉树的最后一个位置。之后进行向上调整，不过这里是新节点的值若小于父节点的值，就交换它们的位置，一直重复直到新节点的值大于等于父节点的值或者到达根节点。

例如，有小根堆 [1, 3, 5, 7, 9]，插入元素 2。先得到 [1, 3, 5, 7, 9, 2]，2 和它的父节点 5 比较，2 小于 5，交换得到 [1, 3, 2, 7, 9, 5]，2 再和 3 比较，2 小于 3，继续交换得到 [1, 2, 3, 7, 9, 5]，此时 2 大于 1，不再调整，小根堆维护完毕。

小根堆删除操作维护

删除小根堆的堆顶元素时，同样先将堆顶和最后一个元素交换，再删除原来的最后一个元素。然后从新堆顶开始向下调整，将堆顶元素和它较小的子节点比较，若堆顶元素大于较小子节点的值，就交换它们位置，持续重复直到堆顶元素小于等于它的子节点的值或者到达叶子节点。

比如小根堆 [1, 2, 3, 7, 9, 5]，删除堆顶 1 后，把 5 放到堆顶得到 [5, 2, 3, 7, 9]，5 和它较小的子节点 2 比较，5 大于 2，交换得到 [2, 5, 3, 7, 9]，2 和 3 比较符合要求，不再调整，小根堆恢复正常结构。

红黑树的结构？

红黑树是一种自平衡的二叉查找树，它在插入和删除等操作后能通过特定规则自动调整，保证树的平衡性，从而保障查找、插入、删除等操作的时间复杂度在最坏情况下依然能维持在对数级别，以下是其结构特点。

节点颜色属性

红黑树中的每个节点除了包含常规二叉查找树的键值、左右子节点指针等属性外，还额外有一个颜色属性，这个颜色只有红色和黑色两种取值。例如，定义一个红黑树节点类，可以有这样的结构：

class RedBlackTreeNode {int key;RedBlackTreeNode left;RedBlackTreeNode right;RedBlackTreeNode parent;boolean color; // true表示红色，false表示黑色
}

红黑树的五条性质

1. 节点颜色规则：每个节点要么是红色，要么是黑色。
2. 根节点颜色：根节点必须是黑色。例如，在构建一棵红黑树初始时，根节点就会被设置为黑色，这为后续的平衡性质奠定基础。
3. 叶节点颜色：所有的叶节点（也就是空节点，在实际实现中通常用 NULL 指针表示）都是黑色的。这意味着从根节点到叶节点的每条路径上，叶节点都统一视为黑色，便于平衡性质的判断和维护。
4. 红色节点约束：如果一个节点是红色的，那么它的子节点必须是黑色的。这个规则能在一定程度上避免树的某一侧分支过长，有助于维持树的平衡性。比如，当插入一个新节点时，如果新节点和它的父节点都是红色，就违反了这个规则，需要进行相应的调整操作来恢复红黑树的性质。
5. 从根到叶节点的黑色节点数量相等：从任意一个节点（包括根节点）到其所有叶节点的路径上，经过的黑色节点的数量是相等的。这条性质是红黑树平衡性的关键体现，无论树如何进行插入、删除等操作，都要保证这个数量始终相等，使得树不会出现极度不平衡的情况，进而保证了操作的时间复杂度的稳定性。

树的结构示例

假设有一个简单的红黑树，存储了一些整数，根节点的值为 10（黑色），它的左子节点为 5（红色），右子节点为 15（黑色）。5 的左子节点为 3（黑色），右子节点为 8（黑色）等，在整个树的结构中，无论从根节点 10 出发到哪个叶节点的路径上，黑色节点数量都是相同的，并且满足红色节点的子节点为黑色等规则，通过这样的结构和性质来实现高效且平衡的二叉查找树功能。

进程的状态？

在操作系统中，进程有着不同的状态，这些状态反映了进程在其生命周期内不同阶段的执行情况以及与系统资源的交互状态，以下是常见的几种进程状态。

就绪状态（Ready）

当一个进程已经分配到了除 CPU 之外的所有必要资源，例如内存空间、文件描述符等，并且已经准备好可以被 CPU 执行时，这个进程就处于就绪状态。此时它在就绪队列中排队等待 CPU 分配时间片，一旦获得 CPU 时间片，就可以立即开始运行。比如，在一个多任务操作系统中，有多个应用程序同时启动，它们完成了初始化等准备工作后，就都处于就绪状态，等待操作系统的调度算法来选择并分配 CPU 时间片让它们运行，就好像一群运动员已经做好准备，等待裁判发令枪响（也就是获得 CPU 时间片）就起跑一样。

运行状态（Running）

进程获得了 CPU 时间片，正在 CPU 上执行指令，处于实际的运行阶段，就处于运行状态。不过，由于 CPU 通常采用分时复用等调度机制，一个进程不会一直独占 CPU，当分配的时间片用完或者被更高优先级的进程抢占 CPU 时，运行状态的进程就会暂停运行，可能转变为其他状态。例如，一个正在运行的文本编辑进程，在它的 CPU 时间片内执行着文字输入、排版等操作，一旦时间片结束，就会暂时停止运行，进入就绪状态等待下一次的 CPU 时间片分配。

阻塞状态（Blocked）

当进程因为等待某些事件的发生而无法继续执行时，就会进入阻塞状态。比如，进程正在进行文件读取操作，但数据还没有从磁盘加载到内存中，此时进程就会阻塞等待磁盘 I/O 完成；或者进程在等待某个信号量、互斥锁等资源被释放，也会处于阻塞状态。处于阻塞状态的进程不能占用 CPU 资源，只有当等待的事件完成后，它才会从阻塞状态转换为就绪状态，重新进入就绪队列等待 CPU 执行。例如，网络应用进程在发送网络请求后等待服务器的响应，在等待期间就是阻塞状态，当收到响应后，就可以继续后续操作，变为就绪状态等待 CPU 处理后续任务。

挂起就绪状态（Suspended Ready）

这是一种特殊的就绪状态，进程原本处于就绪状态，但由于某些原因（比如系统内存资源紧张等），操作系统将其暂时换出到外存（如磁盘）中，此时进程虽然依旧准备好可以运行，但是需要先被重新调入内存才能真正获得 CPU 时间片运行，就好像运动员被暂时安排到了替补席（外存），等待合适的时机再回到赛场（内存）准备起跑（获得 CPU 时间片）。

挂起阻塞状态（Suspended Blocked）

同样是一种特殊状态，进程原本处于阻塞状态，又因为系统资源等问题被换出到外存中。例如，一个正在等待网络响应的进程，由于内存不足被换出到磁盘，它不仅要等待网络响应这个事件完成，还需要先被重新调入内存才能继续后续操作，相当于既在等待特定事件，又处于被 “冷藏”（换出到外存）的状态。

终止状态（Terminated）

进程完成了它的任务或者因为出现错误、被操作系统强制终止等原因结束了自己的生命周期，就进入终止状态。此时进程所占用的系统资源（如内存、文件描述符等）会被操作系统回收，这个进程也就彻底从系统中消失了。比如，一个用户关闭了正在运行的音乐播放应用，这个应用对应的进程就会进入终止状态，其占用的内存空间等资源会被释放，供其他进程使用。

如何判断图中是否有环？

判断图中是否有环可以采用多种方法，以下是几种常见的方式及其具体原理和操作过程。

深度优先搜索（DFS）

深度优先搜索是一种常用的遍历图的方法，通过在遍历过程中记录节点的访问状态来判断是否存在环。

具体操作时，首先标记起始节点为已访问，然后沿着一条路径尽可能深地访问节点，对于每个访问到的节点，递归地对其未访问的邻接节点进行深度优先搜索。在这个过程中，如果遇到一个已经被标记为已访问的节点，且这个节点不是当前节点的父节点（在树结构中，当前节点是通过其父节点访问到的，这种情况不算环），那就说明图中存在环。

例如，有一个有向图，节点分别为 A、B、C、D 等，从 A 节点开始进行深度优先搜索，先访问 A 并标记为已访问，然后访问 A 的邻接节点 B，标记 B 为已访问，接着访问 B 的邻接节点 C，标记 C 为已访问，如果从 C 又能访问回 A 或者 B（且不是通过正常的回溯路径，也就是不是作为当前节点的父节点被访问到），那就可以判断出图中有环了。

在代码实现上，可以使用一个布尔数组来记录节点的访问状态，如下（以 Java 代码示意简单的有向图的 DFS 判断环，假设图用邻接表表示）：

import java.util.ArrayList;
import java.util.List;class Graph {int V; // 图中节点数量List<List<Integer>> adj; // 邻接表表示图的边关系public Graph(int v) {V = v;adj = new ArrayList<>();for (int i = 0; i < v; i++) {adj.add(new ArrayList<>());}}public void addEdge(int v, int w) {adj.get(v).add(w);}boolean[] visited;boolean isCyclicUtil(int v, int parent) {visited[v] = true;for (int i : adj.get(v)) {if (!visited[i]) {if (isCyclicUtil(i, v))return true;} else if (i!= parent) {return true;}}return false;}public boolean isCyclic() {visited = new boolean[V];for (int i = 0; i < V; i++) {if (!visited[i]) {if (isCyclicUtil(i, -1))return true;}}return false;}
}

拓扑排序

对于有向无环图（DAG，Directed Acyclic Graph），可以进行拓扑排序，如果能够成功完成拓扑排序，说明图中没有环，反之则存在环。

拓扑排序的基本思想是，不断从图中选择入度为 0（没有前驱节点）的节点，将其输出，并从图中删除该节点以及它发出的所有边，然后重复这个过程，直到图中所有节点都被输出或者找不到入度为 0 的节点为止。如果最后所有节点都被输出了，那就是一个有向无环图；如果在某个阶段找不到入度为 0 的节点了，但还有节点未被输出，那就说明图中有环。

例如，有一个表示课程依赖关系的有向图，课程 A 没有前驱课程（入度为 0），先输出 A 并删除 A 以及它指向其他课程的边，接着发现课程 B 的入度变为 0 了，再输出 B，依次类推，如果能够按照这样的顺序把所有课程节点都输出，就说明课程之间的依赖关系图是无环的，否则存在环，意味着存在循环依赖的课程关系。

说说索引的结构，为什么用 B + 树好？

索引是一种用于快速查找数据的数据结构，它可以帮助数据库系统或其他数据存储系统更高效地定位和检索数据。

索引结构种类

1. 哈希索引：哈希索引是基于哈希表实现的。它通过一个哈希函数将索引键值转换为哈希码，然后根据哈希码来存储和查找数据。哈希索引的优点是查找速度非常快，时间复杂度接近常数级别。例如，在一个简单的键 - 值存储系统中，当需要查找一个特定的键对应的内容时，哈希索引可以快速定位到存储位置。但是，哈希索引也有缺点，它不支持范围查询，而且哈希冲突可能会影响性能。
2. B 树索引：B 树是一种平衡的多路查找树。它的每个节点可以包含多个键值对和多个子节点指针。B 树的结构特点使得它能够在树的高度相对较矮的情况下存储大量的数据，并且支持范围查询。在 B 树中，数据节点和索引节点是混合在一起的，查找数据时，从根节点开始，通过比较键值来决定沿着哪个子节点继续查找，直到找到目标数据或者确定数据不存在。
3. B + 树索引：B + 树是 B 树的一种变体。它的结构特点主要是所有的数据都存储在叶子节点上，非叶子节点只存储索引信息，用于引导搜索路径到正确的叶子节点。叶子节点之间通过指针连接成一个有序链表，这使得 B + 树在进行范围查询时非常高效。

为什么 B + 树好

1. 磁盘 I/O 效率高：在数据库系统中，数据通常存储在磁盘上，磁盘 I/O 是一个性能瓶颈。B + 树的结构使得它能够在相对较少的磁盘 I/O 操作次数内找到目标数据。因为它的节点可以存储多个键值对，树的高度相对较低。例如，对于一个存储大量用户信息的数据库表索引，如果使用二叉树作为索引结构，树的高度可能会很高，导致在查找数据时需要多次磁盘 I/O 操作。而 B + 树通过存储多个键值对来降低树的高度，减少磁盘 I/O 次数。
2. 范围查询性能好：由于 B + 树的叶子节点形成了一个有序链表，在进行范围查询时，如查找年龄在某个区间内的所有用户，只需要在叶子节点的链表上顺序扫描即可。相比之下，哈希索引不支持范围查询，B 树虽然也能进行范围查询，但没有 B + 树这么方便和高效，因为 B 树的数据存储在不同的层次节点中，范围查询可能需要在不同层次的节点间跳转。
3. 数据存储和检索的平衡性：B + 树能够保持较好的平衡性，保证从根节点到叶子节点的路径长度基本相同。这意味着无论查找哪个键值对应的的数据，所需的查找时间大致相同，不会出现某些键值查找很快，而某些键值查找很慢的情况，从而提供了稳定的查询性能。

数据库的 B + 树为什么不使用红黑树？

红黑树是一种自平衡二叉查找树，它在插入和删除操作后能够通过调整保持平衡，从而保证查找、插入和删除操作的时间复杂度在最坏情况下为对数级别。然而，数据库索引结构通常更倾向于使用 B + 树而不是红黑树，主要有以下原因。

磁盘 I/O 性能

1. 节点存储容量差异：B + 树的节点可以存储多个键值对和多个子节点指针，它的节点大小通常设计为和磁盘块大小相匹配。这样，在读取一个磁盘块（即一个 B + 树节点）时，可以获取多个索引键值信息，从而减少磁盘 I/O 的次数。而红黑树是二叉树，每个节点只能存储一个键值对和两个子节点指针，在相同的数据量下，红黑树的高度相对较高，会导致更多的磁盘 I/O 操作。例如，在数据库存储大量记录时，为了查找一条记录，使用红黑树可能需要读取多个磁盘块，而 B + 树可能只需要读取较少的磁盘块就能定位到目标数据所在的叶子节点。
2. 顺序访问效率：在数据库中，范围查询是很常见的操作，如查询某个时间段内的订单记录等。B + 树的叶子节点通过指针连接成有序链表，这使得在进行范围查询时可以通过顺序访问叶子节点来获取连续的数据，非常高效。而红黑树没有这种顺序访问的便利结构，对于范围查询，可能需要多次在树中上下遍历，效率较低。

数据存储和索引分离

1. B + 树的结构优势：B + 树将索引和数据分离，所有的数据存储在叶子节点上，非叶子节点只用于索引引导查找路径。这种结构使得 B + 树在存储大量数据时，能够更灵活地管理索引和数据。对于数据库来说，可以方便地对叶子节点的数据进行批量加载、更新和删除等操作，而不影响索引结构的整体稳定性。红黑树由于没有这种明确的索引和数据分离结构，在数据库操作中可能会因为数据的频繁更新而导致树的结构频繁调整，影响性能。
2. 索引更新成本：在数据库进行插入和删除操作时，B + 树的索引更新相对简单。因为非叶子节点主要用于索引路径引导，只有当插入或删除操作导致叶子节点的变化影响到索引结构的平衡时，才需要对非叶子节点进行调整。而红黑树在每次插入或删除操作后，都可能需要对树的结构进行调整以保持平衡，这种频繁的结构调整在数据库环境下会带来较高的成本，尤其是在高并发的数据库操作场景中。

大数据的 topN 问题？

在大数据环境下，topN 问题是指从海量的数据中找出最大（或最小）的 N 个数据。这是一个常见且具有挑战性的问题，因为数据量巨大，不能简单地使用传统的排序方法来解决。

基于排序的方法

如果数据量相对较小，或者对时间复杂度要求不是特别高，可以使用排序算法来解决 topN 问题。例如，使用快速排序或者堆排序等高效的排序算法对所有数据进行排序，然后取前 N 个数据。以快速排序为例，它的平均时间复杂度是 O (n log n)，在排序完成后，直接选取前 N 个数据即可得到 topN 结果。但是，当数据量非常大时，这种方法可能会消耗大量的时间和内存资源，因为需要对整个数据集进行排序。

部分排序方法

可以采用部分排序的策略来解决 topN 问题。例如，先选取一个较小的数据子集，对这个子集进行排序，然后用这个子集的最大（或最小）值来筛选剩余的数据。假设要找最大的 N 个数据，先随机选取 k（k > N）个数据进行排序，得到前 N 个最大值，然后遍历剩余的数据，只有当数据大于这个子集中的最小值时，才考虑更新这个子集。这种方法可以减少排序的数据量，但在数据分布不均匀的情况下，可能需要多次调整子集的选择和排序，才能得到准确的 topN 结果。

基于堆的方法

使用堆这种数据结构可以更高效地解决 topN 问题。如果要找最大的 N 个数据，可以构建一个小根堆。首先，将前 N 个数据构建成小根堆，小根堆的堆顶元素是当前 N 个数据中的最小值。然后，遍历剩余的数据，当遇到比堆顶元素大的数据时，替换堆顶元素，并调整堆以保持小根堆的特性。这样，在遍历完所有数据后，堆中的 N 个元素就是最大的 N 个数据。这种方法的时间复杂度在最好情况下可以接近线性，因为不需要对所有数据进行排序，只需要维护一个大小为 N 的堆，并且每次比较和调整堆的操作时间复杂度相对较低。

例如，有一个海量的用户积分数据，要找出积分最高的 100 个用户。可以先将前 100 个用户的积分构建成小根堆，然后遍历剩下的用户积分数据，当发现比堆顶积分高的用户积分时，替换堆顶积分，并调整堆，最后堆中的 100 个积分对应的用户就是积分最高的用户。

分布式环境下的解决方案

在大数据的分布式环境中，数据可能分布在多个节点或者存储设备上。可以先在各个节点上分别解决 topN 问题，然后将各个节点得到的 topN 结果汇总到一起，再进行一次 topN 的筛选。例如，在一个分布式存储系统中有 10 个节点，每个节点存储了一部分用户数据，每个节点可以先找出自己节点上的 topN 用户，然后将这 10 个节点的 topN 用户数据发送到一个中心节点，在中心节点上再从这些汇总的数据中找出最终的 topN 用户。这种方法需要考虑数据的分布情况、节点间的通信成本以及汇总后的筛选方法等因素。

设计一个短连接生成系统，要求把长 URL 变成短 URL？

设计一个短连接生成系统主要涉及到短链接的生成、存储以及长链接和短链接之间的映射关系管理等方面。

短链接生成算法

1. 哈希算法：可以使用哈希算法来生成短链接。例如，对长 URL 进行 MD5 或者 SHA - 1 等哈希运算，得到一个固定长度的哈希值，然后取哈希值的一部分作为短链接。但是，哈希算法可能会产生冲突，即不同的长 URL 可能生成相同的短链接。为了避免这种情况，可以在哈希值后添加一些其他的标识信息，如时间戳、随机数或者用户 ID 等，来确保短链接的唯一性。
2. 自增序列算法：使用一个自增的整数序列来生成短链接。系统维护一个全局的计数器，每次生成短链接时，将计数器的值转换为一个特定的编码格式，如 Base62 编码（包含数字 0 - 9、字母 a - z、A - Z）。这样，短链接就可以是一个简单的字符串，如 “abc123” 这样的形式。这种方法的优点是短链接简单、易于生成和管理，缺点是需要确保计数器的唯一性和持久性，并且在高并发环境下可能需要考虑并发访问的问题。

存储和映射管理

1. 数据库存储：使用数据库来存储长 URL 和短 URL 之间的映射关系。可以创建一个表，包含两个字段，一个用于存储长 URL，另一个用于存储短 URL。当生成一个短链接时，将长 URL 和短 URL 的映射关系插入到数据库中。在查询时，根据短 URL 在数据库中查找对应的长 URL，然后进行重定向操作。为了提高查询效率，可以在短 URL 字段上添加索引。
2. 内存缓存：除了数据库存储，还可以使用内存缓存来存储频繁访问的长 URL 和短 URL 映射关系。例如，使用 Redis 等内存数据库，将最近生成或者频繁访问的映射关系存储在内存中。当需要查询长 URL 时，首先在内存缓存中查找，如果找到则直接使用，否则再到数据库中查找。这样可以减少数据库的访问次数，提高系统的响应速度。

系统流程

1. 生成短链接：当用户输入一个长 URL 时，系统首先根据选定的生成算法生成一个短链接。如果使用哈希算法，对长 URL 进行哈希运算并处理得到短链接；如果使用自增序列算法，获取计数器的值并转换为短链接。
2. 存储映射关系：将生成的短链接和对应的长 URL 存储到数据库和内存缓存中。
3. 查询和重定向：当用户访问短链接时，系统首先在内存缓存中查找对应的长 URL，如果找到就进行重定向；如果没有找到，再到数据库中查找长 URL，找到后进行重定向，并将这个映射关系添加到内存缓存中，方便后续访问。

例如，一个电商网站有很多商品链接，这些长链接很长且不方便分享。通过短链接生成系统，将长的商品链接转换为短链接，如将 “https://www.example.com/product - details?id = 12345&category = electronics” 转换为 “https://short - link - site/abc123”。用户访问短链接 “https://short - link - site/abc123” 时，系统在内存缓存或者数据库中查找对应的长链接，然后重定向到长链接页面。

项目当时没有考虑负载均衡，如果现在让你去做，你会怎么设计？

如果要为原本没有负载均衡设计的项目添加负载均衡功能，以下是一种可能的设计思路，会从负载均衡器的选择、配置以及后端服务的优化等多方面来考虑：

负载均衡器选型

首先需要选择合适的负载均衡器，常见的有硬件负载均衡器和软件负载均衡器。

1. 硬件负载均衡器：
   优点是性能强劲、稳定性高，能够处理大量的并发连接，并且具备丰富的功能，比如 F5 Big-IP 等，适用于对可靠性和性能要求极高的大型企业级项目。不过，硬件负载均衡器的成本较高，包括购买设备、后续的维护升级等费用都比较可观，而且配置相对复杂，需要专业的网络工程师来进行操作。

2. 软件负载均衡器：
   比较常用的有 Nginx、HAProxy 等开源的软件负载均衡解决方案，它们成本低，部署方便，功能也较为强大。例如，Nginx 可以通过简单的配置文件来实现不同的负载均衡策略，对于中小规模的项目或者对成本比较敏感的项目来说是很好的选择。它不仅可以作为 HTTP 负载均衡器，还能用于 TCP、UDP 等协议的负载均衡，通用性较强。

综合考虑项目的规模、预算以及对性能的要求等因素来选择合适的负载均衡器。如果是一个创业公司的 Web 应用项目，可能选择 Nginx 作为负载均衡器会比较合适，既能满足基本的负载均衡需求，又能控制成本和方便部署。

负载均衡策略选择

根据项目的业务特点来选择合适的负载均衡策略，常见的策略有以下几种：

1. 轮询策略（Round Robin）：
   按照顺序依次将请求分配给后端的服务器，比如有服务器 A、B、C，第一个请求分配给 A，第二个请求分配给 B，第三个请求分配给 C，然后再循环分配。这种策略简单公平，适用于后端服务器性能相近、处理能力相当的情况，能够保证每个服务器接收到大致相同数量的请求。

2. 加权轮询策略（Weighted Round Robin）：
   考虑到后端服务器可能性能不同，给每个服务器分配一个权重，权重越高的服务器在轮询分配请求时被选中的概率越大。例如，服务器 A 的权重为 3，服务器 B 的权重为 2，服务器 C 的权重为 1，那么在分配请求时，总共 6 个权重单位，服务器 A 被选中的概率为 3/6，服务器 B 为 2/6，服务器 C 为 1/6。这种策略适合服务器性能有差异的场景，能更合理地分配负载。

3. IP 哈希策略（IP Hash）：
   根据客户端的 IP 地址通过哈希算法计算出一个值，然后根据这个值将请求固定分配到某一台后端服务器上。这样的好处是对于同一个客户端的多次请求，总是会被分配到同一台服务器，有利于保持会话状态等，比如在有用户登录状态需要保持的 Web 应用中，使用 IP 哈希策略可以避免用户在不同服务器间切换导致登录状态丢失等问题。

4. 最少连接数策略（Least Connections）：
   将新的请求分配给当前连接数最少的服务器，因为服务器的负载情况可以通过连接数来一定程度上体现，连接数少意味着负载相对较轻，这种策略能够动态地根据服务器的实时负载来分配请求，使各服务器的负载更加均衡。

什么是 lru 算法？什么数据结构实现？插入这么做的？查询怎么做的？

LRU 算法介绍

LRU（Least Recently Used）算法是一种缓存淘汰策略，用于在有限的缓存空间中，当缓存已满时，决定淘汰哪些数据。其核心思想是认为最近最少使用的数据在未来被使用的概率也较低，所以当需要腾出空间来存放新的数据时，优先淘汰那些最久没有被使用过的数据。

实现的数据结构

LRU 算法通常使用哈希表和双向链表的组合数据结构来实现。哈希表用于快速查找数据，使得插入和查询操作能够在接近常数时间内完成；双向链表用于维护数据的访问顺序，能够方便地将最近访问的数据移到链表头部，以及删除最久未访问的数据（链表尾部的数据）。

插入操作

1. 步骤一：检查数据是否已存在
   • 首先在哈希表中查找要插入的数据是否已经存在。如果存在，说明这是对已缓存数据的访问，需要将这个数据对应的节点在双向链表中移到头部，因为它刚刚被访问，成为了最近使用的数据。
2. 步骤二：插入新数据（如果不存在）
   • 如果要插入的数据在哈希表中不存在，且缓存未满，那么就创建一个新的节点来存储这个数据，将其插入到双向链表的头部，同时在哈希表中添加这个数据的键值对，键为数据的唯一标识，值为对应的链表节点。
   • 如果缓存已满，那么需要先淘汰最久未使用的数据。找到双向链表的尾部节点，这个节点对应的就是最久未使用的数据。从双向链表中删除这个节点，同时从哈希表中删除对应的键值对。然后再创建新节点插入到链表头部，并在哈希表中添加新的键值对。

一次性哈希原理？

一次性哈希（One - Time Hash）也称为一次性密码哈希，主要原理是通过一个单向哈希函数，使得输入的数据（如密码）经过哈希计算后得到一个固定长度的哈希值。而且这个哈希值的特点是很难通过逆向计算得到原始输入数据，并且即使两个相似的输入数据，其哈希值也会有很大的差异。

从安全性角度来看，一次性哈希主要用于保护敏感信息，如密码存储。当用户设置密码时，系统不会直接存储密码的明文，而是存储密码的哈希值。例如，用户设置密码为 “password123”，系统使用哈希函数（如 SHA - 256）对其进行计算，得到一个类似 “a7cdf89e...（哈希值）” 的结果并存储。

在验证用户密码时，用户输入密码后，系统同样对输入的密码进行哈希计算，然后将计算得到的哈希值与存储的哈希值进行比较。如果两个哈希值相同，就认为用户输入的密码正确。

一次性哈希的安全性还基于哈希函数的抗碰撞性。抗碰撞性是指很难找到两个不同的输入数据，使得它们经过哈希计算后得到相同的哈希值。虽然从理论上来说，随着计算能力的提高，可能会出现碰撞的情况，但对于安全的哈希函数，如 SHA - 256 等，在实际应用中这种碰撞的概率极低。

另外，一次性哈希还可以结合盐（Salt）来进一步提高安全性。盐是一个随机生成的字符串，在计算哈希值时，将盐和密码一起作为输入。例如，盐为 “abcdef”，密码为 “password123”，计算哈希时是对 “abcdefpassword123” 进行哈希计算。这样，即使两个用户使用相同的密码，由于盐不同，他们的哈希值也会不同，增加了攻击者破解密码的难度。

在一些安全协议中，一次性哈希也用于消息认证等场景。发送方将消息和一个一次性的密钥（可以是通过哈希函数生成的）一起进行哈希计算，得到消息认证码（MAC），然后将消息和 MAC 一起发送给接收方。接收方使用相同的方法重新计算 MAC，如果计算得到的 MAC 和收到的 MAC 相同，就可以验证消息的完整性和真实性。

mysql 发一个 sql 请求，到磁盘查出来需要经过哪里步骤？

1. 连接建立
   • 首先，客户端（如应用程序）需要与 MySQL 服务器建立连接。这涉及到网络通信，客户端通过 TCP/IP 协议等方式向 MySQL 服务器发送连接请求，服务器在验证客户端的身份（如用户名和密码）等信息后，建立连接。这个过程中，MySQL 服务器会为这个连接分配相关的资源，如线程等。
2. SQL 解析
   • 连接建立后，客户端发送 SQL 请求到 MySQL 服务器。服务器接收到请求后，会有专门的解析模块对 SQL 语句进行解析。这个解析过程包括语法分析和语义分析。语法分析是检查 SQL 语句是否符合 MySQL 的语法规则，例如检查关键字的使用是否正确、语句的结构是否完整等。语义分析则是理解 SQL 语句的实际意图，比如判断是查询操作、插入操作、更新操作还是删除操作，确定涉及的表、列、条件等信息。
3. 查询优化
   • 在解析完成后，MySQL 会对查询进行优化。这是一个复杂的过程，它会根据数据库的结构（如索引的存在情况）、统计信息（如表的大小、列的不同值数量等）来生成一个最优的查询执行计划。例如，如果查询语句中有 WHERE 子句，优化器会考虑是否可以利用索引来加速查询，比较不同的索引使用方案和表连接方式等，以减少数据的读取量和提高查询速度。
4. 存储引擎操作
   • 经过优化后的查询计划会被传递给存储引擎来执行。MySQL 有多种存储引擎，如 InnoDB、MyISAM 等，不同的存储引擎有不同的存储和读取数据的方式。以 InnoDB 为例，它会根据查询计划去访问磁盘上的数据。如果查询涉及到读取数据，它会先查看缓冲池（Buffer Pool）中是否已经缓存了所需的数据。缓冲池是 InnoDB 存储引擎在内存中维护的一个数据缓存区域，用于减少磁盘 I/O。如果数据在缓冲池中，就可以直接读取；如果不在，就需要从磁盘读取数据页（Data Page）到缓冲池中，这个过程涉及到磁盘 I/O 操作，速度相对较慢。
5. 结果返回
   • 存储引擎从磁盘或者缓冲池中读取到数据后，会按照查询要求进行处理，如过滤数据、排序数据等操作。然后将处理后的结果通过服务器的网络通信模块返回给客户端。客户端接收到结果后，可以根据需要进行进一步的处理，如在应用程序中展示数据等。

如何实现 LRU 缓存？

实现 LRU 缓存可以采用多种方式，以下是一种较为常见的基于哈希表和双向链表组合的数据结构来实现的方法。

1. 数据结构定义
   • 双向链表节点：首先定义双向链表的节点结构，一个节点包含三个部分，分别是键（用于在哈希表中查找）、值（存储实际的数据）以及前后节点的指针。例如，在 Java 中可以定义如下节点类：

class Node {int key;int value;Node prev;Node next;Node(int key, int value) {this.key = key;this.value = value;}
}

• 哈希表和双向链表整体结构：定义一个哈希表用于快速查找节点，以及一个双向链表用于维护数据的访问顺序。在 Java 中，可以通过如下方式初始化：

class LRUCache {private int capacity;private Map<Integer, Node> cache;private Node head;private Node tail;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>();this.head = new Node(-1, -1);this.tail = new Node(-1, -1);head.next = tail;tail.prev = head;}
}

这里capacity表示缓存的容量，cache是哈希表，head和tail分别是双向链表的头节点和尾节点，初始化时将头节点和尾节点相连。

1. 获取数据（get 方法）
   • 当获取数据时，首先在哈希表中查找对应的键。如果找到，说明数据在缓存中，需要将这个节点移到双向链表的头部，因为它刚刚被访问，是最近使用的数据。然后返回节点的值。如果在哈希表中没有找到，说明数据不在缓存中，返回 - 1（或者其他表示未找到的标志）。

public int get(int key) {if (cache.containsKey(key)) {Node node = cache.get(key);moveToHead(node);return node.value;}return -1;
}

• moveToHead方法用于将节点移到头部，其实现如下：

private void moveToHead(Node node) {removeNode(node);addToHead(node);
}
private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;
}
private void addToHead(Node node) {node.next = head.next;head.next.prev = node;head.next = node;node.prev = head;
}

removeNode方法用于将节点从当前位置移除，addToHead方法用于将节点添加到双向链表的头部。

1. 插入数据（put 方法）
   • 当插入数据时，先检查数据是否已经在缓存中。如果在，更新节点的值，并将节点移到头部。如果不在，创建一个新的节点，将其插入到头部。如果此时缓存已满，需要删除双向链表的尾节点对应的键值对，然后再插入新节点。

public void put(int key, int value) {if (cache.containsKey(key)) {Node node = cache.get(key);node.value = value;moveToHead(node);} else {Node newNode = new Node(key, value);if (cache.size() >= capacity) {cache.remove(tail.prev.key);removeNode(tail.prev);}addToHead(newNode);cache.put(key, newNode);}
}

通过以上的步骤，就可以实现一个简单的 LRU 缓存，能够有效地管理缓存数据，在缓存已满时淘汰最近最少使用的数据。

系统设计：如何设计一个延迟队列？

延迟队列是一种特殊的队列，它可以让消息或者任务在延迟一段时间后再被处理。以下是一种设计延迟队列的方法。

数据结构选择

• 基于优先级队列和时间轮的组合：可以使用优先级队列来存储任务，任务的优先级根据延迟时间来确定，延迟时间越短，优先级越高。时间轮是一种数据结构，用于管理时间流逝和任务到期。它由多个槽位组成，每个槽位代表一个时间单位，任务根据其延迟时间被分配到相应的槽位中。

基本操作实现

• 任务添加（入队）：
  • 当一个任务需要加入延迟队列时，首先计算任务的延迟时间。根据延迟时间确定任务在优先级队列中的优先级，将任务插入到优先级队列中。同时，根据任务的延迟时间和当前时间，计算任务应该被放入时间轮的哪个槽位。将任务添加到时间轮对应的槽位中。
• 任务获取（出队）：
  • 时间轮按照一定的时间间隔（如每秒）进行滴答（tick）操作。每次滴答时，检查当前槽位中的任务是否到期。如果有到期的任务，将这些任务从时间轮的槽位中取出，放入一个临时的执行队列中。然后，从优先级队列中获取优先级最高（也就是延迟时间最短）的任务，将其放入执行队列中。执行队列中的任务可以被消费者获取并执行。
• 时间轮的实现细节：
  • 时间轮的大小（槽位数量）可以根据任务延迟的范围和精度来确定。例如，如果任务延迟范围是从 0 到 60 秒，精度为 1 秒，那么可以设计一个有 60 个槽位的时间轮。每个槽位可以用一个链表来存储任务，当任务添加到时间轮时，根据延迟时间计算出槽位索引（例如，延迟 10 秒的任务，在时间轮的第 10 个槽位），将任务添加到对应的链表中。
  • 时间轮需要一个定时器来驱动滴答操作。在编程语言中，可以使用操作系统提供的定时器或者专门的定时任务库。例如，在 Java 中，可以使用 ScheduledExecutorService 来实现定时的滴答操作。

可靠性和扩展性

• 持久化：为了保证延迟队列的可靠性，尤其是在系统重启或者出现故障的情况下，需要对任务进行持久化。可以将任务的信息（如任务内容、延迟时间、添加时间等）存储到数据库或者文件系统中。当系统重启时，从存储介质中读取任务信息，重新将任务添加到延迟队列中。
• 分布式扩展：在分布式系统中，可以将延迟队列进行分布式部署。可以使用分布式协调服务（如 Zookeeper 或者 Consul）来管理多个延迟队列实例之间的协调和任务分配。例如，将任务按照一定的规则（如根据任务的类型或者用户 ID 等）分配到不同的延迟队列实例中，通过分布式协调服务来保证任务不会重复处理，并且在某个实例出现故障时，能够将任务转移到其他正常的实例中进行处理。