面试问题

排序

时间复杂度与空间复杂
不同的排序的最好与最坏的时间复杂度
快排
1. 如何实现的
2. 何时会导致快排的最坏时间复杂度
3. 快排是否稳定，为什么不稳定
了解堆排序吗

算法

反转链表(Leetcode ＃206)

C++ 基础

C++ 关键字static，它的作用
C++ 关键字sizeof作用
- strlen与它的区别
- sizeof(“hello”)与strlen(“hello”)区别
- double (a) [3][6]; sizeof(*a)与sizeof(a)的大小
C++ 多态
- 如何实现
- 什么是虚函数，什么是虚表和虚拟指针
- 内存中的布局是什么样子的
C++ 重载与重写
- 什么是重载，什么是重写
- 它们的区别
- 重载是否与类有关，重载是如何实现的
C++ new/delete && malloc/free
- 它们的区别
C++ 的内存分区
- 说一下每个区的作用
C++ 堆栈的区别
C++ 编译执行的过程
C++ 深拷贝与浅拷贝的区别
C++ 11新特性有了解过哪些?
C++ 动态转换有了解过？
- 常见的几种动态转换说一下
- 它们的作用
C++ define 与 typedef
- define的功能与作用
- define 与 typedef 区别
C++ 内存泄漏的原因
C++ move
- move的使用与功能

C++ STL

你有用过哪些容器，可以讲讲
vector容器的底层实现
- map底层实现红黑树
有使用过迭代器吗

操作系统

进程间的通信方式
进程与线程的区别

计算机网络

讲一下TCP/IP的三次握手与四次挥手
- 三次握手
  - TCP/IP 是否可以为两次，为什么
  - TCP/IP 最后一个确认包server端一直接收不到，client应如何操作
- 四次挥手
  - 什么时候会进入Time_wait 等待状态，时间为多久
  - server 是否也会进入Time_wait 等待状态，什么状况会导致server进行这个状态

结束反问

面试官评价
- 指针使用仍有欠缺
- 对于一些底层原理应深入了解
- 操作系统还需要深入
面试官荐书
- 书箱大致属于一些经典书目
- 可以多阅读一些优秀的Blog，参考这些优秀博主的如何思考以及他们对于底层原理的解析

面试问题答案总结

排序

排序算法的时间复杂度与空间复杂度

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$	稳定
直接选择排序	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$	不稳定
直接插入排序	$O(n^{2})$	$O(n^{2})$	$O(n)$	$O(1)$	稳定
快速排序	$O(nlogn)$	$O(n^{2})$	$O(nlogn)$	$O(nlogn)$	不稳定
堆排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(1)$	不稳定
希尔排序	$O(nlogn)$	$O(ns)$	$O(n)$	$O(1)$	不稳定
归并排序	$O(nlogn)$	$O(nlogn)$	$O(nlogn)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
基数排序	$O(N * M)$	$O(N * M)$	$O(N * M)$	$O(M)$	稳定

快速排序

基本思想 * 通过一趟排序将待排记录分割成独立的两个部分，其中一部分关键字均比另一部分记录关键字小，接着对这两部分记录继续进行排序，以达到整个序列有序的目的。
最优与最坏情况分析
- 最优的情况：Parition每次都划分得很均匀。在获得枢轴后将数组一分为二，各自仅需$(n/2)$的时间，这是最好的情况，时间复杂度为$O(nlogn)$
- 最坏的情况：待排序的数组是正序或逆序，每次划分只得到一个比上一次少一个记录的子序列，这里另一个记录是为空的。如果用二叉树表示就是一个斜树,这里就需要n-1次递归调用，所以其最终时间复杂度为$O(n^{2})$
快排的不稳定的原因
- 关键字的比较是跳跃进行的，因此快排是不稳定的

堆排序

