大家好，我是阿Q。
今天给大家分享一篇百度提前批的面经。为什么会三战？因为现在百度的面试每个候选人要是这一面过了就会接着下边的面试，正常情况下也会是三面技术面。
今年的秋招已经进入了白热化的阶段，过完国庆节陆陆续续就会接近尾声，意向的基本上都会发正式offer了。。。
所以，大家可以做最后的决战了，尽快查漏补缺，预祝大家在这一周内都能得到自己满意的结果。
来源： https://www.nowcoder.com/interview/center?entranceType=%E5%AF%BC%E8%88%AA%E6%A0%8F
一面：
1、写题是一道二叉树路径最大路径和。（上来就是一道题。。。）
这里呢，我提供两种方法供大家参考，这道题在面试中算是一个高频题目。在刷题网站上也会找到相应的题目，不用自己写输入输出罢了，ACM模式的话还是需要自己来写输入输出的。
递归：递归遍历二叉树的每个节点，以找到路径的最大权值和。对于每个节点，有两个选择：要么继续沿左子树走，要么继续沿右子树走。所以，我们可以定义一个递归函数，该函数返回以当前节点为路径起点的最大权值和。然后，通过递归遍历每个节点来找到整棵树的最大权值和。
迭代：使用栈进行迭代遍历二叉树，并维护一个全局最大路径和变量。
#include <iostream>#include <algorithm>#include <stack>#include <unordered_map>using namespace std;// 二叉树节点结构struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};int maxPathSumRecursive(TreeNode* root, int& maxSum) {if (root == nullptr) {return 0;}int leftMax = max(maxPathSumRecursive(root->left, maxSum), 0);int rightMax = max(maxPathSumRecursive(root->right, maxSum), 0);int currentMax = root->val + leftMax + rightMax;maxSum = max(maxSum, currentMax);// 返回以当前节点为路径终点的最大路径和return root->val + max(leftMax, rightMax);}int maxPathSumRecursive(TreeNode* root) {int maxSum = INT_MIN;maxPathSumRecursive(root, maxSum);return maxSum;}int maxPathSumIterative(TreeNode* root) {if (root == nullptr) {return 0;}int maxSum = INT_MIN; // 存储最大路径和的全局变量stack<TreeNode*> nodeStack;TreeNode* curr = root;unordered_map<TreeNode*, bool> visited;while (curr || !nodeStack.empty()) {while (curr && !visited[curr]) {nodeStack.push(curr);curr = curr->left;}curr = nodeStack.top();if (visited[curr]) {int leftMax = max(maxPathSumIterative(curr->left), 0);int rightMax = max(maxPathSumIterative(curr->right), 0);int currentMax = curr->val + leftMax + rightMax;maxSum = max(maxSum, currentMax);nodeStack.pop();curr = nullptr;}else {visited[curr] = true;curr = curr->right;}}return maxSum;}int main() {// 创建二叉树TreeNode* root = new TreeNode(-10);root->left = new TreeNode(9);root->right = new TreeNode(20);root->right->left = new TreeNode(15);root->right->right = new TreeNode(7);int resultRecursive = maxPathSumRecursive(root);int resultIterative = maxPathSumIterative(root);cout << "递归方法 - 二叉树最大路径和为: " << resultRecursive << endl;cout << "迭代方法 - 二叉树最大路径和为: " << resultIterative << endl;return 0;}
结果输出：
2、介绍一下智能指针的实现？
3、进程间通信的方式？
4、协程是否了解？协程一定优于线程吗？
协程是一种计算机程序组件，它允许在程序执行中暂停和恢复执行，而不是通过传统的函数调用和返回来实现控制流的转移。协程通常被用于处理异步编程、并发编程和任务调度等场景，它可以改善代码的可读性和可维护性，并提供了一种更轻量级的线程管理方式。
概念：
协程是一种轻量级的执行单元，与线程和进程不同，它不依赖于操作系统的线程调度和管理。协程可以看作是一种更高级别的抽象，它在程序中可以创建多个执行上下文，允许程序员控制这些上下文的执行流程。
特点：
暂停和恢复：协程可以在执行的任意点暂停，并在稍后恢复执行。这种能力使得协程可以更灵活地处理异步操作，例如I/O或等待事件发生。
协作式多任务：协程通常是协作式的，意味着它们需要主动让出CPU控制权给其他协程。这与线程不同，线程可能会被操作系统强制切换。
共享状态：协程可以在同一地址空间内共享数据，而不需要复杂的线程同步机制。这降低了多线程编程中的竞态条件和死锁问题。
对比：
资源消耗：协程通常比线程更轻量级，因为它们不需要操作系统级别的线程管理和内存分配。一个程序中可以创建大量协程而不会导致显著的资源消耗。
并发性：协程可以实现高度的并发性，因为它们可以在一个线程内同时运行多个协程，而线程通常需要多个线程才能实现相同的并发性。
可读性和可维护性：使用协程可以改善代码的可读性和可维护性，因为它们允许编写顺序化的代码，而不需要复杂的回调或线程同步。
性能：协程的性能通常比线程更高，因为它们减少了线程切换的开销。但是在某些情况下，线程可能更适合需要利用多核处理器的计算密集型任务。
适用场景：协程适用于许多异步编程、网络编程、并发编程和任务调度的场景，特别是在处理大量连接或I/O操作时。线程更适合于需要充分利用多核CPU的情况。
总的来说，协程并不一定优于线程，而是根据具体的应用场景来选择。它们各自有自己的优势和限制。在一些情况下，协程可以提供更简单和高效的解决方案，而在其他情况下，线程可能更适合。
5、TCP和UDP的区别？
6、DNS用的是TCP还是UDP？
用于将人类可读的域名（例如，www.xxx.com）转换为计算机可理解的IP地址（例如，192.0.2.1）。DNS充当了互联网上域名和IP地址之间的翻译服务，类似于互联网的"电话号码簿"。
作用及用途：
域名解析：DNS的主要作用是将域名解析为IP地址。当您在浏览器中键入一个网址时，例如 "www.xxx.com"，您的计算机会通过DNS查找该域名对应的IP地址，然后使用该IP地址来定位和连接到服务器，以获取网页内容。
负载均衡：DNS可以用于实现负载均衡。通过在DNS配置中设置多个IP地址，DNS服务器可以轮流将请求分发到不同的服务器上，以分散流量并提高性能和可用性。
反向解析：DNS不仅可以将域名解析为IP地址，还可以执行反向解析，将IP地址转换为域名。这对于了解服务器的主机名和标识非常有用。
邮件路由：DNS用于确定电子邮件的邮件服务器。当您发送电子邮件时，SMTP服务器使用DNS来查找接收电子邮件的目标邮件服务器的IP地址。
安全性：DNS还在互联网中扮演了关键的角色，特别是在安全性方面。DNSSEC（DNS Security Extensions）是一种扩展DNS协议，用于提供域名数据的认证和完整性验证，以防止DNS污染和欺骗攻击。
DNS使用UDP的情况：
查询短小的域名数据：大多数DNS查询都非常短小，包括域名解析和IP地址的响应。UDP是一种无连接的协议，对于小数据包的传输非常高效。
快速响应：UDP的无连接特性使得DNS服务器能够快速响应查询请求，而不需要建立和维护长时间的连接。
降低网络负载：由于DNS是一种广泛分布在互联网上的服务，使用UDP可以降低网络负载和服务器负担。
DNS使用TCP的情况：
大型响应：当DNS响应的数据包超过UDP的最大传输单元（通常是512字节）时，DNS服务器可能会选择使用TCP来传输响应。这通常发生在DNS响应中包含大量资源记录（例如，DNSSEC签名的情况）时。
可靠性：TCP是一种可靠的传输协议，当DNS查询或响应对于某些应用程序来说非常关键时，服务器可能会选择使用TCP，以确保数据的可靠传输。
区域传输：DNS区域传输是DNS服务器之间的数据同步过程，通常使用TCP进行传输，因为它涉及大量数据的传输。
但是需要注意的是，DNS通常在UDP上运行，因为它对于绝大多数域名解析和查询来说足够快速和高效。只有在特定情况下，例如大型响应或需要可靠性的情况下，DNS才会使用TCP。
以上便是一面的算法及八股，总的来说，并没有什么难度，中规中矩。
二面：
1、写题是二叉树的层序遍历，每过一层顺序反转一下？
使用队列来实现，具体步骤如下：
使用一个队列来进行层序遍历。将根节点入队。
在每一层开始时，记录队列的当前大小（即当前层节点的数量）。
遍历当前层的节点数量，依次出队，并记录节点的值。
如果当前层是奇数层（从0开始计数），则将记录的节点值数组翻转。
将当前层的子节点入队。
重复步骤2至5，直到队列为空，即完成了二叉树的层序遍历并在每过一层时顺序反转节点值。
#include <iostream>#include <vector>#include <queue>#include <algorithm>using namespace std;// 二叉树节点结构struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}};vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (!root) {return result;}queue<TreeNode*> q;q.push(root);bool reverseLevel = false; // 是否需要反转当前层的节点值while (!q.empty()) {int levelSize = q.size();vector<int> levelValues(levelSize);for (int i = 0; i < levelSize; ++i) {TreeNode* node = q.front();q.pop();int index = reverseLevel ? levelSize - i - 1 : i;levelValues[index] = node->val;if (node->left) {q.push(node->left);}if (node->right) {q.push(node->right);}}result.push_back(levelValues);reverseLevel = !reverseLevel; // 切换下一层是否需要反转}return result;}int main() {// 创建二叉树TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);root->right->left = new TreeNode(6);root->right->right = new TreeNode(7);vector<vector<int>> result = levelOrder(root);for (const vector<int>& level : result) {for (int val : level) {cout << val << " ";}cout << endl;}return 0;}
结果输出：
2、介绍一下智能指针？
一面已问，不再赘述。。
3、介绍一下常见的排序算法？
4、静态数组和new数组的区别？
内存管理：
静态数组：静态数组在编译时分配内存，其大小是固定的，定义数组时需要指定其大小。数组的生命周期与其所在的作用域相同，一旦离开作用域，数组就被销毁。
new数组：使用
new
运算符创建的数组是在堆内存上动态分配的，其大小可以在运行时确定，不需要在定义时指定大小。数组的生命周期由程序员负责，需要使用delete[]
运算符显式释放内存，否则可能会导致内存泄漏。大小：
静态数组：静态数组的大小在编译时确定，不能更改。
new数组：使用
new
创建的数组的大小可以在运行时动态分配和修改，因此更灵活。作用域：
静态数组：静态数组的作用域通常受限于其所在的函数或代码块。
new数组：使用
new
创建的数组可以在不同的函数之间传递和共享。生存期：
静态数组：静态数组的生存期受限于其所在的作用域，一旦作用域结束，数组将自动销毁。
new数组：使用
new
创建的数组的生存期由程序员控制，需要在适当的时候使用delete[]
运算符手动释放内存。错误风险：
静态数组：由于其固定大小，静态数组在运行时不能动态适应数据需求。如果数组太小，可能会导致缓冲区溢出；如果太大，可能会浪费内存。
new数组：动态数组的大小可以在运行时根据需要进行调整，可以更灵活地管理内存，但需要小心避免内存泄漏和释放后的访问。
如果数组大小固定且较小，并且生存期与作用域相符，静态数组可能更适合。如果数组大小需要在运行时确定或需要在不同函数之间传递，动态数组可能更合适。但在使用动态数组时要格外小心内存管理，以避免内存泄漏和悬挂指针等问题。
5、程序编译的具体过程介绍一下？
预处理（Preprocessing）：在编译的第一阶段，源代码经过预处理器处理。预处理器执行以下操作：
移除注释：删除源代码中的注释行（以
//
或/* */
形式）。展开宏：将源代码中定义的宏展开为其实际内容。
处理条件编译：根据条件编译指令（如
#ifdef
、#ifndef
、#if
等）决定是否包含或排除特定代码块。编译（Compilation）：在编译阶段，预处理后的源代码被编译器翻译成中间代码（通常是汇编语言或机器代码的一种表示形式），这个中间代码通常称为汇编代码（Assembly Code）。
汇编（Assembly）：汇编器将中间代码翻译成目标机器的汇编语言代码。这是一个与具体计算机架构相关的步骤。
链接（Linking）：在链接阶段，编译器会将源代码中使用的外部库（如标准库、自定义库）与程序的汇编代码进行链接，以创建可执行文件。链接器执行以下操作：
解析符号引用：将源代码中引用的函数或变量与其定义关联起来。
解析库依赖：确定程序需要的外部库，并将其链接到程序中。
生成可执行文件：将所有的汇编代码和库组合成一个可执行文件。
优化（Optimization）（可选）：一些编译器会在编译阶段执行代码优化，以提高程序的性能和效率。优化可以包括常量折叠、循环展开、内联函数等。
生成可执行文件（Executable）：最终，编译器将链接后的代码生成可执行文件，这个文件包含了计算机可以直接执行的指令。
执行程序：用户可以运行生成的可执行文件，将程序加载到计算机的内存中，并开始执行。
6、静态库和动态库有什么区别？
静态库（Static Library）：
编译时链接：静态库在编译时与程序代码链接，编译器将库中的函数和数据复制到程序的可执行文件中。
文件扩展名：静态库的文件扩展名通常是
.lib
（Windows）或.a
（Unix/Linux）。体积较大：静态库会增加可执行文件的体积，因为库的代码和数据会被复制到每个使用该库的可执行文件中。
独立性：静态库使得可执行文件具有独立性，不需要依赖外部库文件，因为库的代码已经包含在可执行文件中。
库更新：如果静态库需要更新，需要重新编译和链接可执行文件。
动态库（Dynamic Library）：
运行时链接：动态库在程序运行时与程序代码链接，操作系统加载库文件，并在需要时将其加载到内存中。
文件扩展名：动态库的文件扩展名通常是
.dll
（Windows）或.so
（Unix/Linux）。体积较小：动态库不会增加可执行文件的体积，因为库文件不会被复制到可执行文件中，而是在需要时加载。
共享性：多个程序可以共享同一个动态库的实例，因此节省内存。当库需要更新时，只需替换库文件而无需重新编译和链接程序。
依赖性：可执行文件依赖于动态库，因此在运行时需要确保库文件存在并可访问。如果库文件缺失或版本不兼容，程序可能无法运行。
选择静态库还是动态库取决于以下因素：
可执行文件大小：如果可执行文件的大小是一个重要考虑因素，静态库可能会导致较大的可执行文件。在这种情况下，动态库更有利。
共享性和内存：如果多个应用程序可以共享同一库的实例，并且内存占用是一个重要因素，动态库通常更有利。
库的更新和管理：如果需要频繁更新库，动态库更容易管理。静态库需要重新编译和重新链接可执行文件。
平台兼容性：不同操作系统和平台对于库的处理方式不同。动态库通常更容易实现跨平台兼容性。
7、map和unordered_map的区别？
其实都是老八股了，不仅要了解概念和原理，还要熟悉它们的区别和使用场景。
底层数据结构：
std::map
使用红黑树（Red-Black Tree）作为底层数据结构，因此它是有序的，键值对按键的升序排列。std::unordered_map
使用哈希表（Hash Table）作为底层数据结构，因此它是无序的，键值对的存储顺序与哈希函数的输出无关。
查找时间复杂度：
std::map
的查找时间复杂度为 O(log n)，因为红黑树保证了有序性。std::unordered_map
的查找时间复杂度平均为 O(1)，在大多数情况下非常快，但在极端情况下，可能会退化为 O(n)，需要谨慎选择哈希函数以避免冲突。
插入和删除时间复杂度：
std::map
的插入和删除时间复杂度为 O(log n)，由于要维护红黑树的平衡性。std::unordered_map
的插入和删除时间复杂度平均为 O(1)，在大多数情况下非常高效。
内存占用：
std::map
通常比std::unordered_map
占用更多的内存，因为红黑树的节点需要额外的存储空间。std::unordered_map
的内存占用通常较低，但取决于哈希表的负载因子和键的分布。
有序性：
std::map
保持元素的有序性，可以在特定需求下提供按键值排序的功能。std::unordered_map
不保持元素的有序性，适用于不需要元素排序的情况。
哈希函数：
std::unordered_map
使用哈希函数来确定键的存储位置，因此需要正确选择和设计哈希函数以避免冲突。std::map
不需要哈希函数，因为它使用红黑树进行有序存储。
迭代顺序：
std::map
的迭代顺序与键的升序排列一致。std::unordered_map
的迭代顺序与哈希表的存储顺序无关。
复杂度：
std::map
的操作复杂度通常更稳定，不容易受到哈希冲突等因素的影响。std::unordered_map
的操作复杂度在平均情况下更低，但在某些情况下可能会变得不稳定。
如果需要有序性、对键的排序要求高，或者不太关心内存占用，可以选择 std::map
。如果需要快速的插入、删除和查找操作，并且不关心元素的顺序，可以选择 std::unordered_map
。
8、多线程访问map的冲突怎么解决？
互斥锁（Mutex）：最常见的方法是使用互斥锁来保护对
map
的访问。在每个线程访问map
之前，先获取互斥锁，然后在访问完成后释放锁。这确保了每次只有一个线程能够访问map
，从而防止竞态条件。这种方法虽然简单，但可能会引入性能开销，因为只有一个线程能够同时访问map
。读写锁（Read-Write Lock）：如果多个线程中有很多只是读取
map
而不修改它，可以使用读写锁。读写锁允许多个线程同时读取map
，但只允许一个线程写入map
。这可以提高多读少写场景的性能，减少了互斥锁带来的性能开销。使用线程安全容器：C++11标准引入了一些线程安全的容器，如
std::unordered_map
的线程安全版本std::unordered_map
、std::map
的线程安全版本std::shared_mutex
等。这些容器具有内置的并发控制，因此可以在多线程环境中直接使用而无需额外的锁。分段锁（Sharding）：如果
map
中的数据可以被合理地划分成多个分段，每个分段使用一个锁进行保护，不同分段的数据在不同的锁中操作，以减小锁的竞争范围，提高并发性能。无锁数据结构：一些高级技术，如无锁哈希表，可以在没有锁的情况下实现多线程安全的访问。这通常需要更复杂的编程和算法技巧，但可以提供更高的并发性能。
9、析构函数可以不是虚函数吗？
析构函数可以不是虚函数。虚析构函数通常用于处理基类指针指向派生类对象的情况，以确保在销毁对象时正确调用派生类的析构函数。这对于实现多态性非常重要。
虚析构函数通常在以下情况下使用：
当你打算通过基类指针删除派生类对象时，如果基类的析构函数不是虚函数，那么只会调用基类的析构函数，而不会调用派生类的析构函数。这可能导致派生类资源泄漏或不正确的析构行为。
当你使用动态分配的对象（通过
new
运算符创建的对象）时，删除对象时通常需要虚析构函数来确保正确释放资源。
class Base {public:Base() {}virtual ~Base() {} // 虚析构函数};class Derived : public Base {public:Derived() {}~Derived() {} // 派生类的析构函数};int main() {Base* ptr = new Derived;delete ptr; // 如果Base类的析构函数不是虚函数，则不会调用Derived类的析构函数return 0;}
如果Base
类的析构函数不是虚函数，删除ptr
时将不会调用Derived
类的析构函数，这可能导致资源泄漏。
使用多态性和基类指针时，通常建议将基类的析构函数声明为虚函数，以确保正确的析构行为。
10、数组和链表的区别是什么，各有什么应用场景？
经典老八股，大家可能已经非常熟悉了。。。
数组（Array）：
内存布局：数组是一种线性数据结构，其元素在内存中是连续存储的。数组的元素访问速度较快，因为可以通过索引直接访问。
大小固定：数组的大小在创建时固定，无法动态扩展或缩小。如果需要更多的存储空间，通常需要创建一个新的数组并复制数据。
插入和删除：在数组中插入或删除元素通常需要移动其他元素，因此可能比较慢，特别是在数组的中间插入或删除元素时。
适用场景：适用于元素数量固定且需要快速随机访问的情况，例如数组用于实现堆栈、队列、矩阵等。
链表（Linked List）：
内存布局：链表是一种非线性数据结构，其元素（节点）在内存中可以是分散存储的，每个节点包含数据和指向下一个节点的指针。
大小动态：链表的大小可以动态增长或减小，不需要预先分配固定大小的内存。
插入和删除：在链表中插入或删除元素通常非常高效，因为只需要调整节点的指针，而不需要移动大量数据。
元素访问较慢：链表的元素访问速度较慢，需要从头节点开始遍历链表，直到找到目标节点。
适用场景：适用于需要频繁插入和删除元素、元素数量不确定、或者需要动态分配内存的情况，例如实现链表、栈、队列等。
三面：
项目+八股+写题
1、写了一道链表的局部反转。
#include <iostream>struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}};// 反转链表的一部分，从位置 m 到 nListNode* reverseBetween(ListNode* head, int m, int n) {if (!head || m == n) {return head;}ListNode dummy(0);dummy.next = head;ListNode* prev = &dummy;// 移动到需要反转的起始位置for (int i = 1; i < m; ++i) {prev = prev->next;}// 反转局部区间ListNode* current = prev->next;for (int i = m; i < n; ++i) {ListNode* temp = current->next;current->next = temp->next;temp->next = prev->next;prev->next = temp;}return dummy.next;}// 打印链表void printList(ListNode* head) {ListNode* current = head;while (current) {std::cout << current->val << " -> ";current = current->next;}std::cout << "nullptr" << std::endl;}int main() {// 创建一个示例链表：1 -> 2 -> 3 -> 4 -> 5ListNode* head = new ListNode(1);head->next = new ListNode(2);head->next->next = new ListNode(3);head->next->next->next = new ListNode(4);head->next->next->next->next = new ListNode(5);std::cout << "原始链表：" << std::endl;printList(head);int m = 2; // 起始位置int n = 4; // 结束位置// 调用反转函数head = reverseBetween(head, m, n);std::cout << "反转后的链表：" << std::endl;printList(head);// 释放链表内存while (head) {ListNode* temp = head;head = head->next;delete temp;}return 0;}
结果输出：
2、写一个工厂模式的demo，不用运行。
#include <iostream>#include <memory>// 抽象产品类class Product {public:virtual void use() = 0;};// 具体产品类 Aclass ConcreteProductA : public Product {public:void use() override {std::cout << "使用具体产品 A" << std::endl;}};// 具体产品类 Bclass ConcreteProductB : public Product {public:void use() override {std::cout << "使用具体产品 B" << std::endl;}};// 工厂接口class Factory {public:virtual std::shared_ptr<Product> createProduct() = 0;};// 具体工厂类 A，用于创建产品 Aclass ConcreteFactoryA : public Factory {public:std::shared_ptr<Product> createProduct() override {return std::make_shared<ConcreteProductA>();}};// 具体工厂类 B，用于创建产品 Bclass ConcreteFactoryB : public Factory {public:std::shared_ptr<Product> createProduct() override {return std::make_shared<ConcreteProductB>();}};int main() {// 使用工厂创建产品 Astd::shared_ptr<Factory> factoryA = std::make_shared<ConcreteFactoryA>();std::shared_ptr<Product> productA = factoryA->createProduct();productA->use();// 使用工厂创建产品 Bstd::shared_ptr<Factory> factoryB = std::make_shared<ConcreteFactoryB>();std::shared_ptr<Product> productB = factoryB->createProduct();productB->use();return 0;}
结果输出：
3、设计模式了解吗，介绍一下熟悉的设计模式
上面只是将八股和算法进行了一些参考回答，还有具体的项目就不过多赘述了，相信大家写在简历上的项目都是经过深入思考的，也都能答的非常好！
看完记得点赞收藏哦~
