小米C++ 面试题及参考答案下（120道面试题覆盖各种类型八股文）

指针和引用的区别？怎么实现的？

指针和引用有以下一些主要区别。

从概念上来说，指针是一个变量，它存储的是另一个变量的地址。可以通过指针来间接访问所指向的变量。例如，我们定义一个整型指针int *p;，它可以指向一个整型变量的内存地址。而引用是一个别名，它必须在定义的时候初始化，并且在之后的使用中，它和它所引用的变量完全等价。比如int a = 10; int &b = a;，这里b就是a的引用，对b的操作就是对a的操作。

从实现机制来讲，指针在内存中有自己独立的存储空间，这个空间用来存储所指向变量的地址。它可以被重新赋值，指向不同的变量，例如int c = 5; p = &c;。指针可以为空，即不指向任何有效的内存地址，比如int *q = nullptr;。而引用本质上是原变量的一个别名，它没有自己独立的存储空间（在底层实现上可能有一些细微的差别，但对于使用者的语义来说是没有额外存储的）。一旦引用被初始化，它就不能再引用其他变量了。

在函数参数传递方面，指针作为参数传递时，在函数内部可以通过解引用操作来修改指针所指向的变量的值，也可以改变指针本身的值，让它指向其他变量。引用作为参数传递时，在函数内部对引用的修改就是对原变量的修改，但是引用本身不能重新绑定到其他变量。

在安全性方面，指针可能会出现空指针引用、野指针等问题。如果不小心访问了空指针或者一个已经释放的内存地址，程序就会出现错误。而引用相对来说更安全一些，因为引用必须在定义的时候初始化，并且不能为 null，它始终和一个有效的变量绑定在一起，减少了出现悬空引用的风险。

在语法层面，指针的使用需要使用解引用操作符*来访问所指向的变量的值，使用取地址操作符&来获取变量的地址。而引用在使用的时候就和普通变量一样，不需要额外的操作符，因为它本身就是变量的别名。

说说常见的排序算法。

常见的排序算法有多种，以下是详细介绍。

1. 冒泡排序

   • 基本思想：它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
   • 例如，对于数列{5, 4, 3, 2, 1}，第一轮比较时，先比较 5 和 4，因为 5 > 4，所以交换它们的位置，得到{4, 5, 3, 2, 1}。接着比较 5 和 3，交换得到{4, 3, 5, 2, 1}，以此类推，第一轮结束后，最大的数 5 就会 “浮” 到数列的末尾，变成{4, 3, 2, 1, 5}。然后进行第二轮比较，直到整个数列排序完成。

2. 插入排序

   • 基本思想：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
   • 例如，对于数列{5, 3, 4, 6, 1}，开始时，认为第一个元素 5 是有序序列。然后插入 3，将 3 和 5 比较，因为 3 < 5，所以将 3 插入到 5 的前面，得到{3, 5}。接着插入 4，将 4 和 5 比较，因为 4 <5，再和 3 比较，因为 4> 3，所以将 4 插入到 3 和 5 之间，得到{3, 4, 5}。以此类推，直到所有元素都插入到有序序列中。

3. 选择排序

   • 基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
   • 例如，对于数列{4, 2, 7, 1, 9}，第一轮比较，找到最小的元素 1，将 1 和 4 交换，得到{1, 2, 7, 4, 9}。然后在剩余的{2, 7, 4, 9}中找到最小的元素 2，由于 2 已经在正确的位置，所以不用交换。接着在{7, 4, 9}中找到最小的元素 4，将 4 和 7 交换，得到{1, 2, 4, 7, 9}，以此类推，直到整个数列排序完成。

4. 快速排序

   • 基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
   • 例如，对于数列{5, 3, 8, 4, 6, 3, 3 ,2}，选择一个基准元素，比如 4。然后将数列中比 4 小的元素放在 4 的左边，比 4 大的元素放在 4 的右边，经过一次划分后得到{3, 3, 2, 4, 5, 8 ,6}。然后对 4 左边的{3, 3, 2}和右边的{5, 8 ,6}分别进行快速排序，直到整个数列排序完成。

1. 归并排序

   • 基本思想：是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
   • 例如，对于数列{4, 2, 7, 1, 5}，首先将数列分成两个子序列{4, 2}和{7, 1, 5}。然后对{4, 2}进行排序得到{2, 4}，对{7, 1, 5}进行排序得到{1, 5, 7}。接着将{2, 4}和{1, 5, 7}合并，比较 2 和 1，将 1 放入新序列，接着比较 2 和 5，将 2 放入新序列，以此类推，最终得到{1, 2, 4, 5, 7}。

2. 堆排序

   • 基本思想：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并且满足父节点的值总是大于（或小于）它的子节点的值。将数组构建成一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换，再对剩下的元素重新调整为最大堆（或最小堆），重复这个过程，直到整个数组排序完成。
   • 例如，对于数列{4, 6, 8, 5, 7}，首先将其构建成一个最大堆，得到{8, 7, 6, 5, 4}。然后将堆顶元素 8 与最后一个元素 4 交换，得到{4, 7, 6, 5, 8}，接着对{4, 7, 6, 5}重新调整为最大堆，再交换堆顶元素和最后一个元素，重复这个过程，直到数列排序完成。

说说 bst 树，avl 树。

1. 二叉搜索树（BST）
   • 定义：二叉搜索树是一种二叉树，它满足对于树中的任意节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。例如，对于节点值为 5 的节点，它的左子树节点的值都小于 5，右子树节点的值都大于 5。
   • 基本操作：
     • 插入操作：从根节点开始，比较要插入的值和当前节点的值。如果要插入的值小于当前节点的值，就向左子树移动；如果大于当前节点的值，就向右子树移动。直到找到一个合适的空位置插入新节点。例如，插入一个值为 3 的节点到一个根节点值为 5 的 BST 中，因为 3 < 5，所以向左子树移动，如果左子树为空，就在这个位置插入 3。
     • 查找操作：同样从根节点开始，比较要查找的值和当前节点的值。如果要查找的值等于当前节点的值，就找到了；如果小于当前节点的值，就向左子树查找；如果大于当前节点的值，就向右子树查找。例如，在一个 BST 中查找值为 7 的节点，从根节点开始，如果根节点值为 5，因为 7 > 5，所以向右子树查找。
     • 删除操作：删除操作相对复杂一些。如果要删除的节点是叶子节点，直接删除即可。如果要删除的节点只有一个子节点，将其子节点替换它即可。如果要删除的节点有两个子节点，可以用它的中序后继（右子树中的最小值）或者中序前驱（左子树中的最大值）来替换它，然后删除这个后继或者前驱节点。
   • 时间复杂度：在最好情况下，BST 是平衡的，插入、查找和删除操作的时间复杂度都是，其中 n 是树中节点的个数。但在最坏情况下，例如树是一条链（所有节点都只有左子树或者右子树），时间复杂度会退化为。
   • 应用场景：BST 可以用于实现字典（键 - 值对的存储和查找），快速查找数据集中的某个元素是否存在，以及对数据进行排序（通过中序遍历可以得到有序的数据序列）等。
2. AVL 树
   • 定义：AVL 树是一种自平衡的二叉搜索树。它在插入和删除节点时，会通过旋转操作来保持树的平衡。所谓平衡，是指任何节点的左右子树的高度差的绝对值不超过 1。例如，一个节点的左子树高度为 3，右子树高度为 2 或者 4，这棵树在这个节点处是平衡的。
   • 平衡操作：
     • 旋转操作：有四种基本的旋转方式，左旋、右旋、左右旋和右左旋。左旋是将一个节点的右子节点提升为父节点，原来的父节点变为新父节点的左子节点；右旋是将一个节点的左子节点提升为父节点，原来的父节点变为新父节点的右子节点。左右旋和右左旋是左旋和右旋的组合，用于更复杂的不平衡情况。例如，当一个节点的左子树高度比右子树高度大 2 时，可能需要进行右旋操作来恢复平衡。
   • 时间复杂度：由于 AVL 树始终保持平衡，插入、查找和删除操作的时间复杂度都是，其中 n 是树中节点的个数。这使得 AVL 树在性能上比普通的 BST 更稳定，尤其是在频繁插入和删除操作的情况下。
   • 应用场景：适用于对查找、插入和删除操作的时间复杂度要求比较严格的场景，比如数据库索引的实现，因为它能够保证高效的操作性能，不会因为数据的插入和删除导致性能急剧下降。

树的遍历方式有那些？

树的遍历主要有以下几种方式。

1. 深度优先遍历（DFS）
   • 先序遍历（根左右）：
     • 对于二叉树来说，先访问根节点，然后递归地先序遍历左子树，再递归地先序遍历右子树。例如，对于二叉树 1 / \ 2 3 / \ / \ 4 5 6 7，先序遍历的结果是 1、2、4、5、3、6、7。先访问根节点 1，然后先序遍历左子树，先访问左子树的根节点 2，接着先序遍历 2 的左子树，访问 4，再先序遍历 2 的右子树，访问 5。之后先序遍历根节点 1 的右子树，先访问右子树的根节点 3，再先序遍历 3 的左子树，访问 6，最后先序遍历 3 的右子树，访问 7。
   • 中序遍历（左根右）：
     • 递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。对于上述二叉树，中序遍历的结果是 4、2、5、1、6、3、7。先中序遍历左子树，访问 4，然后访问左子树的根节点 2，接着访问 2 的右子树中的 5。之后访问根节点 1，再中序遍历右子树，访问 6，然后访问右子树的根节点 3，最后访问 3 的右子树中的 7。
   • 后序遍历（左右根）：
     • 递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。对于上述二叉树，后序遍历的结果是 4、5、2、6、7、3、1。先后序遍历左子树，访问 4，再访问 5，然后访问左子树的根节点 2。接着后序遍历右子树，访问 6，再访问 7，然后访问右子树的根节点 3。最后访问整个树的根节点 1。
   • 对于非二叉树，深度优先遍历的思路类似，只是子树的数量可能多于两个，需要按照一定的顺序依次遍历各个子树。例如对于三叉树，在先序遍历中，先访问根节点，然后按照从左到右的顺序深度优先遍历各个子树。
2. 广度优先遍历（BFS）
   • 也称为层次遍历。从根节点开始，按照树的层次，从上到下，从左到右依次访问各个节点。对于前面提到的二叉树，广度优先遍历的结果是 1、2、3、4、5、6、7。首先访问根节点 1，这是第一层。然后访问第二层的节点 2 和 3，接着访问第三层的节点 4、5、6、7。实现广度优先遍历通常使用队列数据结构。首先将根节点入队，然后循环执行以下操作：取出队首节点，访问该节点，将该节点的子节点（如果有）依次入队，直到队列为空。这种遍历方式可以用于寻找树的最短路径等问题，比如在图的广度优先搜索（树是一种特殊的图）中，它可以找到从根节点到其他节点的最短路径长度（以边的数量来衡量）。

怎么计算二叉树的深度？

计算二叉树的深度可以使用递归或者非递归的方法。

1. 递归方法
   • 对于二叉树，树的深度等于 1（根节点）加上其左右子树深度的最大值。如果二叉树为空，深度为 0。例如，对于二叉树 1 / \ 2 3 / \ / \ 4 5 6 7，先计算左子树的深度。左子树的根节点是 2，它的左子树（以 4 为根）深度为 1，右子树（以 5 为根）深度为 1，所以以 2 为根的左子树深度为 2（1 加上左右子树深度最大值 1）。同理，右子树（以 3 为根）深度也为 2。那么整个二叉树的深度为 3（1 加上左右子树深度最大值 2）。
   • 代码实现如下：

// 二叉树节点结构体定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int maxDepth(TreeNode* root) {if (root == NULL) {return 0;}int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);return 1 + (leftDepth > rightDepth? leftDepth : rightDepth);
}