基本思想：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将其移走(实际就是将其与堆数组末尾元素交换，此时末尾元素为最大值),然后将剩余的n-1个序列重新构造成一个椎，这样就会得到n个元素中的次小值。之后重复之前的操作，就可以得到一个有序序列了
稳定性：由于记录的比较与交换是跳跃的，所以堆排序是一种不稳定的排序方式
适用场景：不适合待排序

算法

反转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        
        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

C++ 基础

C++ 用法与作用

隐藏: 在编译多个文件时，所有未加static前缀的全局变量与函数都具有全局可见性
保持变量内容的持久
static变量默认初始化为0
类成员声明为static
- static 变量只会被分配一次内存，因此它具有对值的记忆性
- static 全局变量可以被模块内所有函数访问，不可以被模块外的其它函数访问
- 类中static成员变量属于整个类，对类的对象仅有一份拷贝
- 类的static成员函数为这个类所拥有，这个函数不接收this指针，所以只可以访问类的static成员变量
- static类对象必须在类外进行初始化
- static成员函数不可以被virtul修饰

C++ sizeof用法与作用

定义： sizeof是一个操作符，作用是返回一个对象或类型所占的内存字节数
数组： sizeof(数组)的值等于数组所占用内存字节数
联合类型：操作数为联合类型时，sizeof的结果为其最大字节成员的字节数
内存对齐问题：由于结构体会自动对齐，所以sizeof的结果就是最大类型的所占用的字节数
类：空类大小为1，一个空类作为基类，它的大小为0。如果类的成员函数中有虚函数，就是固定占用4字节
strlen与它的区别
- sizeof 是运算符，strlen是库函数
- sizeof的参数可以为任何数据类型或者数据，strlen参数只能是字符指针且结尾为’\0’的字符串
- sizeof值在编译时确定，所以不能得到动态分配存储空间的大小
sizeof(“hello”) 与 strlen(“hello”)
- sizeof(“hello”) 结果为6
- strlen(“hello”) 结果为5，因为不包含’\0’
sizeof( * a)指向的是整个数组空间，所以大小为144。sizeof(a)指的是单个变量所占用的字节数，又因为指向double类型，所以为8字节

C++ 多态

如何实现多态
- 在基类的函数前加上virtual关键字，在派生类中重写该函数，运行时将会根据所指对象的实际类型来调用相应的函数。
多态实现过程
- 编译器发现类中在虚函数，会自动为其生成一份虚表，该表是一个一维数组，虚表里存储了虚函数入口地址
- 编译器会在对象的前四个字节中保存一个虚表指针，即vptr
- 调用构造函数，在构造函数中创建虚表并对其进行初始化
- 派生类对基类的虚函数没有重写，则派生类的vptr指向基类的虚表。有重写的话，派生类的vptr会指向自身的虚表。当派生类中有自己的虚表时，会将其添加在后面。
内存布局
- 单一继承的内存布局
  - 每个类最多只会有一个vptr指针，并放在第一个拥有virtual function 的类之后(父类必须保证对象的完整性)
  - virtual function 工作方式：可以通过vptr找到vtable，对应的vtable记录了所指对象的真正类型。vtable中第一个slot存储了type_info。对应的函数的真正的地址可以从vtable中的对应slot中找到。
- 多重继承下的内存布局
  - 根据继承父类的个数保存对应的vptr
  - 根据所保存的虚表指针个数，产生相应个数的虚表
  - 构造时会行构造会优先构造第一个基类
  - 多重继承中的菱形继承是存在二义性的风险的，即使可以通过明确调用路径，但是二义性的潜在性还未消除。
- 虚拟继承
  - 解决了菱形继承中，子类拥有多个间接父类实例的情况
  - 虚拟继承而来的子类会生成一个隐藏的虚基类指针，虚基类指针总是在vptr之后
  - 子类会覆盖基类的虚函数

C++ 重载与重写

