我的面试

2022年9月7日

面试

大约 46 分钟

我的面试经历

1.单例模式实现的优点

单例模式在内存中只有一个实例，主要优点可以减少内存的开支
可以减少系统的性能开销，当一个对象产生需要较多的资源时，比如读取配置，产生其他依赖对象时，则可以通过在应用启动时直接生产一个单例对象，然后通过永驻内存的方式来解决
避免对资源的多重占用

缺点

因为单例模式没有抽象层，所以扩展比较困难

2.select，poll，epoll区别

select

select 的核心功能是调用tcp文件系统的poll函数，不停的查询，如果没有想要的数据，主动执行一次调度（防止一直占用cpu），直到有一个连接有想要的消息为止。从这里可以看出select的执行方式基本就是不同的调用poll,直到有需要的消息为止。

缺点：

每次调用select，都需要把fd集合从用户态拷贝到内核态，这个开销在fd很多时会很大；
同时每次调用select都需要在内核遍历传递进来的所有fd，这个开销在fd很多时也很大；
select支持的文件描述符数量太小了，默认是1024。

优点：

select的可移植性更好，在某些Unix系统上不支持poll()。
select对于超时值提供了更好的精度：微秒，而poll是毫秒。

poll

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。

缺点：

1、大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义；

2、与select一样，poll返回后，需要轮询pollfd来获取就绪的描述符。

优点：

1、poll() 不要求开发者计算最大文件描述符加一的大小。

2、poll() 在应付大数目的文件描述符的时候速度更快，相比于select。

3、它没有最大连接数的限制，原因是它是基于链表来存储的。

epoll

epoll同样只告知那些就绪的文件描述符，而且当我们调用epoll_wait()获得就绪文件描述符时，返回的不是实际的描述符，而是一个代表就绪描述符数量的值，你只需要去epoll指定的一个数组中依次取得相应数量的文件描述符即可，这里也使用了内存映射技术，这样便彻底省掉了这些文件描述符在系统调用时复制的开销。

epoll的优点就是改进了前面所说缺点：

1、支持一个进程打开大数目的socket描述符：相比select，epoll则没有对FD的限制，它所支持的FD上限是最大可以打开文件的数目，这个数字一般远大于2048,举个例子,在1GB内存的机器上大约是10万左右，具体数目可以cat /proc/sys/fs/file-max察看,一般来说这个数目和系统内存关系很大。

2、IO效率不随FD数目增加而线性下降：epoll不存在这个问题，它只会对"活跃"的socket进行操作— 这是因为在内核实现中epoll是根据每个fd上面的callback函数实现的。那么，只有"活跃"的socket才会主动的去调用callback函数，其他idle状态socket则不会，在这点上，epoll实现了一个"伪"AIO，因为这时候推动力在os内核。在一些 benchmark中，如果所有的socket基本上都是活跃的—比如一个高速LAN环境，epoll并不比select/poll有什么效率，相反，如果过多使用epoll_ctl,效率相比还有稍微的下降。但是一旦使用idle connections模拟WAN环境，epoll的效率就远在select/poll之上了。

3、使用mmap加速内核与用户空间的消息传递：这点实际上涉及到epoll的具体实现了。无论是select，poll还是epoll都需要内核把FD消息通知给用户空间，如何避免不必要的内存拷贝就很重要，在这点上，epoll是通过内核于用户空间mmap同一块内存实现的。

三者对比与区别：

1、select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升。

2、select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列）。这也能节省不少的开销。

3.ET LT模式区别

当用户关注的 fd 事件发生时，ET 模式，只通知用户一次，不管这个事件是否已经被用户处理完毕，直到该事件再次发生，或者用户通过 epoll_ctl 重新关注该 fd 对应的事件；而 LT 模式，会不停地通知用户，直到用户把事件处理完毕。

LT（电平触发）：类似select，LT会去遍历在epoll事件表中每个文件描述符，来观察是否有我们感兴趣的事件发生，如果有（触发了该文件描述符上的回调函数），epoll_wait就会以非阻塞的方式返回。若该epoll事件没有被处理完（返回EWOULDBLOCK），该事件还会被后续的epoll_wait再次触发。
ET（边缘触发）：ET在发现有我们感兴趣的事件发生后，立即返回（EAGAIN），并且sleep这一事件的epoll_wait，不管该事件有没有结束。

4.TCP 协议如何保证可靠传输？

建立连接（标志位）：通信前确认通信实体存在。
序号机制（序号、确认号）：确保了数据是按序、完整到达。
数据校验（校验和）：CRC校验全部数据。
超时重传（定时器）：保证因链路故障未能到达数据能够被多次重发。
窗口机制（窗口）：提供流量控制，避免过量发送。
拥塞控制：同上。

5.malloc如何分配空间（mmap,brk）

方式一：通过 brk() 系统调用从堆分配内存
方式二：通过 mmap() 系统调用在文件映射区域分配内存；

方式一实现的方式很简单，就是通过 brk() 函数将「堆顶」指针向高地址移动，获得新的内存空间。如下图：

方式二通过 mmap() 系统调用中「私有匿名映射」的方式，在文件映射区分配一块内存，也就是从文件映射区“偷”了一块内存。如下图：

6.进程间同步方式

1. 临界区

2. 同步与互斥

3. 信号量

4. 管程

7.进程间通信方式

进程通信open in new window

进程通信就是指进程间的信息交换