1. 非递归方法（层次遍历）
   • 可以利用层次遍历的思想来计算二叉树的深度。使用队列来存储每一层的节点。首先将根节点入队，记录当前层的节点数为 1，然后循环执行以下操作：取出队首节点，将其左右子

     节点（如果有）依次入队，每处理完一层的节点，深度就加 1。直到队列为空，此时得到的深度就是二叉树的深度。

     以下是用非递归方法（层次遍历）计算二叉树深度的代码实现示例：

     // 二叉树节点结构体定义
     struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     };int maxDepth(TreeNode* root) {if (root == NULL) {return 0;}std::queue<TreeNode*> q;q.push(root);int depth = 0;while (!q.empty()) {int size = q.size();for (int i = 0; i < size; ++i) {TreeNode* node = q.front();q.pop();if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}depth++;}return depth;
     }
     

     在上述代码中：

   • 首先判断根节点是否为空，如果为空则二叉树深度为 0。
   • 然后创建一个队列用于存储节点，将根节点入队。
   • 在循环中，每次先获取当前队列中的节点数量（即当前层的节点数），然后依次取出队首节点并将其左右子节点（如果有）入队。每处理完一层的节点，就将深度加 1。
   • 当队列为空时，就得到了二叉树的深度。

   • 这种非递归的方法通过模拟层次遍历的过程，有效地计算出了二叉树的深度，相比于递归方法，在一些情况下可能具有更好的性能表现，特别是当二叉树的深度较大且递归可能导致栈溢出等问题时，非递归的层次遍历方法是一种不错的选择。

     斐波那契数列的非递归写法？

     斐波那契数列的特点是起始于 0 或 1，从第三项开始，每一项都等于前两项之和。非递归写法主要是利用循环来实现。

     可以通过定义两个变量来存储前两项的值，然后在循环中不断更新这两个变量以及计算下一项的值。例如，定义变量a和b分别表示斐波那契数列中的前两项，初始时如果数列从 0 开始，a = 0，b = 1。然后通过一个循环，计算下一项的值c = a + b，接着将a更新为b，b更新为c，如此循环就可以得到斐波那契数列。

     在 C++ 中，以下是一个简单的示例代码来生成斐波那契数列的前n项（n大于 1）。

     #include <iostream>
     #include <vector>
     using namespace std;
     vector<int> Fibonacci(int n) {vector<int> result;if (n <= 0) {return result;}if (n == 1) {result.push_back(0);return result;}int a = 0, b = 1;result.push_back(a);result.push_back(b);for (int i = 2; i < n; ++i) {int c = a + b;a = b;b = c;result.push_back(c);}return result;
     }
     

     在这个函数中，首先处理了特殊情况，当n小于等于 0 时返回空的向量，当n等于 1 时返回只包含 0 的向量。然后按照前面描述的步骤，通过循环计算并将每一项的值添加到vector中，最后返回这个vector，它就包含了斐波那契数列的前n项。这种非递归的写法避免了递归调用可能带来的栈溢出问题，并且在效率上通常比简单的递归实现要高，因为它不需要频繁地调用函数和保存函数调用的栈帧。

     Linux 经常用的命令。

   • 文件和目录操作命令
     • ls：用于列出目录中的文件和子目录。它有很多选项，例如-l可以以长格式显示文件的详细信息，包括文件权限、所有者、大小、修改时间等；-a可以显示包括隐藏文件（以 “.” 开头的文件）在内的所有文件。例如，ls -l会详细列出当前目录下的文件信息，ls -a会显示所有文件，包括隐藏文件。
     • cd：用于切换当前工作目录。例如，cd /home/user可以将当前目录切换到/home/user。如果只输入cd，没有参数，会切换到用户的主目录。
     • mkdir：用于创建新的目录。例如，mkdir new_folder会在当前目录下创建一个名为new_folder的新目录。可以使用-p选项来创建多级目录，如mkdir -p a/b/c会创建a、a/b和a/b/c目录。
     • rmdir：用于删除空目录。如果目录非空，需要先删除目录中的文件和子目录才能使用rmdir删除。例如，rmdir empty_folder会删除名为empty_folder的空目录。
     • rm：用于删除文件或目录。使用-r或-R选项可以递归地删除目录及其内容。例如，rm -r folder会删除folder目录及其所有内容，rm file.txt会删除名为file.txt的文件。
     • cp：用于复制文件或目录。例如，cp file1.txt file2.txt会将file1.txt复制为file2.txt。如果要复制目录，需要使用-r选项，如cp -r dir1 dir2会将dir1目录及其内容复制到dir2。
     • mv：用于移动文件或目录，也可以用于重命名文件或目录。例如，mv file1.txt new_file1.txt会将file1.txt重命名为new_file1.txt，mv file.txt /home/user/会将file.txt移动到/home/user/目录下。
   • 文件查看和编辑命令
     • cat：用于查看文件的内容并将其输出到终端。例如，cat file.txt会在终端显示file.txt的内容。它也可以用于将多个文件的内容合并输出，如cat file1.txt file2.txt > combined_file.txt会将file1.txt和file2.txt的内容合并后输出到combined_file.txt。
     • less：和cat类似，用于查看文件内容，但less提供了更多的交互功能，如可以上下滚动、搜索等。例如，less file.txt进入less查看模式，按q键可以退出。
     • vim：是一个功能强大的文本编辑器。它有多种模式，如命令模式、插入模式和末行模式。在命令模式下，可以进行光标移动、复制、粘贴等操作；插入模式用于输入文本；末行模式用于保存文件、退出等操作。例如，打开一个文件可以使用vim file.txt，在命令模式下按i进入插入模式开始编辑，编辑完成后按Esc回到命令模式，然后输入:wq保存并退出。
   • 系统信息查看命令
     • uname：用于显示系统信息。例如，uname -a会显示系统的内核名称、主机名、内核版本、处理器类型等信息。
     • df：用于查看磁盘空间使用情况。例如，df -h会以人类可读的格式（如KB、MB、GB等）显示各个磁盘分区的大小、已用空间、可用空间等信息。
     • free：用于查看内存使用情况。例如，free -m会以MB为单位显示系统的内存总量、已用内存、空闲内存等信息。
   • 进程管理命令
     • ps：用于查看当前系统中的进程信息。例如，ps -ef会显示所有进程的详细信息，包括进程 ID、父进程 ID、用户、启动时间、命令等。
     • kill：用于终止进程。例如，kill PID（PID是进程的 ID）会发送一个信号给指定的进程，默认是SIGTERM信号，用于正常终止进程。如果进程无法正常终止，可以使用kill -9 PID发送SIGKILL信号强制终止进程。
     • top：用于实时查看系统中各个进程的资源占用情况，包括 CPU 使用率、内存使用率等。它会动态更新显示的内容，按q键可以退出。
     • htop：是top的增强版，提供了更友好的界面和更多的功能，如可以通过鼠标操作、对进程进行排序等。安装后可以使用htop命令来启动它。

Git 用过吗，有哪些常见命令？

Git 是一个分布式版本控制系统，在软件开发中被广泛使用。

首先是git init命令，它用于初始化一个新的 Git 仓库。当你开始一个新的项目或者想要将一个已有的项目纳入 Git 管理时，在项目的根目录下执行这个命令，就会创建一个隐藏的.git目录，这个目录存储了仓库的所有版本控制信息，如提交历史、分支信息等。

git clone命令用于从远程仓库复制一份代码到本地。例如，git clone [远程仓库URL]，可以将远程仓库中的代码完整地下载到本地，方便开发人员在本地进行修改和开发。它会自动设置好远程仓库的关联信息，以便后续推送和拉取更新。

git add是将文件添加到暂存区的命令。在进行提交之前，需要先把要提交的文件添加到暂存区，比如git add.会将当前目录下所有修改的文件（包括新建的文件）添加到暂存区。如果只想添加特定的文件，可以使用git add [文件名]。

git commit用于将暂存区的内容提交到本地仓库，形成一个新的版本。需要添加提交信息来描述本次提交的内容，如git commit -m "修复了某个Bug"，其中-m选项后面的内容就是提交信息。

git push和git pull是用于与远程仓库交互的命令。git push用于将本地仓库的更新推送到远程仓库，例如git push origin master会将本地的master分支的更新推送到名为origin的远程仓库。git pull则是从远程仓库拉取更新并合并到本地仓库对应的分支，它实际上是git fetch和git merge的组合操作，先获取远程仓库的更新，然后将其合并到本地分支。

git branch用于管理分支。可以使用git branch [分支名]来创建一个新的分支，git branch -a可以查看所有分支（包括本地分支和远程分支），git checkout [分支名]用于切换到指定的分支。

git merge用于将一个分支的修改合并到另一个分支。例如，在一个功能分支开发完成后，将其合并到主分支，可以使用git merge [功能分支名]（在主分支下执行此命令）。

Spinlock，多核时 Spinlock 什么情况？

Spinlock（自旋锁）是一种用于多线程同步的锁机制。在单核环境下，当一个线程尝试获取一个已经被占用的自旋锁时，它会一直循环检查锁是否被释放，这个循环等待的过程就是 “自旋”。

在多核环境下，情况会稍微复杂一些。当一个线程在一个核心上获取了自旋锁后，其他试图获取该锁的线程会在不同的核心上自旋。每个线程都在自己的核心上快速地检查锁的状态，不会主动让出 CPU 时间片。这种方式在锁被占用时间较短的情况下是比较高效的。因为如果线程让出 CPU，涉及到上下文切换的开销，当锁很快就会被释放时，这个开销可能比自旋等待的开销还要大。

然而，如果持有自旋锁的线程被阻塞或者执行时间过长，例如进入了睡眠状态或者执行了一个非常耗时的操作，其他自旋的线程会一直消耗 CPU 资源，导致 CPU 利用率过高，并且这些等待的线程没有实际的进展。这种情况可能会影响系统的整体性能。

另外，在多核系统中，由于存在缓存一致性的问题，当一个线程获取或释放自旋锁时，可能会涉及到多个核心之间的缓存同步操作。比如，在一个核心上修改了锁的状态，其他核心上的缓存可能需要更新这个信息，这也会带来一定的性能开销。而且，不同的多核架构对于缓存一致性的处理方式不同，也会影响自旋锁的性能表现。

为了避免长时间自旋导致的 CPU 资源浪费，可以采用一些改进措施。例如，设置一个自旋的时间限制，当超过这个时间后，线程就不再自旋，而是采用其他的等待策略，如将线程挂起，等待锁被释放的信号，这种方式结合了自旋锁和传统的阻塞锁的优点，能够在一定程度上提高系统的性能。

Spinlock 一直在旋转耗费 CPU，会被切出 CPU 核心吗？

自旋锁（Spinlock）在旋转等待时是否会被切出 CPU 核心取决于具体的操作系统调度策略和实现细节。

在一些简单的实现中，自旋锁会一直占用 CPU 核心，不断地检查锁的状态。因为自旋的线程被认为是处于一种忙等待（Busy - Waiting）的状态，它没有主动放弃 CPU 资源的意图。从操作系统调度器的角度看，这些线程仍然处于可运行（Runnable）状态，它们在等待锁释放的过程中，一直在执行检查锁状态的指令，没有进入等待（Waiting）或者阻塞（Blocked）状态。

然而，在一些更复杂的操作系统或者运行时环境中，为了避免单个线程过度消耗 CPU 资源，导致系统性能下降，可能会有机制来干预自旋的线程。例如，当自旋的线程消耗的 CPU 时间超过了一定的阈值，操作系统可能会判定这个线程处于一种非生产性的等待状态，然后将其暂时从 CPU 核心上移除。

另外，在一些支持自适应调度的系统中，会根据系统的负载情况和线程的行为来决定是否切出自旋的线程。如果系统处于高负载状态，并且自旋的线程对 CPU 资源的占用影响到了其他重要任务的执行，调度器可能会采取措施将自旋的线程暂停，让更紧急的任务先执行。

