以下知识均在后台开发面试中实际出现过、总结而来。

C++

多态的实现

即虚函数表。

STL 容器库

容器库 - cppreference.com

unordered_map 和 map 的区别

略。

multimap 和 map 的区别

略。

智能指针

智能指针（现代C++） | Microsoft Docs

智能指针是对普通指针的一个封装。普通指针 new 了以后一定要 delete，而智能指针是一个类，当这个类的对象超出作用域以后，会自动调用析构函数，因此不再需要 delete，也不会因为忘记 delete 而发生内存泄露。

智能指针和普通指针的对比：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void UseRawPointer()
{
    // Using a raw pointer -- not recommended.
    Song* pSong = new Song(L"Nothing on You", L"Bruno Mars"); 

    // Use pSong...

    // Don't forget to delete!
    delete pSong;   
}


void UseSmartPointer()
{
    // Declare a smart pointer on stack and pass it the raw pointer.
    unique_ptr<Song> song2(new Song(L"Nothing on You", L"Bruno Mars"));

    // Use song2...
    wstring s = song2->duration_;
    //...

} // song2 is deleted automatically here.

智能指针体现什么机制：封装。

  • unique_ptr：unique_ptr 的出现是为了替代 C++98 的 auto_ptr (而 auto_ptr 于 C++11 中被弃用)。如果不知道用什么，默认用 unique_ptr 就对了。unique_ptr 只占一个指针大小的空间
  • shared_ptr：shared_ptr 的管理类似于 Python 的垃圾回收机制：对变量进行计数（如下图）。拷贝构造 auto sp3(sp2); 和赋值 auto sp4 = sp2; 都会使得计数++。shared_ptr 占两个指针大小的空间
  • weak_ptr：shared_ptr 中如果有循环引用，导致二者的计数都不为 0，会导致内存泄露。可以在引用的地方使用 weak_ptr 并将 shared_ptr 赋给它，这不会使得 shared_ptr 计数++，之后能被正确地回收。例子 例子2
shared_ptr
shared_ptr

数据结构

快排算法、快排的时间复杂度（平均、最坏）

数据库

MySQL 数据库引擎

  • MyISAM：读性能高，但不支持外键、行级锁和事务，MySQL 5.5 默认
  • InnoDB：读性能稍弱，支持外键、行级锁和事务，MySQL 5.5.5 及以后默认

二者都使用 B+ 树作为存储的数据结构。

B 树和 B+ 树

B 树

B 树 | 维基百科
面试官问你B树和B+树，就把这篇文章丢给他- SegmentFault 思否

先要纠正两个常见误区：

  • B 树 (B-Tree) 不是二叉树 (Binary Tree)。B 的全称，可能起源于其发明者，不过理解成平衡 (balanced) 或宽的(broad) 或 茂密(bushy) 也不错。
  • 没有 B 减树！B 减树的出现可能是翻译人员错误地将 B 树 (B-Tree) 翻译成了 B 减树。
B 树
B 树

概述：B 树是是一种自平衡的树，能够保持数据有序（听起来就是在说平衡二叉树）。其与平衡二叉树的不同在于，B 树的一个节点可以拥有 2 个以上的子节点，且节点数在某范围内可变。这样的好处有：

  1. 子结点的增多能够降低深度，减少定位记录时所经历的中间过程，运用在磁盘、数据库中可以加快存取速度；
  2. 由于节点数在范围内可变，因此 B 树不需要像其他平衡二叉查找树那样经常进行平衡

定义：一棵 m 阶 B 树的定义：

  1. 每个节点最多有 m-1 个 key；
  2. 根节点最少可以只有 1 个 key，非根节点至少有 m/2 个 key（根节点的 key 数量范围：[1, m-1]，非根节点的 key 数量范围：[m/2, m-1]。）；
  3. 每个节点中的 key 都按照从小到大的顺序排列，每个 key 的左子树中的所有 key 都小于它，而右子树中的所有 key 都大于它；
  4. 所有叶子节点都位于同一层（即根节点到每个叶子节点的长度都相同）；
  5. 每个节点都存有索引和数据，也就是对应的 key 和 value。

B 树插入的规则：插入的时候，判断当前结点key的个数是否小于等于 m-1，如果满足，直接插入即可，如果不满足，将节点的中间的 key 将这个节点分为左右两部分，中间的节点放到父节点中即可。

B+ 树

B+ 树具有上述 B 树的前四个特点。除此之外，B+ 树还有以下特点：

  1. B 树的所有结点都存储数据，而 B+ 树只有叶子结点存储数据，内部节点（或非叶子结点、索引节点）只存放索引；
  2. B+ 树每个叶子结点存有下一个叶子结点的指针，而 B 树无，所以所有叶子结点形成了一条有序链表，遍历整棵树只需要遍历链表，而不需要从树根往下遍历。

B+ 树较 B 树的优点就是遍历快吧。

慢查询

MySQL索引原理及慢查询优化- 美团技术团队

慢查询：超过指定时间的 SQL 语句查询。

优化方法：

  1. 查看日志查看慢查询
  2. 添加索引、修改索引（如先查区分度大的）
  3. 分库、分表

聚簇索引 & 非聚簇索引

聚簇索引 & 非聚簇索引
聚簇索引 & 非聚簇索引
  • 非聚簇索引（二级索引、辅助索引）：表数据和索引分成两部分存储，叶子结点存主键和索引键
  • 聚簇索引：表数据和主键一起存储，主键索引的叶子结点存行数据 (包含主键值)

