C/C++

【必问】一个C程序编译步骤是什么？每一个步骤做了什么？

1. 预处理：各种宏展开、注释去掉、头文件引入

2. 编译：编译代码，生成汇编码

3. 汇编：汇编代码，生成二进制文件

4. 链接：链接各种库（包括动静）

【必问】一个局部变量被加上static修饰，会发生什么？

1. 只会被初始化一次

2. 位置移动到全局区

3. 生命周期延长至程序结束

【必问】全局变量使用static修饰，会发生什么？

1. 依旧是全局的，也位于全局区

2. 但是只能是本文件访问，其他文件不能访问

【必问】const修饰指针，写在前面和后面有什么区别？

1. 星号在末尾：指针指出的那个值不能被修改

2. 星号在中间：指针本身这个地址不能被修改

【必问】inline vs #define的区别是什么？

1. inline是建议编译器去做内联，它不仅仅是简单的替换，编译器会做校验的，它的内联是在编译阶段

2. define只是宏定义，它只是简单的替换，而且是在预处理阶段就发动

【必问】sizeof vs strlen对字符串操作的差别在哪？

1. sizeof是一个关键字、一个运算符，他会考虑\0的

2. strlen只是个函数，不考虑\0

【必问】野指针的成因有哪些？野指针如何避免？野指针和悬垂指针的区别？

1. 前：使用前未初始化

2. 中：各种访问越界

3. 后：使用已销毁的局部变量的地址

避免：就是针对上面的做出反制即可

1. 使用前记得初始化

2. 越界安全检查

3. 函数不要返回局部变量地址

悬垂指针：

1. 这个指针曾经指向过有效的地址，但是后来指向的区域销毁了，但是指针未置空

2. 野指针就从来没指对过

【必问】数组指针 vs 指针数组有什么不同？

1. 数组指针：就是一个指针，但是指向数组：int (*a)[]，星号在括号内

2. 指针数组：就是一个数组，里面存指针：int* a[]，没有括号

【必问】值传递和地址传递有什么不同？那些数据默认使用值传递？

1. 值传递会拷贝一份一模一样的数据，地址传递传的是地址，会对原来的数据有影响

2. 除了指针和数组，都是值传递，包括一个很大的结构体

【必问】指针函数 vs 函数指针有什么不同？

1. 指针函数：就是一个函数，返回一个指针：int* f()

2. 函数指针：就是一个指针，指向一个函数：int (*f)()，星号在括号内

【必问】C语言 vs C++有什么区别？

1. C++有面向对象，封装继承多态，C没有

2. C++有泛型编程、模版，C没有

3. C++是强类型语言，C是弱类型

【必问】Linux运行C++程序的进程内存布局？

从高地址到低地址：

1. 环境变量

2. 栈，一般的局部变量都在这里

3. 共享文件存储映射之MMAP，动态库也会被映射到这里

4. 堆，new malloc

5. 全局数据区，静态变量 + 全局变量

6. 只读数据段，虚函数表、const 静态变量、const 全局变量

7. 代码段，你的代码

【必问】malloc() vs new有什么区别？

1. malloc只是一个函数，它只是分配了一下内存，没有初始化，malloc还需要转换

2. new是C++独有（C没有）的关键字，他不只会分配内存，还会调用构造函数；new还可以重载

【必问】C++引用是什么？做什么的？

1. 给变量取一个别名

2. 其本质为const指针，即指针的地址不能改变，但是指出的值可以改变

3. 所以说引用必须初始化，不然由于其地址不可改变，他会一直处于野指针的状态

【必问】什么是函数重载？它有什么用？

1. 函数名相同

2. 返回值无所谓

3. 参数数量或类型不能相同

【必问】C++类型转换有几种，分别是做什么的？

1. static_cast：一般的类型转换

2. dynamic_cast：父子指针之间的转换

3. const_cast：const和非const之间的转换

4. reinterpret_cast：（是这么拼写吗？）一些指针类型的转换，比较少用

【必问】面向对象思想之一的封装是什么？为什么需要封装？

1. 把成员和成员方法都放到一起，方便调用

2. 有访问权限控制

【必问】类成员的访问权限有几种？分别是什么？

1. public：大家都可以访问

2. protected：子类可以访问

3. private：自己可以访问

【必问】构造函数和析构函数是什么？

1. 构造：成员的初始化

2. 析构：对象即将销毁，这时释放类里的一些指针成员

【必问】深拷贝 vs 浅拷贝有什么区别？浅拷贝需要注意什么？

1. 浅拷贝：直接复制，所有的元素直接复制，包括指针；这样导致两个指针指向同一个内存，可能被释放两次

2. 深拷贝：不仅是直接复制，指针指向的内存区域也会复制一份新的

【必问】类的静态成员是什么？

1. 静态成员和静态方法都不属于任何一个类了，而是只属于对象

2. 静态成员会被放到全局区

3. 静态方法的话，函数本来就在代码段，所以静态方法依旧在代码段

4. 静态方法只能调用静态成员，因为没有 this 指针

【必问】空对象占用内存空间为？

1. 大小为 1，如果大小为 0，那么他会和下一个东西同地址

【必问】C++友元是什么？为什么需要友元？

1. 让其他的类或函数能访问类的私有成员

2. 友元可以是类、也可以是函数

【必问】C++子类继承父类时，使用不同的继承方式，成员访问权限如何被继承？

1. public继承：public变public，protected变protected，private父类私有

2. protected继承：public变protected（最大不能超过protected），protected变protected，private父类私有

3. private继承：public变private（最大不能超过private），protected变private（最大不能超过private），private父类私有

【必问】父类、子类、成员对象的构造和析构顺序是什么？

1. 构造顺序：按继承顺序从左到右的虚基类->按继承顺序从左到右的非虚基类->成员->自己

2. 析构顺序：上述的构造顺序完全相反

【必问】多继承会造成什么问题？菱形继承是什么？如何解决？

1. 问题：某些父类被继承多个副本，造成冗余，甚至逻辑出错

2. B和C都继承自A，但是D继承自B和C，这就会导致上述的那个问题

3. 解决：虚继承，让所有的父类都只有一个副本

【必问】虚基类指针和虚基类表是什么？

1. 如果某个类虚继承自某个类，他就会有虚基类指针

2. 虚基类指针指向虚基表，虚基表记录父类的内存位置偏移量，各个子类（B、C）里面的某个父类（A）的偏移量都指向的是同一个父类（A）

【必问】多态是什么？分为哪两类？为什么需要多态？

1. 静态多态：函数重载、运算符重载、模板

2. 动态多态：虚函数机制

3. 为什么需要：提升抽象层次

【必问】覆盖重写 vs 函数重载有什么区别？

1. 函数重载：函数名相同，返回值无所谓，参数不同

2. 覆盖重写：父子之间，函数名相同、返回值相同、参数相同（函数签名完全一致）

【必问】动态多态，底层原理是什么？

1. 父类指针、子类对象、虚函数覆盖重写

2. 对象内部有虚函数表，指针指向子类的虚函数表

【必问】抽象类是什么？抽象类的特点是什么？为什么需要抽象类？

