目录

• 前言
• 操作系统
  • 内核态和用户态
  • 陷阱、中断、异常、信号
  • 进程和线程
  • 进程的调度
  • 线程和进程的通信方式
  • 锁的类型与实现
  • 进程的同步与互斥
  • 死锁的预防、检测、避免、解除
  • 物理内存管理
  • 虚拟内存管理
  • 虚拟地址空间的组成部分
  • 进程的内存管理
  • 大端法、小端法
  • 缓冲区溢出问题
  • I/O 模型
  • 协程
  • 写时复制 Copy-on-write
  • 其他
• 计算机网络
  • 协议栈
  • TCP 文章推荐
  • TCP 的流量控制和拥塞控制
  • TCP 的三次握手和四次挥手
  • TCP 的粘包问题
  • TCP 协议（其他）
  • TCP、UDP 对比
  • HTTP 原理
  • HTTPS 原理
  • HTTP 的缓存机制
  • DNS 原理
  • IP 原理
  • 从输入一个 URL 到页面加载完成的过程
  • 两台主机间的通信过程
  • 常用的负载均衡软件
  • Socket 通信
• 数据库
  • 数据库基础
  • 数据库的存储引擎
  • 数据库的索引
  • 数据库的事务
  • 数据库的并发控制
  • 数据库分库、分表、主从、读写分离
  • 数据库的优化方法
  • ORM 和原生 SQL 的区别
  • Redis 相关
• 数据结构
  • 哈希表
  • Map 的实现
  • 排序算法
  • 海量数据问题
• 计算机组成原理
  • 引用和指针的区别
  • 函数的参数是如何传递的
  • 大端法、小端法及其判断
  • 原码、反码、补码
  • 存储器的层次结构
• 编程语言
  • Golang
  • C++
• 开发与运维
  • 运维问题
  • Linux 常用命令
  • Linux 相关问题
  • Git 常用命令
  • 常用的中间件
• 系统设计题
• 多线程编程
• 分布式
  • RPC
  • 分布式原理
  • 分布式组件
  • 分布式算法
• 网络安全
• 面经汇总

前言

这是我用来准备后端开发校招面试的笔记汇总。这些题目或多或少都在不同公司的面试过程中出现过，因此将其总结起来，可以用作复习阶段的知识点梳理，也可以用作面试前的快速回顾。点击展开上方目录，可以查看全部题目索引。

本文采用「题目 - 子问题 - 答案」的形式。大部分问题都是简答，可以直接采用。但是深入了解细节，才能应对面试官进一步的问题，因此我也将部分问题整理为单独的文章，之后还会持续更新。

操作系统

内核态和用户态

• 内核态和用户态的区别
• 什么时候会陷入内核态
• C 访问空指针会不会陷入内核态？

答案

陷阱、中断、异常、信号

• 陷阱、中断、异常、信号的产生来源
• 陷阱、中断、异常、信号的处理流程
• 常见的陷阱、中断、异常、信号有哪些？

答案

进程和线程

• 进程与线程的区别
• 为什么需要线程
• 线程的优缺点
• 同一进程中的线程共享与独占的资源
• 线程的实现方式
• 线程池介绍、应用场景

答案

进程的调度

• 进程的状态
• 批处理系统、交互系统的调度算法
• 僵尸进程、孤儿进程、守护进程

答案

线程和进程的通信方式

• 信号、管道、信号量、共享内存、消息队列
• 各种通信方式的原理、适用场景

答案

锁的类型与实现

• 了解哪些类型的锁？
• 互斥锁的实现方式
• 读写锁的实现方式

• 不同类型的锁：互斥锁、读写锁、自旋锁、条件锁。
• Java 中的锁类型：
  • 公平锁/非公平锁
  • 可重入锁
  • 独享锁/共享锁
  • 互斥锁/读写锁
  • 乐观锁/悲观锁
  • 分段锁
  • 偏向锁/轻量级锁/重量级锁
  • 自旋锁
• 互斥锁的实现方式：答案

进程的同步与互斥

• 临界资源和临界区的概念
• 同步和互斥的概念
• 临界区的管理原则
• 信号量和 P / V 操作
• 原子操作的原理 [TODO]
• volatile 解决什么问题
• 一些常见的并发问题
  • 生产者与消费者问题
  • 读者写者问题
  • 浴室洗澡问题
  • 哲学家就餐问题

答案

死锁的预防、检测、避免、解除

• 死锁产生的四个必要条件
• 如何预防、检测、避免、解除死锁？

(1) 死锁产生的四个必要条件

• 互斥条件
• 占有且等待条件：线程占有已经分配给它们的资源（如锁）并且等待其他的资源（也就是说不会主动释放）
• 不可抢占条件（也就是说不会被动释放）
• 环路等待条件：每个进程都在等待下一个进程占有的资源

这四个条件缺少一个就不会有死锁。

(2) 预防死锁

预防死锁就是破坏上面四个条件任意一个，但是实现很难：

• 破坏互斥条件：允许某些资源同时被多个进程访问。但是有些资源本身并不具有这种属性，因此这种方案实用性有限
• 破坏占有并等待条件：
  • 实行资源预先分配策略（当一个进程开始运行之前，必须一次性向系统申请它所需要的全部资源，否则不运行）
  • 或者只允许进程在没有占用资源的时候才能申请资源（申请资源前先释放占有的资源）
  • 缺点：很多时候无法预知一个进程所需的全部资源；同时，会降低资源利用率，降低系统的并发性
• 破坏非抢占条件：允许进程强行抢占被其它进程占有的资源。会降低系统性能
• 破坏循环等待条件：对所有资源统一编号，所有进程对资源的请求必须按照序号递增的顺序提出，即只有占有了编号较小的资源才能申请编号较大的资源。这样避免了占有大号资源的进程去申请小号资源，各个进程申请资源的顺序都是从小到大，就不会有环了

(3) 避免死锁

允许系统中同时存在四个必要条件，但是每当进程提出资源申请时，系统要分析满足该资源请求后，系统是否会发生死锁，若不会发生则实施分配，否则拒绝分配。银行家算法实现了这个过程。

(4) 检测死锁

画出资源分配图，检测是否存在环路。检测环路前要将资源分配图化简，化简的原理是“一个目前占有运行所需的资源的进程，迟早能够执行完成释放资源”。因此，可以从“进程—资源分配图”中找到一个既不阻塞又非孤立的进程，删除所有与该进程相连的有向边，回收资源，使之成为孤立结点，然后将所回收的资源分配给其它进程。循环此过程，直到无法化简。若仍存在环路，则该系统目前处于死锁状态。

检测到死锁后，需要解除死锁。

(5) 解除死锁

破坏除了“互斥条件”之外的其他三个条件：

• 回退执行：系统定期对各个进程进行检查，将检查点的有关信息写入文件。死锁时，让某占有必要资源的进程回退到取得资源之前的一个检查点，释放的资源分配给一个死锁进程（破坏“占有且等待”）
• 抢占资源：剥夺占有进程的资源，分配给另外某些进程，直至死锁环路被打破（破坏“不可抢占”）
• 杀掉进程：一次终止一个进程，直至消除死锁环路（破坏“循环等待”）

物理内存管理

• 不同的内存分配技术及其优缺点
  • 固定分区法（等长、不等长）
  • 动态分区法
  • 页式内存管理
  • 段式内存管理
  • 段页式内存管理
• 不同的动态分区放置算法及其优缺点

内部碎片和外部碎片：

• 内部碎片是固定分区法产生的，指被占用分区上未被利用的空间，由于该分区被占用，因此无法被分配使用
• 外部碎片是动态分区法产生的，指被占用分区之间的小空间，虽然可以被使用，但是由于太小而无法被分配

(1) 不同的内存分配技术及其优缺点