管道
消息队列
共享内存
共享内存最快，一个具体的应用事 webserver中使用 mmap api作为文件映射，mmap的作用就是把磁盘文件的一部分直接映射到进程的内存中，那么进程就可以直接对该内存文件进行操作，mmap也设置了两种机制：共享和私有，如果是共享映射，那么在内存中对文件进行修改，磁盘中对应的文件也会被修改，相反，磁盘中的文件有了修改，内存中的文件也被修改。如果是私有映射，那么内存中的文件是独立的，二者进行修改都不会对对方造成影响。通过这样的内存共享映射就相当于是进程直接对磁盘中的文件进行读写操作一样，那么如果有两个进程来mmap同一个文件，就实现了进程间的通信
信号量
信号
Socket

8.vector具体实现说一下

vector是一种序列式容器，其数据安排以及操作方式与array非常类似，两者的唯一差别就是对于空间运用的灵活性，众所周知，array占用的是静态空间，一旦配置了就不可以改变大小，如果遇到空间不足的情况还要自行创建更大的空间，并手动将数据拷贝到新的空间中，再把原来的空间释放。vector则使用灵活的动态空间配置，维护一块连续的线性空间，在空间不足时，可以自动扩展空间容纳新元素，做到按需供给。其在扩充空间的过程中仍然需要经历：重新配置空间，移动数据，释放原空间等操作

需要注意的是，频繁对vector调用push_back()对性能是有影响的，这是因为每插入一个元素，如果空间够用的话还能直接插入，若空间不够用，则需要重新配置空间，移动数据，释放原空间等操作，对程序性能会造成一定的影响

9.c++从cpp文件到exe可执行文件经历的流程

预处理
预处理有：文件包含(#inlcude)、条件编译(#ifndef #ifdef #endif)、提供编译信息(#pragma)、宏替换(#define)等
编译
编译器主要作语法检查和词法分析。通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码
汇编
汇编语言代码翻译成目标机器指令的过程
链接
链接是将目标文件、启动代码、库文件链接成可执行文件open in new window的过程，得到的文件可以直接执行

10.virtual memory说一下

虚拟内存的定义及特征基于局部性原理，在程序装入时，一方面可以将程序的一部分放入内存，而将其余部分放在外存，然后启动程序（部分装入)。在程序执行过程中，当所访问的信息不在内存中时，再由操作系统将所需的部分调入内存(请求调入)。另一方面，操作系统将内存中暂时不使用的内容置换到外存上，从而腾出空间存放将要调入内存的信息（置换功能)。从效果上看，计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，这种从逻辑上扩充内存容量的存储器系统称为虚拟存储器（简称虚存)。将其称为虚拟存储器是因为这种存储器实际上并不存在，系统只是提供了部分装入、请求调入和置换功能，给用户的感觉是好像存在一个能满足作业地址空间要求的内存。虚拟内存的意义是让程序存在的地址空间与运行时的存储空间分开，程序员可以完全不考虑实际内存的大小，而在地址空间内编写程序。虚拟存储器的容量由计算机的地址结构决定，并不是无限大。

11.移动构造函数用法

我们用对象a初始化对象b，后对象a我们就不在使用了，但是对象a的空间还在呀（在析构之前），既然拷贝构造函数，实际上就是把a对象的内容复制一份到b中，那么为什么我们不能直接使用a的空间呢？这样就避免了新的空间的分配，大大降低了构造的成本。这就是移动构造函数设计的初衷；
拷贝构造函数中，对于指针，我们一定要采用深层复制，而移动构造函数中，对于指针，我们采用浅层复制。浅层复制之所以危险，是因为两个指针共同指向一片内存空间，若第一个指针将其释放，另一个指针的指向就不合法了。

所以我们只要避免第一个指针释放空间就可以了。避免的方法就是将第一个指针（比如a->value）置为NULL，这样在调用析构函数的时候，由于有判断是否为NULL的语句，所以析构a的时候并不会回收a->value指向的空间；

移动构造函数的参数和拷贝构造函数不同，拷贝构造函数的参数是一个左值引用，但是移动构造函数的初值是一个右值引用。意味着，移动构造函数的参数是一个右值或者将亡值的引用。也就是说，只用用一个右值，或者将亡值初始化另一个对象的时候，才会调用移动构造函数。而那个move语句，就是将一个左值变成一个将亡值

12.你认为智能指针有哪些缺陷？

auto_ptr有拷贝语义，拷贝后源对象变得无效，这可能引发很严重的问题；而unique_ptr则无拷贝语义，但提供了移动语义，这样的错误不再可能发生，因为很明显必须使用std::move()进行转移。

auto_ptr不支持拷贝和赋值操作，不能用在STL标准容器中。STL容器中的元素经常要支持拷贝、赋值操作，在这过程中auto_ptr会传递所有权，所以不能在STL中使用

13.C++动态链接和静态链接的比较

静态绑定：绑定的是静态类型，所对应的函数或属性依赖于对象的静态类型，发生在编译期；
动态绑定：绑定的是动态类型，所对应的函数或属性依赖于对象的动态类型，发生在运行期；

14.关系型数据库和非关系型数据库区别

关系型数据库的优点
- 容易理解。因为它采用了关系模型来组织数据。
- 可以保持数据的一致性。
- 数据更新的开销比较小。
- 支持复杂查询（带where子句的查询）
非关系型数据库的优点
- 不需要经过SQL层的解析，读写效率高。
- 基于键值对，数据的扩展性很好。
- 可以支持多种类型数据的存储，如图片，文档等等。

15.TCP三次握手和四次分手，为什么分手要四次

因为当服务端收到客户端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当服务端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉客户端，"你发的FIN报文我收到了"。只有等到我服务端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四次挥手。

16.算法题：实现一下单例模式

*// 单例模式*

SqlConnPool* SqlConnPool::Instance() {

  *static SqlConnPool connPool;

  return &connPool;

}