1. 让一个虚函数=0就是纯虚函数，有至少一个纯虚函数的类就是抽象类

2. 抽象类不能实例化

3. 为什么需要：提升抽象层次，父类提供接口，子类实现即可

【必问】虚析构是什么？为什么需要虚析构？

1. 析构函数是虚函数

2. 为什么需要：在多态的时候，子类有内存需要释放，这时必须使用子类的析构函数；如果析构函数不是虚函数，那么调用的是父类的析构函数，那么有些内存无法正常释放

【必问】虚函数表的创建时机？虚基类表创建的时机？

1. 都是编译期确定的

2. 而虚函数指针和虚基类表指针则是在对象构造的时候创建

【必问】虚函数表存储在内存的哪里？vptr存储在内存的哪里？

1. 表存储在只读数据段

2. vptr跟随对象，对象在栈上就在栈上、也有可能在堆、全局区

【必问】类模板 vs 函数模板的区别？

1. 类模板不能做自动推导，函数模板可以

2. 类模板可以有默认参数

【必问】STL是什么？为什么需要STL？它的六大组件是什么？

1. 标准模板库，为什么需要？为了便捷

2. 六大件：容器、算法、仿函数、迭代器、适配器、空间配置器

【必问】STL容器大概分为哪两类？每种容器都属于哪类？

1. 顺序：vector、deque、list

2. 非顺序：set、map、unordered_set、unordered_map

【必问】假设在capacity为n的时候，此时size也是n，我在插入一个数据，capacity变为多少？vector的扩展机制能详细讲讲吗？

1. 超过 capacity，触发扩容

2. 开辟新内存，大小是 1.5 倍或者 2 倍

3. 把数据复制过去

4. 释放原有内存

【必问】vector插入数据没有超过capacity大小也会整体移动空间吗？迭代器也会失效吗？

1. 没有超过 capacity，不会扩容

2. 如果没有扩容，只有插入的位置及其以后会失效，如果扩容，所有迭代器失效

3. 删除不会缩容，所以只有删除的位置及其以后会失效

【必问】list是什么？它的底层如何实现？

1. 双向链表，对头结点和尾结点的操作复杂度都很低

【必问】set是什么？它的底层如何实现？

1. 自动排序的集合，底层是红黑树

【必问】map是什么？它的底层如何实现？

1. 自动排序的 pair 对组，底层是红黑树

【必问】unordered_map是什么？它和map从底层实现来说有什么不同？

1. 是哈希表

2. 一个是哈希表，一个是红黑树，完全不一样好吧

【必问】array、vector、deque、list、set、map、unordered_map的插入删除查询的时间复杂度？

1. array：都是O（N）

2. vector：都是O（N），但是尾O（1）

3. deque：都是O（N）

4. list：都是O（N），但是头尾O（1）

5. set、map：因为是红黑树，所以是O（log N）

6. unordered_map：因为是哈希表，所以是O（1）

【必问】仿函数是什么？

1. 在一个类里重载小括号，就可以像使用函数那样使用这个类

【必问】说说你知道的算法头文件、以及一些常用的算法？

1. 头文件：algorithm、numeric

2. sort排序

3. max_element最大值

4. find查找

5. reverse翻转

【必问】迭代器是什么？和指针的区别？

1. 迭代器是模版类，里面封装了指针，是一个包含的关系

【必问】decltype vs auto的区别？

1. auto：去除引用信息、去除顶层const

   1. 顶层const是什么？->本身是const

   2. 底层const->指针指出的是const->所以引用他也是顶层const，因为是指针本身不可变

2. decltype：引用信息、顶层const都是在的

   1. decltype表达式推导：左值->左值引用，纯右值->纯右值，亡值->右值引用

【必问】lambda表达式的捕获方式有哪几种？

1. 值捕获

2. 引用捕获

3. 捕获this指针

4. 可以混合使用

【必问】lambda表达式本质是什么？为什么引用捕获可以修改值，值捕获就必须加mutable才能修改？

1. 它经过编译之后是一个类

2. 值捕获的变量会拷贝一份，是这个类的成员；引用捕获的变量依然在外部

3. lambda的小括号部分是这个类的重载小括号的参数（仿函数）

4. 这个仿函数是默认const，const常函数->锁定this为const->导致所有变量除了mutable都不可修改

【必问】std::function vs Lambda表达式有什么不同？

1. function：本质是一个模板类，是一个通用的函数包装器，它不能转化为lambda

2. lambda：本质是一个类且重载小括号，可以捕获外部变量，他可以转化为function

【必问】移动构造函数是什么？

1. 格式：X(X&&) {}

2. 参数是右值引用，传进来的东西需要窃取他的资源，不然两个指针指向一个资源，释放会有问题

3. 从本质上来讲，它没有复制任何东西，比复制构造快

【必问】std::bind是做什么的？

1. 给函数绑定一部分参数，得到新的函数

2. 类中的方法必须绑定到一个对象而不能单独使用，这时候就必须使用bind

【必问】左值是什么？右值是什么？

1. 左值可以取地址，右值不行

2. 左值变右值->move

3. 右值变左值->const A&

4. 右值引用：A&&

【必问】完美转发是什么？

1. 有一个需求，在一个函数里要把参数转发到内层函数，但是左值要保持为左值，右值要保持为右值，如何做？

2. T&&：模板万能引用：左值->左值引用，右值->右值引用

3. forward：转发函数：左值引用->左值，右值引用->右值

4. 这就实现了完美转发

【必问】std::move vs std::forward？

1. move：一切->右值

2. forward：右值引用->右值，其他不变

【必问】shared_ptr循环引用怎么解决？weak_ptr是什么？

1. 循环引用是什么？两个类互相持有对方的shared_ptr，导致引用计数无法归零，导致无法释放

2. 使用weak_ptr解决，weak_ptr只做观察，不影响生命周期

3. 当有任何一方持有弱指针时，另一方只有自已的一个shared_ptr，可以被正常释放，那对方正常释放了，我方自然也能正常释放

【必问】unique_ptr是什么？

1. unique_ptr也是一种智能指针，它不能有多个unique_ptr来控制同一个对象，一个unique_ptr管理一个对象

2. unique_ptr不能复制，但可以移动

【必问】make_shared为什么效率更高？

1. 原本智能指针需要new，他管理的对象也需要new

2. make_shared把两个步骤合为一个操作，只需要new一次，效率高；而且是一步操作，要么都成功要么都失败，非常安全，不会出现一个new成功，一个失败的情况

【必问】智能指针的线程安全问题？

1. 智能指针本身是安全的，它的引用计数都是原子操作，无须担心

2. 智能指针管理的对象不是安全的，需要加锁

【必问】模版的特化和偏特化是什么？

1. 全特化：所有的模版参数都被确定

2. 偏特化：只有一部分模板参数确定

【必问】如何妙用std::lock函数防止死锁？

1. lock内部有机制，例如按照锁的地址排序，这样严格按照顺序加锁能防止死锁

2. lock_guard使用adopt_lock表示已经被lock加过锁，这里不要再加锁

【必问】unique_lock是什么？他和lock_guard有什么不同？

1. unique_lock就是一种锁，但是他可以主动解锁