InnoDB 为什么推荐使用 auto_increment 作为主键

  1. auto_increment 保证能新加入的数据的主键永远是最大的，加入的数据会被放在最后。在写入量大的时候，插入数据时是连续写入，而不是随机 I/O
  2. auto_increment 使得主键和业务分离，这样即便业务上出现调整，也不需要重构数据库

事务的 ACID

ACID，是指数据库管理系统 (DBMS) 在写入或更新资料的过程中，为保证事务 (transaction) 是正确可靠的，所必须具备的四个特性：

  • 原子性 (atomicity)：一个事务要么全做要么全不做；
  • 一致性 (consistency)：数据处于一种有意义的状态，这种状态是语义上的而不是语法上的。最常见的例子是转帐：从帐户 A 转一笔钱到帐户 B 上，如果帐户 A 上的钱减少了，而帐户 B 上的钱却没有增加，那么我们认为此时数据处于不一致的状态；
  • 隔离性 (isolation)：一个事务不影响其他事务的运行效果；
  • 持久性 (durability)：事务一旦提交，则其结果就是永久性的，即使故障也能恢复。

从数据库层面，数据库通过原子性、隔离性、持久性来保证一致性。也就是说 ACID 四大特性之中，C 是目的，AID 是手段，是为了保证一致性，数据库提供的手段。

事务的原子性和持久性的保证

  1. 将所有事务开始、提交、终止，以及数据的更新操作（记录数据更新前的值即前像，或更新后的值即后像）计入 log
  2. 系统崩溃后重启，先读取日志对已提交的事务进行 REDO（保证持久性）
  3. 然后对尚未提交的的事务进行 UNDO（保证原子性）

InnoDB 事务隔离级别

MySQL 事务隔离级别和锁– IBM Developer

SQL 标准定义了四种隔离，隔离程度由高到低依次为：

  • 读未提交/脏读：未提交事务的数据也可以被读，这也被称为脏读；
  • 读提交/不可重复读：提交了的东西就可以被读，但若一个事务两次读取过程中，有事务更新了数据，会导致不可重复读；
  • 可重复读/幻读（默认）：同一个事务中，select 的结果是事务开始时的状态，因此可重复读。但由于 insert 语句等不受影响，所以可能出现幻读（本事务开始后，别的事务提交了数据 pk=1，本事务 select 不到 pk=1，但 insert pk=1 会报错主键冲突，像是读到了幽灵）
  • 序列化：如果要完全解决上面的三种问题，就只能让事务串行化了，也就是把多个事务变成一个序列。
有/无问题 脏读 不可重复读 幻读
读未提交 有 有 有
读提交 无 有 有
可重复读 无 无 有
序列化 无 无 无

InnoDB 锁

MySQL 事务隔离级别和锁 - IBM Developer

Innodb中的事务隔离级别和锁的关系 - 美团技术团队（很有意思，推荐认真阅读）

数据库遵循的是两段锁协议，将事务分成两个阶段，加锁阶段和解锁阶段（所以叫两段锁）

  • 加锁阶段：在该阶段可以进行加锁操作。加锁不成功，则事务进入等待状态，直到加锁成功才继续执行。
  • 解锁阶段：当事务释放了一个封锁以后，事务进入解锁阶段，在该阶段只能进行解锁操作不能再进行加锁操作。

这种方式虽然无法避免死锁，但是两段锁协议可以保证事务的并发调度是串行化（串行化很重要，尤其是在数据恢复和备份的时候）的。

行锁

InnoDB 实现了两种类型的行级锁：

  • 共享锁 (S)：在对任何数据进行读操作之前要申请并获得 S 锁。其它事务可以继续加共享锁，但不能加排它锁；
  • 独占锁 (X)：在进行写操作之前要申请并获得 X 锁。其它事务不能再获得任何锁；

表锁

InnoDB 支持多粒度锁，因此 S 和 X 锁还可以锁表（如使用 ALTER TABLE 等语句会给表上 X 锁）。

另外还设计了两个意向锁，注意意向锁都是表级的：

  • 意向共享锁 (IS)：表明事务即将给表中的行设置 S 锁。事务给行加 S 锁前必须获得该表的 IS 锁。
  • 意向排它锁 (IX)：表明事务即将给表中的行设置 X 锁。事务给行加 X 锁前必须获得该表的 IX 锁。

综上，MySQL 支持两种行锁和四种表锁。

四种表锁的兼容表如下：

锁类型 X IX S IS
X 冲突 冲突 冲突 冲突
IX 冲突 兼容 冲突 兼容
S 冲突 冲突 兼容 兼容
IS 冲突 兼容 兼容 兼容

总结一下就是：

  • 意向锁之间相互不冲突
  • 互斥锁和所有锁都冲突
  • 共享锁和互斥意向锁冲突

行锁的算法

  • Record Locks：锁（单条）记录
  • Rocord Gaps：锁范围
  • Next-Key Locks：锁范围+锁记录

乐观锁和悲观锁，以及多版本并发控制

一文读懂数据库中的乐观锁和悲观锁和MVCC | MySQL 技术论坛
乐观锁和 MVCC 的区别？ - 用心阁的回答 - 知乎

乐观锁和悲观锁都不是数据库锁，而是两种用于解决写-写冲突的思想。

乐观锁（又称乐观并发控制）是乐观地假设，事务间的竞争没有那么多。

乐观并发控制的一种实现是基于版本号。首先进行修改，在提交事务前，检查一下事务开始后是否有别的提交，如果没有就提交，如果有就放弃并回滚重做。