1. 等长固定分区法：每个分区大小相同，在系统启动时分配好，系统运行期间保持不变；每次给进程分配一整块区域，因此进程的大小必须 ≤ 分区的大小
   • 优点：系统需要维护的管理信息非常少，只要维护一个固定行数的表格，记载分区的使用情况；内存分配算法很简单，有足够大空闲分区就分配，否则就拒绝
   • 缺点：不同进程需要的空间不同，内部碎片多，浪费空间；分区总数固定，限制了并发执行的程序数量
2. 不等长固定分区法：每个分区大小不同，在系统启动时分配好，系统运行期间保持不变；分配时，需要根据进程的大小在空闲分区中选择一个大小合适的分区（优缺点同上）
3. 动态分区法：在系统运行中，根据每个进程需要的空间大小确定分区大小；通过空闲分区链表进行组织
   • 优点：并发执行的程序数量不受限制，只取决于是否有大小合适的内存块可以分配
   • 缺点：管理空闲快的复杂度增加；分配算法的时间开销增加，可能需要遍历多次才能找到合适的内存块
4. 页式内存管理：把固定分区面积缩小，一个进程可使用多个分区；进程被分割成若干块，装入内存中的几个分区中，物理上无需相连，逻辑上通过页表关联。这是一种内存的不连续分配方法
   • 优点：不存在任何外部碎片，只在每个进程的最后一个页框中存在内部碎片
5. 段式内存管理：按照逻辑意义将程序分成若干个段，每个段独立载入到内存的不同区间中
   • 优点：分页不考虑每个页中内容的意义，而分段是按照逻辑关系划分
   • 缺点：每个段必须连续、全部加载到内存中
6. 段页式内存管理：把分段和分页两种方式结合，先把程序按照逻辑意义分成段，然后每个段再分成固定大小的页

参考资料：段式内存管理 - Edison Zhou

(2) 不同的动态分区放置算法及其优缺点

• 最佳适应算法
  • 检查所有空闲分区，选择和新进程申请内存大小最接近的空闲分区
  • 优点：该算法保留大的空闲区
  • 缺点
    • 检查所有空闲分区需要时间
    • 外部碎片多：会留下许多难以利用的，很小的空闲分区，称为外部碎片
    • 可以采用内存紧凑的方法，将被使用的分区都移动到一起，减少外部碎片。但是移动内存中的代码和数据也需要很多时间
• 最差适应算法
  • 每次为进程分配分区时，都选择最大的空闲分区分配
  • 最差适应算法使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统
  • 优点：该算法保留小的空闲区，尽量减少外部碎片的产生
  • 缺点：检查比较所有的空闲区间需要时间；系统中不会存在面积很大的空闲区间，难满足大进程的要求
• 首次适应法
  • 只要发现能用的分区就分配。这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区
  • 优点：可以剩下大的分区
  • 缺点：外部碎片多，集中在低址部分；并且每次查找都是从低址部分开始的，这无疑又会增加查找可用空闲分区时的开销
• 下一个适应法
  • 由于上面的放置算法每次都需要从头检查，有可能浪费很多时间。因此“下一个适应法”就是操作系统记住接下来该检查的空闲分区的位置，给进程分配分区时，系统从记录的分区开始依次向后查找直到碰到能用的分区为止，如果到链表尾还没有找到，就再从头开始
  • 缺点：上面的三个放置算法都是按照分区大小来分配，或是留下大区间（首次适应，最佳适应），或是留下小区间（最差适应）。下一个适应法很难剩下面积很大的区间，会使剩余分区的大小比较平均

虚拟内存管理

• 虚拟内存的思想 / 实现方式
• 暂时不在内存中的数据存在哪里？
• 虚拟地址的映射
  • 页表、页表表项结构
  • 多级页表
  • 倒排页表
  • 散列表
• TLB 的原理
• 虚拟地址到物理地址的翻译过程 [TODO: MMU + TLB]
• 缺页中断的处理
• 什么是页面淘汰？
• 不同的淘汰算法及其适用场景

(1) 虚拟内存的思想 / 实现方式

• 在系统中为每个程序定义一个虚拟地址空间，虚拟地址空间中的地址都是连续的
• 虚拟地址空间被分割成多个块，每块称为一个页或者页面
• 物理内存被分成和页面大小相同的多个区域，称作页框
• 程序加载时，可将任意一个页面放入内存中的任意一个页框
• CPU 的硬件负责将虚拟地址映射到物理内存中的地址（页面 -> 页框）
• 程序的整个地址空间无需全部载入物理内存，还有部分暂时存储在外存上，需要时再换入内存
• 如果程序引用到一部分不在物理内存中的虚拟地址时，会发生缺页中断，由操作系统负责将缺失的页面加载入页框中，并重新执行失败的指令

(2) 暂时不在内存中的数据存在哪里？

存储在交换分区（swap）中。当内存不足的时候，操作系统先把内存中暂时不用的数据，存到硬盘的交换空间，释放内存空间。详见 Swap - ArchWiki 。

(3) 虚拟地址的映射

页表：每个进程有一个页表，描述该进程每个页面对应的页框号，以及该页面是否已经被载入内存（“在/不在”位）。以下是一个进程的页表和地址映射过程的示意图：

• 一个完整的页表表项包含以下内容：
  • 页框号
  • 存在位：页面是否在内存中：
  • 访问位：页面是否已被访问，影响页面淘汰选择
  • 修改位：页面是否被修改，修改过的页面需要重新写回外存
  • …
  • 页面号：在页表中的下标，并不是一项真的内容

进程在运行时，需要将页表放在内存中。但在虚拟地址空间很大的情况下，会被分成很多个页面，那么进程的页表将占据很大的内存空间，甚至无法全部载入内存。

有一些针对大内存的页表实现方式：

• 多级页表：将页表进一步分页，页目录表相当于“页表的页表”，记录每个内层页表存放在哪个页框中；内层页表依然记录进程的每个页面存放在哪个页框中。以下是一个多级页表的示意图：
  
• 倒排页表：不再为每个进程记录页面到页框的映射，而是记录每个页框对应的 (进程号, 页面号) 二元组。整个操作系统只需要一个倒排页表，节省了大量空间。但是它必须遍历整个页表才能找到某个表项，无法将页面号当作索引直接找到页框号。
  
• 散列表：为了节省页表空间，同时加速查找过程，可以将当前进程的所有「在内存中」的页面建立一张散列表。用每个页面的虚拟地址来散列，相同散列值的元素会被链接到一起，每个元素包含三项内容：页面号、页框号、指向链表中下一个元素的指针。
  

(4) TLB 的原理

现代操作系统中，页表的个数是很多的，而每次执行语句时都需要先查找页表，将虚拟地址转换为物理内存地址。这部分切换的时间开销是很大的。因此，解决方案是为计算机设置一个小型的硬件设备 TLB。

转换检测缓冲区（TLB，translation-lookaside buffer），是 MMU（内存管理单元）的一部分。它提供一个缓冲区，记录虚拟页面号到物理页框号的映射，这样可以在 O(1) 的时间里直接将虚拟页面映射到物理页框，不需要访问页表，从而节省时间。

工作流程：如果页面号在 TLB 中，得到页框号，访问内存；否则，从内存中的页表中得到页框号，将其存入 TLB，访问内存。

TLB 基于局部性原理实现：

• 空间局部性：如果程序访问了地址 x，那么很有可能访问 x 附近的地址
• 时间局部性：如果程序访问了地址 x，很可能立刻又访问 x

(5) 缺页中断的处理

应用程序访问未加载到内存中的页面时，会引起缺页中断。操作系统回将缺失的页面加载入页框中，然后重新执行引起异常的指令。

缺页中断更准确地说，应当是“缺页异常（page fault）”。异常执行当前指令产生的错误情况，中断则是外部硬件产生的事件。详见陷阱、中断、异常、信号。

(6) 页面淘汰

当内存空间已被占满而又要调入新的页面时，必须将已在内存中的某个页面淘汰掉。如果被淘汰的页面曾被修改过，还要将此页写回到外存，再换进新的页面。这一过程称为页面淘汰。