但是，这种将自旋线程切出 CPU 核心的操作也需要谨慎处理。因为一旦将自旋线程切出，当锁被释放时，需要有一种机制来及时唤醒这个线程，并且重新将其调度到 CPU 核心上执行。否则，可能会导致锁的获取延迟增加，影响系统的同步效率。而且，频繁地将自旋线程切出和重新调度也会带来额外的开销，如上下文切换的成本等。

Linux 用户态内核态有了解过吗？

Linux 操作系统分为用户态和内核态，这是一种基于保护机制的设计。

在用户态，应用程序运行在一个相对受限的环境中。用户态的程序不能直接访问硬件设备和系统的关键资源。例如，普通的用户程序不能直接对物理内存进行随意的读写操作，也不能直接操作 CPU 的某些特权指令。这样做的主要目的是为了系统的安全性和稳定性。用户态的程序通过系统调用（System Call）来请求内核提供服务。比如，当一个用户程序需要读取文件时，它会调用read系统调用，这个调用会触发从用户态到内核态的切换。

内核态则拥有对系统所有资源的完全访问权限。内核负责管理硬件设备，如磁盘、网络接口、CPU 等。它会进行内存管理，包括物理内存的分配和回收，以及虚拟内存和物理内存之间的映射。例如，当一个新的进程被创建时，内核会为其分配虚拟地址空间，并将虚拟地址空间的页面映射到物理内存的页面上。

在进程管理方面，内核负责进程的创建、调度和终止。它会根据进程的优先级和调度策略来分配 CPU 时间片。例如，采用完全公平调度（CFS）算法的 Linux 内核，会尽量公平地将 CPU 时间分配给各个进程，让每个进程都能有机会执行。

从系统调用的角度看，当用户态程序发起一个系统调用时，会发生用户态到内核态的切换。这个切换过程涉及到保存用户态的上下文（如寄存器的值等），然后进入内核态执行相应的内核函数。完成系统调用后，又会从内核态切换回用户态，恢复之前保存的用户态上下文，继续执行用户程序。这种切换是有一定开销的，包括保存和恢复上下文的时间以及内核态和用户态之间的数据传递等。

在安全性方面，内核态和用户态的分离可以防止用户程序的错误或者恶意行为破坏整个系统。因为用户程序的错误操作通常会被限制在用户态的范围内，不会直接影响到内核和其他重要的系统资源。

对驱动了解吗，看过 Linux 里驱动的源码吗？

驱动程序在 Linux 系统中起着至关重要的作用，它是操作系统与硬件设备之间的桥梁。

Linux 驱动程序可以分为字符设备驱动、块设备驱动和网络设备驱动等多种类型。字符设备驱动通常用于处理像终端、鼠标、键盘等以字节流方式进行数据传输的设备。以键盘驱动为例，它需要接收键盘的按键输入，将按键的扫描码转换为字符编码，然后将这些字符传递给用户程序。

块设备驱动主要用于处理存储设备，如硬盘、固态硬盘等。这些设备以固定大小的块为单位进行数据存储和读取。块设备驱动需要管理磁盘的分区、文件系统的挂载等操作。例如，当用户程序需要读取一个文件时，块设备驱动会将文件系统的请求转换为对磁盘物理块的读写操作，从磁盘中获取相应的数据。

网络设备驱动则负责处理网络接口卡（NIC）等网络设备。它需要实现网络协议栈的底层功能，如发送和接收数据包。例如，当应用程序通过 TCP/IP 协议发送数据时，网络设备驱动会将数据封装成合适的网络数据包，通过物理网络接口发送出去。

关于 Linux 驱动源码，它通常是由一系列的 C 语言文件组成。在字符设备驱动源码中，会定义设备结构体，包括设备的操作函数，如open、read、write、release等。这些操作函数会与用户空间的应用程序进行交互。例如，read函数用于从设备中读取数据，它会根据设备的具体情况，从硬件寄存器或者缓冲区中获取数据，并返回给用户程序。

在块设备驱动源码中，会涉及到请求队列的管理。当用户程序发出对块设备的读写请求时，这些请求会被放入请求队列中，驱动程序会按照一定的顺序处理这些请求。同时，源码中还会包含对磁盘缓存等功能的实现，以提高磁盘读写的效率。

对于网络设备驱动源码，会有数据包的发送和接收处理逻辑。包括对网络数据包的缓冲、校验和计算、硬件寄存器的配置等内容。通过研究这些源码，可以深入了解 Linux 系统是如何与各种硬件设备进行通信和交互的，以及如何高效地管理和利用硬件资源。

设计模式知道哪些？工厂方法什么思想？工厂如果生成新的产品需要修改代码吗？怎么让他不修改代码？

常见的设计模式包括创建型模式、结构型模式和行为型模式。

创建型模式有单例模式，它确保一个类只有一个实例，并提供一个全局访问点。例如，在一个系统中，数据库连接池通常可以设计为单例模式，这样可以避免频繁地创建和销毁数据库连接，节省资源。

工厂模式是一种创建型设计模式。工厂方法模式的核心思想是将对象的创建和使用分离。它定义了一个创建对象的接口，让子类决定实例化哪一个类。比如，有一个汽车工厂接口，不同的汽车品牌（如宝马、奔驰）可以通过各自的工厂子类来实现生产汽车的方法。

如果采用简单的工厂实现，当需要生成新的产品时，往往需要修改工厂类的代码。例如，原本工厂类只能生产两种产品，现在要增加一种新产品，就需要在工厂类的生产方法中添加新的分支逻辑来创建新产品。

为了避免修改代码，可以采用抽象工厂模式。抽象工厂模式中，工厂类不再负责创建具体的产品，而是由一系列具体的工厂子类来负责。当需要增加新的产品时，只需要创建新的产品类和对应的工厂子类，而不需要修改现有的工厂类。这样就符合了开闭原则，即对扩展开放，对修改关闭。例如，在图形绘制系统中，有一个抽象工厂用于创建图形，当要增加一种新的图形（如椭圆形），可以创建椭圆形产品类和对应的椭圆形工厂子类，而不会影响到其他图形（如圆形、矩形）的工厂子类和产品类。

C 可以做应用程序吗？

C 语言完全可以用来开发应用程序。在操作系统层面，许多操作系统的内核部分是用 C 语言编写的。例如，Unix 和 Linux 操作系统的内核大量使用 C 语言，因为 C 语言能够直接访问硬件资源并且具有高效的性能。在系统编程领域，C 语言可以用于开发设备驱动程序，通过对硬件寄存器的读写操作，实现操作系统与硬件设备之间的通信。

在应用程序开发方面，C 语言可以用于开发控制台应用程序。例如，编写命令行工具，像文本处理工具、文件压缩工具等。以文本处理工具为例，通过 C 语言的文件操作函数和字符串处理函数，可以读取文本文件的内容，进行字符替换、格式转换等操作，然后将处理后的内容输出到新的文件或者控制台。

C 语言还可以用于开发图形界面应用程序，不过通常需要借助图形库。例如，使用 OpenGL 库结合 C 语言，可以开发出具有复杂 3D 图形效果的应用程序，如游戏开发。在游戏开发中，C 语言用于实现游戏的逻辑，如角色的移动、碰撞检测等，OpenGL 则负责图形的渲染。

另外，在数据库系统领域，一些数据库管理系统的底层核心模块也是用 C 语言编写的，用于高效地管理数据存储、索引构建和查询处理等操作。而且，C 语言编写的应用程序在性能方面有很大的优势，因为它编译后的代码执行效率高，能够充分利用计算机的硬件资源，并且可以很方便地进行内存管理和优化。

知道回调函数吗？

回调函数是一种函数指针的应用。它是一个通过函数指针调用的函数。在 C 和 C++ 等编程语言中被广泛使用。

从功能上来说，回调函数允许将一段可执行代码作为参数传递给另一个函数。这种机制在事件驱动编程和异步编程中非常有用。例如，在图形用户界面（GUI）编程中，当用户点击一个按钮时，系统会调用一个预先注册的回调函数来处理这个点击事件。

以一个简单的排序函数为例，它可能会接受一个比较函数作为回调函数。假设我们有一个函数qsort（C 标准库中的排序函数），它可以对数组进行排序，但是它需要知道如何比较数组中的元素。这时候就可以传入一个比较函数作为回调函数。这个比较函数接受两个参数（要比较的两个元素），然后返回一个整数值来表示这两个元素的大小关系。

在实现层面，回调函数的使用涉及到函数指针。首先需要定义一个函数指针类型，它指向的函数具有特定的参数列表和返回值类型。然后，可以将符合这个函数指针类型的实际函数的地址赋值给这个函数指针。当调用包含函数指针的函数时，就会通过这个函数指针来调用实际的回调函数。

在异步编程中，回调函数也发挥着重要的作用。比如在网络编程中，当发起一个网络请求后，由于网络操作可能需要一些时间才能完成，所以程序不会一直等待。而是在网络操作完成后，通过调用预先设置的回调函数来处理返回的数据或者错误信息。这样可以让程序在等待网络操作的过程中继续执行其他任务，提高了程序的整体效率。

单例模式有用到过吗？

单例模式是一种很常用的设计模式。在实际项目中，有很多场景会用到单例模式。

在数据库连接管理方面经常会使用单例模式。因为在一个应用程序中，通常只需要一个数据库连接池来管理数据库连接。如果有多个数据库连接池实例，可能会导致资源浪费和连接混乱。通过单例模式，可以确保整个应用程序只有一个数据库连接池对象。这个对象可以负责分配和回收数据库连接，当不同的模块需要访问数据库时，都从这个单例的连接池中获取连接。

在日志系统中也会用到单例模式。日志系统通常用于记录应用程序的运行状态、错误信息等。整个应用程序只需要一个日志对象来统一管理日志的记录。这个单例的日志对象可以将日志信息输出到文件、控制台或者发送到远程的日志服务器。这样可以方便地对日志进行集中管理，并且保证日志记录的一致性。

在系统配置管理中，单例模式也很有用。应用程序的配置信息通常是全局共享的，通过单例模式的配置管理器，可以确保整个应用程序在任何地方访问到的都是同一份配置信息。这个配置管理器可以从配置文件中读取配置参数，并且提供接口让其他模块获取和修改这些配置参数。

单例模式的实现方式通常有两种，一种是懒汉式，一种是饿汉式。懒汉式是在第一次调用获取单例对象的方法时才创建对象，这样可以避免在程序启动时就创建可能暂时不需要的对象。饿汉式则是在程序启动时就创建单例对象，这种方式的优点是实现简单，并且在多线程环境下可能更容易保证对象的唯一性。不过，懒汉式在多线程环境下需要注意线程安全问题，通常需要使用锁机制来确保只有一个线程能够创建单例对象。

C 中为什么要加 STL，它的特点，优点？

C 语言本身没有 STL（标准模板库），STL 是 C++ 的内容。不过如果考虑在 C 语言环境中类似的库，其目的和特点有以下这些。

从目的来讲，在 C 语言中加入类似 STL 的库主要是为了提高开发效率和代码的复用性。C 语言虽然功能强大，但在处理复杂的数据结构和算法时，需要开发者自己从头实现。例如，要实现一个动态大小的数组，需要手动管理内存分配、元素插入和删除等操作。类似 STL 的库可以提供现成的容器（如动态数组、链表等），让开发者能够更专注于业务逻辑。

其特点包括通用性。这些库中的容器和算法通常是通用的模板形式。以容器为例，它们可以存储不同类型的数据，只要这些数据类型满足一定的要求（如可比较、可赋值等）。这使得代码能够适应多种数据类型，而不需要为每种数据类型都重新编写一遍代码。

在数据结构方面，提供了丰富多样的数据结构。比如有类似vector（动态数组）的数据结构，它可以方便地进行元素的随机访问和动态扩展。还有链表结构，可以高效地进行元素的插入和删除操作。这些数据结构的实现经过了优化，具有较好的性能。