重载是指在同一范围定义中的同名成员函数才存在重载关系,其特点为：
- 参数名相同
- 参数类型与数目有所不同
- 不能出现参数个数与类型均相同
重写指的是在派生类中的基类中的同名函数，重写就是重写函数体，要求基类函数必须是虚函数且
- 与基类的虚函数有相同的参数个数
- 与基类的虚函数有相同的参数类型
- 与基类的虚函数有相同的返回类型
区别
- 重写是父类与子类之间的垂直关系，重载是不同函数间的水来关系
- 重写要求参数列表相同，重载要求参数列表不同，返回值不要求
- 重写关系中，调用方法根据对象类型决定，重载根据调用时实参表与形参表的对应关系来选择函数体
重载的实现原理
- 利用命名倾轧技术(name mangling)，来改名函数名，区分参数不同的同名函数

C++ new/delete 与 malloc/free 区别

new/delete是C++ 关键字需要编译器支持；malloc/free 是库函数，需要头文件支持。
使用new申请的内存，编译器会自动计算分配大小；malloc申请的内存，需要手动计算大小
new 内存分配成功，返回的是对象的类型指针，无须强制类型转换；malloc分配内存成功后返回是void，需要强制类型转,所以malloc不安全。
new 内存分配失败会抛出bac_alloc异常，malloc分配失败会返回NULL
new/delete 会去调用constructor与deconstructor，而malloc/free 仅是对于资源的申请与释放

C++ 内存分区

一共分为六个区域，分别是：栈、自由存储区、堆、全局/静态存储区、常量存储区与代码区
简单说明各个分区的作用
- 栈：在函数中，函数内部局部变量的存储单元都可以在栈上创建，结束后自动释放。由于栈内置于处理器中，效率高，但是分配的内存有限
- 堆：就是那些由new分配的内存块，需要我们程序去控制。一个delete对应一个new，如果没有释放，程序结束后会由系统自动回收
- 自由存储区：全局变量与静态变量被分配到一块内存中，它们会被自动初始化
- 常量存储区：仅存放常量，不允许修改
- 代码区：存放函数体的二进制代码

C++ 堆栈的区别

申请方式不同
- 栈是由系统自动分配的
- 堆是由自己申请与释放的
申请的大小限制
- 栈顶与栈底是预设好的，栈是向栈底扩展，大小固定
- 堆向高地址扩展，是不连续的内存区域
申请效率不同
- 栈由系统分配，速度快，不会在碎片
- 堆是由程序员分配，速度会比较慢，且会有内存碎片
各自大小
- 栈默认4M
- 堆区一般为1G-4G

C++ 程序编译过程

具体为两步：编译、链接
编译可以细分为三个阶段
- 预编译处理
- 编译优化
- 转换成汇编
链接
- 需要链接原因：某个文件调用了另一个文件的函数或常量,或者是调用了某库函数
- 主要工作就是将有关目标文件连接起来

深拷贝与浅拷贝的区别

浅拷贝
- 浅拷贝只是拷贝一个指针，并没有新开辟一个地址，拷贝的指针与原来的指针指向同一块地址，如果原来的指针所指向的资源被释放了，那么再释放浅拷贝指针的资源就会出现错误。
深拷贝
- 深拷贝不仅影响值，还为其开辟一个新的空间来存放这个值。即使原先的对象被析构且内存被释放掉了，这也不会对深拷贝的值有所影响。在自己实现拷贝赋值时，如果有指针变量的话需要自己实现深拷贝的。

C++ 新特性有了解过哪些

nullptr替代了NULL
引入了auto与decltype这两个关键字，实现了类型推导
基于范围的for循环 for(auto& i : res) {}
类与结构体中初始化列表
Lambda表达式(匿名函数)
std::forward_list(单向链表)
右值引用与move语义
…..

了解C++四种强制转换

