阿Q技术站

深浅色

小米安卓一二三面面经，建议收藏！ ​

时间线：11月中旬

来源：https://www.nowcoder.com/discuss/560935519438270464?sourceSSR=users

一面 ​

1、三数之和（做的太快，加一题） ​

思路：

  1. 排序数组： 首先，对给定的整数数组 nums 进行排序。这一步是为了方便后续的处理，特别是在寻找双指针时。
  2. 遍历数组： 从数组的第一个元素开始，依次遍历数组中的每个元素。在遍历的过程中，以当前遍历到的元素 nums[i] 作为三元组中的第一个元素。
  3. 双指针搜索： 对于当前固定的元素 nums[i]，使用双指针 left 和 right 分别指向数组中剩余部分的起始和结束位置。在 left < right 的条件下，执行以下步骤：
    • 计算当前三元组的目标值 target，即 target = -nums[i]。这是因为我们要找的是三个数的和为0，所以我们将问题转化为了两数之和的问题。
    • 在剩余部分中使用双指针法寻找两个数的和等于 target。具体地，我们让 left 从 i + 1 开始向右移动，right 从 n - 1 开始向左移动，直到 left 不小于 right 为止。
    • 当找到满足条件的两个数时，即 nums[left] + nums[right] == target 时，我们将这个三元组 [nums[i], nums[left], nums[right]] 加入到结果中。然后，我们继续寻找下一个满足条件的三元组。
  4. 跳过重复元素： 在移动指针时，需要注意跳过重复的元素。如果当前指针指向的元素与上一个元素相同，我们应该将指针向后移动，直到找到一个不同的元素。这一步是为了避免重复计算相同的三元组。
  5. 返回结果： 当遍历完整个数组后，我们得到了所有满足条件的三元组。将这些三元组作为结果返回即可。

参考代码：

c++
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;

        // 首先对数组进行排序
        sort(nums.begin(), nums.end());

        int n = nums.size();

        // 遍历数组，将三数之和问题转化为两数之和问题
        for (int i = 0; i < n - 2; ++i) {
            // 跳过重复的数字
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int target = -nums[i]; // 转化为求两数之和的目标值
            int left = i + 1; // 左指针从i的下一个位置开始
            int right = n - 1; // 右指针从数组的最后一个位置开始

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == target) { // 找到了满足条件的三元组
                    result.push_back({nums[i], nums[left], nums[right]});

                    // 跳过重复的数字
                    while (left < right && nums[left] == nums[left + 1]) ++left;
                    while (left < right && nums[right] == nums[right - 1]) --right;

                    ++left;
                    --right;
                } else if (sum < target) { // 如果和小于目标值，左指针右移
                    ++left;
                } else { // 如果和大于目标值，右指针左移
                    --right;
                }
            }
        }

        return result;
    }
};

int main() {
    Solution solution;

    // 测试用例
    vector<int> nums = {-1, 0, 1, 2, -1, -4};

    // 调用函数计算三数之和为0的三元组
    vector<vector<int>> result = solution.threeSum(nums);

    // 输出结果
    cout << "三数之和为0的三元组为：" << endl;
    for (const auto& triplet : result) {
        cout << "[";
        for (int num : triplet) {
            cout << num << ",";
        }
        cout << "]" << endl;
    }

    return 0;
}

2、N皇后问题（确定好每一行的值，回溯处理，结合判断条件） ​

思路：

  1. 初始化棋盘： 首先创建一个 n x n 的棋盘，用一个二维字符向量 board 表示。初始时，所有格子都填充为'.'，表示空位。
  2. 回溯算法： 使用回溯算法，在每一行放置一个皇后，并检查是否满足题目要求。如果满足要求，则继续放置下一行的皇后；如果不满足要求，则回溯到上一行，尝试其他位置。
  3. 递归终止条件： 当放置了 n 个皇后时，即所有行都放置了皇后，得到一个可行解。将当前棋盘状态加入结果集。
  4. 检查位置是否可放置皇后： 在放置皇后时，需要检查当前位置是否可以放置皇后。具体地，我们需要检查当前位置的同一列、同一条斜线上是否已经有皇后。如果没有，则可以放置皇后；如果有，则不能放置。
  5. 输出结果： 最终得到所有满足条件的棋盘状态，即为所有不同的 N 皇后问题的解决方案。

参考代码：