优点首先是开发效率高。开发者可以直接使用这些库中的容器和算法，而不需要自己花费大量时间去设计和实现。例如，使用排序算法时，直接调用库中的排序函数就可以快速地对容器中的元素进行排序，而不用自己编写排序算法。

其次是代码的可维护性好。由于这些库是被广泛使用和测试的，代码质量相对较高。而且，使用统一的库可以使代码风格更加一致，当需要对代码进行修改或者扩展时，也更容易理解和操作。

另外，这些库在性能上也有一定的优势。它们的实现通常经过了优化，例如，容器的内存管理方式能够在保证功能的前提下，尽量减少内存的浪费和频繁的内存分配操作。同时，算法的时间复杂度也经过了优化，能够在合理的时间内完成复杂的操作。

经常用到的字符串的函数，标准的？

在 C 语言中，有许多常用的标准字符串函数。

strcpy函数用于将一个字符串复制到另一个字符串中。它的函数原型是char* strcpy(char* destination, const char* source)。这个函数会把source字符串（包括结束符'\0'）复制到destination字符串中，并且返回destination的指针。例如，char dest[20]; char source[] = "Hello"; strcpy(dest, source);就会把source中的Hello复制到dest中。不过要注意destination的空间要足够大，否则可能会导致缓冲区溢出。

strncpy是strcpy的一个更安全的版本。它的函数原型是char* strncpy(char* destination, const char* source, size_t n)。它会把source字符串的最多n个字符复制到destination中。如果source的长度小于n，则会在destination中填充'\0'。例如，char dest[10]; char source[] = "Hello"; strncpy(dest, source, 3);会把source中的Hel复制到dest中，并且dest后面的字符会被填充为'\0'。

strcat函数用于将一个字符串连接到另一个字符串的末尾。函数原型是char* strcat(char* destination, const char* source)。它会把source字符串（包括结束符'\0'）添加到destination字符串的末尾，并且返回destination的指针。例如，char dest[20] = "Hello"; char source[] = " World"; strcat(dest, source);会得到Hello World的结果。同样要注意destination的空间要足够大。

strncat是strcat的一个变体，函数原型是char* strncat(char* destination, const char* source, size_t n)。它会把source字符串的最多n个字符添加到destination字符串的末尾，并且会在最后添加'\0'。

strcmp函数用于比较两个字符串的大小。函数原型是int strcmp(const char* s1, const char* s2)。它会按照字典序比较s1和s2两个字符串。如果s1小于s2，返回一个负数；如果s1等于s2，返回 0；如果s1大于s2，返回一个正数。例如，char s1[] = "abc"; char s2[] = "abd"; int result = strcmp(s1, s2);会返回一个负数。

strlen函数用于计算一个字符串的长度。函数原型是size_t strlen(const char* s)。它会返回字符串s中除了结束符'\0'之外的字符个数。例如，char s[] = "Hello"; size_t length = strlen(s);会返回 5。

知道可重入函数吗？

可重入函数是指可以被多个任务并发调用，而不会产生不良后果的函数。在多任务或多线程环境下，这是一个很重要的概念。

例如，在一个实时操作系统中，多个任务可能同时需要使用一个函数来进行数据处理。可重入函数能够保证在这种并发访问的情况下，函数的执行结果仍然是正确的，并且函数内部使用的数据不会被破坏。

可重入函数有一些关键的特点。它不依赖于全局变量（或者说对全局变量是只读的），因为全局变量在多个任务同时访问时可能会导致数据不一致。它也不会修改自身代码段的内容，并且在函数执行过程中不会依赖于其他资源（如文件系统、硬件设备等）的状态，因为这些状态可能会被其他任务改变。

以一个简单的数学计算函数为例，比如计算两个数的平方和，这个函数只接收两个参数作为输入，在函数内部仅仅基于这两个参数进行计算，不涉及任何全局变量或者外部资源的状态修改，那么它就是一个可重入函数。这样的函数可以在多个线程或者任务中同时被调用，每个调用都能得到正确的结果，不会因为其他任务的调用而受到干扰。

另外，在一些中断服务程序中，也需要使用可重入函数。因为中断可能在任何时候发生，当中断服务程序和主程序或者其他中断服务程序同时访问一个函数时，如果这个函数是可重入的，就能保证系统的稳定运行，不会出现数据错误或者程序崩溃的情况。

怎么实现的可重入？

要实现可重入函数，主要有以下几种方法。

首先是避免使用全局变量或者对全局变量进行只读操作。如果函数需要保存一些中间数据，可以将这些数据作为函数的参数或者定义为局部变量。例如，在一个函数中，如果原本使用一个全局变量来计数，为了实现可重入，可以将这个计数变量作为函数的参数传入，在函数内部进行操作，而不是直接修改全局变量。这样，当多个任务同时调用这个函数时，每个任务都有自己独立的计数变量，不会相互干扰。

其次是确保函数内部不依赖于外部资源的状态。如果函数需要访问外部资源，如文件系统或者硬件设备，应该在访问之前先获取资源的状态，并且在访问结束后恢复资源的状态。比如，一个函数需要读取一个文件的当前位置，那么在读取之前应该先记录这个位置，在读取完成后将文件位置恢复到原来的状态，这样即使其他任务在这个函数执行过程中修改了文件位置，也不会影响这个函数的正确执行。

另外，在多线程环境下，可以使用线程本地存储（TLS）来实现可重入。TLS 允许每个线程都有自己独立的变量副本。例如，对于一个可能被多个线程调用的函数，如果这个函数需要使用一个变量来保存中间结果，通过 TLS 可以为每个线程分配一个独立的变量副本，这样每个线程在调用这个函数时，都是操作自己的变量副本，不会相互冲突。

还可以通过互斥锁来辅助实现可重入性。虽然互斥锁本身可能会带来一些性能开销和复杂性，但在某些情况下，它可以确保在任何时候只有一个任务能够访问函数中的临界资源。例如，一个函数需要修改一个共享的数据结构，为了保证可重入性，可以使用互斥锁来保护这个数据结构，在函数开始修改之前获取锁，在修改完成后释放锁，这样可以避免多个任务同时修改这个数据结构导致的数据不一致问题。

你知道 static 关键字吗，它和可重入有什么关系？

在 C 和 C++ 中，static是一个很重要的关键字，它有多种用途。

当static用于修饰局部变量时，这个变量的生命周期会延长。通常情况下，局部变量在函数执行完毕后就会被销毁，但是被static修饰的局部变量在函数第一次调用时被初始化，之后它会一直存在，直到程序结束。例如，在一个函数中定义了一个static变量用于计数，每次调用这个函数，这个计数变量的值都会保留上一次调用后的结果。

当static用于修饰全局变量或者函数时，它会改变变量或者函数的可见性。被static修饰的全局变量或者函数只能在当前文件中被访问，对于其他文件是不可见的。这有助于封装数据和功能，避免命名冲突。

在与可重入性的关系方面，如果一个函数内部使用了static修饰的局部变量，并且这个函数可能被多个任务并发调用，那么就可能会出现问题。因为static局部变量在多个任务调用函数时是共享的，这可能会导致数据不一致。例如，一个函数中有一个static的计数器，当两个线程同时调用这个函数时，它们可能会同时修改这个计数器，导致计数结果错误，从而影响函数的可重入性。

但是，如果能够正确地管理static变量，它也可以在一定程度上辅助实现可重入性。比如，在单线程环境下或者对static变量进行适当的保护（如使用互斥锁），可以确保static变量在函数多次调用过程中的正确使用，使得函数仍然能够保持可重入性。不过总的来说，使用static变量需要谨慎考虑，特别是在多任务或者多线程的环境中，以避免对可重入性产生负面影响。

Volotile 关键字你知道吗？

volatile是 C 和 C++ 中的一个关键字，它主要用于告诉编译器，被修饰的变量可能会在程序执行过程中被意外地改变，因此编译器不能对这个变量进行一些优化。

在多线程或者中断处理的环境中，volatile关键字尤为重要。例如，一个变量可能会被一个线程或者中断服务程序修改，而另一个线程在读取这个变量。如果没有volatile关键字，编译器可能会对这个变量的读取进行优化，例如，编译器可能会认为这个变量在一段时间内不会改变，从而缓存这个变量的值，而不是每次都从内存中读取。这样就会导致读取到的数据是过时的，因为另一个线程或者中断服务程序可能已经修改了这个变量。

以一个简单的例子来说明，假设有一个全局变量flag，一个线程负责修改这个变量，另一个线程负责根据这个变量的值来执行不同的操作。如果flag没有被volatile修饰，编译器可能会优化代码，使得读取flag的线程一直使用缓存中的旧值，而不会去获取内存中最新的flag值。

volatile关键字也可以用于硬件寄存器的访问。在嵌入式系统或者设备驱动开发中，硬件寄存器的值可能会因为硬件的状态变化而改变。当程序访问这些硬件寄存器对应的变量时，需要使用volatile关键字来确保每次访问都是从硬件寄存器中获取最新的值，而不是使用缓存的值。

从编译器的角度看，当遇到volatile变量时，编译器会生成代码来确保每次对这个变量的访问都是直接对内存进行操作，而不会进行优化，例如不会把变量的值缓存到寄存器中或者对访问顺序进行重新排列等操作，从而保证程序能够正确地感知变量的实际变化。

结构体大小计算你知道吗？

结构体大小的计算在 C 和 C++ 中是一个比较复杂的问题。

结构体的大小不是简单地将所有成员的大小相加。首先要考虑成员的对齐方式。编译器会按照一定的规则对结构体成员进行对齐，这是为了提高内存访问的效率。一般来说，每个成员的起始地址是其自身大小或者编译器规定的对齐模数（通常是这个成员大小和一个默认对齐模数中的较小值）的倍数。

例如，在一个 32 位的系统中，默认对齐模数可能是 4 字节。如果一个结构体中有一个char类型（1 字节）的成员和一个int类型（4 字节）的成员，那么char成员后面可能会有 3 个字节的填充，使得int成员的起始地址是 4 字节的倍数。这样整个结构体的大小就会大于char和int大小之和。

对于嵌套的结构体，其对齐方式也遵循类似的规则。嵌套结构体的对齐方式是以其内部最大成员的对齐要求来确定的。例如，一个结构体中有一个嵌套的结构体，这个嵌套结构体内部最大成员是double类型（8 字节），那么这个嵌套结构体的对齐要求就是 8 字节，外部结构体在放置这个嵌套结构体成员时，会按照 8 字节的对齐要求来确定其起始地址。

另外，编译器可能会提供一些指令或者选项来改变默认的对齐方式。例如，可以通过#pragma pack指令来指定一个新的对齐模数，这会影响结构体大小的计算。不过，改变对齐方式可能会影响内存访问的效率，需要谨慎使用。在实际计算结构体大小的时候，需要考虑成员的类型、顺序和对齐要求，以及编译器的相关规则，才能准确地得出结构体的大小。

说一下单链表反转的思路。

单链表反转是一个常见的链表操作。单链表是由节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。

一种基本的思路是采用三个指针来实现。首先定义三个指针，分别为prev（前驱指针）、curr（当前指针）和next（后继指针）。开始时，prev初始化为nullptr，curr指向链表的头节点，next指向curr节点的下一个节点。

在每一步操作中，先将curr节点的下一个指针指向prev，这就实现了当前节点的反转。然后，将prev移动到curr的位置，curr移动到next的位置，next再指向curr节点的下一个节点。通过这样的循环操作，就可以逐个节点地反转链表。

例如，对于链表1 -> 2 -> 3 -> 4，开始时prev = nullptr，curr = 1，next = 2。第一步，将curr（1）的下一个指针指向prev（此时为nullptr），然后prev = 1，curr = 2，next = 3。接着，将curr（2）的下一个指针指向prev（1），以此类推，直到curr指向nullptr，此时prev就指向了反转后的链表头节点。

还可以使用递归的方法来实现。递归的基本思想是将链表的反转问题分解为子问题。对于一个链表，先反转除了头节点之外的其余节点组成的链表，然后将头节点插入到反转后的链表的末尾。