reinterpret_cast
- reinterpret_cast(expression)
- type_id必须是一个指针、引用、算术类型、函数指针或者成员指针。它可以用于类型之间的强制转换
const_cast
- const_cast(expression)
- 该运算符用来修改类型const与volatile属性。除了const与volatile修饰之外,type_id与expression的类型一致。用法如下：
  - 常量指针被转化为非常量的指针，并且仍然指向原来的对象
  - 常量引用被转化为非常量的引用，并且仍然指向原来的对象
  - const_cast一般用于修改底层指针，如const char *p形式
static_cast
- static_cast(expression)
- 该运算符把expression转换为type_id类型，但没有运行时类型检查来保证转换的安全性，主要有如下几种用法
  - 用于类层次结构中基类与派生类之间指针或引用的转换
    - 进行上行转换(把派生类指针或引用转换为基类表示)是安全的
    - 进行下行转换(把基类的指针或引用转换为派生类表示)时，由于没有动态类型检查，所以是不安全的。
- 用于基本数据类型之间的转换,如int转换为char，int转换为enum。这种类型的转换的安全性需由开发者来保证
- 把空指针转换为目标类型的空指针
- 把任何类型的表达式转换为void类型
- static_cast 不能转换expression的const、volatile、_unaligned属性
dynamic_cast
- dynamic_cast(expression)
- 在类型检查，基类向派生类转换是安全的，但是派生类向基类转换就有一些不安全
- 该运算符把expression转换为type_id类型。type_id必须是类指针、类的引用或void *
- 如果type_id 是指针类型，那么expression也必须是一个指针，如果type_id是一个引用，那么expression也必须是一个引用
- 这个转换是可以在执行期间决定真正的类型，因此expression必须是多态。
- 在类之间进行转换，dynamic_cast与static_cast的效果一样
- 在进行上下转换时，dynamic_cast具有类型检查功能,比static_cast功能

C++ define 与typedef

宏主要用于定义常量及书写复杂的内容；typedef 主要用于定义类型别名
宏替换发生在编译阶段，属于文本插入替换；typedef是编译的一部分
宏不检查类型；typedef会检查数据类型
宏不是语句，不用在最后添加分号；typedef 是语句，要加分号标识
注意对指针的操作，typedef char * p_char与#define p_char char * 区别巨大

C++ 内存泄漏原因

定义
- 内存泄漏是指堆内存的泄漏。堆内存是指程序从堆中分配的大小任意的内存块。如果通过new/malloc申请意资源后，没有使用delete/free来释放，那么这个内存块将不可被再次使用，这就是内存泄漏。
泄漏的几种情况
- 基类的析构函数没有申明为虚函数
- 对象数组没有使用delete[]来释放
- new/delete,malloc/free 必须成对出现

C++ move语义

作用
- 独享指针所有权的转移
- 左值到右值属性的转移

C++ STL

使用过哪些容器

vector
map
set
…

vector容器的底层实现

vector 是一个类似于array的序列容器。但是array维护的是静态空间，而vector则使用灵活的动态空间配置,维护一块连续的线性空间。在空间不足时，可以自动扩充空间容纳新元素。扩充时也需经历的有：重新配置空间、移动数据、释放原空间行操作
vector 扩充规则
- 以原大小的两倍配置另外一块较大空间(或者旧长度+新增元素个数)(Win+Vs下扩展1.5倍，Linux+GCC扩展是两倍)

迭代器使用

迭代器是一种抽象的设计理念，通过迭代器可以在不了解容器的情况下遍历容器。除此之外，它还是作为容器与STL算法的重要粘合剂。
迭代器的作用就是提供一个遍历容器内部所有元素的接口，因此容器内部必须保存一个与容器相关联的指针
常用的五种迭代器： value type、different type、pointer、reference、iterator catagoly;

操作系统

进程间的通信方式(Linux)