c++
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.')); // 初始化棋盘，全部填充为'.'

        backtrack(result, board, 0, n);
        
        return result;
    }
    
    void backtrack(vector<vector<string>>& result, vector<string>& board, int row, int n) {
        if (row == n) { // 如果已经放置了 n 个皇后，将当前棋盘状态加入结果集
            result.push_back(board);
            return;
        }
        
        for (int col = 0; col < n; ++col) {
            if (isValid(board, row, col, n)) { // 判断当前位置是否可以放置皇后
                board[row][col] = 'Q'; // 放置皇后
                backtrack(result, board, row + 1, n); // 递归放置下一个皇后
                board[row][col] = '.'; // 回溯，重置当前位置
            }
        }
    }
    
    bool isValid(vector<string>& board, int row, int col, int n) {
        // 检查同一列是否有皇后
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        
        // 检查左上方是否有皇后
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        // 检查右上方是否有皇后
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        return true; // 当前位置可以放置皇后
    }
};

int main() {
    Solution solution;
    int n = 4; // 棋盘大小
    
    // 解决 N 皇后问题
    vector<vector<string>> result = solution.solveNQueens(n);

    // 输出结果
    for (const auto& solution : result) {
        for (const string& row : solution) {
            cout << row << endl;
        }
        cout << endl;
    }

    return 0;
}

3、单例类实现 ​

这里把两种单例模式都写一下吧。

饿汉模式

饿汉模式是指在程序启动时就创建单例对象，因此也称为静态初始化方式。在这种模式下，单例对象在程序生命周期内只会被创建一次，因此不存在线程安全的问题。

c++
class Singleton {
public:
    static Singleton& getInstance() {
        static Singleton instance; // 在程序启动时创建单例对象
        return instance;
    }

    // 禁止拷贝构造和赋值操作符
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;

private:
    // 私有化构造函数，禁止外部创建实例
    Singleton() {}
};

懒汉模式

懒汉模式是指在首次使用时才创建单例对象，因此也称为延迟加载方式。在这种模式下，需要考虑多线程环境下的线程安全问题。

c++
#include <mutex>

class Singleton {
public:
    static Singleton& getInstance() {
        std::call_once(flag, [&]() {
            instance = new Singleton(); // 在首次使用时创建单例对象
        });
        return *instance;
    }

    // 禁止拷贝构造和赋值操作符
    Singleton(const Singleton&) = delete;
    Singleton& operator=(const Singleton&) = delete;

private:
    Singleton() {} // 私有化构造函数，禁止外部创建实例
    static Singleton* instance;
    static std::once_flag flag;
};

Singleton* Singleton::instance = nullptr;
std::once_flag Singleton::flag;

1、介绍一下项目 ​

2、spdlog 和 glog是如何替换的 ​

3、数据压缩处理的一个过程 ​

4、池化操作的过程 ​

八股 ​

1、tcp的三次握手，四次挥手 ​

三次握手

  1. 第一次握手： 客户端发送一个TCP报文段，其中包含一个SYN（同步）标志位，以及客户端的初始序列号（ISN，Initial Sequence Number）。这表示客户端请求建立连接，并设置了初始序列号，以便后续的数据传输。
  2. 第二次握手： 服务器接收到客户端的SYN后，确认收到，并发送回一个带有SYN和ACK（确认）标志位的报文段。服务器也会为自己设置一个初始序列号。
  3. 第三次握手： 客户端接收到服务器的SYN-ACK后，确认收到，并发送一个ACK标志位的报文段。这个报文段表示连接已经建立，双方可以开始进行数据传输。

此时，TCP连接已经建立，双方可以安全地传输数据。

四次挥手

  1. 第一次挥手： 当客户端完成了数据传输后，它会发送一个FIN标志位的报文段，表示它不再有数据要发送，但仍然愿意接收数据。客户端进入FIN_WAIT_1状态。
  2. 第二次挥手： 服务器接收到客户端的FIN后，确认收到，并发送一个ACK标志位的报文段。此时，服务器可以继续向客户端发送数据。
  3. 第三次挥手： 当服务器也完成了数据传输后，它会发送一个FIN标志位的报文段，表示它不再有数据要发送。服务器进入CLOSE_WAIT状态，等待客户端的确认。
  4. 第四次挥手： 客户端接收到服务器的FIN后，确认收到，并发送一个ACK标志位的报文段。客户端进入TIME_WAIT状态，等待可能出现的服务器重传。

在TIME_WAIT状态等待一段时间后，客户端和服务器都可以关闭连接。整个四次挥手过程确保双方都完成了数据传输并关闭了连接。

2、cpp的hashmap实现原理，红黑树的结构特点 ​

