腾讯地图一面

https://www.nowcoder.com/feed/main/detail/e97af3df47fc4340b50e95cf43335182

1、进程和线程的区别？

定义

进程：进程是操作系统分配资源的基本单位，是一个正在执行的程序实例。每个进程都有独立的内存空间和系统资源，比如CPU时间、文件句柄等。

线程：线程是进程内部的一个执行单元，是CPU调度的基本单位。一个进程可以包含多个线程，线程共享进程的内存和资源。

资源分配

进程：每个进程拥有独立的地址空间和资源，进程之间相互隔离，一个进程崩溃通常不会直接影响其他进程。

线程：线程属于某个进程，共享进程的内存、文件和状态。线程之间的通信和数据共享更方便，但一个线程出错（如死循环或崩溃）可能影响整个进程。

创建和开销

进程：创建进程需要分配独立的内存和资源，开销较大，上下文切换（从一个进程切换到另一个）成本较高。

线程：创建线程的开销较小，因为它不需要独立的资源分配，上下文切换也更快。

并发性

进程：多进程可以充分利用多核CPU，因为进程间是完全独立的，适合需要高隔离性的任务。

线程：多线程适合I/O密集型或需要共享数据的任务，但在单核CPU上线程是并发执行（时间片轮转），多核CPU上可以并行执行。

通信

进程：进程间通信（IPC）需要特殊机制，如管道、消息队列、共享内存等，相对复杂。

线程：线程间通信简单，可以直接访问共享变量或数据结构，但需要同步机制（如锁）来避免竞争条件。

例子

进程：运行一个浏览器和一个音乐播放器，它们是两个独立进程。

线程：浏览器中打开多个标签页，每个标签页可能由一个线程处理，共享浏览器的内存。

2、select和epoll的区别？

基本概念

select：

select 是一种较早的 I/O 多路复用机制，最初由 BSD Unix 引入，广泛支持于各种操作系统。
它通过轮询一组文件描述符，检查哪些描述符上有 I/O 事件发生。
使用一个 fd_set 结构（文件描述符集合）来表示需要监听的描述符。

epoll：

epoll 是 Linux 内核引入的一种高效 I/O 多路复用机制（Linux 2.5.44 内核开始支持），旨在解决 select 和 poll 的性能瓶颈。
它基于事件驱动，提供更高的性能，尤其在高并发场景下。

工作机制

select：

调用 select() 函数时，传入需要监听的文件描述符集合（读、写、异常三种集合）。
内核会扫描这些描述符，检查是否有事件发生，返回就绪的描述符数量。
用户态需要遍历整个集合，找出具体哪些描述符就绪。
每次调用后，fd_set 会被修改，因此需要重新设置监听集合。

epoll：

使用三个函数：epoll_create 创建事件表，epoll_ctl 注册/修改/删除监听的事件，epoll_wait 等待事件发生。
内核维护一个事件表，当文件描述符状态改变时（如可读或可写），内核通过回调机制将就绪的事件加入队列。
epoll_wait 返回时，直接提供就绪的事件列表，用户无需扫描整个集合。

性能差异

文件描述符数量限制：

select：受限于 FD_SETSIZE（通常是 1024 或 2048，取决于系统），监听的文件描述符数量有硬性上限。
epoll：无固定上限（仅受内存限制），可以轻松处理数千甚至数十万连接。

时间复杂度：

select：内核每次扫描所有传入的文件描述符，时间复杂度为 O(n)，n 是描述符总数。
epoll：基于事件通知，只有就绪的描述符会被返回，时间复杂度接近 O(1)。

上下文切换和数据拷贝：

select：每次调用需要将 fd_set 从用户态拷贝到内核态，返回时再拷贝回来，开销随描述符数量增加而线性增长。
epoll：事件表在内核中维护，注册一次后无需重复拷贝，只有就绪事件返回用户态，开销低。

事件触发模式

select：

只支持水平触发：只要文件描述符上有未处理的事件，select 就会反复报告。
开发者需要确保处理完事件，否则可能导致忙等待。

epoll：

支持水平触发（LT）和边缘触发（ET）：
- LT：类似 select，只要状态未处理就持续通知。
- ET：仅在状态发生变化时通知一次（例如从不可读变为可读），效率更高，但要求开发者一次性处理完数据，否则可能丢失事件。
ET 模式更适合高性能场景，但编程复杂度稍高。