管道
- 无名管道(内存文件): 管道是一种半双工的通信方式，数据只能单向的流通，而且只能在具有亲缘关系的进程之间使用。(进程的亲缘关系：父子进程关系)
- 有名管道(FIFO文件，借助文件系统): 有名管道是半双工的通信方式，但是允许在没有亲缘关系的进程之间使用，管道是先进先出的通信方式
共享内存：映射一段能被其它进程所访问的内存，这段共享内存是由一个进程创建，可由多个进程访问。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而设计的。它往往与信号量配合使用来实现进程间的同步与通信
消息队列：消息队列是有消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
套接字：适用于不同的机器间进程通信，在本地也可作为两个进程通信的方式
信号：用于通知接收进程某个事件已经发生，比如按下Ctrl+c就是信号。
信号量：这是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，实现进程、线程的对临界区的同步及互斥访问

进程与线程

定义
- 进程是资源分配与拥有的基本单位；线程是程序执行的基本单位
切换过程
- 进程是：用户态->内核态->用户态;线程是与其一致
拥有的资源
- 进程拥有CPU资源、内存资源、文件资源与句柄；线程拥有程序计数器、寄存器、栈与状态字。
并发性
- 不同的进程之间acrq实现并发，各自占有CPU实现并行;一个进程内部的多个线程并执行。
通信方面
- 进程间通信需要借助操作系统；线程间可以直接读写进程数据段。

计算机网络

TCP/IP的三次握手
刚开始客户端处于Closed的状态，服务端处于Listen状态，进行三次握手

第一次握手：客户端给服务端发一个SYN报文，并指明客户端的初始化序列号ISN(c)。此时客户端处于SYN_SEND状态
- 首部的同步位SYN=1,初始化seq=x,SYN=1的报文段不能携带数据，但要消耗一个序列号
第二次握手：服务器收到客户端SYN报文之后，会以自己的SYN报文作为应答，并且也是指定了自己的初始化ISN(s)。同时会把客户端的ISN+1作为ACK的值，表示自己已经收到了客户端的SYN，此时服务器牌SYN_RCVD的状态
- 在确认报文段中SYN=1,ACK=1,确认号ack=x+1,初始序号seq = y.
第三次握手：客户端收到SYN报文之后，会发送一个ACK报文，当然，也是一样把报务器的ISN＋1作为ACK的值，表示已经收到了服务端的SYN报文，此时客户端牌ESTABLISHED状态。服务器收到ACK报文之后，也处于ESTABLISHED状态，此时，双方已经建立起了连接
- 确认报文段ACK＝1，确认号ack=y+1,序号seq=x+1(初始为seq=x,第二个报文段所以要＋1),ACK报文段可以携带数据，不携带数据则不消耗序号。

发送第一个SYN的一端执行主动打开(avtive open),接收这个SYN并发回下一个SYN的另一端执行被动打开(passive open)。在socket编程中，客户端执行connect()时，将触发三次握手。

TCP/IP是否可以为两次，为什么

弄清这个问题，我们需要先弄明白三次握手的目的是什么，能否使用再次握手达到目的。
- 第一次握手：客户端发送网络包，服务端到了。这样服务端就能得出结论：客户端的发送能力、服务端的接收能力正常。
- 第二次握手：服务端发包，客户端到了。这样客户端就能得出结论：服务端的接收、发送能力，客户端的接收、发送能力是正常的。不过此时服务器并不能确认客户端的接收能力是否正常。
- 第三次握手：客户端发包，服务端收到了。这样服务端就能得出结论：客户端的接收、发送能力正常，服务器自己的发送、接收能力也正常。
因此，需要三次握手才能确认双方的接收与发送能力是否正常。
如果使用两次握手，则会出现以下这种情况
- 客户端发出连接请求，但因连接请求报文丢失而未收到确认，于是客户端再重传一次连接请求。
- 后来收到确认，建立连接。数据传输完毕后，就释放连接，客户端共发出两个连接请求报文段，其中第一个丢失，第二个到达了服务端。
- 但是第一个丢失的报文段只是在某些网络结点长时间滞留了，延误到连接释放以后的某个时间才到达服务端。
- 此时服务端误认为客户端又发出一次新的连接请求，于是就向客户端发出确认报文段，同意建立，不采用三次握手，只要服务端发出确认，就建立新的连接了。
- 此时客户端忽略服务端发来的确认，也不发送数据，则服务端一致等待客户端发送数据，浪费资源。