2. 代价是什么呢？效率有所降低

【必问】协程是什么？协程 vs 线程的区别？

1. 协程就是一种特殊的函数，它能够暂停然后让线程被调度去执行其他任务；还能恢复运行状态，能从上次执行的点接下去继续执行

2. 协程又被叫做用户态线程，轻量级，切换开销小，不涉及系统调用

3. 使用灵活，可以手动调度

【必问】设计模式有哪三大类？

1. 关乎于类的创建

2. 关乎于类与对象的关系

3. 关乎于类之间的通信

【必问】设计模式有哪些原则？重点：开闭原则是什么？

1. 单一职责：一个类最好只负责一个内容

2. 接口隔离：不要涉及过于臃肿的接口

3. 开闭原则：对修改封闭，对扩展开放

4. 里氏替换：可以使用子类完美替换父类

5. 依赖倒置：代码要提升抽象层次

【必问】单例模式是什么？有何应用？

1. 全局只有一个实例

2. 有一个全局访问点

3. 应用：日志、配置

操作系统

【必问】说说几个知道的Linux命令？

1. ls cd

2. pwd

3. touch cat mkdir cp mv

4. chmod

5. ……

【必问】用户态 vs 内核态有什么区别？

1. 本质问题：权限问题->用户态用户权限低，不能使用系统调用，内核态权限高，能使用系统调用

【必问】请描述系统调用的整个流程？

1. 用户态发起系统调用

2. 中断！

3. 保存当前运行环境，进入内核态

4. 执行系统调用，获得返回值

5. 返回用户态，还原之前的运行环境

【必问】fflush是什么？fsync是什么？他们有什么区别？

1. fflush是库函数，他只是把文件内容刷到缓冲区

2. fsync是系统调用，它把缓冲区的内容真正落盘

3. 如果没有使用缓冲区机制，那也能直接落盘

【必问】请描述一次CPU读内存的完整流程，从虚拟地址到拿到数据？

1. 查内存虚拟地址->MMU->获得物理地址

2. 查物理地址->先查缓存L1、L2、L3

3. 最后查内存，把数据返回

【必问】说说页面置换算法？

1. 页面置换就是在缺页中断时，把页换到内存里

2. 怎么换？最近最少使用算法（LRU）或者时钟置换算法

【必问】说几个内存泄漏检测方法？

1. 代码级：hook malloc、mtrace

2. 工具级：valgrind、ebpf

【必问】delete或free释放内存的时候并不知道内存大小，如何释放？new/delete/malloc/free全讲解！

1. new的本质：分配内存+构造函数，delete的本质：析构函数+释放内存

2. new分配内存默认使用malloc->malloc会在小于128K的时候使用内存池，内存池用完会使用系统调用 brk，在大于128K时，malloc使用mmap

3. malloc会在分配内存的时候偷偷使用chuck来记录分配内存的大小，chunk的地址在实际返回的指针地址之前；free的时候再去读chunk就知道该释放多少

4. new[]在分配内存的时候偷偷使用一个区域来记录数组元素个数，这个区域在malloc分配的指针之后、实际返回的指针地址之前，delete[]读这个区域知道该释放几个元素

【必问】malloc分配的内存分配到物理内存还是虚拟内存？何时才会拥有物理内存？

1. 分配到的都是虚拟内存

2. 当第一次使用这块内存的时候，引发缺页中断，这时候才会拥有物理内存

【必问】内存池是什么？为什么需要内存池？

1. 内存池就是一块已经申请好了的内存，使用完后内存返回内存池

2. 使用内存池可以避免诸如brk之类的系统调用，非常快捷

3. 由于内存池是一整块，还可以减少内存碎片

【必问】CAS是什么？

1. CAS是比较和交换，如果比较值一样就交换，反之不交换

2. CAS的底层需要使用硬件指令保持原子性

3. CAS可以制作无锁队列、自旋锁

【必问】如何使用CAS实现无锁栈/队列？

1. 入栈时：获取top并把新节点指向top，然后尝试把头指针指向新节点，若失败，说明两个步骤之间有人修改了top，则重试

2. 出栈时：获取top，然后尝试把头指针指向top的next，若失败，说明两个步骤之间有人修改了top，则重试

【必问】内存序是什么？有哪些内存序？

1. 内存序就是从另一个线程的视角来看，此线程的指令重排的顺序

2. cst：没有任何一条指令会被重排

3. relax：任何指令都可能重排

4. acquire：该指令之后的内容不会被重排到它之前

5. release：该指令之前的内容不会被重排到它之后

6. acquire+release

【必问】说说你的死锁检测方法？

1. hook操作系统原生创建锁和销毁锁的方法

2. 给锁建立图，即A线程需要B的锁，那就有边AB

3. 检测图是否成环，若有环，则死锁

【必问】gdb的多线程调试如何进行？

1. 查看所有线程：info threads

2. 切换线程：thread <线程ID>

3. 为特定线程设置断点：break <位置> thread <线程ID>

4. 锁定其他线程（只调试当前线程）：set scheduler-locking on

5. 恢复所有线程调度：set scheduler-locking off

6. 查看线程调用栈：bt（backtrace）

【必问】你使用什么测试工具？

1. gtest，做单元测试时可用

【必问】你使用什么性能分析工具？

1. valgrind：内存泄露检测专用，也可以性能分析，但需要完整跑一遍代码，很慢

2. gprof：更轻量级，但是分析效果一般

3. perf：也很轻量级，但效果很好，还可以生成火焰图

【必问】静态库 vs 动态库有什么区别？

1. 静态库会和你的代码一起被打包到最终的可执行文件里，文件会变得很大，但是都放进来了就不会出错

2. 动态库则是不会和你的代码一起打包，而是运行时去查阅动态库，万一没查到就会报错

【必问】进程是什么？

1. 一个可执行程序，正在运行，那就是进程

2. 进程是操作系统资源管理的最小单位

3. 有自己的独立运行空间

【必问】并行 vs 并发有什么区别？

1. 并行：真正的同时执行

2. 并发：多个任务交替执行，看起来像同时执行的一样

【必问】进程的三态模型和五态模型是什么？进程的状态切换过程请大致描述下？

1. 初始态：刚创建，创建之后变为就绪

2. 就绪态：可以被立即调度，被调度之后变成运行态

3. 运行遇到阻塞，变为阻塞态，运行被其他高优先级进行抢占，变为就绪态

4. 运行结束之后变为结束态

【必问】fork()函数之后如何区分父子进程？

1. 子进程：返回值为 0

2. 父进程：返回值为子进程的 pid

【必问】孤儿进程是什么？孤儿进程有危害吗？

1. 子进程存活，但父进程已结束，这时子进程会被 init 进程接收

2. 孤儿进程没有危害

【必问】僵尸进程是什么？僵尸进程有危害吗？

1. 父进程存活，但子进程已结束，父进程一直不回收子进程的资源

2. 僵尸进程有危害，因为一直不回收资源，产生的垃圾会越来越多

【必问】进程通信一共有几种方法？

1. 无名管道

2. 有名管道

3. MMAP

4. 共享内存

5. 信号

6. 条件变量

7. 信号量

8. 本地套接字