如果某个页面频繁的被“调入-淘汰-调入-淘汰”，这种现象称为抖动。抖动导致系统将大部分时间花在了页面的置换上，因此在淘汰时，要选择今后不会或者最近不会用到的内容，以减少抖动。

(7) 不同的淘汰算法及其适用场景

根据具体的应用场景，选择合适的淘汰算法。除了操作系统的页面置换，redis 中也经常用到各种内存淘汰算法，往往需要结合具体业务场景来选择。

以下是几种常见的淘汰算法：

1. 最佳置换算法 / 最优策略（OPT）：选择以后再也不会用到的页面淘汰；如果都会用到，就选择那些再次使用的时间距离现在最远的页面淘汰。这是一种理想情况下的页面置换算法，实际上不可能实现。可以作为评测其他淘汰策略的标准。
2. 先进先出法（FIFO）：直接换出最早装入的页面。
   • 优点：简单
   • 缺点：性能不是很好，因为它淘汰的可能是常用的页面
   • 适用场景：数据只用一次，将来不太可能使用；[redis] 对数据时效性有要求（越旧的缓存越先被淘汰）
3. 第二次机会置换法（SCR：Second Chance Replacement）：对 FIFO 算法的改进，每个页面访问 2 次后再淘汰。具体实现上，设置页面访问位，每次检查队首的页面访问位：如果该位为 0，淘汰该页；如果该位为 1，将该位设为 0，将其移到队尾，看成新装入的页。
   • 优点：一定程度上，避免把经常使用的页面置换出去
     
4. 时钟置换法（Clock）：对第二次机会置换法的改进。第二次机会置换法需要在链表中移动页面，而时钟置换法将页面保存在环形链表中，只需要后移队头指针，就相当于是把原来的队头放到队尾了。
   • 优点：避免了移动链表节点的开销
     
5. 最近最少使用法（LRU：Least Recently Used）：优先淘汰最久未被访问的页面。根据局部性原理，一个进程在一段时间内要访问的指令和数据都集中在一起。如果一个页面很久没有被访问，那么将来被访问的可能性也比较小。
   • 优点：实验证明 LRU 的性能较好，能够降低置换频率
   • 缺点：存在缓存污染问题，即由于偶发性或周期性的冷数据批量查询，热点数据被挤出去，导致缓存命中率下降
   • 适用场景：访问分布未知的情况；[redis] 要求热点数据有效；[redis] 应用对缓存的访问符合二八定律 / 幂律分布
6. LRU-K：LRU-K 算法的核心思想是将“最近使用过 1 次”的判断标准扩展为“最近使用过 K 次”，LRU 可以认为是 LRU-1。能够降低“缓存污染”的问题。
7. 最近最不经常使用法（LFU：Least Frequently Used）：优先淘汰最近访问频率最少的数据。
   • 优点：能够避免缓存污染问题对 LRU 的命中影响
   • 缺点：存在访问模式问题，即如果访问内容发生较大变化，LFU 需要用更长的时间来适应，导致缓存命中率下降；维护相关数据结构的开销大
   • 适用场景：[redis] 数据的访问模式固定
8. 随机淘汰法（Random）：实现简单，不需要保留有关访问历史记录的任何信息
   • 适用场景：[redis] 如果应用对于缓存 key 的访问概率相等，则可以使用这个算法

操作系统常用的是 LRU 算法；一般数据的访问模式是随时间变化的，所以大多数的缓存也都是使用 LRU 算法或其变种。还有一些其他算法如 MRU、SLRU 等，见维基百科。

虚拟地址空间的组成部分

• 虚拟地址空间的组成部分
• 栈的作用、增长方向
• 堆的作用、增长方向
• 栈和堆的区别

(1) 虚拟地址空间的组成部分

整体上，操作系统将每个进程的虚拟地址空间划分成两个部分：内核空间和用户空间。内核空间存放的是内核代码和数据，用户空间存放的是用户程序的代码和数据。在 32 位操作系统中，一般将最高的 1G 字节作为内核空间，而将较低的 3G 字节作为用户空间。

进程运行在内核空间时，处于内核态，此时可以执行任何特权指令。每个进程的内核空间都是相同的，用户代码无法访问内核空间。

虚拟地址空间的完整组成：

从上往下依次是：

• 内核虚拟内存：所有进程共享内核的代码和全局数据结构，独享与进程相关的数据结构，Linux 会将内核虚拟内存的共享区域映射到被所有进程共享的物理页面上
• 用户栈：从高地址向低地址增长
• 共享库：动态链接阶段
• 运行时堆：从低地址向高地址增长
• 程序代码和数据：从可执行文件中加载（代码段、数据段、BSS 段）

(2) 栈

用户栈其实就是函数调用栈，作用主要是：

• 保存函数的局部变量
• 保存某些寄存器的值
• 向被调用函数传递参数
• 返回函数的返回值
• 保存函数的返回地址

每个函数在执行过程中都需要使用一块栈内存用来保存上述这些值，这块栈内存为该函数的栈帧（stack frame）。栈的增长和收缩由编译器插入的代码自动完成，随着函数的调用而分配，随函数的返回而自动释放。程序员无需关心，这一点与堆不同。

(3) 堆

栈内存的分配需要实现确定其大小，而堆内存允许程序在运行时动态申请某个大小的内存空间。申请的内存在函数退出后依然保留，需要手动释放。C 语言中的 malloc / free 就是从堆中分配 / 释放内存，操作系统通过一个记录空闲内存地址的链表来管理堆内存。

如果反复向操作系统申请堆内存而不释放，会导致内存泄漏。在 C / C++ 中，必须由程序员手动释放堆内存。而 Java / Golang 中有垃圾回收器，会定期主动回收内存。但是即使有垃圾回收器，也有内存泄漏的风险，比如长期持有某个大对象的引用。

(4) 栈和堆的区别

1. 增长方向：栈向低地址方向增长，堆向高地址方向增长
2. 申请回收：栈自动分配和回收，堆需要手动申请和释放
3. 生命周期：栈的数据仅存在于函数运行过程中，堆的数据只要不释放就一直存在
4. 连续分配：栈是连续分配的，堆是不连续的，容易产生内存碎片
5. 空间大小：栈的大小是有限的（如默认 8M，Linux 上通过 ulimit -s 查看），而堆的空间较大，受限于系统中有效的虚拟内存

进程的内存管理

• malloc、free 的原理
• 线程、协程的栈空间实现
• 不同语言的内存分配与垃圾回收机制（C++、Golang、Java）

• malloc、free 的原理：答案
  • malloc、free 实现思路、简单实现代码
  • malloc 分配的内存块的格式
  • 为什么 free 只需要传递一个指针就可以释放内存
  • tcmalloc 简单了解
• 解密 Go 协程的栈内存管理
• 内存管理设计精要 - Draveness

大端法、小端法

• 什么是大端法、小端法？
• 如何判断一台机器是大端法还是小端法？
• 面试真题：判断以下程序在 32 位机器上的输出

int main() {
  int a = 0x1234;
  char *p = (char *)&a;
  printf("%02x\n", *p);
  printf("%02x\n", *(p + 1));
  printf("%02x\n", *(p + 2));
  return 0;
}

1. 计算机最小的可寻址的内存单位是字节。按有效字节在内存地址中从小到大的存储顺序，可以分为大端法和小端法：大端法从高位到低位存储，小端法从低位到高位存储。比如某个 int 型整数的值为 0x01234567，存储在 0x100~0x103 的内存地址上。大端法和小端法的字节顺序如下所示：
   
2. 按内存地址顺序从低到高输出一个变量的全部字节，可以借助 char* 类型的指针来完成，见答案
3. 小端法输出 34 12 00，大端法输出 00 00 12，见答案

缓冲区溢出问题

• 什么是缓存区溢出？
• 缓冲区溢出攻击的方式
• 缓冲区溢出攻击的防范方法

C 语言使用运行时栈来存储过程信息。每个函数的信息存储在一个栈帧中，包括寄存器、局部变量、参数、返回地址等。C 对于数组引用不进行任何边界检查，因此对越界的数组元素的写操作会破坏存储在栈中的状态信息，这种现象称为缓冲区溢出。

