拿下鹅厂一面！

图解学习网站：xiaolincoding.com

今天分享一位同学实习面试鹅厂 c++ 岗的面试，全程都是问 C++ 和计算机基础（系统、网络、算法）的内容了。难度中规中矩吧，基本都是追问式的问法，一层一层往下问。

C++相关

对面向对象的理解

C++面向对象编程就是把一切事物都变成一个个对象，用属性和方法来描述对象的信息，比如定义一个猫对象，猫的眼睛、毛发、嘴巴就可以定义为猫对象的属性，猫的叫声和走路就可以定义为猫对象的方法。

用对象的方式编程，不仅方便了程序员，也使得代码的可复用性、可维护性变好。

C++面向对象的三大特性是封装、继承、多态。

• 封装：封装是将数据（变量）和操作数据的函数组合在一起形成一个"对象"，并隐藏了对象的内部细节。这可以防止外部代码直接访问对象的内部表示。

• 继承：继承是从现有类派生出新类的过程。新类包含了现有类的所有特性，并可以添加自己的新特性。这有助于代码重用和减少复杂性。

• 多态：多态是指允许使用一个接口来表示不同的类型。在C++中，多态可以通过虚函数实现，使得不同的对象可以以自己的方式响应相同的消息。

普通的函数和成员函数的区别？

• 普通函数是在类的外部定义的，而成员函数是在类的内部定义的。
• 普通函数不能直接访问类的私有（private）和保护（protected）成员，而成员函数可以访问类的所有成员，包括私有和保护成员。
• 普通函数可以直接调用，而成员函数需要通过类的对象来调用。
• 成员函数有一个特殊的指针this，它指向调用该成员函数的对象。普通函数没有这个指针。

this 指针是干嘛的？

this 指针是指向当前对象的地址。this指针主要用于在类的成员函数中访问当前对象的成员变量和成员函数。

当一个对象调用自己的成员函数时，编译器会隐式地将对象的地址传递给成员函数，作为一个隐藏的参数，这个隐藏的参数就是this指针。通过this指针，成员函数可以访问和操作当前对象的成员变量和成员函数。

this指针只能在非静态成员函数中使用，因为静态成员函数没有this指针，它们不属于任何具体的对象

static关键字的作用？

static:静态变量声明，分为局部静态变量，全局静态变量，类静态成员变量。也可修饰类成员函数。有以下几类：

• 局部静态变量：存储在静态存储区，程序运行期间只被初始化一次，作用域仍然为局部作用域，在变量定义的函数或语句块中有效，程序结束时由操作系统回收资源。

• 全局静态变量：存储在静态存储区，静态存储区中的资源在程序运行期间会一直存在，直到程序结束由系统回收。未初始化的变量会默认为0，作用域在声明他的文件中有效。

• 类静态成员变量：被类的所有对象共享，包括子对象。必须在类外初始化，不可以在构造函数内进行初始化。

• 类静态成员函数：所有对象共享该函数，不含this指针，不可使用类中非静态成员。

Vector扩容，什么情况1.5倍，什么情况2倍？

vector 在插入新的元素时但是之前的内存已经满的时候需要扩容，在VS下是1.5倍，在GCC 下是2 倍。

Vector的resize和reserve有什么区别？

1. resize: resize(n)会改变vector的大小，使其包含n个元素。如果n大于当前的大小，那么新的元素会被添加到vector的末尾，如果n小于当前的大小，那么末尾的元素会被删除。resize会改变vector的size()。

2. reserve: reserve(n)不会改变vector的大小，它只是预先分配足够的内存，以便在未来可以容纳n个元素。reserve不会改变vector的size()，但可能会改变capacity()。reserve的主要目的是为了优化性能，避免在添加元素时频繁进行内存分配。

简单来说，resize改变的是vector中元素的数量，而reserve改变的是vector的内存容量。

vector中push_back和emplace_back的区别？

emplace_back通常在性能上优于push_back，因为它可以避免不必要的复制或移动操作。

1. push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）

2. 而emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

Map，set，unordered_map，unordered_set，底层是用了什么数据结构？

1. Map: 底层实现通常是红黑树，这是一种自平衡的二叉查找树。它可以保证插入、删除和查找的时间复杂度都是O(log n)。

2. Set: 与Map类似，Set的底层实现通常也是红黑树。Set是一种特殊的Map，只有键没有值。

3. Unordered_map: 底层实现通常是哈希表。哈希表可以提供平均时间复杂度为O(1)的查找。

