阿里C++研发二面面经
来源：https://www.nowcoder.com/feed/main/detail/b50e41ddd32941b8b7d41f25c64c4a4b
算法
1、给一棵树和一个sum，判断是否存在从root到叶子结点的path之和等于sum？
问题描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
思路
这里就写一个非递归的吧。
- 使用两个栈，一个栈用来存储当前节点，另一个栈用来存储当前节点到根节点的路径和。
- 从根节点开始，将根节点和其值加入到两个栈中。
- 然后进入一个循环，直到栈为空为止：
- 从当前节点栈中弹出一个节点，并从路径和栈中弹出对应的路径和。
- 如果该节点是叶子节点，并且路径和等于目标和，则返回
true。 - 否则，将当前节点的子节点和对应的路径和加入到两个栈中。
- 如果循环结束时仍未找到路径和等于目标和的叶子节点，则返回
false。
参考代码
c++
#include <iostream>
#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:
bool hasPathSum(TreeNode* root, int targetSum) {
if (!root) {
return false; // 如果根节点为空，直接返回 false
}
stack<TreeNode*> nodes; // 存储节点的栈
stack<int> sums; // 存储路径和的栈
nodes.push(root); // 将根节点入栈
sums.push(root->val); // 根节点的值作为初始路径和
while (!nodes.empty()) {
TreeNode* node = nodes.top(); // 取出栈顶节点
nodes.pop();
int sum = sums.top(); // 取出对应的路径和
sums.pop();
if (!node->left && !node->right && sum == targetSum) {
return true; // 如果当前节点是叶子节点，并且路径和等于目标和，返回 true
}
if (node->right) {
nodes.push(node->right); // 将右子节点入栈
sums.push(sum + node->right->val); // 更新路径和
}
if (node->left) {
nodes.push(node->left); // 将左子节点入栈
sums.push(sum + node->left->val); // 更新路径和
}
}
return false; // 循环结束仍未找到符合条件的节点，返回 false
}
};
// 打印结果的辅助函数
void printResult(bool result) {
cout << (result ? "true" : "false") << endl;
}
int main() {
// 创建示例二叉树
TreeNode* root = new TreeNode(5);
root->left = new TreeNode(4);
root->right = new TreeNode(8);
root->left->left = new TreeNode(11);
root->left->left->left = new TreeNode(7);
root->left->left->right = new TreeNode(2);
root->right->left = new TreeNode(13);
root->right->right = new TreeNode(4);
root->right->right->right = new TreeNode(1);
Solution solution;
cout << "Example 1: ";
printResult(solution.hasPathSum(root, 22)); // 输出 true
cout << "Example 2: ";
printResult(solution.hasPathSum(root, 5)); // 输出 false
cout << "Example 3: ";
printResult(solution.hasPathSum(nullptr, 0)); // 输出 false
return 0;
}2、LRU的实现（双向链表+哈希）？
问题描述
请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
思路
- 首先， 需要定义一个双向链表节点，用于存储键值对。这个节点包括键（key）和值（value），以及指向前一个节点（prev）和后一个节点（next）的指针。
- 需要维护一个哈希表（unordered_map），用于快速查找键对应的节点。哈希表的键是键（key），值是指向节点的指针。
- 双向链表的头部表示最近访问的节点，尾部表示最久未使用的节点。每次访问一个节点时， 需要将它移动到链表头部。
- 当插入一个新的键值对时，如果缓存已满， 需要移除链表尾部的节点，即最久未使用的节点，并从哈希表中删除它。
- 通过上述方法， 可以实现以下操作：
get(key)：如果键存在于缓存中，首先从哈希表中查找该键，然后将访问的节点移动到链表头部，并返回值；如果键不存在，返回-1。put(key, value)：如果键已存在，更新值并将节点移动到链表头部；如果键不存在，需要插入新的节点。如果缓存已满，需要移除最久未使用的节点，然后插入新节点到链表头部。
参考代码
C++
#include <unordered_map>
using namespace std;
class LRUCache {
public:
LRUCache(int capacity) {
capacity_ = capacity;
}
int get(int key) {
// 如果键存在于缓存中
if (cache_.find(key) != cache_.end()) {
// 将访问的节点移动到链表头部，表示最近访问
moveToFront(key);
return cache_[key]->value;
}
return -1; // 如果键不存在，返回-1
}
void put(int key, int value) {
// 如果键已存在，更新值并将节点移动到链表头部
if (cache_.find(key) != cache_.end()) {
cache_[key]->value = value;
moveToFront(key);
} else {
// 如果键不存在，需要插入新的节点
if (cache_.size() >= capacity_) {
// 如果缓存已满，需要移除最久未使用的节点
evictLast();
}
Node* newNode = new Node(key, value);
cache_[key] = newNode;
addToFront(newNode);
}
}
private:
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity_;
unordered_map<int, Node*> cache_;
Node* head_ = nullptr;
Node* tail_ = nullptr;
// 辅助函数：将节点移动到链表头部
void moveToFront(int key) {
Node* node = cache_[key];
if (node == head_) {
return;
}
if (node == tail_) {
tail_ = tail_->prev;
tail_->next = nullptr;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
node->next = head_;
head_->prev = node;
head_ = node;
}
// 辅助函数：将节点插入到链表头部
void addToFront(Node* node) {
if (!head_) {
head_ = tail_ = node;
} else {
node->next = head_;
head_->prev = node;
head_ = node;
}
}
// 辅助函数：移除链表尾部的节点
void evictLast() {
int key = tail_->key;
cache_.erase(key);
if (head_ == tail_) {
delete tail_;
head_ = tail_ = nullptr;
} else {
Node* newTail = tail_->prev;
newTail->next = nullptr;
delete tail_;
tail_ = newTail;
}
}
};八股
1、上面LRU在多线程时存在什么问题？如何解决？用锁来解决，如何提高效率？举个例子：os里的pagecache页面换入换出，多线程下如何提高效率？
存在的问题：
- 线程不安全：LRUCache类的成员函数get和put在多线程环境下可能会导致数据竞争和不一致性，因为多个线程可能同时访问和修改LRUCache对象的内部状态。
- 数据竞争：多个线程同时访问和修改LRUCache对象的cache_、head_、tail_等成员变量，可能导致数据竞争和未定义行为。
解决办法：
- 在LRUCache类中添加一个互斥锁成员变量，用于保护LRUCache对象的访问和修改。
- 在LRUCache类的成员函数中，使用互斥锁对LRUCache对象的访问和修改进行加锁和解锁操作，确保在任意时刻只有一个线程可以访问和修改LRUCache对象。
- 在对LRUCache对象进行访问和修改的地方使用互斥锁进行保护，包括对cache_、head_、tail_等成员变量的访问和修改。
提高效率的办法：
- 细粒度锁：尽量使用细粒度的锁，即只锁定必要的数据，而不是对整个数据结构进行加锁。这样可以减小锁的粒度，提高并发访问性能。
- 读写锁：针对读多写少的场景，可以考虑使用读写锁（Read-Write Lock），读操作可以并发进行，写操作需要独占锁。这样可以提高读操作的并发性能。
- 无锁数据结构：对于一些高并发的场景，可以考虑使用无锁数据结构（Lock-Free Data Structures）或者无锁算法（Lock-Free Algorithms）。这些数据结构和算法不依赖锁来实现并发访问，通过原子操作等机制来确保并发访问的正确性，可以提高并发性能。
- 锁粒度控制：在并发访问时，需要根据实际情况控制锁的粒度，避免过度加锁导致性能下降。可以通过对代码进行分析和优化，减少锁的持有时间，提高并发性能。
- 合理的并发控制：对于一些共享资源，可以通过合理的并发控制机制来限制并发访问的数量，避免过多的线程竞争导致性能下降。
- 缓存优化：对于一些计算密集型的任务，可以考虑使用缓存来减少计算量，提高性能。通过缓存的方式，可以避免重复计算，提高并发访问的效率。
2、C++的内存泄漏以及解决办法？
内存泄漏是指程序在动态分配内存后，由于某种原因未能释放该内存，导致程序在运行过程中持续占用内存，直到程序结束才释放，这样的内存泄漏会导致系统资源浪费和程序性能下降。
C++中的内存泄漏主要发生在动态内存分配的情况下，常见的情形包括使用new操作符分配内存但未使用delete释放，或者使用new[]分配数组内存但未使用delete[]释放。
一些常见的导致内存泄漏的情况以及解决办法：
忘记释放动态分配的内存：
c++// 内存泄漏示例 int* ptr = new int; // 忘记释放内存解决办法：使用
delete释放内存c++delete ptr;使用
new[]分配数组内存后，忘记使用delete[]释放：c++// 内存泄漏示例 int* arr = new int[10]; // 忘记释放内存解决办法：使用
delete[]释放数组内存c++delete[] arr;异常导致内存泄漏： 在C++中，如果在动态分配内存后发生了异常，可能会导致内存泄漏，因为异常发生时无法执行到释放内存的代码。 解决办法：使用RAII（资源获取即初始化）技术，利用对象的析构函数来释放资源，确保资源在任何情况下都能被正确释放。
内存分配与释放不匹配： 在C++中，使用
new分配内存后，应该使用delete释放，使用new[]分配数组内存后，应该使用delete[]释放。如果分配和释放不匹配，可能导致内存泄漏。 解决办法：确保每次分配内存后都能正确释放，严格匹配new和delete、new[]和delete[]。
3、Reactor模型的理解？
核心思想： Reactor模型的核心思想是将IO事件处理分离出来，使得程序能够通过事件驱动的方式处理IO操作。这种模型的主要目标是提高系统的并发性能和可伸缩性。
工作流程：
- 事件注册： 程序通过系统调用（如
epoll、select等）向操作系统注册感兴趣的事件（如读就绪、写就绪等）以及对应的回调函数（事件处理器）。 - 事件循环： 程序进入一个事件循环（通常是一个无限循环），不断地向操作系统询问是否有已注册的事件就绪。
- 事件分发： 当有事件就绪时，操作系统会通知程序，程序会根据事件类型调用对应的事件处理器进行处理。
- 事件处理： 事件处理器会执行相应的业务逻辑，可能包括读取数据、写入数据、连接处理等操作。
- 事件驱动： 在处理完一个事件后，程序会继续等待下一个事件的到来，整个过程是事件驱动的。
特点：
- 事件驱动： 所有的IO操作都是由事件触发的，程序不需要主动去轮询IO状态，这样可以减少系统资源的浪费。
- 非阻塞IO： 在Reactor模型中，通常使用非阻塞IO来处理事件，可以提高系统的并发性能。
- 事件处理器： Reactor模型通过事件处理器来处理不同类型的事件，使得程序结构清晰，易于扩展和维护。
- 适用性广泛： Reactor模型适用于各种类型的IO操作，如网络通信、文件IO等。
4、磁盘IO？什么情况下会发生磁盘IO？
磁盘I/O（Input/Output）指的是计算机系统与磁盘进行数据交换的过程。磁盘I/O通常涉及读取和写入磁盘上的数据，用于存储和检索文件、程序等信息。
- 文件读取： 当应用程序需要访问磁盘上的文件时，会发起文件读取的磁盘I/O操作。例如，打开一个文件、读取文件内容等都会触发磁盘I/O。
- 文件写入： 当应用程序需要向磁盘上的文件写入数据时，会发起文件写入的磁盘I/O操作。例如，向文件中写入新数据、修改文件内容等都会触发磁盘I/O。
- 虚拟内存交换： 当系统的物理内存不足以容纳当前运行的所有进程和数据时，操作系统会使用磁盘作为虚拟内存的交换空间。在内存页被交换到磁盘或从磁盘交换回内存时，会发生磁盘I/O。
- 系统启动和关闭： 在计算机启动或关闭时，会涉及到读取和写入系统配置信息、日志文件等操作，这些都会触发磁盘I/O。
- 数据库操作： 数据库系统经常需要读取和写入大量的数据到磁盘上的数据库文件中，因此数据库操作通常会频繁地触发磁盘I/O。
5、Direct IO？
Direct IO（直接I/O）是一种绕过操作系统缓存（页缓存）直接访问磁盘的I/O方式。在使用Direct IO时，数据直接从应用程序的内存缓冲区（用户空间）直接读取到磁盘或者从磁盘直接写入到应用程序的内存缓冲区，而不经过操作系统的页缓存。这种方式可以避免数据在用户空间和内核空间之间的复制，从而提高I/O操作的效率和响应速度。
Direct IO的主要特点包括：
- 绕过页缓存： 使用Direct IO时，数据直接在应用程序的用户空间和磁盘之间传输，不经过操作系统的页缓存。这意味着每次I/O操作都需要直接访问磁盘，而不会利用操作系统的缓存机制。
- 减少数据复制： 由于Direct IO避免了数据在用户空间和内核空间之间的复制，因此可以减少数据复制的开销，提高I/O操作的效率。
- 适用于大量数据的读写： Direct IO适用于需要大量数据读写的场景，例如数据库系统、文件服务器等，这些场景需要高效地处理大量数据而不受到操作系统缓存的影响。
- 需要特权权限： 由于Direct IO绕过了操作系统的缓存，因此通常需要特权权限（如root权限）才能够使用。这是因为直接访问磁盘可能会绕过操作系统的权限控制，存在一定的安全风险。
- 适用性限制： Direct IO并不适用于所有场景，它通常在对I/O性能要求较高、需要绕过操作系统缓存、对数据一致性要求较高的场景下使用。在一些需要利用操作系统缓存提高性能的场景下，Direct IO并不适用。
6、buffer read？
"Buffered read"（缓冲读取）是一种通过在内存中设置缓冲区来提高读取操作效率的技术。在进行文件或数据读取时，通常会涉及到频繁的I/O操作，而这些操作可能会对性能产生一定的影响。通过使用缓冲读取，可以减少实际的I/O操作次数，从而提高读取的效率。
缓冲读取的工作原理如下：
- 设置缓冲区： 在进行读取操作之前，先在内存中分配一块缓冲区，用于临时存储从文件或数据源中读取的数据。
- 批量读取： 通过适当的缓冲区大小设置，可以实现批量读取的操作。即使是需要读取大量数据的情况下，也可以将数据分批次读取到缓冲区中，减少了对磁盘的频繁访问，提高了读取效率。
- 减少系统调用： 缓冲读取可以减少系统调用的次数。在没有缓冲的情况下，每次读取都会导致系统调用，而使用缓冲读取可以将多个读取操作合并为一次系统调用，减少了系统调用的开销。
- 顺序读取优化： 缓冲读取可以优化顺序读取的性能。当进行顺序读取时，缓冲读取可以预先读取一定量的数据到缓冲区中，以便后续的读取操作能够直接从缓冲区中获取数据，而不需要再次访问磁盘。
7、有两个文件，key文件和record文件，key文件2G，record文件很大无法读入内存，如何做到随机访问记录？
由于record文件很大无法一次性读入内存，我们可以通过索引的方式实现随机访问记录。
具体步骤：
- 创建索引文件： 首先，我们可以针对record文件创建一个索引文件，索引文件中存储着每个记录在record文件中的位置信息（偏移量）。这样，我们就可以通过索引文件快速定位到某个记录在record文件中的位置。
- 索引结构设计： 索引文件的结构可以根据实际需求设计，常见的索引结构包括哈希表、B树、B+树等。选择合适的索引结构可以提高随机访问的效率。
- 读取记录： 当需要随机访问某个记录时，我们首先根据索引文件找到对应记录在record文件中的位置（偏移量），然后通过文件随机访问的方式读取该记录。由于索引文件通常较小且能够加载到内存中，因此可以快速定位到记录在record文件中的位置，实现随机访问。
- 更新索引： 如果record文件中的记录发生变化（新增、删除、修改等操作），需要同步更新索引文件，保持索引与record文件的一致性。
- 性能考虑： 在设计索引时需要考虑性能因素，如索引文件的大小、索引结构的选择、索引文件的存储方式（如内存缓存、磁盘存储）、索引的更新频率等，以提高随机访问记录的效率和性能。
8、动态链接库和静态链接库？
在C/C++中，库（Library）是一组预先编译好的函数和数据，可以被其他程序调用和重用。在使用库时，可以通过链接的方式将其包含到可执行文件中。
静态链接库：
- 静态链接库是编译时链接的一种形式，它是一组预先编译好的目标文件的集合，这些目标文件中包含了函数和数据的定义。
- 静态链接库的文件通常以
.lib（Windows）或.a（Unix/Linux）为扩展名。 - 在编译可执行文件时，静态链接库中的目标文件会被直接复制到最终的可执行文件中，因此可执行文件会变得较大。
- 静态链接库在程序运行时不需要外部的依赖，因为所有的代码和数据都已经被链接到可执行文件中。
动态链接库：
- 动态链接库是一种在程序运行时链接的方式，它在程序运行时才被加载到内存中。
- 动态链接库的文件通常以
.dll（Windows）或.so（Unix/Linux）为扩展名。 - 在编译可执行文件时，只会包含动态链接库的引用信息，而不会包含库的实际内容。
- 在程序运行时，操作系统会根据需要加载动态链接库，并将其中的函数和数据映射到程序的内存空间中，因此可执行文件相对较小。
- 动态链接库可以被多个程序共享使用，节省了系统资源，但需要确保动态链接库的兼容性和可用性。
区别与选择：
- 静态链接库在程序编译时会将库的代码和数据全部复制到可执行文件中，因此可执行文件比较大，但不需要外部依赖，方便程序的分发和部署。
- 动态链接库在程序运行时加载，可执行文件相对较小，但需要确保系统中存在所需的动态链接库，方便库的更新和维护。
9、倒排索引你了解吗？
倒排索引（Inverted Index）是信息检索领域常用的数据结构，用于快速查找包含特定关键词的文档或记录。它常用于搜索引擎、数据库系统等需要快速检索文档的场景中。
倒排索引的结构：
- 倒排索引由一系列的索引项（Inverted Index Entry）组成，每个索引项对应一个关键词（Term）和包含该关键词的文档列表。
- 对于每个关键词，倒排索引会记录包含该关键词的文档或记录的信息，如文档的标识符、出现位置等。
构建倒排索引的过程：
- 文档预处理：对每个文档进行分词和处理，将文档转换为关键词序列。
- 建立索引：遍历所有文档的关键词序列，对每个关键词建立倒排索引。
- 索引存储：将建立好的倒排索引存储在索引文件或数据库中，以便后续的检索使用。
倒排索引的优势：
- 快速检索：倒排索引可以快速定位包含特定关键词的文档或记录，加快了信息检索的速度。
- 索引压缩：倒排索引可以通过压缩技术减小索引的存储空间，提高了存储效率。
应用场景：
- 搜索引擎：用于搜索引擎的文档检索，可以快速找到包含用户查询关键词的网页或文档。
- 数据库系统：用于数据库系统中的全文检索，可以加速对包含特定关键词的记录的查询。
项目
略