C++ 中的 std::unordered_map 使用了哈希表（hash map）来实现。哈希表是一种数据结构，它能够提供快速的插入、删除和查找操作。其实现原理大致如下：

  1. 哈希函数：当元素被插入到哈希表中时，哈希函数将根据键计算出一个索引，该索引用于确定元素在哈希表中的位置。一个好的哈希函数应该将键均匀地映射到哈希表的不同位置，以避免冲突。
  2. 冲突解决：由于哈希函数的映射不一定是唯一的，可能会出现不同的键映射到相同的索引位置，这就是哈希冲突。常见的解决冲突的方法有开放定址法和链表法。在 C++ 中的 std::unordered_map 中，一般使用链表法或者是链表法和开放定址法的混合实现。
  3. 扩容和再哈希：当哈希表中的元素数量超过了一定的阈值，哈希表需要进行扩容。扩容通常会创建一个更大的数组，并将现有的元素重新插入到新的数组中，这个过程称为再哈希。

红黑树是一种自平衡的二叉查找树，它在 C++ 的标准库中被用于实现 std::map 和 std::set。红黑树具有以下特点：

  1. 节点的颜色：每个节点要么是红色，要么是黑色。
  2. 根节点和叶子节点：根节点是黑色的，叶子节点（NIL 节点）也是黑色的。
  3. 红色节点的子节点：红色节点的子节点必须是黑色的（不能有两个连续的红色节点）。
  4. 每条路径的黑色节点数目：从根节点到叶子节点的每条路径上，黑色节点的数目必须相同。

3、cpp编译一般经过几个步骤 ​

  1. 预处理阶段：在这个阶段，预处理器处理源文件中的预处理指令，比如 #include、#define 等。预处理器会根据这些指令展开头文件并替换宏定义，生成一个经过预处理的源文件。

    $ g++ -E source.cpp -o source.ii

  2. 编译阶段：编译器将预处理后的源文件转换成汇编代码。在这个阶段，编译器会对源文件进行词法分析、语法分析和语义分析，并生成相应的中间代码或汇编代码。

    $ g++ -S source.ii -o source.s

  3. 汇编阶段：汇编器将汇编代码转换成机器码或者目标文件。在这个阶段，汇编器会将汇编代码转换成可重定位的机器码，并生成目标文件。

    $ as source.s -o source.o

  4. 链接阶段：链接器将目标文件和库文件链接在一起，生成最终的可执行文件。在这个阶段，链接器会解析目标文件之间的引用关系，将它们连接到正确的位置上，并将库文件中的函数和变量链接到可执行文件中。

    $ g++ source.o -o executable

4、指针和引用的区别 ​

  1. 语法和操作符：
    • 指针使用 * 表示声明和解引用，比如 int *ptr; *ptr = 10;。
    • 引用使用 & 表示声明和获取地址，比如 int &ref = var;。
  2. 空值：
    • 指针可以是空指针（nullptr 或 NULL），表示指向空地址。
    • 引用必须在声明时初始化，并且不能在后续改变引用的绑定对象，因此不存在空引用的概念。
  3. 指向的对象：
    • 指针可以在运行时被重新赋值指向不同的对象。
    • 引用一旦绑定到对象，就不能再改变绑定的对象，它始终引用同一个对象。
  4. 操作的对象：
    • 指针可以指向另一个指针，也可以指向自己。
    • 引用必须在初始化时指定所引用的对象，不能改变引用的目标对象。
  5. 传递方式：
    • 通过指针传递参数，被调用函数可以修改原始数据。
    • 通过引用传递参数，被调用函数也可以修改原始数据，但是语法更加清晰，且不需要手动解引用。

5、static和const的区别 ​

  1. static：
    • static 可以用来修饰变量、函数和类的成员。
    • 修饰变量时，表示该变量在程序的整个生命周期内存在，不会因为函数调用的结束而被销毁，且只会被初始化一次。
    • 修饰函数时，表示该函数是静态函数，它不属于任何对象，可以直接通过类名或对象名调用，静态函数不能访问非静态成员。
    • 修饰类的成员时，表示该成员是静态成员，属于整个类，而不是类的实例，所有类的实例共享同一个静态成员。
  2. const：
    • const 用于定义常量，表示该变量的值在定义后不能被修改。
    • 可以修饰变量、指针和成员函数。
    • 修饰变量时，表示该变量是一个常量，不能被修改。
    • 修饰指针时，表示指针所指向的值是常量，不能通过该指针修改所指向的值。
    • 修饰成员函数时，表示该成员函数不会修改对象的状态。

6、malloc 和 new 的差别 ​

  1. 语法和类型：
    • malloc 是 C 语言中的函数，需要包含 <cstdlib> 头文件，它返回的是 void* 类型的指针，需要进行显式的类型转换。
    • new 是 C++ 中的运算符，不需要包含额外的头文件，它返回的是所申请类型的指针，不需要进行显式的类型转换。
  2. 内存大小：
    • malloc 需要手动计算所需内存的大小，并以字节为单位进行分配。
    • new 在分配内存时，会根据所需类型的大小自动计算需要分配的内存空间。
  3. 构造函数和析构函数：
    • malloc 只分配内存空间，不会调用对象的构造函数和析构函数。
    • new 在分配内存空间的同时，会调用对象的构造函数进行初始化，并在对象生命周期结束时调用析构函数进行清理。
  4. 异常处理：
    • malloc 分配内存失败时返回 NULL，需要手动检查并处理。
    • new 分配内存失败时会抛出 std::bad_alloc 异常，可以使用异常处理机制进行处理。
  5. 对数组的支持：
    • malloc 和 free 配对使用来分配和释放内存。
    • new 和 delete 配对使用来分配和释放单个对象的内存，new[] 和 delete[] 配对使用来分配和释放数组对象的内存。