4. Unordered_set: 与Unordered_map类似，Unordered_set的底层实现通常也是哈希表。Unordered_set是一种特殊的Unordered_map，只有键没有值。

哈希表的时间复杂度为什么是O（1）？

哈希表的时间复杂度为O(1)是因为它使用了一种叫做哈希函数的方法来直接计算出数据应该存储在哪个位置，而不需要逐个检查每个位置。这就像是你有一个巨大的文件柜，每个抽屉都有一个唯一的编号，你可以直接通过编号找到你需要的文件，而不需要从第一个抽屉开始逐个查找。

当你插入、删除或查找一个元素时，哈希表首先使用哈希函数计算出元素的哈希值，然后使用这个哈希值作为索引直接访问到数组中的相应位置。因此，这些操作的时间复杂度都是O(1)。

哈希冲突怎么办？

如果多个元素的哈希值相同，那么这些元素就需要存储在同一个位置，通常是通过链表或者开放寻址的方式来解决。c++ stl 是采用了链表法来解决哈希冲突的问题。

网络相关

TCP和UDP有什么区别？

它们有以下区别：

1. 连接性：TCP 是一种面向连接的协议，而 UDP 是一种无连接的协议。这意味着在使用 TCP 传输数据之前，需要先建立连接，而 UDP 则不需要建立连接。

2. 可靠性：TCP 提供可靠的数据传输，它使用确认、重传和序列号等机制来确保数据的完整性和顺序性。而 UDP 则不提供这些机制，它是尽最大努力交付数据，不保证可靠性。

3. 速度：由于 TCP 需要进行连接的建立和数据的确认等操作，相对而言速度较慢。而 UDP 无需这些操作，速度较快。

4. 传输方式：TCP 是面向字节流的，它将数据分割成一系列的字节流进行传输。而 UDP 是面向数据报的，它将数据分割成数据报进行传输。

5. 数据包顺序：TCP 保证数据包按照发送的顺序进行接收，如果有丢失或乱序的数据包，TCP 会进行重传或重新排序。UDP 则不保证数据包的顺序，可能会出现乱序的情况。

6. 适用场景：由于 TCP 提供可靠的数据传输，适用于需要确保数据完整性和顺序性的应用，如文件传输、电子邮件等。而 UDP 适用于实时性要求较高、对数据可靠性要求较低的应用，如音视频传输、实时游戏等。

总的来说，TCP 提供可靠的、有序的数据传输，适用于对数据完整性和顺序性有要求的场景；而 UDP 则提供快速的、无连接的数据传输，适用于对实时性要求较高的场景。

UDP怎么实现可靠传输？

最简单的方式是在应用层模仿传输层TCP的可靠性传输。下面不考虑拥塞处理，可靠UDP的简单设计。

• 1、添加seq/ack机制，确保数据发送到对端
• 2、添加发送和接收缓冲区，主要是用户超时重传。
• 3、添加超时重传机制。

详细说明：送端发送数据时，生成一个随机seq=x，然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存，并发送一个ack=x的包，表示对方已经收到了数据。发送端收到了ack包后，删除缓冲区对应的数据。时间到后，定时任务检查是否需要重传数据。

滑动窗口是怎么实现的？

发送方的窗口，下图就是发送方缓存的数据，根据处理的情况分成四个部分，其中深蓝色方框是发送窗口，紫色方框是可用窗口：

img

• #1 是已发送并收到 ACK确认的数据：1~31 字节
• #2 是已发送但未收到 ACK确认的数据：32~45 字节
• #3 是未发送但总大小在接收方处理范围内（接收方还有空间）：46~51字节
• #4 是未发送但总大小超过接收方处理范围（接收方没有空间）：52字节以后

在下图，当发送方把数据「全部」都一下发送出去后，可用窗口的大小就为 0 了，表明可用窗口耗尽，在没收到 ACK 确认之前是无法继续发送数据了。

可用窗口耗尽

在下图，当收到之前发送的数据 32~36 字节的 ACK 确认应答后，如果发送窗口的大小没有变化，则滑动窗口往右边移动 5 个字节，因为有 5 个字节的数据被应答确认，接下来 52~56 字节又变成了可用窗口，那么后续也就可以发送 52~56 这 5 个字节的数据了。

32 ~ 36 字节已确认

接下来我们看看接收方的窗口，接收窗口相对简单一些，根据处理的情况划分成三个部分：