9. 消息队列

【必问】无名管道有哪些特点？

1. 单向通信，一端读一端写

2. 没有实体，只存在内存里

3. 只能进行父子进程通信

【必问】命名管道 vs 无名管道有什么不同？

1. 有实体文件，有名字

2. 可以进行非父子进程之间的通信

【必问】共享文件存储映射 vs 共享内存有什么区别？

1. MMAP依赖于文件，每个进程有独立的映射区域；共享内存使用的真的是同一内存

2. MMAP支持持久化；共享内存不支持

3. MMAP性能差；共享内存依赖内存，性能高

【必问】如何避免僵尸进程？

1. 使用信号，父进程提前捕获 SIGCHD 信号，检测子进程是否结束

2. 若检测到结束，循环调用 waitpid（防止突然多个子进程都突然结束）

【必问】说说进程调度/线程调度算法？

1. 先来先服务：不行

2. 时间片调度：古老

3. 优先级队列：古老

4. 多级队列：古老

5. 优先级多级反馈队列：OK

【必问】守护进程是什么，为什么需要他？

1. 守护进程是孤儿进程，没有父进程

2. 守护进程脱离终端，在后台执行

3. 这样可以使得一些特殊程序避免受到终端的问题的影响，让它们可以一直执行

【必问】线程是什么？

1. 进程中的执行单位，就是线程

2. 线程是CPU调度和执行的最小单位

【必问】线程 vs 进程有什么区别？

1. 线程依附于进程，进程不依附于线程

2. 进程负责资源管理，线程负责执行和调度

3. 进程具有隔离性，线程没有

【必问】如何避免僵尸线程？

1. join 线程

2. detach 线程

【必问】同步 vs 互斥有什么区别？

1. 同步是两个任务之间必须按顺序执行

2. 互斥只是说两个任务不能并发执行，不强调顺序

【必问】同步=阻塞？异步=非阻塞？

1. 同步不一定阻塞，异步也不是非阻塞

2. 同步强调两个任务之间必须有顺序，是多个任务之间的关系

3. 阻塞指的是某个任务本身遇到无法继续执行下去的点时是否继续等待

【必问】死锁是什么？

1. 有多个线程，每个线程都在互相等待其他的线程释放资源，导致所有线程都无法继续运行下去

【必问】读写锁 vs 互斥锁有什么区别？

1. 互斥锁：当有一个线程持有锁时，其他线程都不能持有锁

2. 读写锁：当有一个线程持有读时，其他线程也可以持有读锁，但不能写；当有一个线程持有写时，其他线程既不能读也不能写

【必问】互斥锁 vs 自旋锁有什么区别？

1. 互斥锁：当无法持有锁时，阻塞；适合锁持有时间长时，免得CPU一直空转

2. 自旋锁：当无法持有锁时，CPU空转；适合锁持有时间短时，免得因阻塞而频繁调度

【必问】生产者消费者模型是什么？它的流程是怎样的？

1. 生产者

   1. 条件等待

      1. 若队列已满，阻塞

      2. 若队列不满，生产一个产品到队列

   2. 解锁并唤醒消费者

2. 消费者

   1. 条件等待

      1. 若队列为空，阻塞

      2. 若队列不空，消费一个产品

   2. 解锁并唤醒生产者

【必问】信号量 vs 信号有什么区别？

1. 他们完全不一样，信号一般是进程通信，信号量是线程同步

2. 信号量一般用于生产者消费者模型，它和条件变量不一样的点是它的初始值可以大于 1，即原始的资源数量可以多于 1

计算机网络

【必问】OSI七层模型和四层模型是什么？

1. 七层模型：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层

2. 四层模型：数据链路层、网络层、传输层、应用层

【必问】从输入网址后敲完回车到浏览器返回页面，中间发生了什么？

1. URL 解析

2. 域名解析，获得 IP 地址

3. TCP 三次握手四次挥手建立连接

4. 把请求的内容发过去

5. 服务器返回页面和数据

6. 浏览器进行渲染页面

7. 关闭连接

【必问】套接字是什么？套接字的本质是什么？

1. 表层：套接字是一组 API，我们通过套接字进行网络通信

2. 本质：是一种特殊的文件，有读、写两个缓冲区

【必问】对进程通信的方式之一本地套接字有了解吗？

1. 创建的时候的参数：AF_UNIX

2. 使用的地址：sockaddr_un

3. sockaddr_un 的长度计算需要特殊注意

【必问】TCP协议是做什么的？

1. 负责端到端传输

2. 特点：流式传输、有连接、有可靠性

【必问】TCP有几次握手？几次挥手？

1. 三握四挥

【必问】TCP状态转换？

1. 客户端->服务器：SYN，服务器变成 RECV

2. 服务器->客户端：ACK + SYN，客户端变成 RECV

3. 客户端->服务器：ACK，客户端、服务器都变成 ESTABLIASHED

4. 客户端->服务器：FIN，客户端变成 FIN_WAIT1

5. 服务器->客户端：ACK，客户端变成 FIN_WAIT2，服务器变成 CLOSE_WAIT

6. 服务器->客户端：FIN，服务器变成 LASTACK

7. 客户端->服务器：ACK，客户端变成 TIME_WAIT，服务器变成 CLOSE

8. 2 MSL：客户端变成 CLOSE

【必问】为什么需要2MSL时长？

1. 等对方收到 ACK（若未收到会重发FIN的）

2. 等本次的数据包在网络中完全消失

【必问】大量CLOSE_WAIT的原因是什么？

1. 服务器忘记调用 close 函数

2. 服务器因某种原因阻塞导致未能到达 close 函数

【必问】TCP如何保证传输可靠性？

1. 超时重传

   1. 超时重传：有定时器控制，若没有收到回复，则重传

   2. 快速重传：超时重传等待时间较长，快速重传收到连续 3 个一样 ACK 就立刻重传，并使用 SACK 机制只重传丢失的那个数据

2. 滑动窗口

   1. 滑动窗口：解决发送端和接收端处理数据速度不一致的问题

   2. 在一个窗口内发送数据，发送多个数据秩序回一个 ACK 即可

3. 流量控制

   1. 流量控制：解决发送端和接收端处理数据速度不一致的问题

   2. 减小滑动窗口

4. 拥塞控制

   1. 拥塞控制：使用拥塞窗口控制滑动窗口

   2. 慢启动：一开始拥塞窗口很小，但以指数速度增大，直到某一时刻线性增加

   3. 拥塞处理：遇到超时，拥塞窗口减半，如果是快速重传的拥塞，则适当减少拥塞窗口

【必问】TCP粘包是什么？怎么造成的？

1. 因为 TCP 是流式传输，真正在传输的时候，发出去的可能不是一个完整的包，可能是多个包黏在一起，也可能是半个包

【必问】TCP粘包有哪些解决方案？

1. 在应用层的头部加上本次发送的包的长度，用来分割每个数据包

【必问】select的优点和缺点？

1. 优点：跨平台

2. 缺点：文件描述符有最大限制，轮询访问效率低

【必问】为什么epoll效率显著高于select/poll？从他的底层角度说说？

1. 数据结构：红黑树，增删查改 log n