3、epoll的两种模式，描述一下？

水平触发（LT）

定义

水平触发是 epoll 的默认模式。只要某个文件描述符上的事件（例如可读、可写）处于“就绪”状态，且未被完全处理，epoll_wait 就会持续返回该事件。
类似于“状态检查”：只要条件满足（例如缓冲区有数据可读），就会一直触发通知，直到条件不再满足。

工作机制

当文件描述符的状态满足监听条件时（例如 socket 接收到数据），epoll_wait 返回该描述符。
如果用户程序只处理了部分数据（例如缓冲区还有剩余数据未读），下次调用 epoll_wait 时，该描述符仍会被返回。
只有当事件被完全处理（例如缓冲区被读空）或事件条件不再满足时，epoll_wait 才会停止报告该描述符。

代码示例

c++

struct epoll_event ev, events[10];
int epfd = epoll_create(1);
ev.events = EPOLLIN; // 默认 LT 模式，监听可读事件
ev.data.fd = fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev);

int n = epoll_wait(epfd, events, 10, -1);
for (int i = 0; i < n; i++) {
    if (events[i].events & EPOLLIN) {
        char buf[1024];
        int len = read(events[i].data.fd, buf, sizeof(buf)); // 只读部分数据
        // 如果缓冲区仍有数据未读，下次 epoll_wait 仍会返回该 fd
    }
}

边缘触发（ET）

定义

边缘触发是一种高效模式，仅在文件描述符的状态发生变化时（例如从不可读变为可读）触发一次通知。之后即使事件未被完全处理，epoll_wait 也不会再次返回该事件，除非状态再次发生变化。
类似于“事件通知”：只关心状态的边沿变化（从无到有或从有到无），而不是持续状态。

工作机制

当文件描述符的状态发生变化（例如 socket 接收到新数据），epoll_wait 返回该描述符。
如果用户程序未完全处理数据（例如缓冲区还有数据未读），epoll_wait 不会再次返回该描述符，除非有新的数据到达或状态再次改变。
要求用户程序在事件触发时一次性处理完所有数据，否则可能错过后续事件。

代码示例

c++

struct epoll_event ev, events[10];
int epfd = epoll_create(1);
ev.events = EPOLLIN | EPOLLET; // 设置 ET 模式，监听可读事件
ev.data.fd = fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev);

int n = epoll_wait(epfd, events, 10, -1);
for (int i = 0; i < n; i++) {
    if (events[i].events & EPOLLIN) {
        char buf[1024];
        while (1) { // 必须循环读取直到无数据
            int len = read(events[i].data.fd, buf, sizeof(buf));
            if (len <= 0) break; // 读完或出错退出
            // 处理数据
        }
    }
}

LT vs ET

特性	水平触发 (LT)	边缘触发 (ET)
触发时机	只要状态满足条件就持续通知	仅在状态变化时通知一次
通知次数	可能多次（未处理完则重复）	仅一次（除非状态再次变化）
处理要求	可部分处理，剩余数据下次通知	必须一次性处理完所有数据
编程复杂度	简单，容错性高	复杂，需要非阻塞 I/O 和循环
性能	较低（可能重复通知）	高（减少不必要通知）
典型应用	小型应用、简单逻辑	高并发服务器、大规模连接

4、上下文切换？

上下文切换是指 CPU 从执行一个任务（进程或线程）切换到另一个任务时，需要保存当前任务的执行状态（上下文），然后加载新任务的上下文，以便 CPU 能够继续执行新任务。

上下文（Context）

指的是一个任务在 CPU 上运行时的状态，包括：

寄存器内容（如程序计数器 PC、栈指针 SP、通用寄存器等）。
程序的内存状态（内存页表、堆栈等）。
CPU 的状态（如标志位）。
对于线程，还包括线程特定的堆栈和寄存器值。

为什么要上下文切换？

操作系统需要实现多任务并发（例如运行浏览器、音乐播放器等）。
响应中断（例如 I/O 事件、定时器）。
调度更高优先级的任务。

上下文切换的过程