二面 ​

1、你这个怎么样cmake的 ​

2、make -j4 多线程编译，你了解里面的原理吗 ​

3、编译的产物是什么 ​

4、你怎么样进行单元测试的 ​

八股： ​

1、说一下封装继承多态 ​

  1. 封装：
    • 封装是面向对象编程的基本原则之一，它将数据和操作数据的方法（即函数）封装在一起，对外部隐藏对象的内部实现细节。
    • 封装提供了对象的抽象，使得对象可以被看作是一个独立的实体，而不需要了解其内部实现细节。
    • 封装通过访问控制（比如 private、protected、public）来控制对象的访问权限，提高了代码的安全性和可维护性。
  2. 继承：
    • 继承是一种代码复用的机制，它允许一个类（称为子类或派生类）继承另一个类（称为父类或基类）的属性和方法。
    • 继承可以建立类之间的层次关系，子类可以继承父类的属性和方法，并且可以添加自己的新属性和方法，从而实现代码的重用和扩展。
  3. 多态：
    • 多态是指同一个操作作用于不同的对象上时，可以产生不同的行为。
    • 多态可以分为编译时多态（静态多态）和运行时多态（动态多态）两种形式。
    • 编译时多态是指函数重载和运算符重载，它们在编译时确定调用哪个函数或运算符。
    • 运行时多态是指通过虚函数（virtual function）实现的多态，它允许子类重写父类的虚函数，并且在运行时确定调用哪个函数，实现了动态绑定。

2、说一下STL的容器和特点 ​

  1. 序列容器：
    • std::vector：动态数组，支持快速的随机访问和尾部插入/删除操作，适合用于需要动态大小的数组情况。
    • std::deque：双端队列，支持快速的头尾插入/删除操作，适合用于需要在两端进行插入/删除的情况。
    • std::list：双向链表，支持快速的插入/删除操作，但不支持随机访问，适合用于需要频繁插入/删除操作的情况。
  2. 关联容器：
    • std::set：集合，内部元素按照一定的顺序进行排序，不允许重复元素。
    • std::map：映射，键值对的集合，内部元素按照键的顺序进行排序，不允许重复的键。
    • std::multiset：多重集合，允许重复元素。
    • std::multimap：多重映射，允许重复的键。
  3. 无序容器：
    • std::unordered_set：无序集合，内部元素无序存储，不允许重复元素。
    • std::unordered_map：无序映射，键值对的集合，内部元素无序存储，不允许重复的键。
    • std::unordered_multiset：无序多重集合，允许重复元素。
    • std::unordered_multimap：无序多重映射，允许重复的键。
  4. 适配器容器：
    • std::stack：栈，基于其他容器实现的后进先出（LIFO）的数据结构。
    • std::queue：队列，基于其他容器实现的先进先出（FIFO）的数据结构。
    • std::priority_queue：优先队列，基于其他容器实现的按照优先级排序的数据结构。

STL 的容器特点：

  • 高度模板化：STL 容器是模板类，可以存储任意类型的元素。
  • 高效性能：STL 容器在设计上注重性能，并且使用了高效的数据结构和算法。
  • 统一的接口：STL 容器的接口设计统一，使得不同的容器可以以类似的方式进行操作。
  • 丰富的功能：STL 容器提供了丰富的功能，包括插入、删除、查找、排序等操作，以及迭代器支持等。

3、线程和进程的差别 ​

  1. 定义：
    • 进程是程序的一次执行过程，是系统进行资源分配和调度的基本单位。
    • 线程是进程的一个实体，是 CPU 调度和分派的基本单位，是比进程更小的能独立运行的基本单位。
  2. 资源分配：
    • 进程拥有独立的地址空间，每个进程有自己的代码、数据和堆栈，进程间的通信需要使用特殊的机制（比如管道、信号、共享内存等）。
    • 线程共享进程的地址空间和其他资源，比如打开的文件、信号处理等，线程之间的通信更加方便快捷。
  3. 切换开销：
    • 由于进程拥有独立的地址空间，进程间的切换开销较大，需要保存和恢复大量的上下文信息。
    • 线程共享进程的地址空间，线程间的切换开销较小，只需要保存和恢复少量的上下文信息。
  4. 并发性：
    • 进程是独立的执行单位，进程间的通信和同步需要特殊的机制来实现，比如管道、信号、共享内存等。
    • 线程共享进程的地址空间和其他资源，线程间的通信和同步更加方便快捷，可以直接通过共享变量等方式进行。
  5. 灵活性：
    • 进程是资源分配和调度的基本单位，进程的创建和销毁比较耗费资源，但是具有较好的独立性和稳定性。
    • 线程是 CPU 调度和分派的基本单位，线程的创建和销毁比较轻量级，但是由于共享资源，容易出现竞争和冲突。