16.算法题：给一个数组和一个目标数，找出所有的相加之和等于这个目标数的数字组合。


class Solution {
public:
	vector<vector<int>> res;
	vector<int> track;
	int trackSum = 0;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

    	backtrack(candidates, 0, target);

    	return res;
    }

    void backtrack(vector<int> candidates, int start, int target) {
    	if(trackSum == target) {
    		res.push_back(track);
    		return ;
    	}

    	// 剪枝
    	if(trackSum > target)
    		return ;

    	for(int i = start; i < candidates.size(); i++) {
    		track.push_back(candidates[i]);
    		trackSum += candidates[i];

    		backtrack(candidates, i, target);

    		track.pop_back();
    		trackSum -= candidates[i];
    	}
    }
};

17.UDP会不会产生粘包问题呢？

TCP为了保证可靠传输并减少额外的开销（每次发包都要验证），采用了基于流的传输，基于流的传输不认为消息是一条一条的，是无保护消息边界的（保护消息边界：指传输协议把数据当做一条独立的消息在网上传输，接收端一次只能接受一条独立的消息）。

UDP则是面向消息传输的，是有保护消息边界的，接收方一次只接受一条独立的信息，所以不存在粘包问题。

举个例子：有三个数据包，大小分别为2k、4k、6k，如果采用UDP发送的话，不管接受方的接收缓存有多大，我们必须要进行至少三次以上的发送才能把数据包发送完，但是使用TCP协议发送的话，我们只需要接受方的接收缓存有12k的大小，就可以一次把这3个数据包全部发送完毕。

18.你知道哪些socket？

流格式套接字（SOCK_STREAM）

SOCK_STREAM 是一种可靠的、双向的通信数据流，数据可以准确无误地到达另一台计算机，如果损坏或丢失，可以重新发送。

SOCK_STREAM 有以下几个特征：

数据在传输过程中不会消失；
数据是按照顺序传输的；
数据的发送和接收不是同步的

数据报格式套接字（SOCK_DGRAM）

计算机只管传输数据，不作数据校验，如果数据在传输中损坏，或者没有到达另一台计算机，是没有办法补救的。也就是说，数据错了就错了，无法重传。

因为数据报套接字所做的校验工作少，所以在传输效率方面比流格式套接字要高。

可以将 SOCK_DGRAM 比喻成高速移动的摩托车快递，它有以下特征：

强调快速传输而非传输顺序；
传输的数据可能丢失也可能损毁；
限制每次传输的数据大小；
数据的发送和接收是同步的

19.什么是进程上下文？什么是中断上下文？

进程上下文，就是一个进程在执行的时候，CPU的所有寄存器中的值、进程的状态以及堆栈上的内容，当内核需要切换到另一个进程时，它需要保存当前进程的所有状态，即保存当前进程的进程上下文，以便再次执行该进程时，能够恢复切换时的状态，继续执行

中断上下文，硬件通过触发信号，向CPU发送中断信号，导致内核调用中断处理程序，进入内核空间。这个过程中，硬件的一些变量和参数也要传递给内核， 内核通过这些参数进行中断处理。

20.ARP协议地址解析协议

ARP 广播

主机会通过广播发送 ARP 请求，这个包中包含了想要知道的 MAC 地址的主机 IP 地址。
当同个链路中的所有设备收到 ARP 请求时，会去拆开 ARP 请求包里的内容，如果 ARP 请求包中的目标 IP 地址与自己的 IP 地址一致，那么这个设备就将自己的 MAC 地址塞入 ARP 响应包返回给主机

21.交换机和路由器

交换机二层网络设备

根据 MAC 地址表查找 MAC 地址，然后将信号发送到相应的端口。

当 MAC 地址表找不到指定的 MAC 地址会怎么样？

地址表中找不到指定的 MAC 地址。这可能是因为具有该地址的设备还没有向交换机发送过包，或者这个设备一段时间没有工作导致地址被从地址表中删除了。

这种情况下，交换机无法判断应该把包转发到哪个端口，只能将包转发到除了源端口之外的所有端口上，无论该设备连接在哪个端口上都能收到这个包。

这样做不会产生什么问题，因为以太网的设计本来就是将包发送到整个网络的，然后只有相应的接收者才接收包，而其他设备则会忽略这个包

路由器三层网络设备

路由器基本原理

路由器的端口具有 MAC 地址，因此它就能够成为以太网的发送方和接收方；同时还具有 IP 地址，从这个意义上来说，它和计算机的网卡是一样的。

当转发包时，首先路由器端口会接收发给自己的以太网包，然后路由表查询转发目标，再由相应的端口作为发送方将以太网包发送出去。

22.流量控制

接收端在接收到数据后，对其进行处理。如果发送端的发送速度太快，导致接收端的接收缓冲区很快的填充满了。此时如果发送端仍旧发送数据，那么接下来发送的数据都会丢包，继而导致丢包的一系列连锁反应，超时重传呀什么的。而TCP根据接收端对数据的处理能力，决定发送端的发送速度，这个机制就是流量控制。

在TCP协议的报头信息当中，有一个16位字段的窗口大小。在介绍这个窗口大小时我们知道，窗口大小的内容实际上是接收端接收数据缓冲区的剩余大小。这个数字越大，证明接收端接收缓冲区的剩余空间越大，网络的吞吐量越大。接收端会在确认应答发送ACK报文时，将自己的即时窗口大小填入，并跟随ACK报文一起发送过去。而发送方根据ACK报文里的窗口大小的值的改变进而改变自己的发送速度。如果接收到窗口大小的值为0，那么发送方将停止发送数据。并定期的向接收端发送窗口探测数据段，让接收端把窗口大小告诉发送端。