缓冲区溢出会破坏程序运行，也可以被用来进行攻击计算机，如使用一个指向攻击代码的指针覆盖返回地址。

防范缓冲区溢出攻击的机制有三种：随机化、栈保护和限制可执行代码区域。

(1) 随机化

使用缓冲区溢出进行攻击，需要知道攻击代码的地址。因此常见的防范方法有：

1. 栈随机化：程序开始时在栈上分配一段随机大小的空间
2. 地址空间布局随机化（Address-Space Layout Randomization，ASLR）：每次运行时程序的不同部分，包括代码段、数据段、栈、堆等都会被加载到内存空间的不同区域

但是攻击者依然可以使用蛮力克服随机化，这种方式称为“空操作雪橇（nop sled）”，即在实际的攻击代码前插入很长的一段 nop 指令序列，执行这条指令只会移动到下一条指令。因此只要攻击者能够猜中这段序列的某个地址，程序就会最终经过这段序列，到达攻击代码。

因此栈随机化和 ASLR 只能增加攻击一个系统的难度，但不能完全保证安全。

(2) 栈保护

在发生缓冲区溢出、造成任何有害结果之前，尝试检测到它。常见的栈破坏检测方法是栈保护机制：在每个函数的栈帧的局部变量和栈状态之间存储一个随机产生的特殊的值，称为金丝雀值（canary）。在恢复寄存器状态和函数返回之前，程序检测这个金丝雀值是否被改变了，如果是，那么程序异常终止。

(3) 限制可执行代码区域

内存页的访问形式有三种：可读、可写、可执行。只有编译器产生的那部分代码所处的内存才是可执行的，其他页应当限制为只允许读和写。以前 x86 将读和执行视为一个标志位，可读就可执行，为了限制某些页可读但不可执行，往往会带来严重的性能损失。现在新的处理器在硬件上引入新的位，将读和执行分开，由硬件来检查页是否可执行，效率上没有损失。

I/O 模型

• 5 种 I/O 模型
• 同步 I/O 和异步 I/O
• 阻塞 I/O 和非阻塞 I/O
• I/O 多路复用：select / poll / epoll
  • 原理
  • 区别
  • 适用场景
  • 水平触发、边缘触发
  • 为什么边缘触发必须使用非阻塞 I/O？
  • 为什么 Redis 单线程模型依然效率很高？

• 5 种 I/O 模型：阻塞 I/O、非阻塞 I/O、信号驱动式 I/O、I/O 多路复用、异步 I/O（AIO）
• I/O 同步和异步的区别在于：将数据从内核复制到用户空间时，用户进程是否会阻塞（需要用户进程来完成）
• I/O 阻塞和非阻塞的区别在于：进程发起系统调用后，是会被挂起直到收到数据后在返回、还是立即返回成功或错误
• 
• I/O 多路复用 答案

协程

• 什么是协程？
• 进程、线程、协程的区别
• 协程为什么效率高？
• 协程的实现原理
• 协程切换哪些数据？
• 什么时候用协程、什么时候用线程？[TODO]
• 协程的栈空间大小

协程是一个用户态的线程，用户在堆上模拟出协程的栈空间。当需要进行协程上下文切换的时候，主线程只需要交换栈空间和恢复协程的一些相关的寄存器的状态，就可以实现上下文切换。没有了从用户态转换到内核态的切换成本，协程的执行也就更加高效。

(1) 协程的实现原理：

最基本的协程实现原理可以参考这篇文章，分析了一个简单的 C++ coroutine 的源码实现。协程的实现重点在于：

1. 在堆上模拟栈，从而实现一个用户态的线程
2. 调度器，负责协程的调度与上下文切换

Golang 的 goroutine 也是一个有栈协程。Golang 实现了自己的调度器 (GMP 模型)，使用队列管理协程 (运行队列、等待队列)；Golang 封装了系统调用，将阻塞的系统调用改为非阻塞的系统调用，从而在系统调用前将陷入“阻塞”的协程“切换”到等待队列，并让出计算资源。从 1.2 版本开始，goroutine 变为抢占式调度。

[进阶内容] 关于 go 语言的调度器原理和 goroutine 实现原理，可以阅读这些文章：

• Go 语言调度器与 Goroutine 实现原理 - Draveness
• Scheduling In Go: Part I、Part II、Part III：William Kennedy 的经典文章

(2) 协程切换哪些数据？

[TODO 待验证] 类似于线程的切换，协程切换时需要保存：

• 寄存器，包括 PC (指令位置) 和 CPU 寄存器 (参数、上下文…)
• 栈指针
• 返回值

(3) 协程的栈空间大小：

线程栈是固定大小的，可以使用 ulimit -a 查看。默认情况也是 8M（8192 字节），而协程占用的栈空间大小由 runtime 按需进行分配 (初始时很小，随后动态扩展)，可以查看这篇文章。

写时复制 Copy-on-write

• 为什么需要 COW？
• 实现原理
• 优缺点
• 实际应用

答案

其他

• 动态链接、静态链接的区别
• 字符集和字符编码的含义
• 文字乱码的原因
• Unicode 和 UTF-8 的区别

• Google 有详细的回答
• 字符编码笔记：ASCII，Unicode 和 UTF-8 - 阮一峰

计算机网络

协议栈

• OSI 协议栈
• TCP/IP 协议栈
• 每一层的作用
• 每一层的常见协议与作用

答案

TCP 文章推荐

在复习 TCP 相关知识点前，强烈推荐阅读这两篇文章，写得很好：

• TCP 的那些事儿（上）
• TCP 的那些事儿（下）

此外，下面这个网站更全面详细地介绍了 TCP 协议，同样推荐阅读：

• The TCP/IP Guide

TCP 的流量控制和拥塞控制

• TCP 的流量控制机制
  • 滑动窗口的原理
  • 零窗口
  • Nagle 算法
• TCP 的拥塞控制机制
  • 慢启动
  • 拥塞避免
  • 超时重传
  • 快速重传 / 快速恢复

答案

TCP 的三次握手和四次挥手

• 三次握手、四次挥手过程
• 握手阶段、传输阶段、挥手阶段的序列号与确认号
• 为什么需要三次握手，而不是两次或四次？
• 为什么需要四次挥手，而不是三次？
• 为什么客户端 TIME_WAIT 需要等待 2MSL？
• TIME_WAIT 是哪一方会进入的状态？
• SYN 攻击的原理

答案

TCP 的粘包问题

• 什么是粘包？
• 粘包的产生原因
• 如何解决粘包问题？

TCP 是基于字节流的，数据块是没有边界、没有结构的字节流，因此可能产生粘包：

1. 发送方为了将多个发往接收端的包，更有效的发到对方，使用了优化方法（Nagle算法），将多次间隔较小、数据量小的数据包，合并成一个大的数据包一次性发送。
2. 接收方不能及时读取数据，导致缓冲区中的多个包粘连。

解决方法：

1. 发送方关闭 Nagle 算法
2. 应用层定义消息边界，最常见的两种解决方案就是基于长度或者基于终结符（Delimiter）
   1. 基于长度的实现有两种方式，一种是使用固定长度；另一种方式是使用不固定长度，但是需要在应用层协议的协议头中增加表示负载长度的字段，HTTP 协议的消息边界就是基于长度实现的
   2. HTTP 协议除了使用基于长度的方式实现边界，也会使用基于终结符的策略，当 HTTP 使用块传输（Chunked Transfer）机制时，HTTP 头中就不再包含 Content-Length 了，它会使用负载大小为 0 的 HTTP 消息作为终结符表示消息的边界

除了这两种方式之外，我们可以基于特定的规则实现消息的边界，例如：使用 TCP 协议发送 JSON 数据，接收方可以根据接收到的数据是否能够被解析成合法的 JSON 判断消息是否终结。

但值得注意的是，粘包并不是 TCP 协议本身的“问题”，而是一个“现象”。TCP 本身面向字节流的特性，导致会有所谓的“粘包”问题，需要应用层进行拆分。所以也有一种说法是“TCP 粘包是一个伪命题”。