• #1 + #2 是已成功接收并确认的数据（等待应用进程读取）；
• #3 是未收到数据但可以接收的数据；
• #4 未收到数据并不可以接收的数据；

接收窗口

其中三个接收部分，使用两个指针进行划分:

• RCV.WND：表示接收窗口的大小，它会通告给发送方。
• RCV.NXT：是一个指针，它指向期望从发送方发送来的下一个数据字节的序列号，也就是 #3 的第一个字节。
• 指向 #4 的第一个字节是个相对指针，它需要 RCV.NXT 指针加上 RCV.WND 大小的偏移量，就可以指向 #4 的第一个字节了。

怎么理解TCP的流的概念？

当用户消息通过 TCP 协议传输时，消息可能会被操作系统分组成多个的 TCP 报文，也就是一个完整的用户消息被拆分成多个 TCP 报文进行传输。

这时，接收方的程序如果不知道发送方发送的消息的长度，也就是不知道消息的边界时，是无法读出一个有效的用户消息的，因为用户消息被拆分成多个 TCP 报文后，并不能像 UDP 那样，一个 UDP 报文就能代表一个完整的用户消息。

举个实际的例子来说明。

发送方准备发送 「Hi.」和「I am Xiaolin」这两个消息。

在发送端，当我们调用 send 函数完成数据“发送”以后，数据并没有被真正从网络上发送出去，只是从应用程序拷贝到了操作系统内核协议栈中。

至于什么时候真正被发送，取决于发送窗口、拥塞窗口以及当前发送缓冲区的大小等条件。也就是说，我们不能认为每次 send 调用发送的数据，都会作为一个整体完整地消息被发送出去。

如果我们考虑实际网络传输过程中的各种影响，假设发送端陆续调用 send 函数先后发送 「Hi.」和「I am Xiaolin」 报文，那么实际的发送很有可能是这几种情况。

第一种情况，这两个消息被分到同一个 TCP 报文，像这样：

图片

第二种情况，「I am Xiaolin」的部分随 「Hi」 在一个 TCP 报文中发送出去，像这样：

图片

第三种情况，「Hi.」 的一部分随 TCP 报文被发送出去，另一部分和 「I am Xiaolin」 一起随另一个 TCP 报文发送出去，像这样。

图片

类似的情况还能举例很多种，这里主要是想说明，我们不知道 「Hi.」和 「I am Xiaolin」 这两个用户消息是如何进行 TCP 分组传输的。

因此，我们不能认为一个用户消息对应一个 TCP 报文，正因为这样，所以 TCP 是面向字节流的协议。

当两个消息的某个部分内容被分到同一个 TCP 报文时，就是我们常说的 TCP 粘包问题，这时接收方不知道消息的边界的话，是无法读出有效的消息。

要解决这个问题，要交给应用程序。

TCP粘包，怎么解决？

粘包的问题出现是因为不知道一个用户消息的边界在哪，如果知道了边界在哪，接收方就可以通过边界来划分出有效的用户消息。

一般有三种方式分包的方式：

• 固定长度的消息；
• 特殊字符作为边界；
• 自定义消息结构。

固定长度的消息

这种是最简单方法，即每个用户消息都是固定长度的，比如规定一个消息的长度是 64 个字节，当接收方接满 64 个字节，就认为这个内容是一个完整且有效的消息。

但是这种方式灵活性不高，实际中很少用。

特殊字符作为边界

我们可以在两个用户消息之间插入一个特殊的字符串，这样接收方在接收数据时，读到了这个特殊字符，就把认为已经读完一个完整的消息。

HTTP 是一个非常好的例子。

图片

HTTP 通过设置回车符、换行符作为 HTTP 报文协议的边界。

有一点要注意，这个作为边界点的特殊字符，如果刚好消息内容里有这个特殊字符，我们要对这个字符转义，避免被接收方当作消息的边界点而解析到无效的数据。

定义消息结构

我们可以自定义一个消息结构，由包头和数据组成，其中包头包是固定大小的，而且包头里有一个字段来说明紧随其后的数据有多大。

比如这个消息结构体，首先 4 个字节大小的变量来表示数据长度，真正的数据则在后面。

struct { 
    u_int32_t message_length; 
    char message_data[]; 
} message;

当接收方接收到包头的大小（比如 4 个字节）后，就解析包头的内容，于是就可以知道数据的长度，然后接下来就继续读取数据，直到读满数据的长度，就可以组装成一个完整到用户消息来处理了。

操作系统相关