注：16位的窗口大小最大能表示65535个字节（64K），但是TCP的窗口大小最大并不是64K。在TCP首部中40个字节的选项中还包含了一个窗口扩大因子M，实际的窗口大小就是16为窗口字段的值左移M位。每移一位，扩大两倍。

23.为什么有了指针还要迭代器

1、通过迭代器访问容器，可以避免许多错误，同时还能隐藏容器的具体实现。

2、迭代器可以保证对所有容器的基本遍历方式，都是一样的，实现算法时若需要遍历，则使用迭代器，则可以不用关注容器的具体类型，实现数据结构和算法的分离。

3、迭代器本身有很多优点，可以弥补C++语言的不足，比如它的iterator_category，可以得到迭代器所指向的类别，这样可以根据不同的类别的特性，提供不同的算法。

24.TCP粘包问题是什么？你会如何去解决它？

TCP粘包是指发送方发送的若干包数据到接收方接收时粘成一包，从接收缓冲区看，后一包数据的头紧接着前一包数据的尾。

由TCP连接复用造成的粘包问题。
因为TCP默认会使用
Nagle算法，此算法会导致粘包问题。
- 只有上一个分组得到确认，才会发送下一个分组；
- 收集多个小分组，在一个确认到来时一起发送。
数据包过大造成的粘包问题。
流量控制，拥塞控制也可能导致粘包。
接收方不及时接收缓冲区的包，造成多个包接收

解决：

Nagle算法问题导致的，需要结合应用场景适当关闭该算法
尾部标记序列。通过特殊标识符表示数据包的边界，例如\n\r，\t，或者一些隐藏字符。
头部标记分步接收。在TCP报文的头部加上表示数据长度。
应用层发送数据时定长发送

25.索引的目的及优缺点

如果某列出现在查询的条件（where）中，而该列的数据是无序的，那么查询时只能从第一行开始一行一行地匹配。创建索引就是对某些特定列中的数据排序，生成独立的索引表。当在某列上创建索引后，如果该列出现在查询条件中，那么数据库系统会自动地引用该索引

优点

通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大加快数据的检索速度，这也是创建索引的最主要的原因。
帮助服务器避免排序和临时表
将随机IO变为顺序IO。
可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义

缺点

索引必须创建在表上，不能创建在视图上。
创建索引和维护索引要消费时间，这种时间随着数据量的增加而增加。
建立索引需要占用物理空间，如果要建立聚簇索引，那么需要的空间会很大。
当对表中的数据进行增加、删除和更新的时候，系统必须要有额外的时间来同时对索引进行更新维护，以维持数据和索引的一致性，所以，索引降低了数据的维护速度

聚簇（聚集）索引和非聚簇索引（二级索引）

分类	含义	特点
聚集索引	将数据存储与索引放到了一块，索引结构的叶子节点保存了行数据	必须有,而且只有一个
二级索引	将数据与索引分开存储，索引结构的叶子节点关联的是对应的主键	可以存在多个

聚簇索引的优缺点

优点：

数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快
聚簇索引对于主键的排序查找和范围查找速度非常快

缺点：

插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则将会出现页分裂，严重影响性能。因此，对于InnoDB表，我们一般都会定义一个自增的ID列为主键
更新主键的代价很高，因为将会导致被更新的行移动。因此，对于InnoDB表，我们一般定义主键为不可更新。
二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据

26.HTTP 与 HTTPS 有哪些区别？

HTTP 是超文本传输协议，信息是明文传输，存在安全风险的问题。HTTPS 则解决 HTTP 不安全的缺陷，在 TCP 和 HTTP 网络层之间加入了 SSL/TLS 安全协议，使得报文能够加密传输。
HTTP 连接建立相对简单， TCP 三次握手之后便可进行 HTTP 的报文传输。而 HTTPS 在 TCP 三次握手之后，还需进行 SSL/TLS 的握手过程，才可进入加密报文传输。
HTTP 的端口号是 80，HTTPS 的端口号是 443。
HTTPS 协议需要向 CA（证书权威机构）申请数字证书，来保证服务器的身份是可信的。

27.HTTPS 解决了 HTTP 的哪些问题？

HTTP 由于是明文传输，所以安全上存在以下三个风险：

窃听风险，比如通信链路上可以获取通信内容，用户号容易没。
篡改风险，比如强制植入垃圾广告，视觉污染，用户眼容易瞎。
冒充风险，比如冒充淘宝网站，用户钱容易没。

HTTP 与 HTTPS 网络层

28.GET 和 POST 的区别，你知道哪些？

get是获取数据，post是修改数据
get把请求的数据放在url上，以?分割URL和传输数据，参数之间以&相连，所以get不太安全。而post把数据放在HTTP的包体内（requrest body）
get提交的数据最大是2k（限制实际上取决于浏览器）， post理论上没有限制。
GET产生一个TCP数据包，浏览器会把http header和data一并发送出去，服务器响应200(返回数据); POST产生两个TCP数据包，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok(返回数据)。
GET请求会被浏览器主动缓存，而POST不会，除非手动设置。
本质区别：GET是幂等的，而POST不是幂等的

29.Web服务器如何处理以及响应接收到的HTTP请求报文呢?

该项目使用线程池（半同步半反应堆模式）并发处理用户请求，主线程负责读写，工作线程（线程池中的线程）负责处理逻辑（HTTP请求报文的解析等等）。通过之前的代码，我们将listenfd上到达的connection通过 accept()接收，并返回一个新的socket文件描述符connfd用于和用户通信，并对用户请求返回响应，同时将这个connfd注册到内核事件表中，等用户发来请求报文。这个过程是：通过epoll_wait发现这个connfd上有可读事件了（EPOLLIN），主线程就将这个HTTP的请求报文读进这个连接socket的读缓存中users[sockfd].read()，然后将该任务对象（指针）插入线程池的请求队列中pool->append(users + sockfd);，线程池的实现还需要依靠锁机制以及信号量机制来实现线程同步，保证操作的原子性。