乐观并发控制多用于读多写少的场景，由于没有上锁解锁（此处指数据库锁）的过程，读的性能会很高；但在读少写多的场景，需要反复回滚重做，所以效率会变低。

悲观锁（又称悲观并发控制）是悲观地假设，事务间的竞争很多。

悲观并发控制的一种实现就是利用数据库锁，在数据库层对数据进行上锁。

悲观并发控制多用于读少写多的场景，这种场景下，不需要回滚重做而是等待，会比乐观锁好；但是上锁解锁需要消耗一定性能。

多版本并发控制（MVCC）和上面的区别是，MVCC 解决的是读-写冲突。

MVCC 在各数据库中有不同的实现，在 InnoDB 中是一种无锁并发控制。InnoDB MVCC 为事务分配递增的时间戳（或者 version），更新时 version++，读操作只读该事务开始前的数据库的快照。

这样在读操作不用阻塞写操作，写操作不用阻塞读操作的同时，避免了脏读和不可重复读。

计算机网络

OSI 七层

就是把应用层拓展为（自底向上）会话层、表示层（加密相关）、应用层。

TCP 三次握手与四次挥手

TCP 三次握手与四次挥手

三次握手：

  1. 客户端：发送 SYN，进入 SYN_SENT 状态
  2. 服务器：收到包后发送 SYN ACK，进入 SYN_RCVD 状态
  3. 客户端：收到包后发送 ACK，进入 ESTABLISHED 状态（服务器接收后也进入 ESTABLISHED 状态）

三个包的 seq 和 ACKnum 数值有如下关系：

  • SYN ACK 的 ACKnum = SYN 的 seq+1
  • ACK 的 ACKnum = SYN ACK 的 seq+1
TCP 三次握手
TCP 三次握手

四次挥手并不一定是客户端发起，也可以由服务端发起。故下面用 主动关闭 和 被动关闭 称呼：

  1. 主动关闭方：发送最后一个数据包后，发送 FIN，进入 FIN_WAIT_1；
  2. 被动关闭方：收到包后发送 ACK，进入 CLOSE_WAIT；客户端收到后进入 FIN_WAIT_2，此时客户端到服务端的单方连接被关闭；
  3. 被动关闭方：发送最后一个数据包后，发送 FIN，进入 LAST_ACK；
  4. 主动关闭方：收到包后发送 ACK，进入 TIME_WAIT，一段时间后关闭通信；服务端收到后立即关闭通信。

可以理解为两对 FIN - ACK，且每个 ACK 的 ACKnum = 对方的 FIN 的 seq+1。

  • CLOSE_WAIT 可以理解成对方主动关闭了连接，但本方还没有关闭，在等待关闭连接 (wait close)；
  • TIME_WAIT 首先发出 FIN 的一侧，如果给对侧的 FIN 响应了 ACK，那么就会超时等待 2*MSL 时间，然后关闭连接(time wait)。在这段超时等待时间内，本地的端口不能被新连接使用；避免延时的包的到达与随后的新连接相混淆。RFC793 定义了 MSL 为2分钟（即 TIME_WAIT 等待 4 分钟）。
TCP 四次挥手
TCP 四次挥手

被动关闭的一方也可以把 ACK 和 FIN 合并为 FIN ACK，实现三次挥手。

TCP 流量控制

TCP流量控制、拥塞控制

  • 流量控制：考虑到可能接收方处理的比较慢，需要限制发送方的发送速度。方法是，接收方发回的 ACK 中会包含自己接收窗口的大小。
  • 流量控制死锁：当发送者收到了一个窗口为 0 的应答，便停止发送，等待接收者的下一个应答。但如果之后接受者发送的窗口不为 0 的应答在传输过程丢失，发送者一直等待下去，而接收者以为发送者已经收到该应答，等待接收新数据，这样双方就相互等待，从而产生死锁。
  • 流量控制死锁避免：TCP 使用持续计时器。每当发送者收到一个零窗口的应答后就启动该计时器，时间一到便主动发送报文询问接收者的窗口大小。若接收者仍然返回零窗口，则重置该计时器继续等待；若窗口不为0，则表示应答报文丢失了，此时重置发送窗口后开始发送。

TCP 快速重传

  • 在没有快速重传机制下，如果发送方的某报文丢失，即使接受方发送了多个重复确认，发送方仍需等待重传计时器到期才会重传；
  • 快速重传机制下，发送方一旦收到三个重复确认，就重传报文，无需等待计时器到期。

TCP 拥塞控制

TCP流量控制、拥塞控制

发送方维持一个变量：拥塞窗口 (congestion window, cwnd)，取决于网络拥塞情况，且动态变化。

发送方使自己的发送窗口为 $\min(cwnd, wnd_{接收方})$。

  • 慢启动阶段，cwnd=1，每成功传输一次则 cwnd*=2，直至 cwnd 到达慢启动阈值 (slow-start threshold, ssthresh)，进入拥塞避免状态。
  • 拥塞避免状态，每成功传输一次则 cwnd++
  • 任何时刻，出现发送方对某报文的计时器超时，令 ssthresh=cwnd/2，cwnd=1，重新进入慢启动
  • 快速恢复：任何时刻，出现发送方接收到三个重复确认，并不按照上一条执行，而是令 ssthresh=cwnd/2, cwnd=cwnd/2+3，进入拥塞避免状态（能收到重复报文，说明网络没那么拥堵，超时才是真的拥堵）