TCP/IP最后一个确认包server端一直接收不到，client应如何操作

SYN-ACK重传次数的问题：服务器发送完SYN-ACK包，如果未收到客户确认包，服务器进行首次重传，等待一段时间仍未收到客户确认包，进行二次重传。如果重传次数超过系统规定的最大重传次数，系统将该连接信息从半连接队列中删除。(每次重传等待的时间不一定趋同，一般会是指数增长，例如间隔时间为1s,2s,4s,8s…)

TCP/IP 四次挥手
刚开始双方都处于ESTABLISHED状态,假如是客户端先发起关闭请求。四次挥手的过程如下:

第一次挥手：客户端发送一个FIN报文，报文中会指定一个序列号。此时客户端牌FIN_WATI1状态。即发出连接释放报文段(FIN=1,seq=u),并停止再发送数据，主动关闭TCP连接，进入FIN_WATI1状态(终止等待1)状态，等待服务端的确认。
第二次挥手：服务器收到FIN之后，会发送ACK报文，且把客户端的序列号值+1作为ACK报文的序列号值，表明已经收到客户端的报文了，此时服务端处于CLOSE_WAIT(关闭等待)状态，此时的TCP处于半关闭状态，客户端到服务端的连接释放。客户端收到服务端的确认后，进行FIN_WATI2(终止等待2)状态，等待服务端发出的连接释放报文段。
第三次挥手：如果服务端也想断开连接了，和客户端的第一次挥手一样，发给FIN报文，且指定一个序列号。此时服务端处于LAST_ACK状态。即服务端没有要向客户端发出的数据，服务端发出连接释放报文(FIN=1,ACK=1,seq=w,ack=u+1),服务端进入LAST_ACK(最后确认)状态，等待客户端的确认。
第四次挥手：客户端收到FIN之后，一样发送一个ACK报文作为应答，且把服务器端的序列号值+1作为自己ACK报文的序列号值，此时客户端处于TIME_WAIT，。需要过一阵子以确保服务端收到自己的 ACK 报文之后才会进入 CLOSED 状态，服务端收到 ACK 报文之后，就处于关闭连接了，处于 CLOSED 状态。即客户端收到服务端的连接释放报文段后，对此发出确认报文段（ACK=1，seq=u+1，ack=w+1），客户端进入TIME_WAIT（时间等待）状态。此时TCP未释放掉，需要经过时间等待计时器设置的时间2MSL后，客户端才进入CLOSED状态。
收到一个FIN只意味着在这一方向上没有数据流动。客户端执行主动关闭并进入TIME_WAIT是正常的，服务端通常执行被动关闭，不会进入TIME_WAIT状态。在socket编程中，任何一方执行close()操作即可产生挥手操作。

何时会进入TIME_WAIT等待状态，多长时间，为什么是那么长时间

当收到一个FIN只意味着这一方向上没有数据流动。客户端执行主动关闭并进入TIME_WAIT。
2msl，理论上，四个报文者发送完毕，就可以直接进入CLOSED状态了，但是可能网络是不可靠的，在可能最后一个ACK丢失。所以TIME_WAIT状态就是用来生性可能丢失的ACK报文。

server是否也会进入TIME_WAIT状态，什么情况会导致server进行这个状态

会的，出现在高并发短连接的TCP服务器上

Rabbet

腾讯光子一面

面试问题

排序

算法

C++ 基础

C++ STL

操作系统

计算机网络

结束反问

面试问题答案总结

排序

算法

C++ 基础

C++ STL

操作系统

计算机网络