以同样的链表1 -> 2 -> 3 -> 4为例，先递归地反转2 -> 3 -> 4得到4 -> 3 -> 2，然后将头节点 1 插入到4 -> 3 -> 2的末尾，得到4 -> 3 -> 2 -> 1。在递归实现中，需要注意递归的终止条件，当链表为空或者只有一个节点时，链表本身就是反转后的状态，直接返回即可。

说一下队列和栈。

队列和栈都是常见的数据结构。

队列是一种先进先出（FIFO）的数据结构。就像在排队一样，先进入队列的元素会先被取出。它有两个主要的操作，入队和出队。入队操作是将元素添加到队列的末尾，出队操作是从队列的头部取出元素。

例如，在一个任务调度系统中，任务按照提交的顺序进入队列。当处理器资源可用时，从队列头部取出任务进行处理。队列可以用数组或者链表来实现。如果用数组实现，需要考虑队列满和空的情况，以及如何高效地管理数组的空间。如果用链表实现，入队操作就是在链表的尾部添加一个节点，出队操作是删除链表头部的节点。

栈是一种后进先出（LIFO）的数据结构。它就像一个堆叠的容器，最后放入栈中的元素会最先被取出。栈主要有两个操作，压栈和弹栈。压栈是将元素添加到栈顶，弹栈是将栈顶的元素取出。

例如，在表达式求值中，当遇到操作数时，将其压入栈中，当遇到运算符时，从栈中弹出相应数量的操作数进行计算，然后将结果再压入栈中。栈也可以用数组或者链表来实现。用数组实现时，需要一个变量来记录栈顶的位置，压栈操作就是将元素放入栈顶位置，然后栈顶位置加一，弹栈操作是栈顶位置减一，然后取出栈顶位置的元素。用链表实现时，压栈操作是在链表头部添加一个节点，弹栈操作是删除链表头部的节点。

队列和栈在很多算法和程序中都有广泛的应用。队列适用于需要按照顺序处理元素的场景，如消息队列、广度优先搜索算法等。栈适用于需要回溯或者按照逆序处理元素的场景，如函数调用栈、深度优先搜索算法等。

New malloc 区别。

new和malloc都用于在程序中动态分配内存，但它们有一些区别。

从功能上看，new是 C++ 中的操作符，它不仅可以分配内存，还可以调用对象的构造函数。例如，当使用new来创建一个对象时，它会先分配足够的内存来存储这个对象，然后调用对象的构造函数来初始化这个对象。而malloc是 C 语言中的函数，它仅仅是分配一块指定大小的内存，不会进行初始化操作。

在返回值类型方面，malloc返回的是void*类型的指针，这意味着在使用返回的指针之前，需要将其强制转换为合适的指针类型。例如，int *p = (int*)malloc(sizeof(int));。而new根据要创建的对象类型返回相应类型的指针。如果是new int，则返回int*类型的指针，不需要进行强制转换。

在内存分配失败时，malloc返回NULL来表示分配失败。在 C++ 中，new在分配内存失败时会抛出bad_alloc异常。这使得在 C++ 程序中可以使用异常处理机制来更优雅地处理内存分配失败的情况。

从语法角度看，new有多种形式。除了简单的new操作符外，还有new[]用于分配数组，并且在使用new[]分配数组后，需要使用delete[]来释放内存。而malloc只用于分配单个内存块，使用free来释放内存。

例如，int *arr = new int[10];会分配一个包含 10 个int类型元素的数组内存，并返回数组的首地址。delete[] arr;用于释放这个数组的内存。如果使用malloc，则是int *arr = (int*)malloc(10 * sizeof(int));，释放时使用free(arr);。

Free 怎么知道空间大小？

在 C 和 C++ 中，free函数用于释放由malloc、calloc或者realloc分配的内存。

对于malloc分配的内存，free本身并不知道要释放的内存块的大小。这是因为malloc在分配内存时，会在实际分配的内存块之前存储一些管理信息，包括内存块的大小等，但是这些信息对于用户程序是隐藏的。当调用free时，它通过内部的机制来获取这些管理信息，从而知道要释放的内存块的大小。

在一些实现中，malloc分配的内存块的布局可能是这样的：首先是一个头部信息区，这个区域存储了内存块的大小等信息，然后才是用户可以使用的内存区域。当free被调用时，它会根据传入的指针，找到这个内存块的头部信息区，从中获取内存块的大小，然后将整个内存块标记为可再分配的状态。

但是，对于用户来说，必须正确地使用free。如果传递给free的指针不是由malloc、calloc或者realloc返回的，或者这个指针已经被释放过了，就会导致程序出现错误，比如内存泄漏、程序崩溃等。

在 C++ 中，delete和delete[]用于释放由new和new[]分配的内存。它们的工作原理和free类似，但是在释放对象内存时，会先调用对象的析构函数来清理对象资源，然后再释放内存。delete和delete[]也需要正确地使用，要和new和new[]对应使用，否则也会导致程序出现问题。

Const，修饰过的全局变量存在哪？

在 C 和 C++ 中，const修饰的全局变量存储位置与普通全局变量类似，但有一些特殊情况。

一般来说，全局变量（包括const修饰的全局变量）存储在程序的数据段。数据段是内存中的一个区域，用于存储程序中已初始化的全局变量和静态变量。对于const全局变量，由于其值不能被修改，编译器可能会对其进行一些优化。

在 C++ 中，如果const全局变量具有外部链接（即没有使用static关键字），并且其初始值是一个常量表达式，那么这个const全局变量可能会被存储在一个特殊的只读数据段。这个只读数据段的内容在程序运行期间不能被修改，这样可以更好地保证const全局变量的常量性质。

例如，const int global_const = 10;这样的全局常量，其值是一个常量表达式，可能会被存储在只读数据段。但是，如果const全局变量的初始值不是常量表达式，比如const int global_not_const = getValue();（getValue是一个函数），那么这个const全局变量可能会像普通全局变量一样存储在数据段，只是编译器会阻止对其进行修改。

在编译过程中，编译器会对const全局变量进行检查，确保程序中没有试图修改这些变量的代码。如果程序中出现了这样的代码，编译器会发出错误提示。这有助于提高程序的安全性和稳定性，防止因为意外修改全局变量的值而导致程序出现错误。

说说函数指针 指针函数。

函数指针和指针函数是两个不同的概念，在 C 和 C++ 编程中都有各自重要的用途。

函数指针：

函数指针是指向函数的指针变量。它的本质是一个指针，只不过这个指针指向的是函数的入口地址。函数在内存中是有其具体存储位置的，函数指针就可以存储这个位置信息，从而可以通过该指针来调用所指向的函数。

例如，假设有一个函数 int add(int a, int b)，它接受两个整数参数并返回它们的和。那么定义一个函数指针来指向这个函数可以这样做：

int (*funcPtr)(int, int);
funcPtr = add;

这里 int (*funcPtr)(int, int) 声明了一个函数指针 funcPtr，它指向的函数接受两个整数参数并返回一个整数。然后通过 funcPtr = add; 将 add 函数的地址赋给了这个函数指针。之后就可以通过这个函数指针来调用 add 函数了，比如 int result = funcPtr(3, 5);，这就相当于调用了 add(3, 5)，会得到结果 8。

函数指针在很多场景下非常有用，比如在实现回调函数机制时。当一个函数需要根据不同的情况执行不同的操作，但这些操作又有相似的逻辑框架时，就可以将不同的具体函数通过函数指针传递给这个框架函数，让框架函数根据实际传入的函数指针来执行相应的具体操作。

指针函数：

指针函数是指函数的返回值是一个指针类型的函数。也就是说，这个函数执行完后返回的不是一个普通的值，而是一个指针，这个指针可以指向各种数据类型的对象，比如指向数组、结构体等。

例如，下面是一个简单的指针函数示例：

int* createArray(int size) {int* arr = new int[size];return arr;
}

在这个例子中，createArray 函数接受一个整数参数 size，它在函数内部动态分配了一个大小为 size 的整数数组，并返回这个数组的首地址，也就是一个指向整数数组的指针。

指针函数在处理动态内存分配、返回复杂数据结构等场景中经常被用到。比如在处理链表时，一个函数可能需要返回指向链表某个节点的指针，这时候就可以用指针函数来实现。但使用指针函数时要特别注意内存管理问题，比如返回的指针所指向的内存是否需要在合适的时候释放等，否则很容易导致内存泄漏等问题。

面对和上级意见不一致怎么处理？

当与上级意见不一致时，以下是一些较为妥善的处理方式。

首先，要保持冷静和尊重的态度。上级的意见往往基于他们的经验、对整体情况的把握以及公司的战略目标等多方面因素，所以不要急于反驳，而是要认真倾听上级表达的观点和理由。例如，在一次项目讨论会上，上级提出了一种与自己不同的项目推进方案，此时要静下心来听上级详细阐述方案的思路、预期效果以及可能带来的影响等内容。

然后，清晰且有条理地表达自己的观点。在上级陈述完后，找合适的时机，以平和、理性的方式阐述自己的看法。要着重说明自己意见的依据，比如基于自己对项目具体细节的了解、过往类似项目的经验教训、相关数据的分析等。比如可以说 “我理解您提出的方案在某些方面的优势，不过根据我对目前项目中这部分技术细节的深入研究，我认为如果采用另一种方式，可能会在效率上有更大的提升，因为之前我们在类似的技术环节上尝试过不同的做法，得到了这样的经验”。

接着，尝试从双方的意见中寻找共同点和可融合的部分。很可能双方的意见并非完全对立，而是在某些方面有相通之处或者可以相互补充。比如上级的方案侧重于整体的资源调配，而自己的方案在技术实现细节上更有优势，那么就可以探讨是否能将两者结合，既保证资源的合理配置，又能优化技术实现。

如果经过充分的沟通，双方仍然无法达成一致，那么要尊重上级的最终决定。毕竟上级在组织架构中承担着更多的责任和决策权力。但在执行过程中，可以保持关注，若发现确实存在问题，可以适时地再次提出自己的看法，并提供更具说服力的证据来支持。

在整个过程中，沟通的方式和态度至关重要。要避免情绪化的表达，始终以解决问题、推动项目或工作顺利进行为目标，通过良好的沟通来处理意见分歧，维护良好的工作关系。

对小米的了解。

小米是一家在全球范围内颇具影响力的科技公司，业务涵盖多个领域，具有以下一些显著特点和业务板块。

在智能手机领域，小米是重要的参与者之一。小米手机以高性价比闻名于世，其产品线丰富多样，涵盖了从入门级到高端旗舰等不同价位段的产品。例如，小米的 Redmi 系列主打性价比，为预算有限的消费者提供了性能不错的手机选择；而小米数字系列以及 MIX 系列等则在性能、拍照、设计等方面不断创新，向高端市场进军。小米在手机研发上投入颇多，不断推出新的技术和功能，如快充技术、高像素相机等，以满足消费者日益增长的需求。

除了手机，小米在智能家居领域也有着广泛的布局。小米推出了众多智能家居产品，构建了庞大的小米生态链。这些产品包括智能音箱（如小爱同学）、智能摄像头、智能门锁、智能灯具、智能插座等等。通过小米的米家 APP，可以实现对这些智能家居产品的集中控制和互联互通，让用户可以便捷地打造智能化的家居生活场景。例如，用户可以通过语音指令让小爱同学控制智能灯具的开关、调节亮度，或者查看智能摄像头的实时画面等。

在科技创新方面，小米也积极投入。它设立了多个研发中心，致力于新技术的研发和应用。比如在芯片研发领域，小米一直在努力探索，虽未达到行业顶尖水平，但也取得了一定的成果，推出了一些用于自家手机等产品的芯片，展现了其在自主创新方面的决心。