用户从输入域名到获取到信息过程中发生了什么

a. DNS 解析的过程：计算机先检查 DNS 缓存，如果没有缓存则向 DNS 服务器查询域名对应的 IP，查询的过程分为迭代和递归两种方式；面试官接着问了 DNS 基于什么协议，答案是 UDP，服务器一般使用 53 端口；
b. 获取到 IP 以后就可以发包了，需要对包进行一层层的封装，自顶向下的封装顺序为：HTTP、TLS、TCP、IP。
c. HTTP 协议的内容大致为 HTTP/1.1 GET /；
d. TLS 协议会进行 TLS 握手，主要是客户端、服务端交换密钥；
e. 再往下是 TCP 和 UDP 协议。经典一问：TCP 和 UDP 的区别（TCP 面向连接、拥塞控制、流量控制），顺便还简单问了一下拥塞控制；
f. 再往下就是 IP 层，主机会向向路由器发 IP 包、路由器根据路由表和选路算法进行转发的过程；面试官又问了有那些选路算法（分为域内和域间协议，域内有 OSPF 和 RIP，域间使用 BGP）；以及路由表的最长前缀匹配原则；
e. 再往下就是物理层了。

操作系统

进程和线程的区别

  • 调度并分派的单位称为线程（或轻量级进程 LWP）
  • 资源所有权的单位称为进程

进程会创建进程控制块 (PCB)，而线程是线程控制块 (TCB)。由于线程没有父子进程、资源控制等结构，所以 TCB 比 PCB 简单得多，这也导致线程的创建比进程的创建快得多，大概有一个数量级的区别。

这也是平时开发中，为了利用 CPU 多线程，我们常使用多线程开发，而不是多进程开发的原因。

用户态和内核态的区别，这样有什么好处

  • 用户模式：优先权较少，用于运行用户程序
  • 内核模式：优先权更高，用于运行内核，且某些指令、内存只能在特权模式下运行/访问，如：
    • 读取/修改 PSW 等控制寄存器
    • 原始 I/O 指令
    • 内存管理相关

区分用户模式和内核模式的原因：保护 OS 和重要操作系统表不受程序干扰

用户级线程和内核级线程

用户级线程和内核级线程
用户级线程和内核级线程
  • 用户级线程：线程、线程的创建、销毁全部由库函数实现。内核不知道用户级线程的存在，依旧按照进程为单位进行调度。
    • 优点：线程切换不需要内核模式，快；调度策略因应用程序不同而不同；可以运行在任何操作系统上
    • 缺点：系统调用将阻塞同一进程中的其他线程；不能利用多处理器技术
  • 内核级线程：管理线程的所有工作均由内核完成。 Windows是这种方法的一个例子。
    • 优点：ULT 两个缺点反过来说；内核本身也可以是多线程的
    • 缺点：ULT 三个优点反过来说；

进程七状态

  • 运行
  • 就绪
  • 阻塞
  • 就绪/挂起
  • 阻塞/挂起
  • New
  • Exit

僵尸进程和孤儿进程

二者都是进程派生后，父子进程其中一个退出的情况。僵尸进程是子进程退出，孤儿进程是父进程退出。

孤儿进程：父进程派生出子进程。父进程退出，但子进程还在运行，子进程就被称为孤儿进程。Unix 系统下，孤儿进程会被 init 进程收养，并在孤儿进程退出后由 init 进程对它们完成状态收集工作。孤儿进程没有什么危害。

僵尸进程：父进程 fork 出子进程。子进程退出，父进程并没有获取子进程的状态信息，子进程的进程描述符仍然留在系统中，子进程被称为僵尸进程，在 htop 的状态一栏会被标记为 Z。大量僵尸进程会占用内存空间，需要把父进程 kill 掉，僵尸进程转为孤儿进程，进而被 init 回收。

进程调度算法

  • 先来先服务 First Come First Served, FCFS
  • 时间片轮转 Round Robin, RR
  • 短进程优先 Shortest Process Next, SPN
  • 剩余时间最短优先 Shortest Remaining Time, SRT
  • 响应比高者优先 Highest Response Ratio Next, HRRN
  • 反馈 Feedback

进程切换算法

  • 保存处理器上下文（寄存器）
  • 更新当前进程的 PCB（状态、数据结构等变化）
  • 将 PCB 的指针移至相应队列（就绪、阻塞、挂起等）
  • 选择另一进程执行

线程间通信方式

同一进程的线程共享内存地址空间，没有必要依赖 OS 进行通信，但要做好同步/互斥，保护共享的全局变量。

  1. 锁机制：三种常见的锁的实现包括互斥锁、读写锁、条件变量
  • 互斥锁：提供了以排他方式防止数据结构被并发修改的方法
  • 读写锁：允许多个线程同时读共享数据，而对写操作是互斥的
  • 条件变量：可以以原子的方式阻塞进程，直到某个特定条件为真为止（对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用）
  1. 信号量 (Semaphore)
  2. 信号机制 (Signal)：类似进程间的信号处理

进程间通信方式

  1. 管道(pipe)，分为无名管道和有名管道
  2. 信号(signal)
  3. 消息队列
  4. 共享内存
  5. 信号量
  6. 套接字(socket)

记住上面的六个词就可以对付 60% 的面试了，30% 的可能会问一下有名管道和无名管道的区别，剩下 10% 的面试可能每个都会问一下。

如何保证缓存一致性

缓存一致性就是保证内存和缓存中的内容相同。