4、进程通信的方式 ​

  1. 管道：
    • 管道是一种半双工的通信方式，适用于具有亲缘关系的进程间通信。
    • 管道可以是匿名管道（只能用于具有亲缘关系的进程）或命名管道（允许无关的进程之间通信）。
  2. 消息队列：
    • 消息队列是一种消息的链表，存放在内核中并由消息队列标识符标识。
    • 可以通过消息队列进行不同进程之间的通信，发送和接收消息。
  3. 信号量：
    • 信号量是一种计数器，用于保护共享资源，多个进程可以通过操作信号量来实现同步和互斥。
    • 信号量可以用于解决生产者-消费者问题等并发控制问题。
  4. 共享内存：
    • 共享内存允许多个进程访问同一块物理内存区域，进程可以直接读写共享内存中的数据。
    • 共享内存通常用于高性能的数据共享，但需要开发人员自己解决进程间的同步问题。
  5. 套接字：
    • 套接字是一种通信机制，可以用于不同计算机之间的进程通信，也可以用于同一台计算机上的进程通信。
    • 套接字通常用于网络编程，可以实现进程间的跨网络通信。

5、说一下mysql事务的特点 ​

  1. 原子性（Atomicity）：
    • 事务中的所有操作要么全部成功，要么全部失败回滚，不存在部分执行的情况。
    • MySQL 使用了事务日志（Redo Log 和 Undo Log）来保证事务的原子性，可以在发生故障时进行回滚操作，确保事务的完整性。
  2. 一致性（Consistency）：
    • 事务在执行前后，数据库的状态应该保持一致性，即事务执行前后，数据库中的数据应该满足所有的约束和完整性规则。
    • MySQL 使用了锁机制来保证事务的一致性，通过锁定需要修改的数据，防止其他事务的干扰。
  3. 隔离性（Isolation）：
    • 事务的执行应该相互隔离，即一个事务的执行不应该影响其他事务的执行。
    • MySQL 提供了不同的隔离级别（如 READ UNCOMMITTED、READ COMMITTED、REPEATABLE READ、SERIALIZABLE）来控制事务的隔离性，可以根据需求选择合适的隔离级别。
  4. 持久性（Durability）：
    • 一旦事务提交成功，其结果应该持久保存在数据库中，即使发生系统故障也不应该丢失。
    • MySQL 使用了事务日志（Redo Log）来保证事务的持久性，可以在系统故障后通过日志进行恢复，保证数据的持久性。

6、说一下死锁的特点，如何解决死锁，mysql有多少种锁 ​

死锁是指两个或多个进程在执行过程中因争夺资源而造成的一种互相等待的现象，导致它们都无法继续执行。死锁的特点包括：

  1. 互斥条件：资源必须不能被共享，一次只能被一个进程使用。
  2. 持有和等待条件：进程必须持有至少一个资源，并且在等待获取其他进程持有的资源。
  3. 不可抢占条件：已经分配的资源不能被其他进程抢占，只能由持有它的进程显式释放。
  4. 循环等待条件：存在一个等待链，每个进程都在等待下一个进程所持有的资源。

解决死锁的方法主要有以下几种：

  1. 死锁预防：通过合理地设计系统资源分配策略，避免产生死锁的发生。比如，按照某种顺序获取资源，从而破坏循环等待条件。
  2. 死锁避免：在资源分配过程中，通过检查系统状态来避免可能导致死锁的资源分配。比如，银行家算法就是一种死锁避免的方法。
  3. 死锁检测和解除：允许死锁的发生，但是在发生死锁时进行检测和解除。比如，通过检测资源分配图来判断是否存在死锁，然后选择合适的进程进行回滚操作来解除死锁。