小米的商业模式也较为独特。它采用了线上线下相结合的销售模式。线上通过小米官网、各大电商平台等进行产品销售，线下则开设了众多小米之家实体店，为消费者提供了体验和购买产品的场所。这种模式既满足了消费者线上便捷购物的需求，又能让消费者在实体店中亲身感受产品的品质和功能。

此外，小米还积极拓展海外市场，其产品在印度、东南亚、欧洲等多个地区都受到了不同程度的欢迎，提升了小米品牌的国际影响力。

了解其他编程语言吗？

我对多种编程语言都有一定的了解。

Python 是一门非常流行的编程语言，它具有简洁、易读的语法特点，被广泛应用于数据科学、机器学习、网络爬虫、自动化脚本编写等众多领域。例如，在数据科学领域，Python 有丰富的库如 NumPy、Pandas、Matplotlib 等，通过这些库可以方便地进行数据处理、分析和可视化。在机器学习方面，TensorFlow、PyTorch 等深度学习框架都提供了 Python 接口，使得研究人员和开发者可以轻松地构建和训练模型。

Java 是一门面向对象的编程语言，具有很强的跨平台性。它在企业级应用开发、安卓应用开发等领域占据重要地位。Java 的代码结构严谨，有完善的类和对象体系。例如，在企业级应用开发中，通过 Java 的各种框架如 Spring、Hibernate 等，可以快速搭建起复杂的业务逻辑和数据库交互系统。在安卓应用开发中，Java 曾经是主要的开发语言（现在也可以使用 Kotlin 等），用于开发安卓手机上的各种应用程序。

JavaScript 是一种用于网页前端开发的编程语言，同时也在后端开发（通过 Node.js）中得到了应用。在前端开发中，JavaScript 可以与 HTML 和 CSS 配合，实现网页的动态效果、交互功能等。比如通过 JavaScript 可以实现网页上的按钮点击事件、表单验证等功能。在后端开发中，Node.js 使得 JavaScript 可以像其他后端语言一样处理服务器端的请求和响应，构建全栈应用程序。

Ruby 是一门注重编程人员体验的编程语言，它的语法简洁且富有表现力。Ruby on Rails 是一个基于 Ruby 的 Web 开发框架，以快速开发 Web 应用程序而闻名。通过 Ruby on Rails，开发者可以在较短的时间内搭建起一个功能齐全的 Web 应用程序，其内置的各种功能和约定俗成的开发模式大大提高了开发效率。

此外，还有像 C#（主要用于.NET 平台开发，在 Windows 应用程序开发、游戏开发等领域有应用）、Swift（用于苹果设备应用开发，如 iPhone、iPad 等应用程序开发）等编程语言，它们都在各自特定的领域发挥着重要作用，并且都有其独特的语法、特性和应用场景。

对后续的方向有什么打算？

关于后续的方向，我有以下一些初步的打算。

在技术提升方面，我计划继续深入学习和掌握与我目前擅长领域相关的前沿技术。比如，如果是在软件开发领域，我会关注新的编程语言特性、新的开发框架以及先进的算法等。以 C++ 为例，我会深入研究 C++ 的新版本特性，如 C++20、C++23 等所带来的新的语法糖、更高效的容器和算法等，以便在项目开发中能够更灵活地运用这些知识，提升代码的质量和开发效率。

我也打算拓宽我的技术知识面，涉足一些相邻或相关的领域。例如，如果我主要从事前端开发，我可能会开始学习后端开发技术，了解数据库管理、服务器端编程等方面的知识，从而有能力参与全栈开发项目，提升自己的综合竞争力。或者，如果我在某一特定领域如人工智能领域有一定基础，我会去了解与之相关的硬件知识，比如芯片技术、传感器技术等，以便更好地理解和优化整个系统的运行。

在项目参与方面，我希望能够参与到一些更具挑战性的项目中。这些项目可能涉及到复杂的业务逻辑、大规模的数据处理或者高难度的技术实现。通过参与这样的项目，我可以锻炼自己解决复杂问题的能力，积累更多的实践经验，并且可以与更多优秀的同行进行交流和合作，从他们身上学到更多的东西。

从职业发展角度来看，我考虑逐步向技术管理方向转型。在积累了足够的技术经验后，我希望能够带领团队完成项目，负责团队的技术规划、人员培养等工作。我会注重培养自己的沟通能力、领导力以及项目管理能力，以便能够更好地协调团队成员之间的关系，推动项目的顺利进行，实现团队和个人的共同成长。

另外，我也希望能够通过参加技术研讨会、行业展会等活动，与行业内的专家、同行进行广泛的交流，及时了解行业的最新动态和发展趋势，为自己的发展方向做出更准确的调整和规划。

了解 awk 命令吗？

awk 是一种强大的文本处理工具，在 Linux 和 Unix 环境中广泛使用。

awk 命令的基本语法是 awk 'pattern {action}' file。其中，pattern 部分用于指定匹配的模式，action 是在匹配成功后执行的操作，file 是要处理的文件名。如果省略 file，则可以从标准输入读取数据。

从功能上看，awk 主要用于从文本文件或者文本流中提取和处理数据。例如，它可以根据特定的字符或者字段来分割文本行。默认情况下，awk 以空格或者制表符作为字段分隔符。假设有一个文本文件，每行包含用户的姓名、年龄和城市信息，如 "John 30 New York"，可以使用 awk 来提取特定的字段。比如 awk '{print $1}' file.txt 会打印出每行的第一个字段，也就是姓名。

awk 还能进行条件判断。比如，要打印出年龄大于 30 岁的用户信息，可以使用 awk '$2 > 30 {print}' file.txt。这里的 $2 代表每行的第二个字段，也就是年龄，当年龄大于 30 时，就会打印整行的信息。

它也支持自定义变量和函数。可以在 awk 脚本中定义变量来存储中间结果或者进行计数等操作。例如，定义一个变量来计算满足某个条件的行数，通过 BEGIN 块来初始化变量，在 {action} 部分更新变量，最后在 END 部分输出变量的值。

在处理复杂的文本格式转换时，awk 也非常有用。例如，将一种格式的日志文件转换为另一种格式，或者从 HTML 文件中提取特定的标签内容等。同时，awk 还可以与其他命令结合使用，比如和管道操作符一起，将一个命令的输出作为 awk 的输入，从而实现更复杂的文本处理流程。

单向链表只知道其中一个节点的地址，如何删除这个节点？

在单向链表中，如果只知道要删除的节点的地址，情况会比较复杂，因为单向链表没有指向前一个节点的指针。

一种可行的方法是先判断这个节点是否是头节点。如果是头节点，那么直接将头节点指向下一个节点就可以删除当前头节点。但如果不是头节点，就需要遍历链表来找到这个节点的前一个节点。

假设链表节点的结构包含一个数据域和一个指向下一个节点的指针，例如：

struct ListNode {int data;ListNode* next;
};

为了删除一个已知地址的节点（假设这个节点不是头节点），可以从链表头开始遍历，同时维护一个指向当前节点和前一个节点的指针。

void deleteNode(ListNode* nodeToDelete) {if (nodeToDelete == nullptr) {return;}ListNode* current = head;ListNode* prev = nullptr;while (current!= nodeToDelete) {prev = current;current = current->next;}// 找到了要删除的节点if (prev!= nullptr) {prev->next = current->next;}// 释放节点内存delete current;
}

不过，这种方法在链表很长的情况下，时间复杂度是 ，其中  是链表的长度。

还有一种特殊情况，如果要删除的节点是尾节点，在找到尾节点的前一个节点后，将其 next 指针置为 nullptr，就完成了尾节点的删除。

另外，如果可以修改链表节点的结构，一种巧妙的方法是将当前要删除节点的值替换为下一个节点的值，然后将当前节点的下一个指针指向下下一个节点，相当于跳过了下一个节点，间接实现了对当前节点的删除。不过这种方法需要注意边界条件，比如当前节点是尾节点时就不适用。

死锁产生的要素，死锁的检测。

死锁产生的要素：

死锁的产生通常需要四个必要条件，分别是互斥条件、请求和保持条件、不可剥夺条件和循环等待条件。

互斥条件是指资源在某一时刻只能被一个进程所使用。例如，打印机在打印一份文档时，不能同时被其他进程用于打印其他文档。这种独占性的资源访问是死锁产生的基础之一。

请求和保持条件是指进程在已经保持了至少一个资源的情况下，又提出了新的资源请求，而这个新资源此时被其他进程占用，且该进程在等待新资源的同时，不会释放已经持有的资源。比如，进程 A 已经占用了资源 R1，又请求资源 R2，而资源 R2 被进程 B 占用，进程 A 在等待资源 R2 的过程中不会释放资源 R1。

不可剥夺条件意味着资源在被一个进程占用后，不能被其他进程强行剥夺，除非占用资源的进程自己主动释放。例如，内存中的一块特定区域被一个进程分配使用后，其他进程不能直接把这块内存抢走，必须等待该进程使用完毕释放。

循环等待条件是指存在一组进程，每个进程都在等待下一个进程所占用的资源，形成了一个资源等待的环形链。例如，进程 P1 等待进程 P2 占用的资源 R2，进程 P2 等待进程 P3 占用的资源 R3，进程 P3 又等待进程 P1 占用的资源 R1，这样就形成了一个死锁循环。

死锁的检测：

死锁检测主要有两种方式，一种是基于资源分配图的检测，另一种是通过系统状态的监测来判断。

基于资源分配图的检测方法是构建一个有向图，图中的节点包括进程节点和资源节点。如果进程请求资源，就从进程节点向资源节点画一条有向边；如果资源被分配给了进程，就从资源节点向进程节点画一条有向边。当图中存在一个环，并且环中的每一条边都是请求边（从进程指向资源）时，就表示存在死锁。这种方法能够直观地反映资源分配和请求的关系，但在复杂的系统中，构建和分析资源分配图可能会比较复杂。

通过系统状态的监测来判断死锁，是通过收集系统中进程的资源请求、分配和等待信息来进行分析。例如，记录每个进程所占用的资源列表和请求的资源列表，定期检查是否存在一组进程满足死锁的四个必要条件。这种方法需要系统维护详细的资源和进程状态信息，并且需要一定的算法来分析这些信息，以判断是否存在死锁。在一些操作系统中，会有专门的死锁检测模块，通过检查系统内核中的进程和资源状态表来发现死锁情况。

说一下死锁。

死锁是指在多进程或者多线程环境下，一组进程或线程在执行过程中，因为竞争系统资源或者相互等待对方释放资源而导致的一种僵持状态，使得这些进程或线程都无法继续向前推进。

从资源角度看，死锁通常涉及到对系统有限资源的竞争。这些资源可以是硬件资源，如打印机、磁盘驱动器等，也可以是软件资源，如互斥锁、信号量等。例如，在一个数据库系统中，多个事务可能同时竞争数据库中的锁资源。如果两个事务分别锁定了一部分数据，然后又请求对方已经锁定的数据，就可能会导致死锁。

死锁产生的后果比较严重。对于发生死锁的进程或线程，它们会处于一种无限等待的状态，无法完成它们本来要执行的任务。这不仅会浪费系统资源，如 CPU 时间、内存等，还可能导致系统的性能下降，甚至整个系统出现故障。

以一个简单的进程示例来说明，假设有两个进程 P1 和 P2，它们都需要访问两个资源 R1 和 R2。P1 首先获取了 R1，P2 获取了 R2。然后 P1 请求 R2，同时 P2 请求 R1，由于它们都不会释放已经获取的资源，并且等待对方释放自己所需的资源，就陷入了死锁状态。

在操作系统或者并发程序设计中，死锁是一个需要重点关注的问题。为了避免死锁的发生，需要对资源的分配和使用进行合理的规划和管理。例如，采用合适的资源分配策略，确保资源请求的顺序是合理的，或者对资源进行预先分配等方式，都可以在一定程度上减少死锁发生的可能性。

怎么避免死锁？

为了避免死锁，可以从破坏死锁产生的四个必要条件入手。