30.可重入锁、偏向锁、自旋锁（阿里9.5）

自旋锁：是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环

31.线程池的改进，哪地方做的改进？（阿里9.5）

首先我们使用一个队列来存储任务序列。这一部分的核心就是怎么实现将一个任务提交到任务序列，也就是入队。

一个任务，一般可以表示为一个函数。那么我们需要传入的参数就有一个函数指针以及这个函数的所有参数。其中一个问题是这个函数的参数往往不是不确定的，类型也是未知的，因此，我们需要使用可变参数函数模板。二者，里面的一个难点在于怎么将各种不同的类型统一。我们使用std::bind + std::funtion + std::packaged_task 等层层封装。最后就是同步和互斥操作。

接着，就是线程池的工作过程。我用一个vector来存储线程。主要的思路就是在没任务的时候保持线程处于非活跃状态，有任务的时候进行处理。其中也利用了lambda表达式的特性，以及同步和互斥操作。

最后，就是线程池的析构实现。用一个bool变量来存储是否要停止使用线程池，当需要析构的时候，唤醒所有线程，并且逐个join。

32.CPU密集型和IO密集型（阿里9.5）

CPU密集型任务应配置尽可能小的线程，如配置CPU核数+1个线程的线程池，+1的目的是防止CPU空跑；

任务类型合理配置线程个数

（1）CPU 密集型任务 = N（CPU 核心数） + 1

这种任务消耗的主要是 CPU 资源，可以将线程数设置为 N（CPU 核心数）+1，比 CPU 核心数多出来的一个线程是为了防止线程偶发的缺页中断，或者其它原因导致的任务暂停而带来的影响。一旦任务暂停，CPU 就会处于空闲状态，而在这种情况下多出来的一个线程就可以充分利用 CPU 的空闲时间。【适用场景】：数字计算、排序、挖矿等等

（2）IO 密集型任务 = 2N（CPU核心数）

这种任务应用起来，系统会用大部分的时间来处理 I/O 交互，而线程在处理 I/O 的时间段内不会占用 CPU 来处理，这时就可以将 CPU 交出给其它线程使用。因此在 I/O 密集型任务的应用中，我们可以多配置一些线程，具体的计算方法是 2N。【适用场景】：操作数据库、文件等

33.对于多线程的程序来说，同步指的是在一定的时间内只允许某一个线程访问某个资源，具体可以使用一下四种方式实现：

互斥锁（mutex）
互斥锁是最常见的线程同步方式，它是一种特殊的变量，它有 lock 和 unlock 两种状态，一旦获取，就会上锁，且只能由该线程解锁，期间，其他线程无法获取
条件变量（condition）
针对互斥锁浪费资源且效率低的缺点，可以使用条件变量。
条件变量的方法是，当线程在等待某些满足条件时使线程进入睡眠状态，一旦条件满足，就唤醒，这样不会占用宝贵的互斥对象锁，实现高效
条件变量允许线程阻塞并等待另一个线程发送信号，一般和互斥锁一起使用。
条件变量被用来阻塞一个线程，当条件不满足时，线程会解开互斥锁，并等待条件发生变化。一旦其他线程改变了条件变量，将通知相应的阻塞线程，这些线程重新锁定互斥锁，然后执行后续代码，最后再解开互斥锁
读写锁（reader-writer lock）
一般用在读和写的次数有很大不同的场合。即对某些资源的访问会出现两种情况，一种是访问的排他性，需要独占，称之为写操作；还有就是访问可以共享，称之为读操作。
信号量（semphore）
信号量和互斥锁的区别在于：互斥锁只允许一个线程进入临界区，信号量允许多个线程同时进入临界区
可以这样理解，互斥锁使用对同一个资源的互斥的方式达到线程同步的目的，信号量可以同步多个资源以达到线程同步

34.大文件排序（阿里9.5）

**一种方法是：**先分成小的到内存中，排好序后，取出每个文件最小值，然后肯定能找到一个最小值，写到大文件里面，这就是大文件的最小值，然后第二轮选取次小值，以此类推的话，一定能全部写入到大文件里面，最后做到大文件排序完成

另一种方法是：

比如场景是 100G的字符串文件，1G的内存，对字符串进行排序操作

首先是分成若干个小部分，每个部分不超过内存的一半，就是每个部分不超过500MB，分别读取这些小部分排序，排序完成写到外存中。这样就是分的部分，每部分也都排序完成；
第二步就是多路归并排序，对于 K 个已经排好序的小部分，每次取出他们的各自最小值，写入到

35.如果现在有远远多于线程的任务数量在等待处理你要怎么分析这个问题

首先判断这个请求数量远远多于线程是常态吗，如果是常态则先要考虑是不是线程数量设置有问题，然后判断机器是否能力不足以处理这些数据
假如说硬件软件都没有问题，那么考虑这个问题为什么会产生，是不是我们的高计算密集型任务太多了，如果说我们的请求任务比较复杂，那么考虑进行一个分类，将处理特别慢的请求作为一个特定类，将一些线程固定给他们使用，而不是所有线程都用来处理这种任务，因为既然很慢，那么慢1个和慢10个点区别就没有那么大了，将其他线程用来处理能够快速处理完的请求，这样子就保证了一个相对的处理效率

36.Ping 原理