2. 可以设置 ET 非阻塞

3. 事件就绪队列，避免轮询

【必问】epoll的操作函数主要有哪三个？都是做什么的？

1. epoll_create：创建 epoll

2. epoll_ctl：把事件挂载到 epoll，或者从 epoll 中取消

3. epoll_wait：开启事件监听

【必问】ET vs LT有什么区别？

1. ET：边缘触发，只检测 fd 的状态变化来通知，例如 fd 一直是有数据的状态，则新数据来了也不会通知；ET + 非阻塞 fd = 效率高

2. LT：水平触发，只要 fd 处于就绪状态（例如有数据可读，或可以写入），epoll 就会持续通知应用程序，若频繁通知，效率低

【必问】epoll reactor（反应堆）思想是什么？

1. IO 多路复用机制，一般是 epoll

2. 有事件通知机制和就绪事件队列

3. 当事件通知时，需要手动处理这个事件

【必问】Proactor vs Reactor有什么区别？

1. Proactor：当事件通知时，我们无需手动处理这个事件，而是自动处理

2. Reactor：当事件通知时，需要手动处理这个事件

【必问】io_uring做异步IO的底层实现是什么？如何做到异步？

1. 用户态和内核态使用共享内存环进行通信，他们有共享的 SQ 和 CQ 的映射，这样可以减少进入内核态的次数，效率提升

2. 使用内存屏障来做线程间的同步，而非互斥锁，效率提升

3. 批量提交、批量处理

4. 支持多种 IO，包括网络 IO 和文件 IO

【必问】UDP vs TCP的优缺点？

1. TCP：有连接、可靠、数据流、包头大 = 效率低但可靠

2. UDP：无连接、不可靠、数据报、包头小 = 效率高但不可靠

【必问】TCP做了什么使得它比UDP更稳定呢？

1. 重传机制

2. 滑动窗口

3. 流量控制

4. 拥塞控制

【必问】QUIC vs UDP做了哪些提升？

1. 确认号机制

2. 安全性

3. 多路复用

4. 0-RTT 响应

5. 拥塞控制

【必问】HTTP是什么？

1. 应用层协议

2. 无状态

3. 都是由客户端先发起请求，服务端返回响应

【必问】GET vs POST有什么不同？

1. GET 一般请求数据，POST 一般提交数据

2. GET 一般把数据直接写在 URL 里，POST 一般把数据放在请求体里

【必问】HTTP有哪些版本？各有什么不同？

1. HTTP 1.0：最古老的版本

2. HTTP 1.1：支持长连接

3. HTTP 2.0：二进制传输，多路复用

4. HTTP 3.0：底层从 TCP 变为 QUIC，解决队头阻塞

【必问】WebSocket vs HTTP有什么优势？我们为何需要WebSocket？

1. 更小的协议头，传输效率高

2. 可以双向通信，而非只能由客户端发起请求

【必问】断点续传如何实现？

1. 记录上次下载了多少

2. HTTP range 机制，可以只取部分数据下载

【必问】Cookie vs Session vs Token之间有什么区别？

1. cookie 是存储在客户端里的一小段数据，session 是存储在服务器的一小段数据，客户端向服务器请求数据时会携带 cookie，这样服务器就可以根据它的session 去校验这个 cookie 来做身份认证

2. token 则是只存在于浏览器里的一段数据，而服务器不需要存任何数据，token 中自带数字签名，服务器只需要校验这个签名即可

【必问】HTTP vs HTTPS的区别？

1. HTTP 端口 80，HTTPS 端口 443

2. HTTP 不安全，HTTPS 安全

   1. 为什么安全？SSL 加密通信 + 证书校验

数据结构与算法

【必问】红黑树是什么？

1. 自平衡、二叉搜索树

2. 红节点和黑节点

3. 左旋和右旋动态调整

【必问】B+树是什么？

1. 多叉树

2. 非叶子节点只做索引，不存数据，叶子节点才存数据

3. 叶子结点是有顺序的

4. 叶子结点之间有链表连接

5. 叶子结点都在同一层

【必问】树的深度优先遍历（DFS）是什么？前序中序后序遍历是什么？

1. 前序遍历：根节点、左子树、右子树

2. 中序遍历：左子树、根节点、右子树

3. 后序遍历：左子树、右子树、根节点

【必问】树的广度优先遍历（BFS）是什么？如何层序遍历？

1. 有一个队列存放节点

2. 每次从队头读节点，然后把他的子节点放到队尾

3. 直到遍历到整个队列为空

【必问】如何用数组实现一个小顶堆/大顶堆？

1. 假设你有一个乱序数组，需要组成一个小顶堆

2. 那么设置一个空数组，对于任意位置 i， 其父节点是 i / 2，子节点是 i * 2 和 i * 2 + 1

3. 把第一个数放到空数组里，对于后续的数，如果它不满足小顶堆性质，则把他不断和父节点交换，使整个数组满足小顶堆

4. 接着就把每个数都陆续放到堆里，每放一个新的数据都需要维护堆的性质

【必问】快速排序是什么？时间复杂度？空间复杂度？稳定性？

1. 找一个标志位（例如是最后一个数），遍历区间，让比标志位小的放到左边，比标志位大的放到右边

2. 接着递归排序左侧和右侧

3. 时间复杂度 n log n，空间复杂度 log n，不稳定

【必问】二分查找是什么？时间复杂度？空间复杂度？

1. 必须是有顺序的数组

2. 直接比较要查的数据和当前数组的中间数字，这样就可以过滤一半的数据

3. 时间复杂度 log n，空间复杂度 1

【必问】hash冲突之链地址法是什么？hash最差能退化到什么复杂度？链地址法链表过长如何解决？

1. 当出现哈希冲突的时候，落入到同一个哈希值的数据会放进一个链表里

2. 最差的情况，所有的数据哈希值相同，都在一个链表里，变成 O（n）

3. 过长的话，开放地址法，换哈希函数，或者不用哈希、改用红黑树

【必问】hash冲突之开放地址法是什么？

1. 当出现哈希冲突的时候，按照一定算法改变哈希地址直到不冲突

2. 例如哈希地址 + 1、- 1、+ 2、- 2……

【必问】组合问题？

1. 检测是否递归深度足够，若够，则将当前结果加入总结果集

2. 遍历当前深度所有的可能值：

   1. 把值加入到当前结果

   2. 继续递归，深度 + 1

   3. 把值从当前结果中去掉

【必问】打家劫舍问题的解法是什么？

1. 分打劫和不打劫两个数组，若打劫就可以加上打劫的值，不打劫则是跟前一天的状态相关

【必问】背包问题的解法是什么？

1. 算排列还是组合：排列是外层遍历背包容量，内层遍历每个物品；组合是外层遍历每个物品，内层遍历背包容量

2. 物品唯一（01背包）还是物品无限（完全背包）：01是逆序遍历背包容量；完全背包是正序变量背包容量

【必问】最长递增子序列的解法是什么？

1. dp[i] = max(dp[j]) + 1, 0 <= j < i, nums[j] < nums[i]

2. ans = max(dp[i])

【必问】最长公共子序列的解法是什么？