为什么 UDP 协议没有粘包问题？UDP 是面向报文的，应用层交给 UDP 多长的报文，UDP 就照样发送，既不合并，也不拆分，而是保留这些报文的边界。

参考资料：为什么 TCP 协议有粘包问题 - draveness。

TCP 协议（其他）

• TCP 为什么是面向连接的？
• TCP 如何保证传输的可靠性？
• TCP / UDP 协议头 [TODO]

TCP 为什么是面向连接的：

• 发送之前需要先建立连接（三次握手）
• 使用排序和确认机制（分组之间并不是独立的；记录了分组之间的状态信息）
• 具有流量控制与拥塞控制
• 发送完毕后要释放连接（四次挥手）

参考资料：TCP/IP 高效编程：改善网络程序的 44 个技巧 第 2 章：理解面向连接和无连接的区别

TCP 如何保证传输的可靠性？

• 序列号：解决乱序问题
• 确认号 / 超时重传机制：解决丢包问题

TCP、UDP 对比

• 二者对比
• 应用场景
• 面向字节流、面向报文的含义

• TCP：面向连接的、可靠的、基于字节流的传输层通信协议
• UDP：无连接的、不可靠的、基于报文的传输层通信协议
• 面向字节流：TCP 将要发送的数据视为无结构的字节流，如果发送的数据太长，就拆分发送，如果发送的数据太短，则积累较多的字节后再发送
• 面向报文：UDP 一次发送一个报文，不管多大，都以报文为发送单位

HTTP 原理

• HTTP 请求方法、GET 和 POST 的区别？
• HTTP 状态码
• 301/302 重定向原理
• 304 缓存原理，不同缓存头的区别
• HTTP/1.1、2.0 引入的变化
• HTTP/2.0 关键特性：压缩首部、服务端推送、多路复用
• HTTP 请求报文、响应报文的格式
• Cookie 和 Session 的区别
• HTTP 分块传输编码
• Header 中 Content-Type / Content-Length / Content-Encoding 等字段的含义
• [进阶] 断点续传原理 [TODO]
• [进阶] QUIC、HTTP 3.0

答案

HTTPS 原理

• HTTPS 四次握手过程
• 访问的网站是如何自动切换到 HTTPS 的
• 什么是中间人攻击？如何预防？

HTTP 的缓存机制

• 强制缓存、协商缓存的原理，两者对比
• 判断缓存失效的依据（Expires、Last-Modified、ETag 等）
• 与缓存相关的 HTTP 状态码
• 与缓存相关的 HTTP 消息头
• 用户行为与缓存是否刷新的关系
• 缓存策略的选择思路

DNS 原理

• DNS 记录格式
• DNS 的解析过程
• DNS 劫持原理与防范 [TODO]
• [进阶] 主流的公有云的 DNS 服务端架构

整体流程：浏览器搜索自身的 DNS 缓存、搜索操作系统的 DNS 缓存、读取本地的 Host 文件和向本地 DNS 服务器进行查询等。

DNS 查询共有两类：递归查询和迭代查询。递归查询是指，当 A 向 B 查询某个域名的 IP 地址时，如果 B 不知道被查询的域名的 IP 地址，那么 B 会替 A 向更上层的服务器发起查询，将查询结果返回 A。迭代查询是指，当 A 向 B 查询某个域名的 IP 地址时，如果 B 不知道被查询的域名的 IP 地址，B 会告诉 A 下一步应该向哪个服务器查询，由 A 自己去查。

一般来说，主机（也就是我们的电脑）向本地域名服务器的查询是递归查询，而本地域名服务器向根域名服务器的查询是迭代查询。

IP 原理

• IP 号分类规则
• 如何划分子网
• IP 分组转发规则
• 什么是 NAT 协议
• 什么是 ARP 协议
• 集线器、网桥、交换机、路由器位于哪一层
• 为什么局域网的 IP 普遍是 192.168 开头
• IPv6 的基本概念 / 为什么引入 IPv6

从输入一个 URL 到页面加载完成的过程

答案

两台主机间的通信过程

[TODO] 同局域网、不同局域网的情况。ARP、IP 协议。

什么是 ARP 协议

常用的负载均衡软件

[TODO] 第四层 LVS、第七层 Nginx。

Socket 通信

• Socket 通信流程图（服务端、客户端）
• 创建服务端：socket() / bind() / listen() / accept() / read()/write() / close()
• 创建客户端：socket() / connect() / read()/write() / close()
• 上述各个系统调用的作用
• TCP 和 UDP 可以同时监听同一个端口吗？

参考文章：

• https://www.cnblogs.com/skynet/archive/2010/12/12/1903949.html

流程图 [来源]：

TCP 和 UDP 可以同时监听同一个端口，操作系统根据五元组 {传输协议，源IP，目的IP，源端口，目的端口} 判断数据的接收者。

数据库

数据库基础

• 数据库三个范式的定义 [TODO]
• 内连接、外连接的含义
• 主键、联合主键
• 游标的原理

数据库的存储引擎

• MySQL 支持哪些存储引擎
• 不同存储引擎的区别、适用场景
• InnoDB 引擎的原理
• 如何选择存储引擎

答案

数据库的索引

• 索引类型
• 索引的实现原理
• 索引的优缺点
• 如何设置索引？
• 数据库为什么用 B+ 树做索引？如果是内存数据库用什么？
• 联合索引与最左匹配原则
• 数据库查询 offset 的流程？如果 offset 非常大会有什么问题？

数据库为什么用 B+ 树做索引？

用 B+ 树是为了减少 I/O 次数：

• 不可能把索引全部加载到内存中，只能逐一加载每个索引节点
• B+ 树的单个节点中包含的值个数越多，那么节点总数就会越少，I/O 次数也越少
• B+ 树高度一般为 2-4 层，查找记录时最多只需要 2-4 次 I/O
• 相反，二叉搜索树的高度高，所以需要的 I/O 次数更多

如果是内存数据库，不涉及磁盘 I/O，可以直接用二叉搜索树。

数据库的事务

• 事务的特性
• 事务可能存在的并发问题
• 事务的隔离级别，各个隔离级别可能发送的问题

• 『浅入深出』MySQL 中事务的实现
• 数据库内核杂谈 (十)：事务、隔离、并发（1）
• MySQL的四种事务隔离级别

数据库的并发控制

• 乐观锁、悲观锁、MVCC 的原理
• 不同机制的适用场景

• 数据库内核杂谈 (十一)：事务、隔离、并发（2）
• 数据库内核杂谈 (十二)：事务、隔离、并发（3）
• 浅谈数据库并发控制 - 锁和 MVCC

数据库分库、分表、主从、读写分离

• 垂直分库、垂直分表、垂直拆分的优缺点
• 库内分表、分库分表、分表策略
• 垂直分库的关键问题：跨节点 Join、事务
• 分库分表的关键问题：事务、查询、跨分片 Join、跨节点聚合、唯一 ID、分页排序
• 主从复制的原理（binary log）
• 读写分离

数据库的优化方法

• SQL 语句优化
• 索引优化
• 数据库部署优化（主从分离、读写分离）
• 数据库拆分
• 系统配置的优化、硬件的优化

ORM 和原生 SQL 的区别

ORM 封装了数据库底层实现的差异，开发人员不需要关注数据库是 mysql、mssql 还是 mongodb（不同数据库在 SQL 语法上有差异）。

ORM 使用链式函数调用来构建 SQL 语句，比直接写 SQL 语句更加友好，也不容易出错。

ORM 定义的模型是强类型的，能够编写类型友好的代码。而原生 SQL，返回的数据类型是未知的。

此外 ORM 能够抽象表与表之间的关系，可以让开发者专注于逻辑的编写。ORM 是面向对象的，利于管理和组织代码。

ORM 的缺点是效率低，另外有些场景只能用原生 SQL 实现。

Redis 相关