ping主要是用来探测主机和主机之间是否可以进行通信，如果不能ping到某台主机，表示不能与这台主机建立连接。 ping使用的是ICMP协议，他发送ICMP回送请求消息给目的主机。 ICMP协议规定：目的主机必须返回ICMP回送应答消息给源主机，如果源主机在一定时间内收到应答，表明主机可达。

37.TCP 三次握手相关，三次握手与网络编程API的对应关系

客户端调用connect()函数，此时客户端会向服务端发送SYN
服务端收到SYN后，会从listen()函数返回SYN+ACK
客户端收到connect()函数的返回，之后向服务端发送最后一个ACK
服务端收到最后一个ACK以后，将该连接请求从未完成连接队列放入已完成连接队列中，等待accept()从该队列中取出

38.1 ~ n 个人报数，数到3退出，最后一个退出的人是谁？

循环报数问题，当时说法是采用数组，实际上更好的方式是采用循环链表

该问题 2 步完成

创建循环链表
循环删除数到 3 的元素

39.Reactor 和 Proactor

Reactor 非阻塞同步是会立即返回控制权给调用者的。调用者不需要等等，它从调用的函数获取两种结果：要么此次调用成功进行了；要么系统返回错误标识告诉调用者当前资源不可用，你再等等或者再试度看吧。比如read()操作，如果当前socket无数据可读，则立即返回EWOULBLOCK/EAGAIN，告诉调用read()者”数据还没准备好，你稍后再试”。

Proactor 非阻塞异步调用中，稍有不同。调用函数在立即返回时，还告诉调用者，这次请求已经开始了。系统会使用另外的资源或者线程来完成这次调用操作，并在完成的时候知会调用者（比如通过回调函数）

简单直观的理解：

1、Reactor 模式是等待关心的动作的发生后，将如何处理这个动作的后续交给了用户态的应用本身来处理，Reactor 的事件分享器只关心事件的发生，其它的就完全交给应用程序来处理了；而 Proactor 模式则是只关心由操作系统(内核)完成异步非阻塞的操作后返回的结果；

2、Proactor 场景中只能够使用异步非阻塞的syscall(系统调用)，而Reactor的场景中更多地是使用非阻塞同步的syscall(系统调用)；

40.项目中单 Reator 多线程

单 Reator 多线程的方案优势在于能够充分利用多核 CPU 的能，那既然引入多线程，那么自然就带来了多线程竞争资源的问题

41.webbench 怎么压测

-c 并发数

-t 测试时间

42.shared_ptr智能指针的内存分布情况，count计数器是怎么分布的存在内存中的哪里，多个指针怎么同步count

每一个shared_ptr的拷贝都指向相同的内存。每使用它一次，内部的引用计数加1，每析构一次，内部的引用计数减1，减为0时，释放所指向的堆内存。shared_ptr内部的引用计数是安全的，但是对象的读取需要加锁。

43.为什么使用B+树原因：相对于B树

（1）B+树空间利用率更高，可减少I/O次数，一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗。而因为B+树的内部节点只是作为索引使用，而不像B-树那样每个节点都需要存储硬盘指针。也就是说：B+树中每个非叶节点没有指向某个关键字具体信息的指针，所以每一个节点可以存放更多的关键字数量，即一次性读入内存所需要查找的关键字也就越多，减少了I/O操作。 e.g.假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。 （2）增删文件（节点）时，效率更高， 因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。 （3）B+树的查询效率更加稳定， 因为B+树的每次查询过程中，都需要遍历从根节点到叶子节点的某条路径。所有关键字的查询路径长度相同，导致每一次查询的效率相当。

44.360面试（9.6）

手撕代码 1 ：删除倒数第 n 个结点

手撕代码 2 ：编辑距离

45.Linux常用命令 360

命令	功能说明
man	查看命令帮助
help	查看 Linux 内置命令的帮助
vim/vi	命令行文本编辑器
diff	比较文件的差异，常用于文本文件
sort	并不是对文件内容进行实际排序，仅仅是将内容按有序方式输出
echo	将字符输出到终端上，当然也可以输出到文件中
cat	连接多个文件并且打印到输出屏幕
top	能够实时显示系统中各个进程的资源占用状况，类似于Windows的任务管理器
chmod	改变文件或目录权限
ifconfig	类似于Windows下的ipconfig
find	查找文件或目录
gzip/zip/unzip	压缩和解压的命令
rm	删除文件
mv	移动或者重命名文件
cp	拷贝
clear	清除屏幕
kill	终止进程

46.STL二级配置器 360 待续

申请的空间大于128字节，则直接交至一级空间配置器处理，如果小于128字节，则使用二级空间配置器

维护16条链表，分别是 0 - 15号链表，最小8字节，以8字节逐渐递增，最大128字节，分配时候你传入一个参数，自动校对到第几号链表，在找到第n个链表后查看链表是否为空，如果不为空，直接从free_list拔出，将已经拔出的指针向后移动一位

47.多核CPU多级缓存一致性协议MESI

CPU在摩尔定律指导下以每18个月翻一番的速度在发展，但是内存硬盘发展速度远远不及CPU，这就造成了高性能的内存和硬盘价格极其昂贵。CPU在高度运算需要告诉的数据，CPU厂商在CPU中内置了少量的高速缓存以解决I/O速度和CPU运算速度不匹配的问题。

带有高速缓存的CPU执行计算的流程

程序以及数据被加载到主内存
指令和数据被加载到CPU的高速缓存
CPU执行指令，把结果写到告诉缓存
高速缓存中的数据写回主内存

多核CPU多级缓存一致性协议MESI

