lc113
class Solution {
vector<vector<int>> ret;
vector<int> path;
int sum = 0;
int targetSum = 0;
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum)
{
this->targetSum = targetSum;
dfs(root);
return ret;
}
void dfs(TreeNode* node)
{
if (!node) return;
sum += node->val;//前序
path.push_back(node->val);
// 只有叶子节点才判断是否满足条件
if (!node->left && !node->right && sum == this->targetSum) {
ret.push_back(path);
}
// 剪枝优化：如果左子树存在才继续递归
if (node->left) {
dfs(node->left);
path.pop_back(); //回溯
sum -= node->left->val;
}
// 如果右子树存在才继续递归
if (node->right) {
dfs(node->right);
path.pop_back();
sum -= node->right->val;
}
}
};
一
1 进程/线程
1.1 概念/区别
- 进程：是程序的一次执行过程，是系统资源分配的基本单位，拥有独立的地址空间等资源。
- 线程：是进程内的一个执行单元，是CPU调度的基本单位，共享进程的资源。
区别在于进程资源独立，切换开销大；线程共享资源，切换开销小。
1.2 什么样的情况考虑多线程/多进程
- 多进程：适用于程序间需要隔离（如不同应用程序）、充分利用多核CPU且任务间耦合度低的场景，比如服务器上多个独立服务运行。
- 多线程：适用于进程内任务可并发、任务间需要共享数据且通信频繁的场景，像图形界面程序中UI更新和后台数据处理同时进行。
1.3 考虑到数据量和实际应用场景
数据量大且任务可拆分时，多进程可利用多CPU分散处理大数据分块；
多线程适合数据需频繁共享、交互，且单进程内可并发处理不同数据操作的场景，比如大数据处理中部分数据预处理用多线程，整体不同任务用多进程。
2 MySQL
2.1 索引底层实现
MySQL中索引底层常用B + 树实现
B + 树是一种多路平衡查找树，非叶子节点存索引键
叶子节点存数据（聚簇索引）或指向数据的指针（非聚簇索引），通过树的结构快速定位数据。
2.2 为什么使用B + 树而不是B树，用B + 树有什么优势
- B树每个节点都存数据，导致查询时可能在非叶子节点就停止，而B + 树只有叶子节点存数据，且叶子节点间有链表连接。
- 优势：
查询更稳定（每次都要到叶子节点）；
范围查询效率高（可通过叶子节点链表快速遍历）；
磁盘IO次数少（非叶子节点存更多索引键，树更矮）。
3 new/delete malloc的区别
- new / delete ：是C++的操作符， new 会调用构造函数初始化对象， delete 会调用析构函数清理资源，类型安全，直接操作对象。
- malloc / free ：是C的函数， malloc 只分配内存，不初始化对象，返回 void* 需强转， free 只释放内存，不处理对象的构造和析构。
4 C++的多态
4.1 实现/条件
- 实现：通过虚函数实现。
- 条件：要有继承关系；子类要重写父类的虚函数；通过父类指针或引用调用虚函数。
4.2 重载和重写
- 重载：同一作用域内，函数名相同，参数列表（个数、类型、顺序）不同，与返回值无关，是静态多态（编译时确定）。
- 重写：子类对父类虚函数的重新定义，函数名、参数列表、返回值（协变情况除外）都相同，是动态多态（运行时确定）。
5 缓存击穿/缓存雪崩
- 缓存击穿：指一个热点缓存key突然失效，大量请求直接打到数据库，导致数据库压力骤增。
- 缓存雪崩：指大量缓存key在同一时间失效，或者缓存服务宕机，导致所有请求都涌向数据库，数据库可能被压垮。
6 场景题
这部分属于项目经验交流。涉及算法时，要讲清楚算法在项目中解决的问题（如数据处理效率、业务逻辑实现等）
具体实现思路（结合所用语言和技术栈）；
沟通问题时，要说明遇到的问题类型（如需求理解偏差、进度协调等）
如何与甲方有效沟通解决（如明确需求文档、定期汇报等）
二
1. 算法题：判断链表交叉点；为类实现拷贝赋值函数；船载人最少船数问题。
2. 项目相关：
RTSP流媒体服务器项目（RTSP协议作用、工作流程、请求响应格式；epoll使用原因、水平/边缘触发选择及原因；RTSP概念）；
CMU15445中并发B + 树实现（并发做法、悲观锁和乐观锁原理，与MySQL中锁概念是否一致；是否手写、参考代码情况；B + 树实现难点；数据库宕机内存数据未写入硬盘的恢复）；
数据库相关（索引、事务、隔离级别；锁依赖图构建、死锁检测及实现难度）；
Redis和MySQL（Redis认知及使用情况）；
Linux相关（基本命令；多线程和多进程区别、优缺点、应用场景，多线程是否可取代多进程；IPC方式）；
操作系统项目（fork流程、COW实现；虚拟内存作用及使用原因；malloc实现）；
分布式与一致性（mit6.824相关内容）。
回答问题
算法题
- 判断链表交叉点：
可使用双指针法。设两个指针 p1 、 p2 分别从两个链表头出发，相遇时若在交叉点前，继续走；
若走到链表尾，就从另一个链表头开始走，最终会在交叉点相遇。
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode* a=headA;
ListNode* b=headB;
while(a!=b)
{
a=a==nullptr?headB:a->next;
b=b==nullptr?headA:b->next;
}
return a;
}
};
- 为类实现拷贝赋值函数：
要考虑深拷贝，避免浅拷贝导致的内存问题。
先释放当前对象已有的资源，再为新资源分配内存并复制值，同时处理自赋值情况（如 if (this == &other) return *this; ）。
- 船载人最少船数问题：
先对人员重量排序，用双指针，左指针指向最轻的，右指针指向最重的。若左右指针重量和≤ limit ，则两人同乘一船，左右指针都移动；否则重的人单独一船，右指针左移。统计船数。
项目与技术问题
- RTSP相关
- 作用：
用于控制流媒体会话，如播放、暂停、录制等。
- 工作流程：
包括建立连接、媒体协商、播放控制、会话终止等阶段，通过请求和响应交互。
- 请求响应格式：
请求有方法（如 DESCRIBE 、 PLAY ）、URI等；响应包含状态码和相关描述信息。
- epoll使用原因：
相比 select 、 poll ， epoll 没有文件描述符数量限制，且采用事件驱动，效率更高，适合高并发场景。
- 水平/边缘触发：
若希望及时处理所有就绪事件，可选择水平触发；
若要精准控制事件处理时机，边缘触发更合适。需结合RTSP服务器的IO处理需求，比如若需确保每个就绪事件都被处理，水平触发更稳妥。
- RTSP概念：实时流传输协议，是应用层协议，用于在客户端和服务器之间建立、控制和终止实时流媒体会话。
- 并发B + 树
- 并发做法：可通过锁（悲观锁、乐观锁）来控制并发访问，确保数据一致性。
- 悲观锁和乐观锁原理：悲观锁假设会发生冲突，操作前先加锁；乐观锁假设不会冲突，操作时检查版本号或时间戳等，冲突则回滚。与MySQL中概念一致，都是解决并发冲突的机制。
- B + 树实现难点：并发时的锁竞争、数据分裂与合并时的同步问题，需保证操作的原子性和一致性。
- 数据库宕机恢复：利用事务日志（如WAL），宕机后通过日志重做未持久化的操作，保证数据一致性。
- 数据库相关
- 索引：加速数据查询，MySQL中常用B + 树索引，通过树结构快速定位数据。
- 事务：是一组原子性的操作，具有ACID（原子性、一致性、隔离性、持久性）特性。
- 隔离级别：有读未提交、读提交、可重复读、串行化，用于控制事务间的隔离程度，解决脏读、不可重复读、幻读等问题。
- 锁依赖图与死锁检测：锁依赖图中节点是事务，边是锁依赖关系。死锁检测通过查找图中的环来确定，实现难度在于动态维护依赖图和高效检测环，尤其是在高并发场景下。
- Redis和MySQL：Redis是内存数据库，常用作缓存，也可做数据存储，支持多种数据结构；MySQL是关系型数据库，用于持久化存储结构化数据，两者常配合使用（如Redis缓存减轻MySQL压力）。
- Linux与进程线程
- 基本命令：如 ls （列目录）、 cd （切换目录）、 ps （查看进程）、 top （系统监控）等。
- 多线程和多进程区别、优缺点、应用场景
- 区别：进程是资源分配单位，有独立地址空间；线程是调度单位，共享进程资源。
- 优缺点：进程隔离性好，但切换开销大；线程切换开销小，但共享资源易引发同步问题。
- 应用场景：多进程适合程序间隔离（如不同服务）；多线程适合进程内并发且共享数据（如UI与后台逻辑）。
- 多线程是否可取代多进程：不能。多进程的隔离性是多线程无法替代的，某些场景（如需要强隔离、利用多CPU核心且任务独立）必须用多进程。
- IPC方式：包括管道（ pipe ）、消息队列、共享内存、信号量、套接字（ socket ）、信号（ kill 相关）等。
- 操作系统项目
- fork流程：父进程调用 fork 后，内核为子进程创建进程控制块等结构，复制父进程地址空间等资源，然后子进程从 fork 返回0，父进程返回子进程PID。
- COW（写时复制）： fork时子进程与父进程共享内存页，当其中一方要修改内存时，才复制该页，避免不必要的内存复制，节省资源。
- 虚拟内存作用及原因：作用是扩展进程地址空间、实现内存保护和共享。
使用原因是解决物理内存不足，为进程提供统一的内存视图，便于内存管理
- malloc实现（以tcmalloc为例）：采用线程缓存（Thread - Cache）、中心缓存（Central Cache）和页堆（PageHeap）分层结构。
线程缓存供线程快速分配小内存；中心缓存协调不同线程缓存，避免内存碎片；页堆管理大内存页，提升大内存分配效率。
- 分布式与一致性：mit6.824课程涉及分布式系统设计，如分布式一致性算法（Paxos、Raft等），用于解决分布式环境下多副本数据的一致性问题，确保多个节点数据一致
三
1. 网络协议：TCP三次握手、四次挥手；
断点续传实现；
HTTP/2.0与HTTP/1.0差别。
2. C++特性：多态（虚函数工作原理、调用确定）；C++20新特性；智能指针（使用场景、环形引用及解决、 weak_ptr 使用场景、引用计数器形式、 shared_ptr 线程安全、 weak_ptr 计数与空间分配）。
3. 数据库：InnoDB与MyISAM索引区别。
4. 中间件：Redis用作消息队列相关。
5. 并发编程：进程、线程、协程区别。
6. 算法编程：分割字符串为回文子串的所有可能方案
回答问题
网络协议
- TCP三次握手：
- 第一次：客户端发 SYN 包，发起连接请求。
- 第二次：服务端回 SYN + ACK 包，确认客户端请求并发起连接。
- 第三次：客户端回 ACK 包，确认服务端请求，连接建立。
- TCP四次挥手：
- 第一次：客户端发 FIN 包，请求断开连接。
- 第二次：服务端回 ACK 包，确认客户端断开请求。
- 第三次：服务端发 FIN 包，请求断开连接。
- 第四次：客户端回 ACK 包，确认服务端断开请求，连接断开。
- 断点续传实现：利用HTTP的 Range 请求头，客户端记录已下载部分的字节范围，下次请求时带上 Range: bytes=已下载字节 - ，服务端根据该范围返回剩余数据，客户端续接写入。
- HTTP/2.0与HTTP/1.0差别：HTTP/2.0支持二进制帧、多路复用（同一连接并发传输多个请求/响应）、头部压缩等，性能更优；HTTP/1.0是文本协议，无这些特性，且每次请求需建立新连接（或复用困难）。
C++特性
- 多态与虚函数：
- 多态通过虚函数实现，类有虚函数时会生成虚函数表（ vtable ），对象包含虚函数表指针（ vptr ）。调用虚函数时，通过 vptr 找到 vtable ，再根据函数在表中的索引调用对应函数，运行时确定调用的是子类还是父类虚函数。
- C++20新特性：
概念（ concepts ）用于约束模板参数；
范围（ ranges ）简化区间操作；
协程（ coroutines ）支持更简洁的异步编程等。
- 智能指针
- 使用场景：
shared_ptr 用于多对象共享资源，自动引用计数管理生命周期；
unique_ptr 用于独占资源，转移所有权而非复制。
- 环形引用及解决：两个 shared_ptr 相互引用形成环，导致内存泄漏。用 weak_ptr （弱引用，不增加引用计数）配合 shared_ptr ，打破循环。
- weak_ptr 其他场景：获取被 shared_ptr 管理对象的临时访问权，且不影响其生命周期；观察对象是否存在（通过 lock() 方法）。
- 引用计数器形式：通常是和管理对象一起分配的整型变量， shared_ptr 通过增减该计数器管理对象生命周期。
- shared_ptr 线程安全：其引用计数操作是线程安全的，但对指向对象的访问不是，需额外同步。
- weak_ptr 计数与空间： weak_ptr 不影响 shared_ptr 的引用计数，但有自己的弱引用计数，用于跟踪 shared_ptr 的存在。空间与 shared_ptr 的控制块一起分配。
数据库
InnoDB与MyISAM索引区别：
- InnoDB索引是聚簇索引，数据存于索引叶子节点，辅助索引指向聚簇索引；支持事务、行级锁。
- MyISAM索引是非聚簇索引，索引和数据分开存储，辅助索引直接指向数据文件；不支持事务，表级锁。
中间件
Redis用作消息队列：可通过 list （ lpush 入队， rpop 出队）、 pub/sub （发布 - 订阅）、 Stream （更完善的消息队列功能，支持消费组等）实现消息队列，适用于轻量级、低延迟的消息传递场景。
并发编程
进程、线程、协程区别：
- 进程：资源分配基本单位，独立地址空间，切换开销大。
- 线程：CPU调度基本单位，共享进程资源，切换开销小。
- 协程：用户态轻量级线程，由程序调度，切换开销极小，适合高并发、IO密集型场景。
算法编程
分割回文子串：用回溯法。定义函数判断子串是否为回文，再递归分割，收集所有符合条件的分割方案。
#include <vector>
#include <string>
using namespace std;
bool isPalindrome(const string& s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
start++;
end--;
}
return true;
}
void backtrack(vector<vector<string>>& result, vector<string>& path, const string& s, int start) {
if (start == s.size()) {
result.push_back(path);
return;
}
for (int end = start; end < s.size(); end++) {
if (isPalindrome(s, start, end)) {
path.push_back(s.substr(start, end - start + 1));
backtrack(result, path, s, end + 1);
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> path;
backtrack(result, path, s, 0);
return result;
}
总结
这些问题覆盖网络、C++、数据库、中间件、并发、算法等多领域，是技术面试常见考点。需扎实掌握各领域基础概念与原理，同时提升算法实践能力，才能更好应对面试。