• 为什么使用 Redis？
• Redis 基本数据类型和使用场景
• zset、跳表
• Redis 持久化方案对比
• Redis 线程模型
• 缓存雪崩 / 缓存穿透 / 缓存击穿及其解决方案
• Redis 的大 key 问题
• Redis 单个 key 能够承受的最大 QPS（10W）
• Redis 实现分布式锁
• Redis 与数据库的同步问题

• 《吊打面试官》系列 — Redis 基础
• 《吊打面试官》系列 — 缓存雪崩、击穿、穿透
• 《吊打面试官》系列 — Redis 哨兵、持久化、主从
• Redis 设计与实现

数据结构

哈希表

• 哈希表的实现方式
• 哈希表冲突解决方法
• 哈希表如何查找数据

Map 的实现

• Java HashMap 实现原理
• Go map 原理
• map 使用不同数据结构实现的区别

排序算法

• 不同排序算法的时间复杂度、空间复杂度、稳定性、代码实现
• 不同排序算法的适用场景
• 外部排序的实现原理

排序算法总结：

基数排序：rr 代表关键字的基数，比如对十进制数字的 r==10r==10；dd 代表位数，比如 [0~999] 范围内的数字的 d==3d==3。
桶排序：mm 代表桶的个数。

稳定的排序算法：冒泡排序、归并排序、基数排序、直接插入排序、桶排序。
不稳定的排序算法：快速排序、堆排序、直接选择排序、希尔排序。

O(nlogn) 的排序算法：快速排序、堆排序、归并排序。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        xxxSort(nums); // TODO: 调用具体的排序算法
        return nums;
    }

    void bubbleSort(vector<int>& nums) {}

    void quickSort(vector<int>& nums) {}

    // ...
};

void bubbleSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n-1; i++) { // i 表示已经排序的元素，排完 n-1 个后最后一个也不需要排了
        for (int j = 1; j < n-i; j++) {
            if (nums[j-1] > nums[j]) {
                swap(nums[j-1], nums[j]);
            }
        }
    }
}

插入排序：

void insertSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        int key = nums[i]; // 待排序元素
        int j = i-1; // 已排序元素中最后一个不大于 key 的位置，key 将插在 j+1 的位置
        while (j >= 0 && nums[j] > key) {
            swap(nums[j], nums[j+1]);
            j--;
        }
        nums[j+1] = key;
    }
}

直接选择排序：

void selectSort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n-1; i++) { // 最后一个不用排
        int min = i;
        for (int j = i+1; j < n; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums[i], nums[min]);
    }
}

快速排序：

• [0, last) 表示所有小于 pivot 的元素集合，初始时 last = 0 表示区间为空
• 选择左侧第一个元素作为 pivot
• 不断地将小于 pivot 的元素，移动到该区间后面
• 递归过程中，区间左边界为 start

void quickSort(vector<int> &nums) {
    quickSort(nums, 0, nums.size() - 1);
}
    
void quickSort(vector<int>& nums, int start, int end) {
    if (start >= end) return;
    int pivot = partition(nums, start, end);
    quickSort(nums, start, pivot-1);
    quickSort(nums, pivot+1, end);
}

int partition(vector<int>& nums, int start, int end) {
    int pivot = nums[start];
    int last = start;
    for (int i = start+1; i <= end; i++) {
        if (nums[i] < pivot) {
            swap(nums[i], nums[last++]);
            swap(nums[last], nums[i]);
        }
    }
    nums[last] = pivot;
    return last;
}

归并排序：有递归法和迭代法两种实现方式。

void mergeSort (vector<int>& nums) {
  mergeSort(nums, 0, nums.size() - 1);
}

void mergeSort(vector<int>& nums, int left, int right) {
  if (left >= right) {
    return;
  }
  int mid = (left + right) / 2;
  mergeSort(nums, left, mid);
  mergeSort(nums, mid + 1, right);
  merge(nums, left, mid, right);
}

// 合并 [left, mid]，[mid+1, right] 两部分有序数组
void merge(vector<int>& nums, int left, int mid, int right) {
  vector<int> newNums(right - left + 1);
  int c = 0, i = left, j = mid + 1;
  while (i <= mid && j <= right) {
    if (nums[i] < nums[j]) {
      newNums[c] = nums[i];
      c++;
      i++;
    } else {
      newNums[c] = nums[j];
      c++;
      j++;
    }
  }
  while (i <= mid) {
    newNums[c] = nums[i];
    c++;
    i++;
  }
  while (j <= right) {
    newNums[c] = nums[j];
    c++;
    j++;
  }
  for(i = left; i <= right; i++) {
    nums[i] = newNums[i-left];
  }
}

void mergeSort(vector<int>& nums) {
    int n = nums.size();
    for (int s = 1; s < n; s*=2) { // 遍历所有可能的区间长度，注意这里的范围是 s < n，不能是 s <= n/2
        for (int k = 0; k < n; k+=2*s) { // 找每个区间
            int left = k, 
                mid = min(k+s, n), 
                right = min(k+2*s, n);
            merge(nums, left, mid, right);
        }
    }
}

// 合并两个有序区间 [left, mid) 与 [mid, right)，使 [left, right) 有序
// 注意区间是左闭右开，这是为了遵循 STL 的计算方式，可以简化代码（少很多 +1、-1）
void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> arr(right-left);
    int i = left, j = mid, k = 0;
    while (i < mid && j < right) {
        if (nums[i] < nums[j]) {
            arr[k++] = nums[i++];
        } else {
            arr[k++] = nums[j++];
        }
    }
    if (i < mid) copy(nums.begin()+i, nums.begin()+mid, arr.begin()+k);
    if (j < right) copy(nums.begin()+j, nums.begin()+right, arr.begin()+k);
    copy(arr.begin(), arr.end(), nums.begin()+left);
} 

堆排序：

• 分为“构建堆”、“堆排序”两个过程
• “构建堆”可以使用向上调整或向下调整，“堆排序”必须使用向下调整
• 升序 -> 构建最大堆，降序 -> 构建最小堆

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 构建堆
    for (int i = n/2-1; i >= 0; i--) { // 从最后一个非叶节点开始，不断向下调整
        heapAdjustDown(nums, i, n);
    }
    // 堆排序
    for (int i = n-1; i > 0; i--) {
        swap(nums[0], nums[i]); // 将堆顶元素弹出，和堆的末尾元素交换，此时 [i, n-1] 为排序后的区间，[0, i-1] 为堆的元素范围
        heapAdjustDown(nums, 0, i); // 维护堆
    }
}

// 向下调整，只调整下标为 s 的元素，堆的大小为 n
void heapAdjustDown(vector<int>& nums, int s, int n) {
    int t = nums[s];
    for (int i = 2*s+1; i < n; i = 2*i+1) {
        if (i+1 < n && nums[i] < nums[i+1]) {
            i++;
        }
        if (t >= nums[i]) { // 构建最大堆
            break;
        }
        nums[s] = nums[i];
        s = i;
    }
    nums[s] = t;
}

void heapSort(vector<int>& nums) {
    int n = nums.size();
    // 构建堆
    for (int i = 0; i < n; i++) { // 从第一个节点开始遍历，直到最后一个节点,向上调整
        headAdjustUp(nums, i);
    }
    // 堆排序
    for (int i = n-1; i > 0; i--) {
        swap(nums[0], nums[i]);
        heapAdjustDown(nums, 0, i);
    }
}

// 向上调整
void headAdjustUp(vector<int>& nums, int s) {
    int t = nums[s];
    // i 表示当前节点，手动计算父节点
    for (int i = s; i > 0; i = (i - 1) / 2) {
        if (nums[(i-1)/2] < t) {
            nums[s] = nums[(i-1)/2];
            s = (i - 1) / 2;
        } else {
            break;
        }
    }
    nums[s] = t;
}