首先是破坏互斥条件。在某些情况下，可以通过采用共享资源的方式来避免互斥。例如，对于一些可以同时被多个进程访问的只读文件，允许多个进程同时读取，而不是独占式的访问。不过，在很多实际场景中，资源的互斥性是由资源本身的性质决定的，如打印机等物理设备很难实现同时被多个进程使用，所以这种方法有一定的局限性。

其次是破坏请求和保持条件。一种方法是采用一次性分配策略，即进程在运行前就一次性申请它所需要的全部资源。只有当所有资源都分配成功后，进程才开始运行。这样就避免了进程在持有部分资源的情况下又请求其他资源的情况。例如，在一个数据库事务处理系统中，一个事务可以在开始时就请求它可能需要的所有锁资源，而不是在执行过程中逐步请求。

破坏不可剥夺条件也是一种策略。可以允许系统剥夺进程已经占有的资源。例如，在优先级较高的进程需要资源时，系统可以强制收回优先级较低的进程占用的资源。不过，这种方法可能会导致进程的执行被中断，需要考虑如何妥善地恢复被中断进程的执行状态，以避免数据丢失或其他问题。

另外，还可以通过破坏循环等待条件来避免死锁。这可以通过规定资源的请求顺序来实现。例如，给系统中的资源编号，要求进程按照资源编号递增的顺序请求资源。这样就不会出现循环等待的情况。比如，资源有 R1、R2、R3，进程必须先请求 R1，在获得 R1 后才能请求 R2，获得 R2 后才能请求 R3，这样就避免了一个进程等待另一个进程已经占用的较低编号资源的情况。

除了从破坏死锁产生条件入手，还可以采用死锁预防算法。这些算法会在资源分配之前进行检查，判断是否可能导致死锁。例如，银行家算法是一种经典的死锁预防算法，它通过检查系统的资源分配状态和进程的资源请求，来判断是否存在安全状态。如果一个资源分配请求会导致系统进入不安全状态（可能导致死锁），则拒绝这个请求。

你知道同步互斥吗？

同步和互斥是在多线程或多进程编程中非常重要的概念。

互斥主要用于保护共享资源，防止多个线程或进程同时访问和修改这些资源，从而导致数据不一致或错误。例如，在一个银行账户系统中，有多个线程可能会同时对一个账户余额进行操作，如存款和取款。如果没有互斥机制，可能会出现一个线程在读取余额进行取款操作时，另一个线程同时修改了余额，导致取款金额计算错误。

互斥通常通过互斥锁（Mutex）来实现。当一个线程想要访问共享资源时，它需要先获取互斥锁。如果互斥锁已经被其他线程获取，那么这个线程就会被阻塞，直到互斥锁被释放。例如，在 C++ 的std::mutex，当一个线程调用lock函数获取锁时，如果锁是可用的，它就会成功获取并继续执行后续操作；如果锁已经被其他线程占用，该线程就会等待。当线程完成对共享资源的访问后，需要调用unlock函数释放互斥锁，这样其他等待的线程才有机会获取锁并访问资源。

同步则是用于协调多个线程或进程的执行顺序，使得它们能够按照预期的顺序进行操作。比如，在一个生产者 - 消费者模型中，生产者线程负责生产数据并将其放入缓冲区，消费者线程负责从缓冲区中取出数据进行消费。同步机制可以确保生产者在缓冲区满之前不会继续生产，消费者在缓冲区空之前不会尝试消费。

条件变量（Condition Variable）是实现同步的一种重要工具。它允许一个线程等待某个条件满足后再继续执行。例如，消费者线程可以等待缓冲区非空这个条件，当生产者将数据放入缓冲区后，通过条件变量通知消费者线程，消费者线程被唤醒后就可以从缓冲区中取出数据进行消费。

在实际的多线程编程中，正确地使用同步和互斥机制可以有效地提高程序的并发性能和正确性，但如果使用不当，也可能会导致死锁、饥饿等问题。

基类、派生类调用构造函数、析构函数的顺序，以及一些访问权限问题。

在继承关系中，构造函数和析构函数的调用顺序是非常重要的。

对于构造函数，首先会调用基类的构造函数，然后再调用派生类的构造函数。这是因为派生类是基于基类构建的，在创建派生类对象时，需要先确保基类部分的成员得到正确的初始化。例如，假设有一个基类Base和一个派生类Derived，Derived类继承自Base类。当创建Derived类的对象时，会先调用Base类的构造函数来初始化基类部分的成员，然后调用Derived类的构造函数来初始化派生类特有的成员。

如果基类有多个构造函数，派生类在初始化列表中可以指定调用基类的哪一个构造函数。比如，基类Base有两个构造函数Base(int)和Base(double)，派生类Derived可以在其构造函数的初始化列表中写Derived(int a) : Base(a) {... }来调用基类的Base(int)构造函数。

在访问权限方面，派生类可以访问基类的公有（public）和保护（protected）成员。公有成员可以在任何地方访问，就像普通的函数和变量一样。保护成员可以在派生类内部访问，但不能在类外部访问（除非通过派生类的接口）。而基类的私有（private）成员在派生类中是不可访问的。

对于析构函数，调用顺序与构造函数相反。首先会调用派生类的析构函数，然后再调用基类的析构函数。这是因为在对象销毁时，派生类部分的清理工作应该先完成，然后再清理基类部分。例如，在Derived类的析构函数执行完后，会自动调用Base类的析构函数来释放基类部分的资源。

需要注意的是，如果在构造函数或析构函数中调用了虚函数，可能会出现一些意外的情况。在构造函数中，由于对象还没有完全构造完成，此时调用虚函数，实际上调用的是当前正在构造的类的函数，而不是派生类中重写后的函数。在析构函数中也有类似的情况，这是因为在析构函数执行时，派生类部分可能已经被部分销毁，所以要谨慎使用虚函数。

C 里如何实现 C++ 的容器，比如：一种类型是 list，另一种类型是 RB - tree，都是 insert 操作函数，能根据类型选择对应数据类型的 insert。

在 C 语言中实现类似 C++ 容器的功能需要自己构建数据结构和相关的操作函数。

对于list（链表）结构，可以定义一个链表节点的结构体。例如：

// 链表节点结构体
typedef struct ListNode {void* data;struct ListNode* next;
} ListNode;

这里的data指针可以用来存储任意类型的数据（通过强制类型转换），next指针指向下一个节点。

insert操作函数可以这样实现：

// 在链表头部插入节点
void list_insert(ListNode** head, void* data) {ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));newNode->data = data;newNode->next = *head;*head = newNode;
}

对于RB - tree（红黑树），首先要定义红黑树节点的结构体。红黑树节点除了存储数据外，还需要存储节点的颜色（红或黑）以及左右子节点和父节点的指针。

// 红黑树节点结构体
typedef struct RBTreeNode {void* data;int color;struct RBTreeNode* left;struct RBTreeNode* left;struct RBTreeNode* parent;
} RBTreeNode;

RB - tree的insert操作会比较复杂。首先要按照二叉搜索树的规则找到插入位置，然后插入新节点，之后再根据红黑树的性质进行调整，以保持红黑树的平衡。

为了能够根据类型选择对应的insert操作，可以定义一个通用的函数指针类型，然后根据具体的容器类型来调用相应的insert函数。例如：

// 定义函数指针类型
typedef void (*InsertFunction)(void*, void*);// 根据类型调用insert函数
void insert_data(void* container, InsertFunction insertFn, void* data) {insertFn(container, data);
}

这样，当有一个链表和一个红黑树时，可以分别定义它们的insert函数，然后通过insert_data函数来调用相应的insert操作，具体调用哪个insert函数取决于传递给insert_data函数的insertFn函数指针。

在 C 语言中实现这些功能需要更精细地管理内存，因为没有像 C++ 那样的自动内存管理机制（如构造函数和析构函数）。并且，这些自定义的容器在安全性和易用性方面可能不如 C++ 的标准容器，需要开发者自己确保正确的使用和数据的完整性。

不想让别的对象访问本类，应该怎么做？然后自己怎么访问的？

如果不想让别的对象访问本类，可以将类的成员设置为私有（private）或保护（protected）访问权限。

在 C++ 中，当成员被设置为私有访问权限时，只有类内部的成员函数和友元函数可以访问这些成员。例如，假设有一个类MyClass：