多核CPU的情况下有多个一级缓存，如何保证缓存内部数据的一致,不让系统数据混乱。这里就引出了一个一致性的协议MESI

MESI协议缓存状态

MESI 是指4种状态的首字母。每个Cache line有4个状态，可用2个bit表示，它们分别是：

状态	描述	监听任务
M 修改 (Modified)	该Cache line有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。	缓存行必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S（共享）状态之前被延迟执行。
E 独享、互斥 (Exclusive)	该Cache line有效，数据和内存中的数据一致，数据只存在于本Cache中。	缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S（共享）状态。
S 共享 (Shared)	该Cache line有效，数据和内存中的数据一致，数据存在于很多Cache中。	缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
I 无效 (Invalid)	该Cache line无效。	无

48.设计模式之五大设计原则 —— SOLID

单一原则 Single Responsibility Principle

一个类被改变的原因不能超过一个，也就是说，一个类只有一个职责，如果职责过多，代码就会臃肿，可读性更差，也更难以维护

开闭原则 Open-Closed Principle
a. 对拓展新功能是开放的
b. 对修改原有功能是关闭的
里氏替换原则 Liskov Substitution Principle
任何能使用父类对象的地方，都应该能透明地替换为子类对象。
也就是说子类对象可以随时随地替换父类对象，且替换完以后，语法不会报错，业务逻辑也不会出现问题。
接口隔离原则 Interface Segregation Principle
使用多个专门的接口比使用单一的总接口要好。
一个类对另外一个类的依赖性应当是建立在最小的接口上的。
**依赖倒置原则 ** Dependence Inversion Principle
上层不能依赖于下层，它们应该都依赖于抽象，
每当下层变动时，上层也要跟着一起动，违反依赖倒置原则

49.迭代器失效 360

以vector为例：

插入元素：

首迭代器不失效但插入元素之后所有迭代器失效，size == capacity时，所有迭代器均失效。

删除元素：

删除位置之后所有迭代失效

deque 和 vector 的情况类似,

而list双向链表每一个节点内存不连续, 删除节点仅当前迭代器失效，erase返回下一个有效迭代器;

map/set等关联容器底层是红黑树删除节点不会影响其他节点的迭代器, 使用递增方法获取下一个迭代器 mmp.erase(iter++);

unordered_(hash) 迭代器意义不大, rehash之后, 迭代器应该也是全部失效

50.红黑树 VS AVL树

红黑树是不符合AVL树的平衡条件的，即每个节点的左子树和右子树的高度最多差1的二叉查找树。但是提出了为节点增加颜色，红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高

插入情况

插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)

删除情况

删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转，只需要O(1)的复杂度

查询情况

AVL树更好，因为是平衡的，但是红黑树最多也只需要多一次查找即可，相对于删除带来的影响，综合比较还是红黑树更高效

51.InnoDB VS MyISAM

总结

事务: InnoDB 是事务型的，可以使用 Commit 和 Rollback 语句。
并发: MyISAM 只支持表级锁，而 InnoDB 还支持行级锁。
外键: InnoDB 支持外键。
备份: InnoDB 支持在线热备份。
崩溃恢复: MyISAM 崩溃后发生损坏的概率比 InnoDB 高很多，而且恢复的速度也更慢。
其它特性: MyISAM 支持压缩表和空间数据索引。

52.TOP K 算法

可以使用堆排序和快速排序

堆排序

// 堆排序，只排序前 k 个即可
#include <bits/stdc++.h>

using namespace std;

void maxHeapify(vector<int> &nums, int i, int n);

void buildMaxHeap(vector<int> &nums);

// 堆排序
void heapSort(vector<int> &nums, int k) {
    int n = nums.size();
    buildMaxHeap(nums);

    for (int i = n - 1; i >= n - k; --i) {
        swap(nums[0], nums[i]);
        maxHeapify(nums, 0, i);
    }
}

// 先建好堆，大根堆
void buildMaxHeap(vector<int> &nums) {
    int n = nums.size();

    // 从下到上，从右到左依次调整
    for (int i = (n - 1) / 2; i >= 0; --i) {
        maxHeapify(nums, i, n);
    }
}

// i 当前调整位置， n 所有的结点
void maxHeapify(vector<int> &nums, int i, int n) {
    while (i * 2 + 1 < n) {
        int j = 2 * i + 1;
        // 先从当前 i 结点找到左右两个较大的那一个
        if (j + 1 < n && nums[j + 1] > nums[j]) ++j;

        // 如果大于父节点
        if (nums[j] > nums[i]) {
            swap(nums[i], nums[j]);
            i = j;
        } else {
            break;
        }
    }
}


// top k 问题
int main() {
    vector<int> nums = {1, 7, 9, 8, 6, 5, 3, 0, 2, 4};
    int k = 3;
	
    heapSort(nums, k);
    for(auto& num : nums) {
        cout << num << " ";
    }
}

快速排序

#include <bits/stdc++.h>

using namespace std;

void quickSort(vector<int> &nums, int l, int r, int k) {
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] > nums[l]) --j;
        while (i < j && nums[i] <= nums[l]) ++i;
        swap(nums[i], nums[j]);
    }
    swap(nums[i], nums[l]);

    if (i > k) {
        quickSort(nums, l, i - 1, k);
    }
    if (i < k) {
        quickSort(nums, i + 1, r, k);
    }
}


// top k 问题
int main() {
    vector<int> nums = {1, 7, 9, 8, 6, 5, 3, 0, 2, 4, 11, 28, -2};
    int k = 3;

    //heapSort(nums, k);
    quickSort(nums, 0, nums.size() - 1, k);
    for (auto &num: nums) {
        cout << num << " ";
    }
    cout << endl;
}