触发切换
- 由中断（硬件中断如定时器、I/O 完成）、系统调用（如 sleep）或调度器决定。
- 例如，当前进程时间片用尽，调度器决定切换到另一个进程。
保存当前任务的上下文
- 将 CPU 寄存器（如 PC、SP、通用寄存器）的值保存到当前任务的控制块（PCB 或 TCB）中。
- 对于进程，PCB（进程控制块）保存进程的完整状态；对于线程，TCB（线程控制块）保存线程特定状态。
- 如果是进程切换，还可能保存内存管理信息（如页表基地址）。
选择新任务
调度器根据调度算法（例如优先级、轮转调度）从就绪队列中挑选下一个任务。
加载新任务的上下文
- 从新任务的 PCB 或 TCB 中恢复寄存器值到 CPU。
- 更新内存管理单元（MMU），加载新任务的内存页表（对于进程切换）。
- 将程序计数器（PC）设置为新任务的下一条指令地址。
执行新任务

CPU 开始运行新任务，从上一次中断的位置继续执行。

上下文切换的类型

进程间上下文切换

发生在不同进程之间。
开销较大，因为需要切换完整的地址空间（页表、TLB 刷新等）。
涉及用户态到内核态的切换（保存用户态上下文）以及内核态的调度。

线程间上下文切换

发生在同一进程内的线程之间。
开销较小，因为线程共享地址空间，无需切换页表，只需保存和恢复寄存器及线程栈。
如果线程属于不同进程，则退化为进程间切换。

5、如何实现线程之间的独立？

方法 1：内存隔离

目标：让每个线程有独立的内存空间，避免共享数据带来的干扰。

实现方式：

使用线程局部存储（Thread-Local Storage, TLS）：
- 为每个线程分配独立的变量副本，避免共享全局变量。
- 在 C/C++ 中使用 __thread 或 pthread_key_t。
避免全局变量：
将数据封装在线程私有结构体中，通过参数传递给线程。
动态分配内存：
每个线程在堆上分配自己的内存，互不干扰。

方法 2：资源隔离

目标：让每个线程使用独立的系统资源（如文件、网络连接）。

实现方式：

独立的文件描述符：
每个线程打开自己的文件或 socket，避免共享。
独立的信号处理：
使用 pthread_sigmask 屏蔽线程间的信号干扰，或者为每个线程设置独立的信号处理。
独立的锁：
为每个线程分配独立的互斥锁，避免竞争共享资源。

方法 3：执行隔离

目标：让线程的执行互不干扰，避免一个线程影响其他线程。

实现方式：

异常隔离：
使用 try-catch（C++）或信号处理（如 SIGSEGV）捕获线程异常，避免进程崩溃。
独立的执行逻辑：
每个线程运行独立的函数或任务，避免调用共享代码导致耦合。
CPU 绑定（Affinity）：
使用 pthread_setaffinity_np 将线程绑定到特定 CPU 核心，减少线程间的调度干扰。

方法 4：完全隔离（退化为进程）

目标：如果线程需要完全独立，可以直接使用进程。
实现方式：
- 使用 fork() 创建进程，每个进程有独立的地址空间和资源。
- 通过 IPC（如管道、共享内存）实现进程间通信。
缺点：开销比线程大，上下文切换成本高。

6、虚函数的实现原理？

虚函数是 C++ 中实现动态多态的核心机制。它允许在运行时根据对象的实际类型调用相应的函数，而不是根据指针或引用的静态类型决定。虚函数的实现依赖于编译器和运行时的一些底层机制，主要通过虚函数表（vtable）和虚函数指针（vptr）来完成。

实现原理

虚函数表（vtable）：每个含有虚函数的类都有一个静态的虚函数表，存储该类的虚函数地址。

虚函数指针（vptr）：每个对象实例中都包含一个指向其类虚函数表的指针。

虚函数表（vtable）

虚函数表是一个编译期生成的静态数组，存储类的虚函数地址。每个类（含虚函数的基类及其派生类）有自己独立的 vtable。

内容：

表的每一项是一个虚函数的函数指针，按声明顺序排列。
如果派生类重写了基类的虚函数，vtable 中对应位置会被替换为派生类的函数地址。

存储位置：vtable 通常存储在程序的只读数据段（.rodata），是全局唯一的。

虚函数指针（vptr）

每个含有虚函数的类的对象实例中，编译器会自动插入一个隐藏的指针（vptr），指向该对象所属类的 vtable。

初始化时机：

vptr 在对象构造时由构造函数初始化，指向对应类的 vtable。
如果有继承，基类构造函数先初始化 vptr，派生类构造函数可能覆盖它。