MySQL 中常用的锁包括：

  1. 行级锁：MySQL 支持行级锁，可以在操作某行数据时对该行进行加锁，以防止其他事务对该行进行修改。常见的行级锁包括共享锁（SELECT ... LOCK IN SHARE MODE）和排它锁（SELECT ... FOR UPDATE）。
  2. 表级锁：MySQL 也支持表级锁，可以对整个表进行加锁。常见的表级锁包括读锁（LOCK TABLES ... READ）和写锁（LOCK TABLES ... WRITE）。
  3. 页级锁：MySQL 的 MyISAM 存储引擎支持页级锁，将数据按照页（通常是 1KB 或 4KB）进行加锁。
  4. 意向锁：MySQL 使用意向锁来表示事务对表中某些行或页的意向加锁，以协调不同事务对同一表的加锁操作。

手撕 ​

写一下快排 ​

快速排序的思想

快速排序（Quick Sort）是一种基于分治思想的排序算法。其基本思想是选择一个基准值，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有元素都比基准值小，另一部分的所有元素都比基准值大，然后对这两部分分别进行快速排序，最终使整个序列有序。

快速排序的递归实现思路

  1. 选择基准值：从待排序的数据中选择一个基准值（通常选择最后一个元素）。
  2. 分割数组：将数组分割成两部分，使得左侧部分的所有元素都小于基准值，右侧部分的所有元素都大于基准值，基准值所在的位置称为分割点。
  3. 递归排序：对左右两个子数组分别进行递归排序。

参考代码：

c++
#include <iostream>
#include <vector>
using namespace std;

// 快速排序的分区函数，将数组分割成两部分并返回分割点的索引
int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high]; // 选择最后一个元素作为基准值
    int i = low - 1; // i 是小于基准值的元素的最后一个索引
    for (int j = low; j < high; ++j) {
        if (nums[j] < pivot) {
            ++i;
            swap(nums[i], nums[j]); // 将小于基准值的元素交换到左侧
        }
    }
    swap(nums[i + 1], nums[high]); // 将基准值放到正确的位置
    return i + 1; // 返回基准值的索引
}

// 递归实现
void quickSortRecursive(vector<int>& nums, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(nums, low, high);
        quickSortRecursive(nums, low, pivotIndex - 1); // 对左侧子数组进行快排
        quickSortRecursive(nums, pivotIndex + 1, high); // 对右侧子数组进行快排
    }
}

int main() {
    vector<int> nums = {3, 2, 5, 1, 7, 4};
    
    // 输出排序前的数组
    cout << "排序前的数组：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    // 递归实现快速排序
    quickSortRecursive(nums, 0, nums.size() - 1);

    // 输出排序后的数组
    cout << "递归实现快速排序后的数组：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

快速排序的非递归实现思路

非递归实现使用栈来模拟递归过程，将待排序区间的边界存储在栈中，实现了迭代的效果。

  1. 选择基准值：从待排序的数据中选择一个基准值（通常选择最后一个元素）。
  2. 使用栈模拟递归：将待排序的区间边界入栈。
  3. 循环处理：循环从栈中取出边界，对当前区间进行分割和排序，直到栈为空。

参考代码：

c++
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 快速排序的分区函数，将数组分割成两部分并返回分割点的索引
int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high]; // 选择最后一个元素作为基准值
    int i = low - 1; // i 是小于基准值的元素的最后一个索引
    for (int j = low; j < high; ++j) {
        if (nums[j] < pivot) {
            ++i;
            swap(nums[i], nums[j]); // 将小于基准值的元素交换到左侧
        }
    }
    swap(nums[i + 1], nums[high]); // 将基准值放到正确的位置
    return i + 1; // 返回基准值的索引
}

// 非递归实现
void quickSortIterative(vector<int>& nums, int low, int high) {
    stack<pair<int, int>> stk;
    stk.push({low, high});
    while (!stk.empty()) {
        auto [l, h] = stk.top();
        stk.pop();
        if (l < h) {
            int pivot = nums[h];
            int i = l - 1;
            for (int j = l; j < h; ++j) {
                if (nums[j] < pivot) {
                    ++i;
                    swap(nums[i], nums[j]);
                }
            }
            swap(nums[i + 1], nums[h]);
            int pivotIndex = i + 1;
            stk.push({l, pivotIndex - 1});
            stk.push({pivotIndex + 1, h});
        }
    }
}