53.什么是内存泄露，如何检测与避免

内存泄露

一般我们常说的内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的，大小任意的(内存块的大小可以在程序运行期决定)内存块，使用完后必须显式释放的内存。应用程序般使用malloc,、realloc、 new等函数从堆中分配到块内存，使用完后，程序必须负责相应的调用free或delete释放该内存块，否则，这块内存就不能被再次使用，我们就说这块内存泄漏了

避免内存泄露的几种方式

使用智能指针来自动管理内存
一定要将基类的析构函数声明为虚函数
对象数组的释放一定要用delete []
有new就有delete，有malloc就有free，保证它们一定成对出现

检测工具

Linux下可以使用Valgrind工具
Windows下可以使用CRT库

54.二分查找

int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;

    while(l <= r) {
        int m = l + (r - l) / 2;

        if(nums[m] == target) {
            return m;
        }

        if(nums[m] < target) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return -1;
}

55.CLOSE_WAIT状态的原因 360

close_wait 状态是在TCP四次挥手的时候收到 FIN，但是没有发送自己的FIN，服务器收到大量close_wait状态的原因有两种：

服务器业务内部处理占用了过多的时间，都没能处理完业务；或者还有数据需要发送；或者服务器的业务逻辑有问题，没有执行 close() 方法
服务器的父进程派生出子进程，子进程继承了socket，收到FIN的时候子进程处理但父进程没有处理该信号，导致socket的引用不为 0，无法回收

处理方法

停止应用程序
修改程序里的bug

56.为什么TIME_WAIT状态需要经过2MSL才能返回到CLOSE状态？

如果客户端直接进入CLOSED状态，如果服务端没有接收到最后一次ACK包会在超时之后重新再发FIN包，此时因为客户端已经CLOSED，所以服务端就不会收到ACK而是收到RST。所以TIME_WAIT状态目的是防止最后一次握手数据没有到达对方而触发重传FIN准备的。
在2MSL时间内，同一个socket不能再被使用，否则有可能会和旧连接数据混淆（如果新连接和旧连接的socket相同的话）。

我的面试

# 1.单例模式实现的优点

# 缺点

# 2.select，poll，epoll区别

# select

# poll

# epoll

# 三者对比与区别：

# 3.ET LT模式区别

# 4.TCP 协议如何保证可靠传输？

# 5.malloc如何分配空间（mmap,brk）

# 6.进程间同步方式

# 1. 临界区

# 2. 同步与互斥

# 3. 信号量

# 4. 管程

# 7.进程间通信方式

# 8.vector具体实现说一下

# 9.c++从cpp文件到exe可执行文件经历的流程

# 10.virtual memory说一下

# 11.移动构造函数用法

# 12.你认为智能指针有哪些缺陷？

# 13.C++动态链接和静态链接的比较

# 14.关系型数据库和非关系型数据库区别

# 15.TCP三次握手和四次分手，为什么分手要四次

# 16.算法题：实现一下单例模式

# 16.算法题：给一个数组和一个目标数，找出所有的相加之和等于这个目标数的数字组合。

# 17.UDP会不会产生粘包问题呢？

# 18.你知道哪些socket？

# 流格式套接字（SOCK_STREAM）

# 数据报格式套接字（SOCK_DGRAM）

# 19.什么是进程上下文？什么是中断上下文？

# 20.ARP协议 地址解析协议

# 21.交换机和路由器

# 22.流量控制

# 23.为什么有了指针还要迭代器

# 24.TCP粘包问题是什么？你会如何去解决它？

# 25.索引的目的及优缺点

# 优点

# 缺点

# 聚簇（聚集）索引和非聚簇索引（二级索引）

# 聚簇索引的优缺点

# 优点：

# 缺点：

# 26.HTTP 与 HTTPS 有哪些区别？

# 27.HTTPS 解决了 HTTP 的哪些问题？

# 28.GET 和 POST 的区别，你知道哪些？

# 29.Web服务器如何处理以及响应接收到的HTTP请求报文呢?

# 30.可重入锁、偏向锁、自旋锁（阿里9.5）

# 31.线程池的改进，哪地方做的改进？（阿里9.5）

# 32.CPU密集型和IO密集型（阿里9.5）

# 任务类型合理配置线程个数

# 33.对于多线程的程序来说，同步指的是在一定的时间内只允许某一个线程访问某个资源，具体可以使用一下四种方式实现：

# 34.大文件排序（阿里9.5）

# 35.如果现在有远远多于线程的任务数量在等待处理你要怎么分析这个问题

# 36.Ping 原理

# 37.TCP 三次握手相关，三次握手与网络编程API的对应关系

# 38.1 ~ n 个人报数，数到3退出，最后一个退出的人是谁？

# 39.Reactor 和 Proactor

# 40.项目中 单 Reator 多线程

# 41.webbench 怎么压测

# 42.shared_ptr智能指针的内存分布情况，count计数器是怎么分布的存在内存中的哪里，多个指针怎么同步count

# 43.为什么使用B+树原因：相对于B树

# 44.360面试（9.6）

# 45.Linux常用命令 360

# 46.STL二级配置器 360 待续

# 47.多核CPU多级缓存一致性协议MESI

# 带有高速缓存的CPU执行计算的流程

# 多核CPU多级缓存一致性协议MESI

# MESI协议缓存状态

# 48.设计模式之五大设计原则 —— SOLID

# 49.迭代器失效 360

# 50.红黑树 VS AVL树

# 插入情况

# 删除情况

# 查询情况

# 51.InnoDB VS MyISAM

# 总结

# 52.TOP K 算法

# 53.什么是内存泄露，如何检测与避免