调用过程

获取 vptr：从对象内存中读取 vptr，找到对应的 vtable。
索引 vtable：根据虚函数在声明时的顺序（索引），从 vtable 中取出函数地址。
调用函数：间接调用该地址指向的函数。

7、new和malloc的区别？

基本定义

new

C++ 中的关键字/运算符，用于在堆上分配内存并构造对象。
自动调用构造函数初始化对象。
示例：int* p = new int(5);

malloc

C 标准库函数（<stdlib.h>），用于在堆上分配指定大小的原始内存块。
不负责对象初始化，仅返回内存地址。
示例：int* p = (int*)malloc(sizeof(int));

对比

特性	new	malloc
语言	C++	C（C++ 兼容）
类型	运算符	库函数
内存分配	分配并调用构造函数	只分配内存，不初始化
释放方式	delete / delete[]	free
返回类型	类型安全的指针	void*（需转换）
错误处理	抛异常或返回 nullptr	返回 NULL
大小计算	自动根据类型	手动指定字节数
数组支持	支持，自动构造/析构	支持，但无构造/析构
可重载	是	否

8、new有分配内存吗？

见上表

9、vector和list区别？

基本定义

std::vector

基于连续内存的动态数组。
提供随机访问，支持快速尾部插入和删除。
定义在 <vector> 头文件中。
示例：std::vector<int> vec;

std::list

基于双向链表（Doubly Linked List）。
每个元素是一个节点，节点间通过指针连接，支持快速任意位置插入和删除。
定义在 <list> 头文件中。
示例：std::list<int> lst;

底层数据结构

vector

元素存储在连续的内存块中。
内部维护三个指针：begin（起始位置）、end（尾部位置）、capacity（容量末尾）。
当容量不足时，重新分配更大内存并复制元素。

list

元素存储在非连续的节点中，每个节点包含数据、前指针和后指针。
节点间通过指针链接，形成双向链表。
内存分配是分散的，按需为每个节点分配。

区别

内存布局

vector

连续内存，元素紧凑排列。
优点：缓存友好（Cache-Friendly），访问效率高。
缺点：插入/删除（非尾部）需要移动元素。

list

非连续内存，节点分散。
优点：插入/删除只需调整指针。
缺点：缓存不友好，访问效率低。

访问方式

vector

支持随机访问，通过下标 vec[i] 或迭代器直接访问。
时间复杂度：O(1)。

list

不支持随机访问，只能通过迭代器顺序遍历。
访问第 n 个元素时间复杂度：O(n)。

插入与删除

vector

尾部：push_back 和 pop_back 是 O(1)（均摊复杂度，可能触发扩容）。
中间/头部：insert 和 erase 是 O(n)，需要移动后续元素。
扩容时可能重新分配内存并拷贝所有元素。

list

任意位置：insert 和 erase 是 O(1)，只需调整指针。
不涉及内存重新分配。

内存管理

vector

预分配容量（capacity），通过 reserve 可减少重新分配。
扩容时通常按倍增（例如 2 倍）分配新内存。

list

按需分配，每个节点独立申请内存。
无需预分配，但内存开销大（每个节点有额外指针）。

迭代器失效

vector

插入可能导致扩容，使所有迭代器失效。
删除或插入（非尾部）使后续迭代器失效。

list

插入和删除只影响当前节点的迭代器，其他迭代器保持有效。

元素存储开销

vector

仅存储元素本身，无额外指针。
内存效率高。

list

每个节点存储数据、前指针和后指针（通常 8+8 字节额外开销，64 位系统）。
内存效率低。

性能对比

操作	vector	list
随机访问	O(1)	O(n)
头部插入	O(n)	O(1)
尾部插入	O(1)（均摊）	O(1)
中间插入	O(n)	O(1)
头部删除	O(n)	O(1)
尾部删除	O(1)	O(1)
中间删除	O(n)	O(1)
遍历	O(n)，缓存友好	O(n)，缓存不友好

10、vector超过给定大小是怎么扩容的？

当调用 push_back 或 insert 导致 size 超过 capacity 时，vector 执行以下步骤：