class MyClass {
private:int privateData;
public:MyClass(int data) : privateData(data) {}void accessPrivateData() {// 类内部可以访问私有成员std::cout << privateData << std::endl;}
};

在这个例子中，privateData是私有成员，只有MyClass类内部的函数（如accessPrivateData）可以访问它。其他类的对象无法直接访问privateData。

如果想在类内部访问这些私有成员，就像上面的例子一样，通过类的成员函数来访问。成员函数可以直接使用私有成员变量，对其进行读取、修改等操作。

如果是保护访问权限，除了类内部的成员函数可以访问外，派生类也可以访问这些成员。这在继承关系中比较有用。例如，有一个基类Base和一个派生类Derived：

class Base {
protected:int protectedData;
public:Base(int data) : protectedData(data) {}
};class Derived : public Base {
public:Derived(int data) : Base(data) {}void accessProtectedData() {// 派生类可以访问基类的保护成员std::cout << protectedData << std::endl;}
};

在这个例子中，Derived类可以访问Base类的protectedData成员，这是因为protectedData是保护成员，在派生类内部是可以访问的。

Static 局部变量？生命周期？

在 C 和 C++ 中，static局部变量是一种特殊的变量。

当一个局部变量被声明为static时，它的生命周期会发生变化。普通的局部变量在函数执行完毕后就会被销毁，它的存储空间也会被释放。但是static局部变量在函数第一次被调用时初始化，之后它的生命周期会贯穿整个程序的运行过程，直到程序结束才会被销毁。

例如，有一个函数：

void myFunction() {static int staticVar = 0;staticVar++;std::cout << staticVar << std::endl;
}

每次调用myFunction函数时，staticVar的值都会在上一次的基础上增加 1。因为staticVar是static局部变量，它在第一次调用函数时被初始化为 0，之后即使函数执行完毕，staticVar也不会被销毁，下一次调用函数时，它仍然保留着上一次的值。

在内存分配方面，static局部变量存储在数据段（在一些编译器实现中），而普通局部变量存储在栈上。由于static局部变量的生命周期长，并且存储在数据段，所以它在初始化时需要注意。如果没有显式初始化，static局部变量会被自动初始化为 0（对于基本数据类型）或者空指针（对于指针类型）。

static局部变量的这种特性使得它在一些场景下非常有用。例如，当需要在一个函数内部记录一些状态信息，并且这些信息需要在多次调用函数之间保持时，就可以使用static局部变量。不过，由于它的生命周期长，在多线程环境下可能会出现一些问题，需要谨慎使用，避免多个线程同时访问和修改static局部变量导致数据不一致。

描述堆栈溢出的可能情况。

堆栈溢出是一种常见的程序错误，主要发生在栈空间被过度使用的情况。

在函数调用过程中，每次调用一个函数，系统会在栈上为函数的局部变量、返回地址等信息分配空间。当一个函数递归调用自身时，如果没有正确的终止条件或者递归层次过深，就很容易导致栈溢出。例如，一个计算斐波那契数列的函数，如果使用简单的递归实现（如int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }），当n的值较大时，会产生大量的递归调用，每个递归调用都会在栈上占用一定的空间，最终可能会耗尽栈空间，导致堆栈溢出。

局部变量数组分配过大也可能引起堆栈溢出。如果在一个函数中定义了一个非常大的局部数组，而栈的空间有限，当这个数组的大小超过栈所能承受的范围时，就会出现问题。例如，在一个函数中定义int arr[100000000]（假设栈空间无法容纳这么大的数组），在程序运行到这个函数时，可能会因为无法为这个大数组分配足够的栈空间而导致堆栈溢出。

另外，在一些嵌套函数调用的场景中，如果每个函数都有大量的局部变量，并且嵌套层次较深，也会增加栈的负担。比如，函数 A 调用函数 B，函数 B 又调用函数 C，每个函数内部都有较多的局部变量，这样累积起来的栈空间使用量可能会超出栈的限制。

在多线程环境下，每个线程都有自己的栈空间。如果线程的栈空间设置过小，而线程执行的函数调用或局部变量分配又比较复杂，也可能会导致线程的栈溢出，进而影响整个程序的稳定性。

SVM 有哪些优点，以及基本原理。

支持向量机（SVM）是一种强大的机器学习算法，具有诸多优点。

从优点方面来说，SVM 在处理小样本数据集时表现出色。它能够在有限的数据量下有效地学习数据的特征和模式，避免了过拟合。例如，在一些医学研究中，可能获取的病例样本数量有限，SVM 可以通过这些少量样本找到疾病与症状之间的有效分类边界。

SVM 的泛化能力强。它可以很好地处理高维数据，并且对于数据中的噪声和离群点有一定的鲁棒性。在文本分类领域，文档通常被表示为高维的向量空间模型，SVM 能够在这个高维空间中找到一个合适的超平面来划分不同的文本类别，即使数据中存在一些噪声干扰，也能保持较好的分类效果。

它的基本原理是基于寻找一个最优的分类超平面。对于线性可分的数据，SVM 的目标是找到一个超平面，使得不同类别的数据点到这个超平面的间隔最大。这个间隔被称为 “margin”。假设我们有两类数据点，分别用不同的颜色表示，SVM 会寻找一个超平面，将这两类数据点尽可能地分开，并且保证这个超平面到最近的数据点（这些点被称为支持向量）的距离最大。

对于非线性可分的数据，SVM 通过核函数（Kernel Function）将原始数据映射到一个高维空间，在这个高维空间中数据可能变得线性可分。例如，多项式核函数可以将数据映射到一个高维的多项式空间，高斯核函数可以将数据映射到一个无限维的空间。通过这种方式，SVM 能够处理各种复杂的非线性分类问题。在实际应用中，通过选择合适的核函数和调整相关的参数，可以优化 SVM 的分类性能，以适应不同的数据集和分类任务。

全局变量和全局静态变量的区别。

在 C 和 C++ 中，全局变量和全局静态变量有一些重要的区别。

全局变量是在所有函数外部定义的变量，它的作用域是从定义点开始到整个源文件结束，并且可以通过extern关键字在其他文件中访问（如果在多文件程序中）。例如，在一个源文件中有int globalVariable;，这个全局变量可以在同一个源文件的任何函数中使用，并且如果在其他源文件中进行了正确的声明（如extern int globalVariable;），也可以在其他源文件中访问。

全局静态变量是使用static关键字修饰的全局变量。它的作用域仅限于定义它的源文件内部，不能被其他源文件访问。这使得全局静态变量具有更好的封装性。例如，static int globalStaticVariable;这个变量只能在定义它的源文件中被使用，即使在其他源文件中使用extern关键字也无法访问这个变量。

从存储位置来看，全局变量和全局静态变量通常都存储在数据段。但是，由于全局静态变量的访问范围受限，它在一定程度上可以避免命名冲突。在一个大型项目中，多个源文件可能会定义相同名称的全局静态变量，但是由于它们的作用域仅限于各自的源文件，所以不会相互干扰。

在生命周期方面，全局变量和全局静态变量都是在程序开始运行时就被创建，直到程序结束才被销毁。不过，因为全局静态变量的作用域限制，它在内存中的使用更加安全，不会被其他源文件中的代码意外修改，有助于提高程序的可靠性和可维护性。

静态函数和普通函数的区别，存储的位置有什么不同？

静态函数和普通函数在多个方面存在区别。

首先是作用域方面，普通函数的作用域是整个程序。只要在函数声明或定义之后的任何地方，都可以调用这个函数。例如，在一个源文件中定义了一个函数int normalFunction(int x) { return x * 2; }，在同一个项目的其他源文件中，只要进行了正确的声明，就可以调用这个函数。

而静态函数的作用域仅限于定义它的源文件内部。它就像是这个源文件的私有函数。例如，static int staticFunction(int y) { return y + 1; }这个静态函数只能在定义它的源文件中被调用，其他源文件无法访问这个函数。这种限制作用域的特性使得静态函数有助于封装代码，避免函数名冲突。

在存储位置上，对于大多数编译器而言，普通函数和静态函数在代码段（Text Segment）存储。代码段是用来存储程序的可执行指令的内存区域。它们在存储位置上并没有本质的区别，但是编译器在链接过程中对它们的处理方式不同。

普通函数在链接时，符号是可以被外部文件引用的，这使得其他文件可以通过链接找到这个函数的地址并调用它。而静态函数在编译时，其符号是内部链接的，这意味着编译器不会将这个函数的符号暴露给其他文件，从而实现了函数的局部化。

另外，从使用场景来看，普通函数适合于提供公共的功能接口，供多个不同的模块使用。静态函数则更多地用于在一个源文件内部，对一些不需要被外部访问的功能进行封装，提高代码的模块化程度和可维护性。

数据结构用过哪些？

我用过多种数据结构。

首先是数组，它是一种简单而基础的数据结构。数组在内存中是连续存储的元素集合。例如，在 C 和 C++ 中，int arr[10];定义了一个包含 10 个整数的数组。数组的优点是可以快速地访问元素，通过下标操作，访问元素的时间复杂度是。它适用于存储同类型的、数量固定的数据，比如存储一个班级学生的成绩。不过，数组的大小在定义时通常是固定的，如果需要动态扩展数组大小，在一些语言中会比较复杂。

链表也是常用的数据结构。链表分为单向链表、双向链表等。以单向链表为例，它由节点组成，每个节点包含数据和指向下一个节点的指针。链表的优点是可以方便地进行插入和删除操作。例如，在一个简单的链表插入操作中，插入一个新节点只需要修改相关节点的指针即可，时间复杂度在合适的位置插入是。但是，链表的随机访问性能较差，要访问链表中的某个节点，需要从表头开始遍历，时间复杂度是，其中n是链表的长度。链表适用于需要频繁插入和删除元素的场景，比如实现一个简单的任务队列。

栈和队列也是重要的数据结构。栈是一种后进先出（LIFO）的数据结构，主要操作是压栈和弹栈。例如，在函数调用过程中，系统会使用栈来存储函数的局部变量、返回地址等信息。队列是先进先出（FIFO）的数据结构，用于模拟排队等场景，其主要操作是入队和出队。在消息队列系统中，消息按照发送的顺序进入队列，然后按照先进先出的原则被处理。

树结构也被广泛使用，如二叉树、二叉搜索树、平衡二叉树等。二叉搜索树是一种特殊的二叉树，它满足对于任意节点，其左子树中的所有节点的值都小于该节点的值，右子树中的所有节点的值都大于该节点的值。这种结构使得查找、插入和删除操作的时间复杂度在平衡情况下可以达到，其中n是树中的节点数量。在数据库索引等领域，二叉搜索树及其变体（如 AVL 树、红黑树）被用来提高数据查找的效率。

还有图结构，图由顶点和边组成。图可以用于表示各种复杂的关系，如社交网络中的人际关系、交通网络中的路线等。在图中，可以进行深度优先搜索（DFS）和广度优先搜索（BFS）等操作来遍历图。例如，在地图导航应用中，通过对交通网络图的搜索，可以找到从一个地点到另一个地点的最短路径。

自旋锁和互斥锁，使用场景。

自旋锁和互斥锁都是用于多线程同步的机制，但它们有不同的特点和适用场景。

自旋锁：

自旋锁的特点是当一个线程尝试获取已经被占用的锁时，它不会进入睡眠状态，而是会一直循环检查锁是否被释放，这个循环等待的过程就像是线程在 “自旋”。

使用场景方面，自旋锁适用于锁被占用的时间很短的情况。例如，在多处理器系统中，对于一些简单的共享资源保护，如一个简单的计数器，其操作可能非常快速。如果一个线程获取了这个计数器的自旋锁，其他线程在尝试获取锁时，由于计数器的操作很快就能完成，这些线程在自旋等待一小段时间后就能获取到锁，这种情况下使用自旋锁可以避免线程上下文切换的开销。

在一些实时性要求较高的场景中，自旋锁也比较有用。因为线程在自旋等待时不会像进入睡眠状态那样有不确定的唤醒延迟。例如，在一个实时操作系统的内核中，对于一些对时间非常敏感的中断处理程序和任务之间的共享资源访问，如果使用自旋锁，可以确保任务能够尽快地获取锁并继续执行，从而满足实时性的要求。

但是，自旋锁如果长时间获取不到会一直占用 CPU 资源，导致 CPU 利用率过高。所以如果锁被占用的时间可能比较长，就不适合使用自旋锁。

互斥锁：

互斥锁的工作方式是当一个线程获取了互斥锁后，其他试图获取该锁的线程会被阻塞，直到锁被释放后才会被唤醒。

互斥锁适用于锁被占用时间较长的情况。例如，在一个文件读写操作中，一个线程可能需要较长时间来读取或写入一个大型文件。当这个线程获取了文件访问的互斥锁后，其他线程可以进入睡眠状态等待锁被释放，这样可以避免像自旋锁那样长时间占用 CPU 资源进行无意义的等待。

在复杂的资源访问场景中，互斥锁也更合适。比如，在一个数据库事务处理系统中，一个事务可能需要对多个数据库表进行一系列复杂的读写操作，这个过程可能涉及到大量的计算和数据访问。使用互斥锁可以有效地保护这些数据库资源，确保在一个事务完成之前，其他事务不会干扰，并且其他等待的事务可以在合适的时候被唤醒继续执行。

总的来说，选择自旋锁还是互斥锁需要根据共享资源的性质、锁被占用的时间长短以及对系统性能的要求等因素来综合考虑。

堆和栈的区别。

堆和栈是计算机内存中的两个不同的存储区域，它们在内存管理、数据存储方式、使用场景等方面都有诸多区别。

内存管理方面：

栈是由系统自动管理的内存区域。当一个函数被调用时，系统会在栈上为函数的局部变量、参数、返回地址等分配空间。当函数执行结束后，系统会自动回收这些空间。例如，在一个简单的函数int add(int a, int b) { int result = a + b; return result; }中，a、b和result这些局部变量的空间是在栈上分配的，当add函数执行完毕后，这些空间会被系统自动释放。

堆则需要程序员手动进行内存管理。在 C 和 C++ 中，通过函数如malloc（C）或new（C++）来在堆上分配内存，使用free（C）或delete（C++）来释放内存。如果程序员忘记释放堆上的内存，就会导致内存泄漏。例如，int* ptr = (int*)malloc(sizeof(int));在堆上分配了一个整数类型大小的空间，当不再需要这个空间时，需要使用free(ptr);来释放。

数据存储方式：

栈是一种后进先出（LIFO）的数据结构。数据在栈上的存储是连续的，每个新的数据项会被压入栈顶，当需要取出数据时，从栈顶开始弹出。例如，在函数调用栈中，当一个函数调用另一个函数时，新函数的相关信息（如参数、返回地址等）会被压入栈顶，当被调用函数执行完毕后，这些信息从栈顶弹出，程序控制返回到调用函数。

堆上的数据存储则没有像栈那样严格的顺序。堆中的内存是动态分配的，内存块的大小和位置取决于分配时的具体情况。堆中的数据可以通过指针来访问，这些指针可以指向堆中任意位置的内存块。

使用场景方面：

栈主要用于存储函数内部的局部变量、函数参数等短期存在的数据。由于栈的自动管理特性，它适用于简单的、局部的、生命周期较短的数据存储。例如，在一个循环中，每次循环的临时变量可以存储在栈上。

堆则用于存储那些生命周期较长、大小不确定或者需要在多个函数之间共享的数据。比如，在一个动态数据结构（如链表）的创建中，每个节点的内存通常是在堆上分配的，因为节点的数量可能会动态变化，而且这些节点可能需要在程序的不同部分被访问和修改。