void heapAdjustDown(vector<int>& nums, int s, int n) {
    int t = nums[s];
    for (int i = 2*s+1; i < n; i = 2*i+1) {
        if (i+1 < n && nums[i] < nums[i+1]) {
            i++;
        }
        if (t >= nums[i]) {
            break;
        }
        nums[s] = nums[i];
        s = i;
    }
    nums[s] = t;
}

基数排序：

• 一种非基于比较的排序算法
• 分别按照每一位进行排序，有最高位优先（Most Significant Digit first，MSD）和最低位优先（Least Significant Digit first，LSD）两种方法
• 基数排序以计数排序为基础，按照每一位排序时，实际上就是在进行计数排序

下面使用 LSD 方法实现基数排序。

73, 22, 93, 43, 55, 14, 28, 65, 39, 81

对以上未排序数组，首先按照个位数的数值进行排序 —— 遍历每个数，并将其按照个位数分桶，对于同一个桶内的数字，维持其相对关系（稳定性）：

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
|-- --- --- --- --- --- --- --- --- --|
|   81  22  73  14  55          28  39|
|           93      65                |
|           43                        |

随后依次串联桶中的数字，得到一个个位升序的序列：

81, 22, 73, 93, 43, 14, 55, 65, 28, 39

接着根据十位数分配：

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
|-- --- --- --- --- --- --- --- --- --|
|   14  22  39  43  55  65  73  81  93|
|       28                            |

随后依次串联桶中的数字，得到一个整体升序的序列：

14, 22, 28, 39, 43, 55, 65, 73, 81, 93

计数排序的原理是：对于一个待排序序列中的某一个元素 x，一旦确定了该序列中小于 x 的元素的个数 c，就可以将 x 直接放在最终的有序序列的 c+1 位置上。计数排序的时间复杂度为 Ο(n+k)Ο(n+k)，空间复杂度为 O(k)O(k)，其中 nn 为序列的元素个数，kk 为元素的取值范围。代码如下：

#define K 1000000 // nums[i] 的取值范围，0~K
vector<int> aux(nums.size()); // 辅助数组，存放最终排序后的结果
vector<int> count(K, 0); // count[x] 表示值为 x 的元素的个数
for (int i = 0; i < nums.size(); i++) // 计数
    count[nums[i]]++;
for (int i = 1; i < count.size(); i++) // 统计小于等于 nums[i] 的元素个数
    count[i] += count[i - 1];
for (int i = nums.size() - 1; i >= 0; i--) // 从后往前遍历，将每个元素放到正确的位置
    aux[--count[nums[i]]] = nums[i]; // TODO：先思考一下为什么这么写，再看下文的解释
for (int i = 0; i < nums.size(); i++) // 复制辅助数组
    nums[i] = aux[i];

解释 aux[--count[nums[i]] = nums[i]：

• count[nums[i]] 表示小于等于 nums[i] 的元素个数，所以需要将 nums[i] 放到 count[nums[i]] - 1 的位置
• 与 nums[i] 相等的元素可能有多个，所以放完 nums[i] 以后需要将 count[nums[i]] 减 1，从而让后面的元素放到正确的位置
• for 循环是从后往前遍历，而值相等的元素也是从后往前放置到最终的数组中，因此保证了排序的稳定性

举例：给定待排序数组 [2(a), 2(b), 1, 3]，有 count[1] == 1，count[2] == 3，count[3] == 4，各变量的变化过程如下：

当前元素  count[]数组      aux 数组  
   _    [0, 1, 3, 4]    [_ _ _ _]
   3    [0, 1, 3, 3]    [_ _ _ 3]
   1    [0, 0, 3, 3]    [1 _ _ 3]
  2(b)  [0, 0, 2, 3]    [1 _ 2(b) 3]
  2(a)  [0, 0, 1, 3]    [1 2(a) 2(b) 3]

vector<int> radixSort (vector<int>& nums) {
    int maxVal = *max_element(nums.begin(), nums.end());
    int exp = 1; // 1, 10, 100, 1000 ...
    int radix = 10; // 基数为 10
    vector<int> aux(nums.size()); // 存放最终结果

    /* LSD Radix Sort */
    while (maxVal / exp > 0) { // 从低位向高位，遍历每一位
    // 这里是计数排序的代码
        vector<int> count(radix, 0);
        for (int i = 0; i < nums.size(); i++)
            count[(nums[i] / exp) % 10]++; // 统计当前位为 0～9 的元素数量
        for (int i = 1; i < count.size(); i++)
            count[i] += count[i - 1];
        for (int i = nums.size() - 1; i >= 0; i--)
            aux[--count[(nums[i] / exp) % 10]] = nums[i];
        for (int i = 0; i < nums.size(); i++)
            nums[i] = aux[i];
        exp *= 10;
    }

    return aux;
}

vector<int> sortArray(vector<int>& nums) {
    int minVal = *min_element(nums.begin(), nums.end());
    int offset = minVal < 0 ? -minVal : 0;
    for (int i = 0; i < nums.size(); i++) nums[i] += offset;
    nums = radixSort(nums);
    for (int i = 0; i < nums.size(); i++) nums[i] -= offset;
    return nums;
}

桶排序：TODO

希尔排序：略。

不同排序算法的适用场景：

1. 若 n 较小(如 n≤50)，可采用直接插入或直接选择排序。
2. 若文件初始状态基本有序，则应选用直接插人、冒泡或随机的快速排序。
3. 若 n 较大，则应采用时间复杂度为 O(nlogn) 的排序方法：快速排序、堆排序或归并排序。
   1. 当待排序的关键字是随机分布时，快速排序的平均时间最短。
   2. 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。
   3. 若要求排序稳定，则可选用归并排序。
   4. 归并排序需要较大的额外空间，但归并排序可以多路归并。
   5. 相比于从长度为 1 的序列开始归并，归并排序也可以和直接插入排序结合使用，先通过直接插入排序获得较长的有序序列，然后再进行归并。这种方式依然是稳定的。

大部分情况可以直接使用快速排序。

当待排序的关键字无法全部加载到内存中时，需要使用归并排序进行外部排序。

海量数据问题

• 百万量级的数据排序（任意大小，或者 0～10000）
• 百万量级的数据查询在不在
• 百万量级的数据求 TopK

百万量级的数据排序：

• 任意大小：外排序，先将数据拆分到多个文件中，分别加载到内存中排序，然后再归并到一个文件里。实际上就是 LeetCode 23. 合并 k 个有序链表，需要用到最小堆。
• 范围为 [0, 10000]：计数排序。

百万量级的数据查询在不在：可以使用位图，前提是数据范围不超过内存大小。

百万量级的数据求 TopK：数据流的 TopK 问题，维护一个大小为 k 的小根堆，然后分片读入数据，并更新堆。

计算机组成原理

引用和指针的区别

TODO

函数的参数是如何传递的

引用传递、值传递。

大端法、小端法及其判断

答案

原码、反码、补码

正数的原码、反码、补码都一样。这里只针对负数讨论。

反码是原码除符号位外的所有位进行按位取反运算。补码是原码符号位不变，其他位取反再加 1，或者反码再加 1。

比如：-1，原码 10000001，反码 11111110，补码 11111111。

计算机使用的是补码加法，这样就可以将减法运算转为加法运算，减去一个数等价于加上一个相反数，也即加上这个相反数的补码。

存储器的层次结构

• 存储器的层次结构
• 局部性原理
• 如何编写局部性友好的代码？

程序的局部性原理包含两个方面，一个是时间局部性，即程序在运行时，最近刚刚被引用过的一个内存位置容易再次被引用。另一个是空间局部性，即最近引用过的内存位置以及其周边的内存位置容易再次被使用。

编写局部性友好的代码：

• 使用局部变量
• 数组步长为 1（利用缓存行）
• 多维数组按行遍历（利用缓存行）

编程语言

Golang

• Golang 和其他语言的对比，优缺点
• Golang 编译速度为什么快？
• Golang 的内存管理与垃圾回收
• Golang slice 的内存分配细节
• goroutine 与 channel 的同步问题
• Golang 的 GMP 模型
• 什么情况下 M 会进入自旋的状态？
• WaitGroup 使用
• Channel、互斥锁、读写锁的适用场景
• 动态 interface 和静态 interface
• Golang 里返回一个 MyError 类型的 nil，可以用 err != nil 判断吗？答案
• 其他资源
  • lifei6671/interview-go
  • xiaobaiTech/golangFamily
  • Search · golang 面试

GMP 模型分别对应 goroutine、系统线程、logic processor。

M 为了保证自己不被释放，所以自旋。这样一旦有 G 需要处理，M 可以直接使用，不需要再创建。换句话说，如果 M 自旋，表示此时没有 G 需要处理。

C++

• C++ 构造函数、析构函数的执行顺序
• C++ 多态是如何实现的？
• C++ 为什么继承的析构函数必须是虚函数？
• 编写一个 string 类，实现构造函数、析构函数、拷贝构造函数、operator =、c_str 方法（返回 const char*）
• 64 位机器上执行以下代码的输出

  char str[] = "Hello";
  char* pstr = str;
  const char* str_list[] = {"Hello", "World"};
  void* pbuf = malloc(100);
  int n = 10;
  
  sizeof (str ) = ________，
  sizeof ( pstr ) = _____ ，
  sizeof ( str_list ) = _____ ，
  sizeof ( pbuf ) = _____ ，
  sizeof ( n ) = _________
  void func ( char str[100])
  {
  sizeof( str ) = _____ 
  }

• 其他资源
  • chankeh/cpp-backend-reference
  • huihut/interview

1. 析构函数：基类 -> 成员类 -> 自身；析构函数相反。因为子类在构造函数和析构函数中可以访问父类（基类）。
2. 动态联编（运行时绑定）[TODO: 不确定的回答]
3. [TODO: 不会]
4. [TODO: 不会]

5. 6    // 字符数组的大小，5 + 1 (末尾的 \0)
   8    // 字符指针大小，8 字节
   8    // 字符指针数组的指针大小，8 字节
   8    // 指针大小，8 字节，64 位机器的指针大小都是 8 字节
   4    // int 在 32 位和 64 位系统都是 4 字节，long 在 32 位系统是 4 字节，在 64 位系统是 8 字节
   100  // 字符数组的大小

   
   

开发与运维

运维问题

• 如何分析进程的消失原因？
• 如何分析、排查现场问题？
• 如何应对突发流量？
• 压测时关注哪些指标？
• 如何提升服务稳定性？
• 如何优化服务性能？

如何优化服务性能？火焰图是一个常用的工具。各类语言还有 profile 工具（比如 Golang 的 pprof），profile 就是定时采样，收集 CPU、内存等信息，进而给出性能优化指导。也可参考知乎的这个问题。

Linux 常用命令

• 如何查看某个命令的文档？
• 如何查看占用某个端口的进程？
• 如何搜索当前目录下某个名字的文件？
• 如何统计文件行数？
• 如何统计一个文件中出现次数最多的前 10 个单词？
• 统计 nginx 日志文件中请求量最高的前 10 个 IP，假设日志文件格式是 {ip} {time} {…}，每有一个请求会生成一行日志。
• grep 查找文件内容常用的几个选项

// 如何查看某个命令的文档？ man // 如何查看占用某个端口的进程？ lsof -i :{port} // 如：lsof -i :8080 // 如何搜索当前目录下某个名字的文件？ find ./ -name filename // 如何统计文件行数？ wc [选项] 文件1 文件2 -c 统计字节数
  -l 统计行数
  -w 统计字数 // 如何统计一个文件中出现次数最多的前 10 个单词？ cat words.txt | sort | uniq -c | sort -nr | head -10 sort: 对单词进行排序，以行为单位。-n 以数字格式排序而非 ascii 字符，-r 从大到小输出。
  uniq：显示唯一的行，只统计相邻的行，所以必须先排序。-c 每行行首加上本行在文件中出现的次数。 // grep 查找文件内容常用的几个选项 -A 输出匹配行之后的多少行
  -B 输出匹配行之前的多少行
  -C 输出匹配行前后多少行
  -c --count 只统计总行数
  -i 忽略大小写

  -e 使用正则表达式
  -n --line-number 显示行号，常和 -r 一起使用
  -r 递归搜索整个目录
  -v --revert-match 反转查找，查找不包含指定字符串的文本行

  --color 关键字着色

统计 nginx 日志文件中请求量最高的前 10 个 IP。假设 Nginx 的日志每行记录一个请求的相关信息，用空格分隔各个字段：

{ip} {time} {header} {status} {useragent} {path}
220.181.108.104 - - [09/Apr/2015:07:00:20 +0800] "GET /xref/linux-3.18.6/ HTTP/1.1" 502 181 "-" "Mozilla/5.0 (compatible; B*aiduspider/2.0; +http://www
.baidu.com/search/spider.html)" 