检查容量：
- 如果 size() < capacity()，直接插入元素，结束。
- 如果 size() == capacity()，触发扩容。
计算新容量：
- 新容量通常是当前容量的 2 倍（具体倍数由实现决定，如 GCC 用 2 倍，MSVC 可能用 1.5 倍）。
- 公式：new_capacity = old_capacity * growth_factor。
- 如果用户通过 reserve 指定了更大值，则以用户指定值为准。
分配新内存：
- 调用底层分配器（默认 std::allocator）分配新内存块。
- 使用 operator new 或类似机制申请连续内存。
- 新内存大小为 new_capacity * sizeof(T)。
移动元素：
- 将旧内存中的元素移动到新内存。
- 如果元素类型支持移动构造（C++11），优先使用移动（std::move）；否则使用拷贝。
- 移动后，旧内存中的元素被销毁（析构函数调用）。
更新内部指针：
- 更新 begin（起始指针）、end（尾指针）、capacity（容量指针）指向新内存。
- 释放旧内存（通过 operator delete）。
插入新元素：
- 在新内存中添加新元素，size 增加。

11、扩容后迭代器会发生改变吗？

在 C++ 中，std::vector 的扩容会对迭代器产生影响，具体来说，扩容后迭代器通常会失效（变得不可用）。这是因为 vector 的底层实现依赖连续内存，当容量不足触发扩容时，元素会被移动到新的内存区域，导致原有迭代器指向的地址不再有效。

为什么扩容会导致迭代器改变？

vector 的内存特性：

vector 的元素存储在连续内存中，迭代器本质是指向元素地址的指针（或封装的指针）。
扩容时，vector 分配一块新的、更大的连续内存，将旧元素移动过去，然后释放旧内存。
旧内存地址失效，原有迭代器指向的地址不再对应有效元素。

扩容触发条件：

当 size() 达到 capacity() 时（例如通过 push_back 或 insert），vector 触发扩容。
新内存地址通常与旧内存不同（除非实现支持原地扩展，但标准不保证）。

结果：

扩容后，所有基于旧内存的迭代器、指针和引用都失效。

迭代器失效的具体情况

所有迭代器失效：

包括 begin()、end() 返回的迭代器，以及用户保存的任何迭代器。

c++

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin(); // it 指向 vec[0]
vec.push_back(4);      // 可能触发扩容
// it 现在失效，使用会导致未定义行为

指针和引用失效：

指向 vector 元素的裸指针（&vec[0]）和引用也会失效。

c++

int* ptr = &vec[0];
vec.push_back(4); // 扩容后 ptr 指向旧内存，可能已释放

失效时机：

仅当操作导致扩容时失效。如果 capacity 足够（例如通过 reserve 预分配），插入不会影响迭代器。

c++

std::vector<int> vec;
vec.reserve(10);       // 预分配容量 10
auto it = vec.begin(); // it 有效
vec.push_back(1);      // 未扩容，it 仍有效

为什么迭代器会失效？（底层视角）

内存重新分配：

扩容时，vector 调用分配器（std::allocator）分配新内存。
旧元素通过移动（std::move）或拷贝移到新地址。
旧内存通过 operator delete 释放。

迭代器本质：

vector 的迭代器通常是原始指针（或封装的智能指针）。
扩容后，指针指向的地址被释放或重用，迭代器失去意义。

12、i++和++i的区别？

i++（后置递增）：

先返回 i 的当前值，然后将 i 加 1。
操作顺序：使用旧值 → 自增。
示例：int a = i++;（a 得到 i 的旧值，i 增加 1）。

++i（前置递增）：

先将 i 加 1，然后返回新的值。
操作顺序：自增 → 使用新值。
示例：int a = ++i;（i 先增加 1，a 得到新值）。

13、智能指针有了解吗，说一下？

智能指针

14、左值和右值？

左值：

表示“具有身份”的对象，通常是可以取地址的实体。
可以出现在赋值表达式的左侧。
通常是有名字的、持久存在的变量。
示例：变量名、a = 5 中的 a。

右值：

表示“临时”或“无身份”的值，通常不能取地址。
只能出现在赋值表达式的右侧。
通常是临时的、即将销毁的值。
示例：字面量（如 5）、临时对象。

区别

特性	左值 (Lvalue)	右值 (Rvalue)
身份	有（可取地址）	无（通常不可取地址）
持久性	持久（生命周期明确）	临时（生命周期短暂）
赋值左侧	可以	不可
引用绑定	左值引用（T&）	右值引用（T&&）
典型示例	变量名、引用	字面量、临时对象