1. i, j 符合要求：dp[i][j] = dp[i + 1][j - 1] + 1

2. i, j 不符合要求：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

3. 外层可能需要逆序

【必问】双指针思想是什么？

1. 设计两个指针 lpos 和 rpos

2. 通过一定条件，使他们相遇，或是达到别的条件

【必问】类接雨水的思想是什么？

1. 设计两个数组，分别是从左到右的某项数据的累计、从右到左的某项数据的累计

2. 那么某一点 i 的值就会和这两个数组相关

分布式系统

【必问】RPC通信的流程是什么？

1. 客户端调用远程服务，序列化请求

2. 服务器反序列化，服务器计算

3. 服务器计算完把数据序列化发回客户端

4. 客户端反序列化，接收结果

粗略讲讲Seata和它的4种事务模式？

1. Seata 的角色：TC、TM、RM

2. AT 模式：事务本地先提交，Seata 负责协调回滚

3. XA 模式：本地事务预提交，Seata 分析后让本地提交、本地回滚

4. TCC 模式：try、confirm、cancel

5. Saga 模式：事件驱动、异步、长事务

详细说说Redis分布式锁？

1. 为什么需要分布式锁：多个分布式进程需要访问同一个资源

2. 为什么选择 Redis 来做分布式锁：SET NX 语句天然支持，Redis 单线程天然的原子性

3. 如何标识持有锁的人：分布式 ID 方案记录每一个持有锁的进程

4. 看门狗机制：后台进程，定期给快到期的锁续时间

5. 如何做可重入锁：额外使用一个计数器记录持有相同锁的个数即可

6. 主从切换锁丢失怎么办：红锁机制

详细说说4种定时器？

1. 时间轮定时器：需要多级时间轮，高效但是实现复杂

2. 最小堆定时器：取最上面的节点容易，维护堆性质效率低

3. 红黑树定时器：各项性能均衡

4. 跳表定时器：各项性能均衡，支持范围查询，Redis zset 天然支持，适合做分布式定时器

详细说说Raft分布式一致性算法？

1. 有哪些节点：主节点、从节点、选举节点

2. 主节点挂了，怎么选举：从节点升级为选举节点，随后看选举节点的任期来投票选举，当票数过半，选举节点升级为主节点，广播消息，选举结束

3. 节点之间如何同步：通过日志，当有新记录要进入日志时，主节点向从节点发布这个新内容，半数节点校验通过这个日志内容，主从节点就都把这个内容写到日志

详细说说4种限流算法？

1. 计数：记录一段时间的访问次数；这种方法防御不了刚好卡一段时间末尾和下一段开头的攻击

2. 滑动窗口：限制在任何一个窗口内的访问次数

3. 漏桶：把你的请求放到漏桶里，我恒定速度处理漏桶，漏桶满了就禁止你再请求

4. 令牌桶：把令牌放到桶里，令牌产生的速度恒定，一个令牌一个请求，没有令牌时，请求禁止

详细说说一致性哈希算法？

1. 哈希环：把数据和节点都做哈希运算映射到一个区间，并且区间头尾相连

2. 那么对于某一个数据路由到哪个节点就很好计算了，例如有节点 3000，4000，那么数据 3111 就会被路由到 3000 那个节点

3. 如果节点经过计算之后映射到哈希环上分布不均匀怎么办：使用虚拟节点

中间件

【必问】SQL语句在数据库中执行的详细全部步骤是什么？

1. 连接器：用户连接到数据库，进行校验

2. 查缓存：（该步骤已废弃）

3. 解析器：词法分析 + 语法分析

4. 优化器：生成执行计划 + 优化

5. 执行器：执行 MySQL 语句

【必问】MySQL索引的数据结构是什么？

1. B+ 树

   1. 多叉树

   2. 只有叶子结点存储数据

   3. 叶子结点都在同一层

   4. 叶子结点之间相互连接

   5. 叶子结点之间按顺序排列

【必问】MySQL聚集索引和非聚集索引是什么？

1. 聚集索引

   1. 全局只有一个聚集索引表

   2. 聚集索引表存储全部数据，即这张表本身

2. 非聚集索引

   1. 可以有多个非聚集索引

   2. 非聚集索引表存储的只有：你设定的索引列 + 主键

   3. 若查询非聚集索引没有查到完整数据，则会根据逐渐再回聚集索引表查询，即回表

【必问】最左前缀原则是什么？

1. 索引排序的时候，按照你设定的最左侧的索引列先排序，再排序后面的列

2. 所以说，越左边的列越应该区分度大

3. 查询的时候，先等值查询，再范围查询

【必问】MySQL索引失效的情况？

1. 违背最左前缀原则去查询，例如以右侧的索引列去查询

2. 使用一些公式

3. 使用 LIKE，且 % 符号在最前

4. 触发类型转换

【必问】事务的四个基本特性是什么？分别是怎么实现的？

1. 原子性：一个事务里的所有语句要么全部成功，要么全部失败

   1. 使用 Undo Log 实现，记录所有的操作数据，失败就进行回滚

2. 一致性：一条数据在事务执行前和事务执行后，其约束性质不变（例如唯一性）

   1. 当其他三个特性都实现时，一致性自然实现

3. 隔离性：多线程并行执行事务时，不会受到其他线程的干扰

   1. 使用：锁 + MVCC 机制

4. 持久性：一个事务一旦执行成功，就必须写入磁盘

   1. 使用 Redo Log 实现

【必问】并发条件下脏读、幻读、不可重复读分别是什么？

1. 脏读：读到了其他线程的事务未提交的数据

2. 不可重复读：读到的数据都是提交的数据，但是同一个数据读多次，其值不同

3. 幻读：读到的数据都是提交的数据，但是读数据的时候，多出来了之前不存在的行

【必问】数据库隔离级别有哪几种？每种级别解决哪种问题？

1. 读未提交：不解决任何问题，可能发生脏读、不可重复读、幻读

2. 读已提交：解决脏读，可能发生不可重复读、幻读

3. 可重复读：解决脏读、不可重复读和大部分的幻读，可能发生幻读（小概率）

4. 串行化：解决脏读、不可重复读、幻读

【必问】MySQL四种事务隔离级别分别如何使用MVCC实现？

1. MVCC：多版本并发控制，不使用锁，但是能做到事务线程安全

   1. 机制——版本链：每个数据有不同的版本，串成一个链，存储在 Undo Log 里

   2. 机制——ReadView：一个特殊数据结构，能通过它查询到当前事务能查看的数据的版本链的范围

2. MVCC 实现隔离级别

   1. 读未提交：不使用 MVCC，什么都不用

   2. 读已提交：select 快照读、每次 select 时都创建 ReadView，且都依据这个新的 ReadView 去查询事务看到的数据范围，这会导致可能每次执行看到的同一个数据的值不同

   3. 读已提交：select 快照读、只有第一次 select 时创建 ReadView，以后这个事务都使用这个 ReadView，这保证每个数据都查到的是事务开始时的版本；update、insert 当前读 + 邻键锁，这能防止幻读（大部分的）

   4. 串行化：不使用 MVCC，使用锁

【必问】MySQL undo log是什么？