int main() {
    vector<int> nums = {3, 2, 5, 1, 7, 4};

    // 非递归实现快速排序
    quickSortIterative(nums, 0, nums.size() - 1);

    // 输出排序后的数组
    cout << "非递归实现快速排序后的数组：";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

智力题 ​

两次机会如何确定8个球中最重的那个，其他7个都一样重？

这个智力题大家下去可以思考思考，有答案可以给我留言哈哈哈。

三面 ​

1、介绍一下mysql的四种隔离级别 ​

  1. 读未提交：
    • 这是最低的隔离级别，事务可以读取其他事务未提交的数据。
    • 可能会导致脏读、不可重复读和幻读的问题。
  2. 读已提交：
    • 事务只能读取其他事务已提交的数据，可以避免脏读。
    • 但是可能会出现不可重复读和幻读的问题。
  3. 可重复读：
    • 在同一个事务内，多次读取同一数据会得到一致的结果，即使其他事务对该数据进行了修改。
    • 可以避免脏读和不可重复读，但是可能会出现幻读的问题。
  4. 串行化：
    • 最高的隔离级别，事务按照串行的方式执行，可以避免脏读、不可重复读和幻读的问题。
    • 但是会降低数据库的并发性能，因为它会限制多个事务同时访问相同的数据。

2、可重复读是怎么样实现的？原理是怎么样的 ​

可重复读是指在同一个事务内多次读取同一数据时，可以得到一致的结果，即使其他事务对该数据进行了修改。这种隔离级别可以避免脏读和不可重复读的问题，但仍然可能出现幻读的问题。

实现可重复读的主要原理是在事务开始时，将事务需要读取的数据行的快照（Snapshot）保存在事务的视图（View）中，事务内的所有读操作都使用这个视图来获取数据。这样即使其他事务对数据进行了修改，事务的视图仍然可以看到一致的数据状态，从而保证了可重复读的效果。

具体来说，实现可重复读的过程可以分为以下几个步骤：

  1. 事务开始：当事务开始时，会创建一个事务 ID，并建立一个事务视图，该视图包含了事务开始时数据库中的所有数据快照。
  2. 读取数据：当事务执行读操作时，会使用事务开始时建立的事务视图来获取数据。这意味着无论其他事务对数据做了什么修改，事务都只能看到事务开始时的数据状态。
  3. 写入数据：当事务执行写操作时，会在事务日志中记录对数据的修改，但不会立即将修改应用到数据库中。
  4. 提交事务：当事务提交时，会将事务对数据的修改应用到数据库中，并释放事务视图。这样其他事务就可以看到该事务所做的修改。

3、mysql有多少种索引，介绍一下B+树 ​

见的索引包括以下几种：

  1. B-Tree 索引：B-Tree（Balance Tree）索引是 MySQL 中最常用的索引类型，用于加速对数据的查找。B-Tree 索引适用于各种类型的查询，包括精确匹配和范围查询。
  2. Hash 索引：Hash 索引基于哈希表实现，适用于等值查询，对于范围查询效果不佳。Hash 索引在内存中进行查找，速度较快，但不支持排序。
  3. 全文索引：全文索引用于对文本内容进行全文搜索，适用于包含大量文本的列，如文章内容、博客评论等。
  4. 空间索引：空间索引用于地理空间数据的存储和查询，可以加速对地理位置信息的搜索。

B+Tree 是一种多路搜索树，常用于数据库和文件系统中。在 MySQL 中，B+Tree 是默认的存储引擎 InnoDB 的索引结构。B+Tree 索引的特点包括：

  1. 平衡性：B+Tree 是一种平衡树，每个非叶子节点都有相同的高度，使得在进行查询时能够保持较为稳定的性能。
  2. 有序性：B+Tree 的叶子节点构成了一个有序链表，使得范围查询更加高效。
  3. 支持范围查询：由于 B+Tree 的有序性，可以很方便地支持范围查询操作。
  4. 适用于磁盘存储：B+Tree 的节点通常较大，适合在磁盘上存储，对于数据库系统来说，磁盘存储是常见的场景。
  5. 非叶子节点只存储键值信息：B+Tree 非叶子节点只存储键值信息，不存储实际数据，这样可以使得每个节点能够存储更多的键值信息，减少了树的高度，提高了查询效率。

4、索引什么时候失效 ​

  1. 函数运算：当在查询条件中对字段进行了函数运算时，索引可能会失效。例如，WHERE YEAR(date_column) = 2022，如果 date_column 上有索引，由于 YEAR() 函数的运算，索引可能无法有效使用。
  2. 隐式类型转换：如果查询条件中的字段类型与索引字段的类型不匹配，数据库可能会进行隐式类型转换，导致索引失效。例如，如果字段是字符串类型，而查询条件中使用了数字，索引可能会失效。
  3. 使用了不支持的操作符：某些操作符可能会导致索引失效，例如使用 LIKE '%keyword%'，这种模糊查询会导致索引失效，因为无法使用索引的前缀匹配优化。
  4. 对索引字段进行了运算：如果在查询条件中对索引字段进行了运算，比如 WHERE indexed_column + 1 = 10，索引可能会失效。
  5. 表达式索引无法使用：如果查询条件中包含了表达式索引无法涵盖的条件，表达式索引可能会失效。
  6. 查询条件使用 OR 操作符：如果查询条件中使用了 OR 操作符，并且每个条件都不是索引，那么索引可能会失效。
  7. 数据量过大：如果表中数据量非常大，而查询的数据量非常小，数据库优化器可能会选择全表扫描而不是使用索引。
  8. 数据分布不均匀：如果索引字段的数据分布不均匀，比如某个值的出现频率过高或过低，可能会导致索引失效。

5、mysql聚簇索引和非聚簇索引的差别 ​

聚簇索引

  1. 数据存储方式：聚簇索引中，索引本身就是数据的物理排序方式，因此数据行的存储顺序和索引的顺序是一致的。
  2. 索引结构：聚簇索引实际上是将索引和数据行存储在同一个 B+Tree 结构中，叶子节点存储的是整行数据，而非叶子节点存储的是索引键值和指向数据页的指针。
  3. 主键索引：在 MySQL 中，如果表定义了主键，那么主键索引就是聚簇索引。
  4. 查询效率：由于数据行的存储顺序和索引顺序一致，因此对于使用聚簇索引的表，范围查询效率通常较高。

非聚簇索引

  1. 数据存储方式：非聚簇索引中，索引和数据行是分开存储的，索引只存储索引键值和指向数据行的指针，而不存储整行数据。
  2. 索引结构：非聚簇索引也是使用 B+Tree 结构，但叶子节点存储的是索引键值和指向数据页的指针，而不是整行数据。
  3. 查询效率：对于使用非聚簇索引的表，在使用索引进行查询时，首先需要通过索引找到对应的数据行指针，然后再根据指针找到数据行，因此相对于聚簇索引，非聚簇索引可能需要额外的 I/O 操作，查询效率较低。

6、解释一下TCP和UDP的差别 ​

TCP（传输控制协议）

  1. 连接导向：TCP 是一种面向连接的协议，通信双方在数据传输之前需要先建立连接，然后进行数据传输，最后再释放连接。
  2. 可靠性：TCP 提供可靠的数据传输，它使用确认和重传机制来确保数据的可靠性，可以保证数据不丢失、不重复、按序到达。
  3. 流量控制：TCP 通过滑动窗口和拥塞控制等机制来进行流量控制，防止数据包的过多丢失和网络拥塞。
  4. 适用场景：适用于对数据可靠性要求较高的场景，如文件传输、邮件发送等。

UDP（用户数据报协议）

  1. 无连接：UDP 是一种无连接的协议，通信双方在传输数据时不需要建立连接，可以直接发送数据报。
  2. 不可靠性：UDP 不提供可靠的数据传输，数据包可能丢失、重复或者乱序到达，不保证数据的可靠性。
  3. 无拥塞控制：UDP 不提供拥塞控制机制，发送方会以固定速率发送数据，不会根据网络状况进行调整。
  4. 适用场景：适用于对实时性要求较高的场景，如视频直播、在线游戏等，也常用于一些简单的数据传输，如 DNS 查询、SNMP 等。

7、HTTP3.0使用UDP实现的，这个你具体了解吗 ​

HTTP/3 是基于 UDP 实现的，而不是像之前的版本（HTTP/1.1 和 HTTP/2）那样基于 TCP。HTTP/3 使用了 QUIC（Quick UDP Internet Connections）作为传输协议，QUIC 是一个由 Google 开发的基于 UDP 的多路复用协议，后来被纳入 IETF（Internet Engineering Task Force）标准化。

特点和优势

  1. 低延迟连接建立：QUIC 使用了 0-RTT（Zero Round Trip Time）连接建立技术，可以在第一次连接时就发送数据，减少了连接建立的时间开销。
  2. 多路复用：QUIC 支持多路复用，可以在单个连接上同时传输多个数据流，避免了 TCP 中的队头阻塞问题。
  3. 移动端优化：QUIC 对移动网络环境进行了优化，具有更好的拥塞控制和流量控制机制，适应了移动网络的特点。
  4. 安全性：QUIC 内置了 TLS 加密，提供了更好的安全性，同时也减少了 TLS 握手的开销。
  5. 适应性：QUIC 能够在网络切换或 IP 地址变更时快速恢复连接，具有良好的网络适应性。

实现原理

QUIC 在传输层实现了类似 TCP 的可靠性和流控制机制，但与 TCP 不同的是，QUIC 在应用层和传输层之间引入了一个新的层，称为 QUIC 协议层。QUIC 协议层负责实现了传输层和应用层之间的多路复用、连接管理、可靠性、流控制、拥塞控制等功能，同时还包括了 TLS 加密和快速连接恢复等功能。

由于 QUIC 是基于 UDP 的，它可以更好地应对网络环境中的丢包和延迟，从而提供了更好的用户体验。在 HTTP/3 中，使用 QUIC 作为传输层协议，可以带来更低的连接建立延迟和更好的性能，特别是在高延迟和丢包率较高的网络环境下。