15、快排的实现？

原理

核心是分治法，通过选择一个“基准”将数组分成两部分，递归地对子数组排序。其基本思想如下：

分区：选择一个基准元素，将数组分成小于基准和大于基准的两部分。
递归：对分出的两个子数组递归应用快速排序。
终止条件：当子数组长度为 1 或 0 时停止。

工作流程

选择一个基准（通常是第一个、最后一个或中间元素）。
将小于基准的元素放到左侧，大于基准的元素放到右侧。
递归对左右子数组排序。

基本实现（C++递归）

使用数组和尾元素作为基准。

c++

#include <iostream>

// 分区函数，返回基准的最终位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;       // i 指向小于基准的区域边界

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) { // 如果当前元素小于等于基准
            i++;               // 扩展小于区域
            std::swap(arr[i], arr[j]); // 交换到左侧
        }
    }
    std::swap(arr[i + 1], arr[high]); // 将基准放到中间
    return i + 1;                     // 返回基准位置
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // 分区并获取基准位置
        quickSort(arr, low, pi - 1);        // 递归排序左侧
        quickSort(arr, pi + 1, high);       // 递归排序右侧
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Before sorting: ";
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    std::cout << "\n";

    quickSort(arr, 0, n - 1);

    std::cout << "After sorting: ";
    for (int i = 0; i < n; i++) std::cout << arr[i] << " ";
    std::cout << "\n";

    return 0;
}

输出：

c++

Before sorting: 10 7 8 9 1 5
After sorting: 1 5 7 8 9 10

16、C++面向对象的设计原则？

OOP 三大特性

封装

将数据和操作封装为一个整体，隐藏内部实现细节，通过访问控制（如 private、protected）限制外部直接访问。

目的：提高模块独立性，降低耦合。

c++

class Person {
private:
    std::string name; // 数据隐藏
    int age;
public:
    void setName(const std::string& n) { name = n; } // 受控访问
    std::string getName() const { return name; }
};

继承

允许子类复用父类的属性和方法，支持代码重用和层次化设计。

目的：实现“is-a”关系，增强扩展性。

c++

class Animal {
public:
    virtual void speak() { std::cout << "Animal sound\n"; }
};
class Dog : public Animal {
public:
    void speak() override { std::cout << "Woof\n"; }
};

多态

通过基类接口调用不同子类的实现，支持运行时动态行为。

目的：提高灵活性和可替换性。

c++

Animal* pet = new Dog();
pet->speak(); // 输出 "Woof"
delete pet;

SOLID 原则

单一职责原则

一个类应该只有一个职责，只因单一原因而改变。

目的：降低类的复杂性，减少修改时的副作用。

开放封闭原则

类应对扩展开放，对修改封闭。

目的：新增功能时无需修改现有代码，降低风险。

里氏替换原则

子类对象应能替换基类对象而不破坏程序正确性。

目的：确保继承关系符合行为一致性。

接口隔离原则

客户端不应被迫依赖它不使用的接口。

目的：减少不必要的耦合，提高模块独立性。

依赖倒置原则

高层模块不应依赖低层模块，二者应依赖抽象。
细节应依赖抽象，而非抽象依赖细节。

目的：解耦模块，增强可替换性。

17、三次握手描述一下？

三次握手的步骤

步骤 1：客户端发送 SYN（请求建立连接）

发送一个 TCP 段，设置 SYN = 1，并携带初始序列号 Seq = x（x 通常是随机值）。

此时客户端进入 SYN_SENT 状态，等待服务器响应。

步骤 2：服务器响应 SYN + ACK（确认并请求同步）

服务器 → 客户端：

收到客户端的 SYN 后，发送一个 TCP 段：

设置 SYN = 1，携带服务器的初始序列号 Seq = y（y 也是随机值）。
设置 ACK = 1，确认号 Ack = x + 1，表示已收到客户端的 Seq = x，并期望接收下一个序列号。

服务器进入 SYN_RCVD（同步收到）状态。

步骤 3：客户端发送 ACK（确认连接）

客户端 → 服务器：

收到服务器的 SYN + ACK 后，发送一个 TCP 段：
- 设置 ACK = 1，确认号 Ack = y + 1，表示已收到服务器的 Seq = y。
- 序列号 Seq = x + 1，继续之前的序列。
客户端进入 ESTABLISHED 状态。