则：

cat nginx.log | awk '{print $1}' | sort | uniq -c | sort -nr | head -10 | awk '{print $2}' 

• awk '{print $1}'：输出 nginx 日志第一列，即 ip 地址。
• uniq -c：相邻的相同行只显示一个，并在前面添加出现次数。由于只统计相邻行，所以需要先 sort。
• sort -nr：从大到小排序，-n 表示将第一列视作数字进行排序，输出的第一列是出现次数。
• head -10：取前 10 个。
• awk '{print $2}'：输出第二列，只有 ip 地址。

Linux 相关问题

• Linux 各个目录的作用
• Linux 的定时任务
• Linux 文件权限的含义

Git 常用命令

• merge, rebase, cherry-pick, reset, reflog
• 推荐学习 Learn Git Branching 的所有课程，足以应对工作需要

常用的中间件

中间件是为应用提供通用服务和功能的软件。以下是分类和举例：

• RPC
  • drpc
  • thrift
• 内存缓存
  • redis
  • memcached
• 消息队列
  • kafka
  • rabbitmq
• 数据库分片
• 动态配置中心
• 打点
• 分布式链路追踪
  • opentracing
• 微服务 / 服务注册、发现
  • etcd
  • zookeeper

系统设计题

• 短网址系统
• 分布式 ID 生成器
• 定时任务调度器，要求：对外表现的颗粒度为秒级；能处理海量定时任务；单机、单线程实现；具有 Schedule() 和 Cancel() 两个接口。
• 如果后端有许多台服务器，如何保存用户的 session？
• 其他资源
  • soulmachine/system-design / 在线阅读
  • donnemartin/system-design-primer
  • checkcheckzz/system-design-interview
  • Search · system design

多线程编程

• 两个线程交替打印奇偶数 Bilibili 视频课

分布式

RPC

• RPC 框架是长连接还是短连接？
• RPC 和 HTTP 对比？
• RPC 传输速度比 HTTP 更快吗？
• RPC 框架的组成部分与实现原理（客户端、服务端、序列化协议、传输协议）
• 常见的 RPC 序列化协议及对比
• 常见的 RPC 传输协议及对比
  • Protobuf
  • Thrift
• RPC 传输可以使用 HTTP 协议吗？
• 了解哪些不同的 RPC 框架？对比

分布式原理

• 分布式概念（服务注册、服务监控、负载均衡等）
• 分布式系统一致性、CAP、BASE 理论（低频）
• 你参与的业务满足 CAP 理论中的 CP 还是 AP？

分布式组件

• 消息队列的作用，原理
• etcd
• memcache：内存管理（内存结构、分配方式、回收方式）、分布式（实现原理、分布式算法）
• ZooKeeper：工作过程、zab 协议、节点类型、Watcher、会话

分布式算法

• 分布式共识算法：Paxos，Raft（低频）
• 分布式事务的相关算法：两阶段提交、三阶段提交
• Google 的 MapReduce、BigTable 等论文
• 分布式 UUID 生成算法（数据库自增 ID、雪花算法等）

网络安全

• XSS：原理、攻击方式、防御方式
• CSRF：原理、防御方式
• 浏览器的同源策略、CORS
• OAuth2.0 原理：答案

其他面经汇总

💡 校招复习 / 面试方法论