理想汽车C++一面面经
二叉树的后序遍历是一种深度优先遍历方式，它的遍历顺序是先访问左子树，然后访问右子树，最后访问根节点。
给个思路：
使用迭代方法实现后序遍历需要借助栈来模拟递归的过程。具体地，可以使用两个栈，一个栈用来存储遍历的节点，另一个栈用来存储遍历的结果。
在遍历的过程中，我们先将根节点入栈，然后循环执行以下操作：
将栈顶节点弹出并将其值插入到结果栈中。
如果该节点有左子树，则将左子树入栈。
如果该节点有右子树，则将右子树入栈。
参考代码：（这里给出ACM模式的）
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 二叉树节点的定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result; // 用于存储后序遍历结果的数组
stack<TreeNode*> s; // 辅助栈，用于模拟递归的过程
if (root != nullptr) {
s.push(root); // 如果根节点不为空，则将根节点入栈
}
while (!s.empty()) {
TreeNode* node = s.top(); // 获取栈顶节点
s.pop(); // 弹出栈顶节点
result.insert(result.begin(), node->val); // 将当前节点值插入到结果数组的头部
if (node->left != nullptr) {
s.push(node->left); // 如果当前节点的左子节点不为空，则将其左子节点入栈
}
if (node->right != nullptr) {
s.push(node->right); // 如果当前节点的右子节点不为空，则将其右子节点入栈
}
}
return result; // 返回后序遍历结果
}
};
// 测试函数
int main() {
// 创建一棵二叉树
TreeNode* root = new TreeNode(1);
root->right = new TreeNode(2);
root->right->left = new TreeNode(3);
// 创建解决方案对象
Solution solution;
// 进行后序遍历
vector<int> result = solution.postorderTraversal(root);
// 输出结果
cout << "后序遍历结果：";
for (int val : result) {
cout << val << " ";
}
cout << endl;
return 0;
}C++
1、C++11了解哪些内容？
- 自动类型推导（Auto）：允许编译器推导变量的类型，使代码更加简洁。
auto x = 5; // x的类型将被推导为int- 范围-based for 循环：简化了对容器元素的遍历。
std::vector<int> numbers = {1, 2, 3, 4, 5};
for (const auto& num : numbers) {
// 使用num
}- 智能指针：引入了
std::shared_ptr和std::unique_ptr等智能指针，用于管理动态分配的内存，帮助防止内存泄漏。
std::shared_ptr<int> sharedPtr = std::make_shared<int>(42);- Lambda 表达式：允许在函数内部定义匿名函数，提高代码可读性和灵活性。
auto add = [](int a, int b) { return a + b; };- nullptr：引入了空指针常量
nullptr，用于替代传统的空指针NULL。
int* ptr = nullptr;- 强制类型转换（Type Casting）：引入了
static_cast、dynamic_cast、const_cast、reinterpret_cast等更安全和灵活的类型转换操作符。
double x = 3.14;
int y = static_cast<int>(x);- 右值引用和移动语义：支持通过右值引用实现移动语义，提高了对临时对象的处理效率。
std::vector<int> getVector() {
// 返回一个临时vector
return std::vector<int>{1, 2, 3};
}
std::vector<int> numbers = getVector(); // 使用移动语义- 新的容器和算法：引入了新的容器，如
std::unordered_map、std::unordered_set，以及一些新的算法。
std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}};- 线程支持（std::thread）：提供了原生的多线程支持，使得并发编程更加方便。
#include <thread>
void myFunction() {
// 线程执行的代码
}
int main() {
std::thread t(myFunction);
t.join(); // 等待线程结束
return 0;
}2、智能指针介绍一下，shared_ptr的作用，存储方式，weak_ptr的作用，如何和shared结合使用？
这里讲讲这四种智能指针吧。
std::shared_ptr：- 原理：
std::shared_ptr使用引用计数来管理内存。每当你将一个std::shared_ptr指向某个对象时，引用计数会增加。当引用计数达到零（没有任何shared_ptr指向该对象）时，对象的内存将被自动释放。 - 何时释放内存：当最后一个指向对象的
std::shared_ptr被销毁或重置时，对象的内存会被释放。
- 原理：
std::unique_ptr：- 原理：
std::unique_ptr使用独占所有权语义，确保只有一个指针可以拥有资源。它不使用引用计数，而是在std::unique_ptr被销毁时自动释放资源。 - 何时释放内存：当
std::unique_ptr被销毁、离开其作用域或通过std::move转移资源时，资源会被释放。
- 原理：
std::weak_ptr：- 原理：
std::weak_ptr是一种弱引用智能指针，它用于协助解决循环引用问题。它不会增加引用计数，仅用于监视std::shared_ptr的状态。 - 何时释放内存：
std::weak_ptr不会直接释放内存，它只是用于观察std::shared_ptr的生命周期。内存释放由相关的std::shared_ptr负责。
- 原理：
std::auto_ptr（已过时，不建议使用）：- 原理：
std::auto_ptr具有独占所有权，类似于std::unique_ptr。但它有一些缺陷，不支持复制操作，且没有移动语义。 - 何时释放内存：当
std::auto_ptr被销毁时，它会释放其内存。然而，由于其缺陷，它容易导致不安全的内存管理。
- 原理：
3、Lambda表达式的原理？
Lambda表达式的一般形式如下：
[capture](parameters) -> return_type { body }其中：
capture指定了Lambda表达式所捕获的外部变量的方式，可以是值传递或引用传递。parameters指定了Lambda表达式的参数列表。return_type指定了Lambda表达式的返回类型。body是Lambda表达式的函数体。
Lambda表达式的原理可以简单概括为以下几点：
闭包：
Lambda表达式实际上是一个闭包，它可以捕获所在作用域中的变量，并在其函数体内使用这些变量。捕获的方式可以是值传递或引用传递，通过在Lambda表达式的
[]中指定捕获方式。函数对象：
Lambda表达式本质上是一个匿名的函数对象，它可以像普通函数一样被调用。编译器会根据Lambda表达式的定义生成一个匿名的函数对象类型，并在需要的地方实例化这个类型的对象。
模板元编程：
Lambda表达式的类型是通过模板元编程生成的。编译器会根据Lambda表达式的定义推断出其类型，并在需要的地方实例化这个类型的对象。
闭包类型：
Lambda表达式会生成一个闭包类型，这个类型的对象可以在其作用域内使用捕获的外部变量，并且可以像函数一样被调用。
4、STL迭代器的失效情况，unordered_map的底层结构？
迭代器失效意味着迭代器指向的元素不再有效，可能指向了错误的元素，或者根本无法使用。
以下是对STL容器迭代器失效情况的总结：
插入操作：
在容器中插入元素时，可能会导致容器重新分配内存，原有的迭代器失效。例如，对vector进行插入操作时，如果导致vector的容量不足，可能会触发重新分配内存的操作，使得原有的迭代器失效。
删除操作：
在容器中删除元素时，可能会导致容器内部元素的移动，从而使得原有的迭代器失效。例如，对list进行删除操作时，可能会导致迭代器指向的元素被移动或删除，使得迭代器失效。
清空操作：
对容器执行clear操作会清空容器中的所有元素，导致所有迭代器失效。
复制和赋值操作：
当一个容器被复制给另一个容器或者进行赋值操作时，目标容器的迭代器会失效。这是因为复制和赋值操作可能会导致目标容器的内部结构发生变化。
unordered_map和unordered_set的rehash操作：
对于unordered_map和unordered_set，它们的内部实现通常是哈希表。当容器进行rehash操作时，会重新分配桶的数量，这可能会导致所有的迭代器失效。
vector和deque的insert和erase操作：
在vector和deque中，如果在中间位置进行插入或者删除操作，会导致后续元素的移动，这可能会使得之前的迭代器失效。
list的splice操作：
list提供了splice操作用于将两个list合并，这个操作可能会导致迭代器失效，具体取决于splice的参数和实现方式。
unordered_map
std::unordered_map 是 C++ 标准库提供的一个无序关联容器，它基于哈希表实现。哈希表是一种高效的数据结构，它通过将元素的键（key）映射到一个确定的位置来实现快速的查找、插入和删除操作。
在 std::unordered_map 中，元素被存储在一个数组中，这个数组被称为哈希表。每个元素的键经过哈希函数映射到数组中的一个位置，这个位置称为桶（bucket）。当两个不同的键映射到了同一个桶时，就会产生哈希冲突，这时通常会使用链表或者红黑树等数据结构来解决冲突。
下面是 std::unordered_map 的底层结构主要特点：
哈希函数：
哈希函数是用于将键映射到桶的位置的函数。它通常会将键的值转换成一个整数，然后通过取模等方式将其映射到桶的位置上。
桶：
桶是哈希表中存储元素的位置。每个桶存储一个链表或者红黑树，用于解决哈希冲突。当多个键映射到同一个桶时，它们会以链表或者红黑树的形式存储在这个桶中。
负载因子和rehash：
负载因子是哈希表中元素数量与桶的数量的比值。当负载因子超过某个阈值时，通常会触发rehash操作，即重新分配更大的桶数，并重新将元素插入到新的桶中，以保持哈希表的效率。
冲突解决：
哈希表中可能会出现冲突，即多个键映射到同一个桶的情况。常见的解决冲突的方法包括链地址法（Chaining）和开放地址法（Open Addressing）。在
std::unordered_map中，通常使用链地址法来解决冲突，即将冲突的键值对以链表或者红黑树的形式存储在同一个桶中。
Linux
1、linux程序崩溃怎么定位问题？
查看错误信息：
当程序崩溃时，通常会输出一些错误信息，例如错误代码、错误位置等。可以查看程序崩溃时的输出信息，以了解程序崩溃的原因。
使用调试工具：
使用调试工具可以帮助定位程序崩溃的问题。常用的调试工具包括GDB（GNU Debugger）和Valgrind。GDB是一个强大的调试器，可以在程序崩溃时提供调试信息，并允许你逐步执行程序、查看变量的值等。Valgrind是一个内存检测工具，可以检测内存泄漏、非法内存访问等问题，对于一些内存相关的程序崩溃问题特别有用。
日志文件：
程序通常会输出日志文件，其中包含了程序运行时的信息。查看日志文件可以帮助定位程序崩溃的原因。可以使用
tail命令实时查看日志文件的最后几行，或者使用grep命令查找特定的关键词。核心转储文件：
在程序崩溃时，Linux系统会生成一个核心转储文件（core dump），其中包含了程序崩溃时的内存状态。可以使用GDB等调试工具来分析核心转储文件，以了解程序崩溃时的内存状态和调用栈信息。
使用日志记录：
在程序中添加日志记录功能，可以在程序运行时输出详细的日志信息，以帮助定位程序崩溃的问题。可以使用标准的日志库（如syslog、log4cpp等）来实现日志记录功能。
内存检测工具：
使用内存检测工具（如Valgrind）可以检测程序中的内存问题，例如内存泄漏、非法内存访问等，这些问题可能导致程序崩溃。
代码审查：
对程序的代码进行审查，查找可能导致程序崩溃的代码段，例如未初始化的变量、空指针引用等。
2、在某些情况下core文件的堆栈调用顺序会被溢出的内容覆盖，这时就没办法使用backtrace命令查看调用堆栈了，这种情况下如何定位问题？
在某些情况下，如果核心转储文件（core dump）的堆栈调用顺序被溢出的内容覆盖，导致无法使用backtrace命令或其他调试工具查看调用堆栈，可以尝试以下方法来定位问题：
查看日志文件：
如果程序在崩溃时有日志输出，可以查看日志文件中的信息，尝试从中找到程序崩溃的原因或相关线索。
静态分析代码：
对程序的代码进行静态分析，尝试找出可能导致程序崩溃的代码段。可以使用静态分析工具（如Clang Static Analyzer、Cppcheck等）来检测代码中的潜在问题。
增加日志记录：
在程序中增加更多的日志记录，特别是在可能导致程序崩溃的关键代码段添加详细的日志信息，以便在程序崩溃时能够获取更多的调试信息。
使用内存检测工具：
使用内存检测工具（如Valgrind）来检测程序中的内存问题，例如内存泄漏、非法内存访问等。这些问题可能导致程序崩溃，即使无法获取完整的调用堆栈信息，仍然可以通过内存检测工具来定位问题。
增加异常处理：
在程序中增加异常处理代码，捕获可能导致程序崩溃的异常，并在捕获异常时记录相关信息，以便在程序崩溃时能够获取更多的调试信息。
代码审查和重构：
对程序的代码进行审查，尝试找出可能存在的问题，并进行代码重构或修复。通过代码审查和重构，可以改善程序的稳定性和可靠性，减少程序崩溃的可能性。
3、linux的内存是如何组织的？
主要包括以下几个部分：
内核空间和用户空间：
Linux将整个内存划分为内核空间和用户空间。内核空间是保留给操作系统内核使用的部分，而用户空间是供用户程序运行的部分。内核空间通常位于高地址区域，而用户空间位于低地址区域。
物理内存和虚拟内存：
Linux中的内存管理是建立在虚拟内存的基础上的。物理内存是实际存在的硬件内存，而虚拟内存是一种抽象的概念，它允许操作系统将物理内存和硬盘上的空间组合起来使用。这样可以实现更灵活的内存管理，提高系统的稳定性和安全性。
页式存储管理：
Linux使用页式存储管理机制来管理内存。在页式存储管理中，内存被分成固定大小的页（通常为4KB或者更大），每个页都有一个对应的页表项。当程序访问内存时，操作系统会根据页表将虚拟地址转换成物理地址。
内存分配器：
Linux内核提供了内存分配器（Memory Allocator）来管理内核空间的内存分配。常见的内存分配器包括SLUB、SLAB和kmalloc等，它们负责管理内核空间的内存分配和释放，确保内核空间的内存使用高效和可靠。
交换空间：
Linux还提供了交换空间（Swap Space）来扩展系统的虚拟内存。当物理内存不足时，操作系统会将部分内存数据写入交换空间，以释放物理内存供其他程序使用。交换空间通常位于硬盘上，可以是一个分区或者一个文件。
内存映射：
Linux中的内存映射（Memory Mapping）机制允许进程将文件映射到自己的地址空间中，从而可以像访问内存一样访问文件。内存映射提供了一种高效的文件访问方式，同时也可以用于共享内存等应用场景。
4、你说到缺页中断，能介绍一下缺页中断么？
缺页中断（Page Fault）是操作系统中的一种机制，用于处理虚拟内存中缺少对应物理内存页的情况。当程序访问一个尚未载入到物理内存中的虚拟内存页时，就会触发缺页中断，操作系统会根据情况进行处理，将所需的页面加载到物理内存中。
缺页中断的处理过程如下：
发生缺页中断：
当程序访问的虚拟内存页不在物理内存中时，CPU会产生一次缺页中断，将控制权交给操作系统内核。
处理缺页中断：
操作系统内核会根据缺页中断的原因进行处理。如果缺页中断是由于页面不在物理内存中而导致的，操作系统会按照一定的算法选择一个物理页面进行替换，将所需的页面从磁盘或者其他存储介质中读取到物理内存中，并更新页表等相关数据结构。
恢复程序执行：
当缺页中断处理完毕后，操作系统会重新启动被中断的指令，使程序能够继续执行。此时所需的页面已经在物理内存中，程序可以正常访问。
5、对于缺页中断这种情况，linux操作系统是如何减少页面的换入换出的呢，有哪些方式？
页面置换算法的优化：
Linux操作系统中使用了多种页面置换算法，例如最近最久未使用（LRU）、时钟（Clock）算法等。这些算法根据页面的访问情况和时间信息来决定哪些页面应该被置换出去。通过优化页面置换算法，可以减少不必要的页面置换，提高内存的利用率。
预取机制（Prefetching）：
Linux操作系统引入了预取机制，通过预先将可能会被访问的页面提前加载到内存中，可以减少缺页中断的发生率。预取机制可以根据程序的访问模式和历史访问情况来预测未来可能的访问，提高页面命中率。
页面合并（Page Merging）：
Linux操作系统中的页面合并机制可以将相邻的相同内容的页面合并成一个页面，减少内存中的重复数据量，从而减少页面的换入换出。页面合并可以提高内存的利用率，降低内存碎片化的程度。
页面回写策略的优化：
Linux操作系统中使用了多种页面回写（Writeback）策略，包括定期回写、脏页面回写等。通过优化页面回写策略，可以减少不必要的页面写入磁盘的次数，降低IO开销，提高系统的性能。
内存压缩（Memory Compression）：
Linux操作系统引入了内存压缩机制，可以在内存紧张时将部分内存页进行压缩，从而节省内存空间。内存压缩可以减少页面的换入换出，提高系统的响应速度。
内存分配策略的优化：
Linux操作系统中的内存分配策略对页面的换入换出也有影响。通过优化内存分配策略，可以减少内存碎片化，提高内存的利用率，从而减少页面的换入换出。
计算机网络
1、你了解数字证书么？
数字证书是一种用于证明数字实体身份和提供加密通信安全的数字文件。它通常包含了一些公开的信息，如证书持有者的名称、公钥等，并由认证机构（CA，Certificate Authority）使用其私钥签名，以确保证书的真实性和完整性。
以下是数字证书的一些重要概念和作用：
- 证书持有者身份认证： 数字证书可以用于验证网络上的实体（如网站、服务器、个人等）的身份。通过验证证书中的信息，可以确定通信方的身份是否合法可信。
- 数据加密与签名验证： 数字证书中包含了公钥，可以用于数据的加密和签名验证。当通信双方拥有对方的数字证书时，可以使用对方的公钥进行加密，确保数据在传输过程中的机密性。同时，可以使用数字证书中的签名信息来验证数据的完整性和真实性。
- HTTPS通信安全： 在HTTPS通信中，服务器会向客户端发送自己的数字证书，客户端通过验证证书的有效性来确认服务器身份。如果证书有效且受信任，客户端就可以使用证书中的公钥来加密通信内容，确保通信的安全性。
- 数字签名： 数字证书中的签名信息是由CA使用私钥对证书内容进行签名的结果。通过验证签名的有效性，可以确保证书的真实性和完整性。数字签名在各种网络安全场景中都有广泛的应用，如电子邮件、文件传输等。
- 证书链： 数字证书通常是以链式结构存在的，每个证书都包含了签发者的信息，形成了一个证书链。通过验证证书链的完整性，可以确保整个通信过程中的信任链路是可靠的。
2、https的握手过程说一下？
客户端Hello：
客户端向服务器发送一个ClientHello消息，其中包含了客户端支持的SSL/TLS协议版本、加密算法、压缩算法等信息。
服务器Hello：
服务器收到客户端的ClientHello消息后，会从中选择一个SSL/TLS协议版本、加密算法、压缩算法，并向客户端发送一个ServerHello消息，该消息中包含了服务器选择的协议版本和加密算法等信息。
证书：
服务器在ServerHello消息中还会携带自己的数字证书，用于证明服务器的身份。证书中包含了服务器的公钥和相关信息，并由服务器的私钥进行签名。
密钥交换：
客户端收到服务器的证书后，会验证证书的有效性，并提取出服务器的公钥。然后客户端生成一个随机数作为对称加密算法的密钥，并使用服务器的公钥对该密钥进行加密，发送给服务器。
握手结束：
客户端发送一个ClientKeyExchange消息，其中包含了使用服务器公钥加密后的对称密钥。接着客户端发送一个ChangeCipherSpec消息，表示接下来的通信都将使用协商好的加密算法进行加密。最后客户端发送一个Finished消息，其中包含了握手消息的摘要，用于服务器验证握手消息的完整性。
服务器验证：
服务器收到客户端的Finished消息后，会进行解密并验证摘要的完整性。如果验证通过，服务器也会发送一个ChangeCipherSpec消息和一个Finished消息，表示服务器端的握手结束。
加密通信：
握手完成后，客户端和服务器就可以使用协商好的对称密钥进行加密通信了，保证了通信的安全性和机密性。
3、对于https中的加密算法，rsa和ecc椭圆加密，这两者有什么区别么？
RSA（Rivest-Shamir-Adleman）和ECC（Elliptic Curve Cryptography）都是公钥加密算法，用于在HTTPS中进行密钥协商和数据加密。它们之间的主要区别如下：
密钥长度：
RSA密钥长度通常较长，一般为1024位到4096位不等，而ECC密钥长度相对较短，一般为160位到256位不等。相同安全级别下，ECC所需的密钥长度更短，能够提供相同的安全性。
计算复杂度：
ECC相对于RSA来说，具有更高的计算效率和更小的资源消耗。ECC在相同安全级别下，需要更少的计算量和存储空间，能够提供更快的加密和解密速度。
抵抗量子计算攻击：
ECC对于量子计算攻击具有更好的抵抗性。由于量子计算机的特性，它们可以在较短时间内破解大多数当前使用的加密算法，但是ECC相对于RSA来说，对量子计算攻击具有更强的抵抗能力。
安全性：
在相同密钥长度下，ECC相对于RSA来说，提供了更高的安全性。这意味着可以使用更短的密钥长度来达到相同的安全级别，从而减少了加密和解密所需的计算量。
应用范围：
RSA广泛应用于传统的加密场景中，如SSL/TLS协议、数字签名等。而ECC在资源受限的环境下（如移动设备、物联网设备等）有着更大的优势，因为它所需的密钥长度更短，能够减少通信时的数据量和计算消耗。