服务器：

收到客户端的 ACK 后，也进入 ESTABLISHED 状态。

图示

c++

客户端                 服务器
  |    1. SYN (Seq=x)    |
  |--------------------->|
  |    2. SYN (Seq=y)    |
  |      ACK (Ack=x+1)   |
  |<---------------------|
  |    3. ACK (Ack=y+1)  |
  |      Seq=x+1         |
  |--------------------->|
  |    (连接建立)         |

18、为什么是三次不是两次不是四次？

为什么不是两次握手？

无法确认双向通信

TCP 是全双工协议，需要确保客户端和服务器都能发送和接收数据。

两次握手的过程：

客户端 → SYN → 服务器。
服务器 → ACK → 客户端。

问题：

服务器发送 ACK 后，认为连接已建立，但客户端可能未收到 ACK（例如网络丢包）。
客户端无法确认服务器的接收能力，服务器也无法确认客户端是否收到 ACK。

后果：服务器单方面认为连接成功，可能开始发送数据，而客户端未准备好，导致数据丢失。

无法同步服务器的序列号

TCP 使用序列号（Sequence Number）确保数据按序传输。

两次握手中，服务器的 ACK 只确认了客户端的序列号（x），但未发送自己的序列号（y）。

问题：客户端无法知道服务器的初始序列号，后续数据传输可能因序列号不同步而混乱。

后果：缺乏双向序列号同步，无法保证可靠传输。

无法防止旧连接干扰

网络中可能存在延迟的旧数据包（例如之前的 SYN）。

两次握手场景：

客户端发送旧 SYN（Seq = 100），服务器收到后返回 ACK。
服务器认为连接建立，但客户端并未发起新连接。

问题：两次握手无法区分新旧连接，服务器可能误处理旧包。

后果：旧数据干扰新连接，导致不可靠性。

为什么不是四次握手？

三次已足够确认双向通信和序列号同步，第四次是多余的。

四次握手可能被设想为：

客户端 → SYN。
服务器 → ACK。
服务器 → SYN。
客户端 → ACK。

虽然四次也能建立连接，但它是多余的，且效率较低。

19、为什么要closewait？

支持半关闭状态

TCP 是全双工协议，发送和接收通道独立。

场景：客户端发送 FIN 表示“我发送完了”，但服务器可能仍有数据要发送（如响应或日志）。

CLOSE_WAIT 的作用：

允许服务器在收到 FIN 后继续发送剩余数据。
半关闭状态确保服务器能优雅地完成任务。

确保被动方控制关闭时机

如果服务器收到 FIN 后立即关闭（无 CLOSE_WAIT），可能遗漏未发送的数据。

CLOSE_WAIT 的作用：

给服务器缓冲时间，应用程序决定何时发送 FIN。
避免数据丢失，保证关闭的可靠性。

防止数据丢失

场景：

客户端发送 FIN 时，服务器可能还有未处理的数据。

CLOSE_WAIT 的作用：

服务器在 CLOSE_WAIT 期间处理剩余数据并发送。
确保数据传输完整性。

20、为什么要timewait？

确保最后的 ACK 被接收

场景：

客户端发送第四次 ACK 后，如果 ACK 在网络中丢失，服务器未收到。
服务器在 LAST_ACK 状态会超时重传 FIN。

TIME_WAIT 的作用：

客户端在 TIME_WAIT 期间等待，接收可能的 FIN 重传并重新发送 ACK。
确保服务器正确进入 CLOSED 状态。

为什么需要时间？

等待 2MSL 确保网络中所有延迟的包（包括 FIN 和 ACK）都失效。

后果（无 TIME_WAIT）：如果客户端立即关闭，服务器未收到 ACK，会认为连接未关闭，浪费资源。

防止旧连接的数据干扰新连接

场景：

网络中可能存在延迟的旧数据包（例如之前的 ACK 或数据）。
如果客户端和服务器立即复用相同端口建立新连接，旧包可能被误认为是新连接的数据。

TIME_WAIT 的作用：

等待 2MSL，确保旧连接的所有数据包在网络中消失（MSL 是报文段的最大生存时间）。
防止旧数据混入新连接。

为什么 2MSL？

MSL 是数据包单程最大生存时间，2MSL 覆盖往返，确保旧包失效。