1. 存什么：一个事务里的数据的版本变化

   1. 用于回滚事务

   2. 用于 MVCC 的 ReadView 查询版本链

【必问】MySQL redo log是什么？

1. 存什么：MySQL 语句操作的物理信息

   1. 用于崩溃恢复，通过物理信息立即恢复

   2. 用于实现事务的持久性，Redo Log 刷盘不成功则视为事务提交失败，保证必须落盘

【必问】MySQL bin log是什么？为什么bin log可以用来备份恢复？

1. 存什么：MySQL 语句操作的逻辑信息

   1. 用于主从复制，从节点按照逻辑顺序一条一条执行就可以和主节点一致

   2. Redo Log 和 Bin Log 不一致怎么办：Redo Log 的两阶段提交

【必问】MySQL中的乐观锁 vs 悲观锁有什么区别？

1. 悲观锁：悲观地认为资源很可能被多个线程持有，必须加锁

2. 乐观锁：不加锁，乐观的认为不一定要加锁，就算出了问题也能回滚（MVCC），或是只需要最终一致性

【必问】Redis为什么快？

1. 存储在内存中，速度远超磁盘

2. 优秀的数据结构：String、List、Hash、Set、ZSet

3. 支持 IO 多路复用

【必问】Redis中，String、Hash、List、Set和ZSet的底层是什么数据结构？这些底层数据结构的底层又是什么？

1. String

   1. 短 String：int

   2. < 44 字节：ebpm，一块内存

   3. > 44 字节：raw，多块内存

2. Hash

   1. 少：ZipList，连续内存

   2. 多：Dict，本质哈希表（链地址法 + 渐进式 rehash）

3. List

   1. 少：ZipList

   2. 多：双向链表

   3. 现代：多个 ZipList 之间使用双向链表连接

4. Set

   1. 只存整数：intset

   2. 其他：Dict

5. ZSet

   1. 少：ZipList

   2. 多：跳表（范围查询） + Dict（O（1）查询）

【必问】Redis有哪些用途？

1. 数据库缓存

2. 分布式锁、分布式 Session

3. 利用其数据结构，例如排行榜等

【必问】Redis缓存穿透是什么，如何解决？

1. 用户大量查询不在 Redis 里的数据，导致 Redis 显得无用

2. 解决：布隆过滤器，对一个数据使用多个哈希函数，如果全部命中，则可能存在，若有一个没命中，则一定不存在；使用布隆过滤器可以明确知道不存在的数据

【必问】Redis缓存击穿是什么，如何解决？

1. 一个热点 key 突然过期，导致大量请求打到数据库

2. 解决：互斥锁，对所有的请求加互斥锁，只有第一个请求会查询数据库，并将数据填回到 Redis，这样释放锁之后，后续的请求就可以查到 Redis

【必问】Redis缓存雪崩是什么，如何解决？

1. 大量热点 key 突然过期，导致数据库崩溃

2. 解决：热点 key 的过期时间错开设置 + 数据库高可用（主从、哨兵、集群）

【必问】Redis缓存更新策略有哪几种？具体的读写策略是什么？

1. 旁路缓存

   1. 读：先读 Redis，没有则读数据库，并将数据回填

   2. 写：先写数据库，再删除缓存 -> 这无法确保强一致性

2. 读写穿透

   1. 读写都之和 Redis 交互，若 Redis 中无数据，则由 Redis 来将数据回填

【必问】旁路缓存如何保证缓存和数据库的一致性？

1. 先写数据库，再删除缓存 -> 这无法确保强一致性

2. 最终一致性方案

   1. 方案一：延迟双删，删除的缓存有可能被脏数据回填，所以要在短时间内再删一次

   2. 方案二：合理设置过期时间，这样即使 Redis 中是脏数据，也能在一段时间后自动删除

【必问】Redis的RDB持久化方法是什么？

1. 物理级的持久化方法，是 Redis 数据的全量拷贝

2. 问题：拷贝一次需要花很久时间，在这期间 Redis 挂了会丢失部分数据

【必问】Redis的AOF持久化方法是什么？

1. 记录每次 Redis 的操作，并一直追加

2. 问题：一直追加导致 AOF 过大 -> 可以使用 AOF 重写，把操作记录合并到最精简

【必问】Redis的混合持久化方案是什么？

1. RDB + AOF

2. 当触发 AOF 重写时，全量拷贝一次 RDB，随后在这基础上记录 AOF

【必问】Redis主从模式是什么？主从复制策略有哪些？

1. 主节点、从节点；从节点是主节点的备份

2. 复制策略：增量复制、全量复制

【必问】Redis哨兵模式是什么？

1. 哨兵节点：监控主节点和从节点

2. 当主节点挂了的时候，哨兵节点互相之间确认主节点是否真的挂了，真的挂了，则哨兵互相投票选出哨兵首领，哨兵首领选择一个从节点升级为主节点

3. 哨兵节点通知所有节点主节点已变更

【必问】Redis集群模式是什么？

1. 多个主从结构组成集群

2. 如何看你的数据会被路由到哪个主节点？哈希环、即一致性哈希（这个分布式系统说过了，这里再写一遍）

   1. 各个节点和数据都映射到一个环上，每个节点或数据都有哈希值，数据落在哪个两节点之间，你就属于前面的那个节点

   2. 当你属于的节点挂了，很容易就可以重新路由到更前面的节点

   3. 节点映射到环上不均匀咋办？使用虚拟节点，让你均匀

【必问】消息队列的数据结构是什么？topic、broker是什么？

1. 队列：队列就是队列，没什么说的，一般是先进先出的结构

2. topic：主题，订阅这个主题的人就能收到这个主题的消息，主题下面又有分区

3. broker：消息队列的服务器，负责收发消息以及消息的持久化

【必问】docker是什么？容器技术是什么？容器技术==docker吗？

1. 容器技术是一种虚拟化技术，虚拟化不是虚拟机但是类似于轻量级的虚拟机，容器层在操作系统看来像是一个进程，但是对容器内的程序看来像是在一个独立环境中，具有隔离性

2. Docker 就是容器技术的一种，Docker 不等于容器技术，他只是一个子类

【必问】K8s是做什么的？

1. 容器的编排

2. 服务的监控

3. 扩缩容

【必问】Zookeeper是什么？

1. 服务协调器

   1. 可用作服务发现

   2. 可用作配置管理

【必问】Zookeeper是数据结构是什么？

1. 树形结构

   1. 节点、子节点：顺序节点、临时节点、永久节点

   2. 路径

   3. 元数据：这个节点本身的信息

   4. 数据：节点携带的数据

【必问】Nginx能干什么？

1. Web 服务器，静态 HTTP 访问

2. 反向代理服务器

3. 邮件服务器

【必问】正向代理 vs 反向代理有什么区别？

1. 正向代理：是对于客户端而言的，客户端通过正向代理服务器，将请求转发到真正的服务器

2. 反向代理：是对于服务器而言的，客户端只能访问反向代理服务器，随后由反向代理服务器决定你真正要访问的背后的服务器，这通常用来做负载均衡

游戏服务器业务

粗略说说Zinx框架？