进程通信方式有哪些方式？

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，管道分为「匿名管道」和「命名管道」。

匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

命名管道突破了匿名管道只能在亲缘关系进程间的通信限制，因为使用命名管道的前提，需要在文件系统创建一个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信。另外，不管是匿名管道还是命名管道，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。

消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SIGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

以上，就是进程间通信的主要机制了。

信号和信号量有什么区别？

• 信号：一种处理异步事件的方式。信号是比较复杂的通信方式，用于通知接收进程有某种事件发生，除了用于进程外，还可以发送信号给进程本身。

• 信号量：进程间通信处理同步互斥的机制。是在多线程环境下使用的一种设施，它负责协调各个线程，以保证它们能够正确，合理的使用公共资源。

共享内存怎么实现的？

共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。

除了互斥锁你还知道什么锁？分别应用于什么场景？

还有读写锁、自旋锁、条件变量、信号量。

1. 读写锁：读写锁允许多个线程同时读取共享资源，但只允许一个线程进行写操作。适用于读操作频繁、写操作较少的场景，可以提高并发性能。

2. 自旋锁：自旋锁是一种忙等待锁，线程在获取锁时不会进入阻塞状态，而是循环忙等待直到获取到锁。适用于临界区很小且锁的持有时间很短的场景，避免线程频繁切换带来的开销。

3. 条件变量：条件变量用于线程间的同步和通信。它通常与互斥锁一起使用，线程可以通过条件变量等待某个条件满足，当条件满足时，其他线程可以通过条件变量发送信号通知等待线程。

4. 信号量：信号量是一种计数器，用于控制对共享资源的访问。它可以用来限制同时访问资源的线程数量，或者用于线程间的同步。

程序的内存布局是怎么样的？

虚拟内存空间划分

通过这张图你可以看到，用户空间内存，从低到高分别是 6 种不同的内存段：

• 代码段，包括二进制可执行代码；
• 数据段，包括已初始化的静态常量和全局变量；
• BSS 段，包括未初始化的静态变量和全局变量；
• 堆段，包括动态分配的内存，从低地址开始向上增长；
• 文件映射段，包括动态库、共享内存等；
• 栈段，包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

上图中的内存布局可以看到，代码段下面还有一段内存空间的（灰色部分），这一块区域是「保留区」，之所以要有保留区这是因为在大多数的系统里，我们认为比较小数值的地址不是一个合法地址，例如，我们通常在 C 的代码里会将无效的指针赋值为 NULL。因此，这里会出现一段不可访问的内存保留区，防止程序因为出现 bug，导致读或写了一些小内存地址的数据，而使得程序跑飞。

在这 7 个内存段中，堆和文件映射段的内存是动态分配的。比如说，使用 C 标准库的 malloc() 或者 mmap() ，就可以分别在堆和文件映射段动态分配内存。

初始化和未初始化的静态变量分别放在哪？

• 初始化的静态变量放在数据段里。
• 未初始化的静态变量放在BSS段里。

虚拟地址是怎么转化到物理地址的？

虚拟地址转化为物理地址是通过内存管理单元（Memory Management Unit，MMU）来完成的。MMU是计算机系统中的硬件组件，负责虚拟地址和物理地址之间的转换。

在虚拟地址转换的过程中，通常会使用页表（Page Table）来进行映射。页表是一种数据结构，它将虚拟地址空间划分为固定大小的页（Page），对应于物理内存中的页框（Page Frame）。每个页表项（Page Table Entry）记录了虚拟页和物理页的对应关系。

当程序访问一个虚拟地址时，MMU会将虚拟地址分解为页号和页内偏移量。然后，MMU会查找页表，根据页号找到对应的页表项。页表项中包含了物理页的地址或页框号。最后，MMU将物理页的地址与页内偏移量组合，得到对应的物理地址。

虚拟地址转化为物理地址的过程中，还可能涉及到多级页表、TLB（Translation Lookaside Buffer）缓存等机制，以提高地址转换的效率。

img

算法

• 写一个快速排序算法

• leetcode 题：k个一组，反转链表

面试感受

全程都在问八股文了，整体感觉是一层一层追着往下问，还好基本都准备过了，虽然没有回答很好，整体还是都回答了，遇到卡壳的地方，面试官还会善意提醒一下，面试体验太好了，算法快排生疏了没有 a 掉，第二个算法到是 a 掉了，一面是扛住了，不知道二面会问啥，这一次没问项目，二面我继续准备下项目问题吧。。。

历史好文：