支持 TCP 的可靠性

TCP 是可靠协议，关闭过程必须保证双方一致。

TIME_WAIT 确保主动关闭方承担“最后确认”的责任，避免连接异常。

21、并发和并行？

定义

并发

并发是指在同一时间段内，多个任务交替执行的能力。任务的执行可能不是同时发生的，而是通过时间分片（Time-Slicing）在单个处理器上快速切换。

处理多任务的“逻辑同时性”，强调任务的独立性和交错执行。

并行

并行是指在同一时刻，多个任务真正同时执行。通常需要多个处理器或核心（多核 CPU）支持。

任务的“物理同时性”，强调利用多硬件资源并行处理。

区别

特性	并发	并行
定义	多个任务交替执行	多个任务同时执行
时间	同一时间段（逻辑上）	同一时刻（物理上）
硬件要求	单核即可（通过调度）	需要多核或多处理器
执行方式	时间分片、上下文切换	真正的同时运行
目标	提高响应性、任务管理	提高吞吐量、计算速度
依赖	操作系统线程/任务调度	硬件并行能力

22、手撕：从左上角到右下角的最短路径。

思路

定义 dp[i][j] 为从 (0,0) 到 (i,j) 的路径数。

递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]（从上方或左方到达）。

边界条件：第一行和第一列只有一条路径：dp[0][j] = 1，dp[i][0] = 1。

目标：dp[m-1][n-1]。

参考代码（C++）

c++

#include <iostream>
#include <vector>

long long shortestPaths(int m, int n) {
    std::vector<std::vector<long long>> dp(m, std::vector<long long>(n, 0));
    
    // 初始化第一行和第一列
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    
    // 填充 DP 表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

int main() {
    int m = 3, n = 3; // 示例：3x3 网格
    std::cout << "Number of shortest paths: " << shortestPaths(m, n) << "\n";
    std::cout << "Shortest path steps: " << m + n - 2 << "\n";
    return 0;
}

微服务

文档

基础

腾讯地图一面 ​

1、进程和线程的区别？ ​

定义 ​

资源分配 ​

创建和开销 ​

并发性 ​

通信 ​

例子 ​

2、select和epoll的区别？ ​

基本概念 ​

工作机制 ​

性能差异 ​

事件触发模式 ​

3、epoll的两种模式，描述一下？ ​

水平触发（LT） ​

定义 ​

工作机制 ​

代码示例 ​

边缘触发（ET） ​

定义 ​

工作机制 ​

代码示例 ​

LT vs ET ​

4、上下文切换？ ​

上下文（Context） ​

为什么要上下文切换？ ​

上下文切换的过程 ​

上下文切换的类型 ​

进程间上下文切换 ​

线程间上下文切换 ​

5、如何实现线程之间的独立？ ​

方法 1：内存隔离 ​

方法 2：资源隔离 ​

方法 3：执行隔离 ​

方法 4：完全隔离（退化为进程） ​

6、虚函数的实现原理？ ​

实现原理 ​

虚函数表（vtable） ​

虚函数指针（vptr） ​

调用过程 ​

7、new和malloc的区别？ ​

基本定义 ​

new ​

malloc ​

对比 ​

8、new有分配内存吗？ ​

9、vector和list区别？ ​

基本定义 ​

std::vector ​

std::list ​

底层数据结构 ​

vector ​

腾讯地图一面

1、进程和线程的区别？

定义

资源分配

创建和开销

并发性

通信

例子

2、select和epoll的区别？

基本概念

工作机制

性能差异

事件触发模式

3、epoll的两种模式，描述一下？

水平触发（LT）

定义

工作机制

代码示例

边缘触发（ET）

定义

工作机制

代码示例

LT vs ET

4、上下文切换？

上下文（Context）

为什么要上下文切换？

上下文切换的过程

上下文切换的类型

进程间上下文切换

线程间上下文切换

5、如何实现线程之间的独立？

方法 1：内存隔离

方法 2：资源隔离

方法 3：执行隔离

方法 4：完全隔离（退化为进程）

6、虚函数的实现原理？

实现原理

虚函数表（vtable）

虚函数指针（vptr）

调用过程

7、new和malloc的区别？

基本定义

new

malloc

对比

8、new有分配内存吗？

9、vector和list区别？

基本定义

std::vector

std::list

底层数据结构

vector