1. 三层模型

   1. 通道层：负责消息的收发

   2. 协议层：应用层对协议解包解析

   3. 业务层：做业务，所有游戏实体都继承自 Role

   4. 消息类：自定义的消息类

2. 责任链模式：能处理的消息在本层处理，若不能则发往上一层

Skynet使用的Actor模型是什么？它和Reactor模型、Proactor模型的区别是什么？

1. 多进程的模型，Actor 是 Lua 的虚拟进程，天然具有隔离性；所有的服务都抽象成 Actor

2. 每个 Actor 有自己的消息队列，epoll 把消息发到消息队列，Actor 自己来取

TrinityCore的网络模型是怎样的？

1. network 线程：负责建立连接

2. acceptor 线程：负责处理连接，把消息 push 到消息队列

3. logic 线程：负责处理主线程主逻辑，处理不了的其他逻辑（例如地图逻辑），push 到地图线程的消息队列

4. map 线程：每个地图区块都是一个独立线程，处理地图逻辑

【必问】protobuf遇到数组类型如何处理？

1. proto 文件里关键字：repeated

2. 代码中，使用 add 申请一个单位的内存，set 设置数组内单个元素

【必问】protobuf遇到嵌套类型如何处理？

1. 代码中，使用 mutable 方法获取嵌套类；在嵌套类中，就和普通类一样 set 即可

【必问】登录+创建游戏房间的流程是什么？

1. 登录器发起登录，数据传输到 Nginx 登录服务器

2. 登录服务器验证登录，然后负载均衡地选择一个逻辑服务器 IP，并利用发布订阅机制让逻辑服务器建房

3. 逻辑服务器建房，发回端口、房间号

4. 登录服务器收到端口、房间号，把 IP + 端口 + 房间号全部传回去

5. 登录器启动 Unity 程序，并向 IP + 端口 + 房间号 发起连接

你登录模块用的什么算法？SRP-6是什么？

1. 安全远程密码验证协议

2. 无需发送密码，而是用一种算法转换密码，服务器使用转换的值就可以进行校验

AOI算法是什么？

1. 对地图进行分区，当前角色只能看到周围附近的单位，降低服务器负载

2. AOI 方法：网格法、四叉树（2D）、八叉树（3D）

AI模块之状态机是什么？

1. 状态机的元素：状态、转移条件、任务、状态机的管理器

2. 状态机的分类：有限状态机、多层状态机

AI模块之行为树是什么？

1. 树形结构

   1. 组合节点

      1. 顺序节点：按顺序执行所有

      2. 选择节点：选择一个执行

      3. 并行节点：同时执行多个节点

   2. 任务节点：你要执行的任务

   3. 装饰节点：例如取反

   4. 黑板：记录整个行为树的其他信息

2. 节点状态：成功、失败、运行中

状态同步 vs 帧同步有什么区别？

1. 状态同步

   1. 客户端发来消息，它的某些状态需要发生变化

   2. 服务器计算这些变化

   3. 然后把变化的东西通过消息发回给相关联的所有客户端

2. 帧同步

   1. 客户端发来消息，服务器记录消息

   2. 服务器把这段时间（一个固定时间）收集到的所有客户端消息打成包

   3. 把这个包发给客户端，由客户端完成计算

游戏服务器如何做热更新？

1. 使用脚本语言

2. 使用重新加载动态库

3. 使用配置表或是配置在数据库

场景代码题

【必问】手撕智能指针？

1. 控制器：原生指针、引用计数、弱引用计数

2. 构造函数：构造控制器

3. 拷贝构造函数：复制控制器。引用计数 + 1

4. 析构函数：控制器引用计数 - 1，若达到 0，则释放指针，若此时连弱引用计数都为 0，则控制块也要释放

5. 重载 -> 和 *，就不说了，补上就行

#include <atomic>

template<class T>
class ControlBlock {
public:
        T* ptr;
        std::atomic<int> use_count;
        std::atomic<int> weak_count;

        ControlBlock(T* p) : ptr(p), use_count(1), weak_count(0) {}
};

template<class T>
class SharedPtr {
public:
        ControlBlock<T>* control_block;
        SharedPtr(T* p) : control_block(new ControlBlock<T>(p)) {}
        SharedPtr(const SharedPtr& other) : control_block(other.control_block) {
                control_block->use_count.fetch_add(1, std::memory_order_relaxed);
        }
        ~SharedPtr() {
                if (control_block && control_block->use_count.fetch_sub(1, std::memory_order_acq_rel) == 1) {
                        delete control_block->ptr;
                        if (control_block->weak_count.load(std::memory_order_acquire) == 0) {
                                delete control_block;
                        }
                }
        }
        T& operator*() const {
                return *(control_block->ptr);
        }
        T* operator->() const {
                return control_block->ptr;
        }
        int use_count() const {
                return control_block ? control_block->use_count.load(std::memory_order_acquire) : 0;
        }
};

【必问】手撕LRU Cache？

1. list 存 KV

2. 哈希表存 K 和 list 节点地址

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (!cache.count(key)) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            // 添加进哈希表
            cache[key] = node;
            // 添加至双向链表的头部
            addToHead(node);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode* removed = removeTail();
                // 删除哈希表中对应的项
                cache.erase(removed->key);
                // 防止内存泄漏
                delete removed;
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

【必问】手撕链表是否有环？

1. 快慢指针法，慢指针走一格，快指针走两格，若相遇，则链表有环

2. 确定环的大小：一个指针不动，另一个指针继续走并开始计数，当他们再次相遇时，那个动的指针走过的节点个数就是环的大小

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) {
            return false; // 空链表或只有一个节点且无环
        }

        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;          // 慢指针走一步
            fast = fast->next->next;    // 快指针走两步

            if (slow == fast) {         // 相遇则有环
                return true;
            }
        }

        return false; // 快指针遇到 nullptr，说明无环
    }
};

【必问】手撕快排？

1. 对当前区间，随便找一个元素，然后把所有比他小的排到他左边，比他大的排到他右边

   1. 具体怎么做？遍历整个区间，若某个数比他小，则和第 i 位置的元素交换，i 为统计出来的比他小的元素数量 + 1，最后记得把该元素也放到正确的位置上

2. 随后，以该元素为界，继续快排左右两个子分区

// 分区函数（Lomuto Partition Scheme）
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为基准
    int i = low - 1;        // i 是小于 pivot 的区域的最后一个索引

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);  // 把小于 pivot 的元素交换到左边
        }
    }
    swap(arr[i + 1], arr[high]);  // 最后把 pivot 放到正确的位置
    return i + 1;  // 返回 pivot 的索引
}

// 快速排序主函数
void quickSort(vector<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);        // 递归排序右半部分
    }
}

【必问】手撕单例模式（懒汉式）？

1. 禁止拷贝构造、禁止 = 赋值、私有构造函数

2. 获取单例对象：静态方法、返回引用

   1. 函数体内静态单例变量

【必问】一般在Linux系统下遇到网络问题用哪些命令或手段进行排查？

1. ping：查看目标主机是否可达

2. telnet：查看目标地址是否能连上 TCP

3. netstat -antp：查看当前所有的 TCP 连接

4. tcpdump：TCP 抓包工具