实现上，每一行的缓存用一个 modified 标记了是否被修改。当这行缓存将被替换时，就会将这行内容写回内存。

开发

深拷贝和浅拷贝

  • 浅拷贝是创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值，如果属性是引用类型，拷贝的就是内存地址 ，所以如果其中一个对象改变了这个地址，就会影响到另一个对象。
  • 深拷贝是将一个对象从内存中完整的拷贝一份出来,从堆内存中开辟一个新的区域存放新对象,且修改新对象不会影响原对象。
浅拷贝
浅拷贝
深拷贝
深拷贝

如何进行调试

  • 利用标准输出 / log 调试；
  • 利用 IDE 单步调试；
  • 利用 assert 语句调试。

设计模式

设计模式- 廖雪峰的官方网站

范围/目的 创建型模式 结构型模式 行为型模式
类模式 工厂方法 (类）适配器 模板方法、解释器
对象模式 单例
原型
抽象工厂
建造者		 代理
(对象）适配器
桥接
装饰
外观
享元
组合		 策略
命令
职责链
状态
观察者
中介者
迭代器
访问者
备忘录

设计模式的原则

  • 开闭原则：对扩展开放、对修改关闭
  • 里氏替换原则：如果对父类的调用可以成功，对子类的调用也应该成功，这也是面向对象编程的基础

创建型模式

工厂方法：工厂方法的目的是使得创建对象和使用对象是分离的，并且客户端总是引用抽象工厂和抽象产品

1
2
3
4
5
6
7
8
┌─────────────┐      ┌─────────────┐
│   Product   │      │   Factory   │
└─────────────┘      └─────────────┘
       ▲                    ▲
       │                    │
┌─────────────┐      ┌─────────────┐
│ ProductImpl │<─ ─ ─│ FactoryImpl │
└─────────────┘      └─────────────┘

抽象工厂：抽象工厂模式和工厂方法不太一样，它要解决的问题比较复杂，不但工厂是抽象的，产品是抽象的，而且有多个产品需要创建，因此，这个抽象工厂会对应到多个实际工厂，每个实际工厂负责创建多个实际产品：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
                                ┌────────┐
                             ─ >│ProductA│
┌────────┐    ┌─────────┐   │   └────────┘
│ Client │─ ─>│ Factory │─ ─
└────────┘    └─────────┘   │   ┌────────┐
                   ▲         ─ >│ProductB│
           ┌───────┴───────┐    └────────┘
           │               │
      ┌─────────┐     ┌─────────┐
      │Factory1 │     │Factory2 │
      └─────────┘     └─────────┘
           │   ┌─────────┐ │   ┌─────────┐
            ─ >│ProductA1│  ─ >│ProductA2│
           │   └─────────┘ │   └─────────┘
               ┌─────────┐     ┌─────────┐
           └ ─>│ProductB1│ └ ─>│ProductB2│
               └─────────┘     └─────────┘

生成器模式（Builder）：使用多个“小型”工厂来最终创建出一个完整对象。

原型模式（Prototype）：创建新对象的时候，根据现有的一个原型来创建。

单例模式（Singleton）：保证在一个进程中，某个类有且仅有一个实例。

结构型模式

适配器（Adapter）：转换器，即负责将 A 类转换为 B 类的类

InputStreamReader 就是 Java 标准库提供的 Adapter，它负责把一个 InputStream 适配为 Reader。类似的还有 OutputStreamWriter。

桥接模式（Bridge）：不要过度使用继承，而是优先拆分某些部件，使用组合的方式来扩展功能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
桥接前：

                   ┌───────┐
                   │  Car  │
                   └───────┘
                       ▲
    ┌──────────────────┼───────────────────┐
    │                  │                   │
┌───────┐          ┌───────┐          ┌───────┐
│BigCar │          │TinyCar│          │BossCar│
└───────┘          └───────┘          └───────┘
    ▲                  ▲                  ▲
    │                  │                  │
    │ ┌───────────────┐│ ┌───────────────┐│ ┌───────────────┐
    ├─│  BigFuelCar   │├─│  TinyFuelCar  │├─│  BossFuelCar  │
    │ └───────────────┘│ └───────────────┘│ └───────────────┘
    │ ┌───────────────┐│ ┌───────────────┐│ ┌───────────────┐
    ├─│BigElectricCar │├─│TinyElectricCar│├─│BossElectricCar│
    │ └───────────────┘│ └───────────────┘│ └───────────────┘
    │ ┌───────────────┐│ ┌───────────────┐│ ┌───────────────┐
    └─│ BigHybridCar  │└─│ TinyHybridCar │└─│ BossHybridCar │
      └───────────────┘  └───────────────┘  └───────────────┘

桥接后：

       ┌───────────┐
       │    Car    │
       └───────────┘
             ▲
             │
       ┌───────────┐       ┌─────────┐
       │RefinedCar │ ─ ─ ─>│ Engine  │
       └───────────┘       └─────────┘
             ▲                  ▲
    ┌────────┼────────┐         │ ┌──────────────┐
    │        │        │         ├─│  FuelEngine  │
┌───────┐┌───────┐┌───────┐     │ └──────────────┘
│BigCar ││TinyCar││BossCar│     │ ┌──────────────┐
└───────┘└───────┘└───────┘     ├─│ElectricEngine│
                                │ └──────────────┘
                                │ ┌──────────────┐
                                └─│ HybridEngine │
                                  └──────────────┘

组合（Composite）：将对象组合成树形结构以表示“部分-整体”的层次结构，使得用户对单个对象和组合对象的使用具有一致性。

1
2
3
4
5
6
7
8
public interface Node {
    // 添加一个节点为子节点:
    Node add(Node node);
    // 获取子节点:
    List<Node> children();
    // 输出为XML:
    String toXml();
}

装饰器（Decorator）模式，是一种在运行期动态给某个对象的实例增加功能的方法。类似于这样的方法 A decorator(A a);。
顺带一提，Python 的装饰器就玩得很好。

1
2
3
4
5
6
7
8
9
10
11
12
// 创建原始的数据源:
InputStream fis = new FileInputStream("test.gz");
// 增加缓冲功能:
InputStream bis = new BufferedInputStream(fis);
// 增加解压缩功能:
InputStream gis = new GZIPInputStream(bis);

// 或者一次性写成这样：
InputStream input = new GZIPInputStream( // 第二层装饰
                        new BufferedInputStream( // 第一层装饰
                            new FileInputStream("test.gz") // 核心功能
                        ));

外观模式（Facade）：将复杂的流程包装成一个函数并暴露给调用方。

1
2
3
4
5
6
7
8
9
10
11
// 将 register, openAccount, applyTaxCode 三个步骤包装成一个函数
public class Facade {
    public Company openCompany(String name) {
        Company c = this.admin.register(name);
        String bankAccount = this.bank.openAccount(c.getId());
        c.setBankAccount(bankAccount);
        String taxCode = this.taxation.applyTaxCode(c.getId());
        c.setTaxCode(taxCode);
        return c;
    }
}

享元模式（Flyweight）：通过工厂方法创建对象，在工厂方法内部，很可能返回缓存的实例，而不是新创建实例，从而实现不可变实例的复用。如 Integer.valueOf()。

代理模式（Proxy）：将 A 接口转换成 A 接口，可在调用 A 的方法前后加一些额外的代码，实现对 A 的控制。

装饰器和代理的区别

代理模式和装饰器模式的区别 - 知乎

装饰器和代理很相似，都是接收 A 接口，返回 A 接口。其区别主要是思想上的区别：

装饰模式是为装饰的对象增强功能；

而代理模式对代理的对象施加控制，但不对对象本身的功能进行增强；

行为型模式

责任链模式（Chain of Responsibility）是一种处理请求的模式，它让多个处理器都有机会处理该请求，直到其中某个处理成功为止。责任链模式把多个处理器串成链，然后让请求在链上传递：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
     ┌─────────┐
     │ Request │
     └─────────┘
          │
┌ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ┐
          ▼
│  ┌─────────────┐  │
   │ ProcessorA  │
│  └─────────────┘  │
          │
│         ▼         │
   ┌─────────────┐
│  │ ProcessorB  │  │
   └─────────────┘
│         │         │
          ▼
│  ┌─────────────┐  │
   │ ProcessorC  │
│  └─────────────┘  │
          │
└ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ┘
          │
          ▼

命令模式（Command）是指，把请求封装成一个命令，然后执行该命令。好处是可以对请求排队、记录请求日志，以及支持可撤销的操作。

解释器模式（Interpreter）：如 Python 解释器、正则表达式匹配等。

迭代器模式（Iterator）

中介模式（Mediator）：在多个组件的相互交互中，添加一个中介，所有组件和中介交互，实现组件间的松耦合。

备忘录模式（Memento），主要用于捕获一个对象的内部状态，以便在将来的某个时候恢复此状态。简单的实现是，编写这个类的 getState() 和 setState() 方法，负责导出、导入信息即可。

观察者模式（Observer）又称发布-订阅模式（Publish-Subscribe, Pub/Sub）：发布方搞一个 Observer 数组；订阅操作就是将订阅者加入数组中；当发布方需要告知订阅者时，对数组中每个对象调用通知方法 void onEvent(Event event); 即可。

状态（State）

策略（Stategy）：即排序算法时使用的 Comparator

模板方法（Template Method）：使用抽象类定义流程，流程中的部分细节让子类实现

访问者（Visitor）：

Linux 命令

命令 用途
top 任务管理器
free 查看剩余内存等（不过为什么不用 top 呢）
ps 查看进程，可使用 `ps aux
kill -9 <pid> 杀进程
lsof -i:8000 查看 8000 端口的占用进程
nload 查看流量大小
wc (word count) 统计文件的字数、行数、字符数
tail --follow 实时输出（日志）文件内容
journalctl -f -u <unit.service> 实时输出日志内容
grep word file.txt 在 find.txt 查找 word 字符串，-i 大小写不敏感
find <directory> -name 'file.txt' 在目录下查找 file.txt
df -h 查看文件剩余空间

低频考点

以下是低频考点，但是在真实面试中问过一次，读者可以按需掌握。

C++

C 语言获取当前文件夹、函数名、行数

中望龙腾 C++ 岗笔试考过。

1
2
3
4
5
6
7
8
9
10
11
12
#include<iostream>
#include<direct.h>

using namespace std;

int main()
{
    cout << _getcwd(0, 0) << endl                   // 获取当前文件夹
        << "__FUNCSIG__:" << __FUNCSIG__ << endl    // 获取函数完整签名
        << "__FUNCTION__:" << __FUNCTION__ << endl  // 获取函数名
        << "__LINE__:" << __LINE__;                 // 获取行数
}

输出：

1
2
3
4
C:\Users\liu\Desktop\test\cpp
__FUNCSIG__:int __cdecl main(void)
__FUNCTION__:main
__LINE__:11

C 语言字节对齐

cv 限定符

cv（const 与 volatile）类型限定符 | cppreference.com

cv 限定符是 const 和 volatile 的合称。

当对象最初被创建时，所用的 cv 限定符决定对象的常量性或易变性。

const 大家都懂，就是不能修改的常量 (constant)，直接修改会编译报错，间接修改（如利用 const_cast<int&> 等手段）为未定义行为。还有一点，就是写为 const 之后，编译器会进行优化。

而 volatile 翻译过来是“易变”的，表明该变量可能通过软件甚至硬件方式变化。这会阻止编译器对这个变量进行任何优化，包括但不限于：不会将变量放到寄存器中；不会对 const volatile 变量当做 const 进行优化。（不过，CPU 仍可以将变量放入缓存中，因为缓存对程序员是透明的）

代码例子见 const_cast 部分。

static 用处

C 语言的 static 有三个用处：

  1. 对函数内变量使用，扩展其生存期；
  2. 对函数外变量和函数使用，使其他文件不能通过 extern 访问到该变量/函数（默认是可以的）；
  3. 对类的成员/方法使用，使得该变量/函数属于类（其他的都是属于每个对象），可以直接由类名 Classname:: 调用；

禁止继承

C++ 11 引入了 final 关键字。

1
2
3
4
5
6
7
class A final {

};

class B : public A {

}; // error: 不能选择 final 类作为基类

禁止拷贝构造函数和赋值构造函数

C++11 加入了 = delete 控制类默认函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Thing
{
public:
    Thing(const Thing&) = delete;
    Thing& operator = (const Thing&) = delete;
};

int main(int)
{
    Thing t1;       // 错误 E0291：类 "Thing" 不存在默认构造函数
    Thing t2(t1);   // 错误 E1776：无法引用 函数 "Thing::Thing(const Thing &)" (已声明 所在行数:4) -- 它是已删除的函数
    Thing t2 = t1;  // 错误 E1776：无法引用 函数 "Thing::Thing(const Thing &)" (已声明 所在行数:4) -- 它是已删除的函数
    return 0;
}

C++98 前可以定义为 private。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Thing 
{
public:
private:
    Thing (const Thing &);
    Thing & operator = (const Thing &);
};

int main(int)
{
    Thing t1;
    Thing t2(t1);  //error C2248: “Thing::Thing”: 无法访问 private 成员
    Thing t2 = t1; //error C2248: “Thing::Thing”: 无法访问 private 成员
    return 0;
}

std::vector 和 std::array

  • vector 和 array 都是可以通过 [] 访问下标对应元素的数组；
  • vector 是变长数组，可以通过 push_back insert 和 erase 修数组大小。（注意 insert 和 erase 都是 $O(n)$ 的）；
  • C++ vector 内存分配与回收机制；
  • array 则是 C++11 引入的、对标准数组的封装，是定长数组。

Lambda 捕获值列表

Modern C++ zh-cn

分为三种：

  1. 值捕获 [value] 或 [=value]：与参数传值类似，值捕获的前提是变量可以拷贝。不同之处则在于，被捕获的变量在 Lambda 表达式被创建时拷贝， 而非调用时才拷贝。
  2. 引用捕获 [&value]：与引用传参类似，引用捕获保存的是引用，值会发生变化。
  3. 隐式捕获 [=] 或 [&]：手动书写捕获列表有时候是非常复杂的，这种机械性的工作可以交给编译器来处理，这时候可以在捕获列表中写一个 & 或 = 向编译器声明采用引用捕获或者值捕获。（很多地方说的是捕获 this，我觉得还是这个好理解一些，毕竟如果在 main 函数中，也没有 this 一说）

总结一下，捕获提供了 Lambda 表达式对外部值进行使用的功能，捕获列表的最常用的四种形式可以是：

  1. [] 空捕获列表
  2. [name1, name2, ...] 捕获一系列变量
  3. [&] 引用捕获, 让编译器自行推导引用列表
  4. [=] 值捕获, 让编译器自行推导值捕获列表

数据结构

堆的复杂度

面腾讯的时候被问到，建堆的复杂度是多少，还好之前写过博客，还有一点点印象不是 $O(n\log n)$，而是 $O(n)$。回顾了一下博客，果然是，顺便重温了一下证明。

计算机网络

TIME_WAIT 快速回收与复用

time-wait快速回收与复用 - rosewind的博客 | BY Blog
time_wait的快速回收和重用
NAT环境下tcp_timestamps问题_〓☆〓 清风徐来918 （QQ:89617663）-CSDN博客_tcp_timestamps

这是腾讯主管问的问题，一般第二次考到的概率很小，但作为一个知识了解也不错。

TIME_WAIT 状态产生的原因在上面部分提到了，这里不再赘述。如果 TIME_WAIT 太多，导致无法对外建立新 TCP 连接。

在 Linux 下，可以从系统层面，或从应用程序层面解决这个问题。

系统层面上，也有三种方法。

一是提高 tcp_max_tw_buckets，就能接受更多的 TIME_WAIT，但是治标不治本。

二是开启 TIME_WAIT 快速回收 tcp_tw_recycle（需同时开启 tcp_timestamps，系统默认开启）。原理是在 TCP 报文中加入时间戳（时间戳在 TCP 报文中的可选字段），然后系统缓存每个连接最新的时间戳。如果收到的 TCP 报文的时间戳早于缓存值，就丢弃数据包 (RFC1323)。

快速回收的问题在于，搭配 NAT 可能会出现问题。现在很多公司都用 LVS 做负载均衡，通常是前面一台 LVS，后面多台后端服务器，这其实就是 NAT，当请求到达 LVS 后，它修改地址数据后便转发给后端服务器，但不会修改时间戳数据，对于后端服务器来说，请求的源地址就是 LVS 的地址，加上端口会复用，所以从后端服务器的角度看，原本不同客户端的请求经过 LVS 的转发，就可能会被认为是同一个连接，加之不同客户端的时间可能不一致，所以就会出现时间戳错乱的现象，于是后面的数据包就被丢弃了，具体的表现通常是是客户端明明发送的 SYN，但服务端就是不响应 ACK。如果服务器身处 NAT 环境，安全起见，通常要禁止 tcp_tw_recycle，至于TIME_WAIT连接过多的问题，可以通过 TIME_WAIT 复用解决。

三是开启 TIME_WAIT 复用 tcp_tw_reuse（也需要同时开启 tcp_timestamps）另外复用也是也是有条件的：协议认为复用是安全的。与 tcp_tw_recycle 选项相比，本选项一般不会带来副作用。

应用层面上，有两种解决办法：一是将 TCP 短连接改造为长连接，二是快速关闭 socket。

HTTP 状态码

HTTP 状态码

  • 1xx：
    • 102 Processing (WebDAV) 用于表明 WebDAV 服务器收到了请求，但请求的操作比较费时，服务器正在处理（如遍历当前文件夹）。为了防止客户端 TCP 超时、假设请求丢失，于是服务器可以发送一个没有信息的 102 应答。
  • 2xx：
    • 200 OK
    • 201 Created
    • 202 Accepted 表示正在进行一个异步操作。用于 1. 重置密码时，服务器返回 202，然后将重置邮件发送给邮箱；2. Onedrive 分段上传时，如果完成了一部分的上传，会返回 202。
    • 204 No Content
    • 206 Partial Content
  • 3xx：
    • 301 302 307 308 见后
    • 304 Not Modified
  • 4xx：
    • 400 Bad Request
    • 401 Unauthorized
    • 403 Forbidden
    • 404 Not Found
    • 405 Method Not Allowed
    • 409 Conflict
    • 415 Unsupported Media Type
  • 5xx：
    • 500 Internal Server Error
    • 502 Bad Gateway 常见于 Nginx 反代的服务出锅了
    • 504 Gateway Timeout
永久重定向 Permanently 暂时重定向 Temporarily
允许将 POST 方法改为 GET 301 Moved Permanently 302 Moved Temporarily
不允许将 POST 方法改为 GET 308 Permanent Redirect 307 Temporary Redirect

HTTPS 原理及握手过程

SSL/TLS协议运行机制的概述 - 阮一峰的网络日志

  1. 客户端发送：ClientHello + 随机数 client random
  2. 服务端发送：ServerHello + 随机数 server random + 证书
  3. （客户端验证证书有效性）
  4. 客户端发送：随机数 premaster secret (经公钥加密)
  5. （服务器和客户端使用三个随机数生成一个会话密钥）
  6. 客户端发送：finished (经会话密钥加密)
  7. 服务端发送：finished (经会话密钥加密)

Nginx

Nginx为什么快到根本停不下来？ - 知乎

Nginx 的进程模型
Nginx 的进程模型

Nginx 多进程

一个 Master 进程配合多个 Worker 进程

  1. Master 进程：管理 Worker 进程
  • 对外接口：接收外部的操作（信号）
  • 对内转发：根据外部的操作的不同，通过信号管理 Worker
  • 监控：监控 worker 进程的运行状态，worker 进程异常终止后，自动重启 worker 进程
  1. Worker 进程：所有 Worker 进程都是平等的
  • 实际处理：网络请求，由 Worker 进程处理；
  • Worker 进程数量：可在 nginx.conf 中配置，一般设置为核心数；

Nginx IO 多路复用

Nginx 使用epoll 多路复用

Nginx 均衡负载算法

共五种：

  1. 轮询 (Round Robin)
  2. 加权轮训，权越大表示服务器的能力越强，能承受更大负载
  3. 最小连接数 (Least Connections)
  4. IP Hash，保证同 IP 映射到同一服务器，在集群不同享 Session 时很好用
  5. URL Hash，保证同 URL 映射到同一服务器，在有 URL 缓存时效率高

Docker

Docker 底层

Docker 的底层技术

概要：Docker 使用 Linux 命名空间实现容器的隔离，使用控制组实现对容器的资源限制，使用联合文件系统提高存储效率。

和虚拟机不同，Docker 进程和宿主机进程共用一个内核和某些系统库等。而彼此各个进程的方法是 Linux 上的**命名空间 (Namespaces)**。

Docker 使用名称空间来为容器提供隔离的工作空间。当一个容器运行时，Docker 就会为该容器创建一系列的名称空间，并为名称空间提供一层隔离。

Docker 引擎也依赖另一项叫 Control groups (cgroups，控制组) 的技术。控制组可以对程序进行资源限定，并允许 Docker 引擎在容器间进行硬件资源共享以及随时进行限制和约束，如内存等。

联合文件系统 (UnionFS) 是一种分层、轻量级并且高性能的文件系统，它支持将文件系统的修改作为一次提交来一层层地叠加。不同 Docker 容器可以共享基础的文件系统层，与自己独有的改动层一起使用，可以大大提高存储效率。

I/O 多路复用

内存零拷贝