MeiK / 面经答案整理一

Created 2018-09-16 Modifyed 2018-09-16

秋招季，从牛客网上收集了一些 C++ 的面经。基本都是一线大厂的题目，应该有一定的代表性。

本篇题目转自《感谢牛客网！发一波面经！阿里、网易游戏、京东等offer。》，答案是我按我自己的理解作答的，可能有些疏漏或错误。

一些感慨

哎，大学这几年基本都去学 Python 了，等到春招找实习才发现基本没有大厂收 Python 岗的…一些要 Python 的基本也都是运维岗，需要很多的运维知识，我也不是很懂。

春招投了阿里和腾讯两家，都没有 Python 岗，所以都投的 C++，血崩。阿里从笔试开始体验就很差，C++ 岗尽是些 Java 和机器学习的题目。电面的时候听说我不会 Java，贴心的没有问 Java，但是一直在问数据库相关的，然后我就 GG 了。腾讯的体验倒是不错，笔试和面试都很贴心，面试的时候面试官还给我提了很多建议，只可惜我的 C++ 水平确实很差…

春招面试了这两家之后，明白了自己的水平离找工作还差得远，因此剩下的时间也没有继续再投。在腾讯面试的时候，腾讯的面试官给了我一些学习的建议，主要是关于 Linux 和计算机网络的，因此从春招结束后到现在我主要就是在学习 Linux 和计网。然后到了秋招，我惊讶的发现：

我忘了学 C++！！！我要投 C++ 岗但是我忘了学 C++！！！

不感慨了，不论如何我也已经努力了半年，如果水平还是不够就等明年春招。现在还是来看题目吧。

计算机网络

计算机网络分为哪几层？

OSI 分为七层，从上往下依次为：应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。

TCP/IP 协议分为四层，从上往下依次为：应用层、运输层、网际层、网络接口层。

TCP 和 UDP 有什么区别？什么场景使用 TCP，什么场景使用 UDP？哪些应用层协议使用了 TCP，哪些使用了 UDP？

TCP 是可靠的传输，而 UDP 是不可靠的传输。

TCP 的可靠并非是保证能送达，而是保证了其送达的数据的可靠性，以及递送失败时的可靠故障通知。

UDP 的不可靠体现在其不对送达与否进行验证，在传输的时候 UDP 还是尽力去送达的。也因为不做送达的保证，UDP 比 TCP 需要的数据交换更少，更加适合实时性要求较高而可以容忍部分丢包的场景（比如直播、游戏等）

HTTP、SSL、FTP、SMTP、POP3、IMAP、Telnet 等协议使用了 TCP。

TFTP、DHCP 等协议使用了 UDP。

DNS 协议同时使用了 TCP 与 UDP。

什么是窗口滑动协议，什么是快速重传，什么是拥塞避免，什么是慢启动？

关于滑动窗口，可以参照我的博客《TCP 的滑动窗口》

关于快速重传、拥塞避免、慢启动等，可以参照我的博客《TCP 的拥塞控制》

TCP 连接需要几次握手？几次分手？

建立一个 TCP 连接需要三次握手，断开一个 TCP 连接需要四次挥手。具体过程可以参考我的博客《TCP 的三次握手与四次挥手》

当你输入域名访问一个网站的时候，背后的过程是什么？

对于客户端（浏览器）

• 首先进行域名解析
  • 如果本地有 DNS 缓存，则直接使用本地的 DNS 缓存
  • 如果本地没有 DNS 缓存，则使用 DNS 协议去网络配置中指定的 DNS 服务器进行查询
  • 如果指定的 DNS 服务器依旧没有查询到结果，则 DNS 服务器会向上层服务器发起查询，当查询到结果时返回给客户端
  • 如果最终还是没能拿到解析结果，则返回解析失败，无法找到域名对应的 IP 地址
• 获得对应服务器的 IP 地址之后，开始尝试连接对应服务器
  • 首先判断 IP 与本机是否处于同一网段（使用子网掩码）
  • 如果处于同一网段，则直接访问；否则转发给网关。此过程中对应服务器或者网关的 mac 地址由 ARP 协议获得。
  • 建立 TCP 连接
• 连接成功，构建 HTTP 报文，开始正式交换数据

对于服务器

• 首先，服务进程监听某个端口，向外提供服务
• 如果有来自客户端的 TCP 连接请求，则由内核进行三次握手，完成后的连接被服务进程接管
  • 为防范 DDoS 攻击，三次握手有可能由防火墙代为完成
• 连接建立完成，客户端开始发送其 HTTP 数据，服务进程接收并解析数据
  • 如果请求的是静态文件，则寻找对应文件，进行一系列权限与安全验证，返回文件
  • 如果请求的是 CGI 等接口，则将请求转发
  • 如果服务进程为负载均衡、反向代理等，则根据此时负载或与客户端距离等信息将请求转发
• 返回响应数据，客户端接收数据并渲染页面

这个问题也可以附带着扯一些 CDN 或者其他相关知识。

什么是 https 协议？https 协议用到了哪种密钥？

可以先参考《深入理解HTTPS协议》，这篇博客，我之后将会针对这个知识点写一篇博客。

什么是 socket？

网络编程中，相互通信的两个进程（有可能在不同的电脑上，也有可能在同一个电脑上）需要知道对方的 IP 与端口号，socket 就标识了这些信息。

在 UNIX C 中，socket 创建一个全双工的管道，可以直接 read 与 write 来读取与写入数据。

什么是 IO，什么是 NIO，什么是 AIO，什么是 netty 框架？

IO 就是 input 与 output，输入输出。

在 Linux 中有五种 IO 模型：

• 阻塞 IO（bloking IO）
• 非阻塞 IO（non-bloking IO）
• IO 多路复用（multiplexing IO）
• 信号驱动 IO（signal-driven IO）
• 异步 IO（asynchronous IO）

在 Java 中，nio 为同步非阻塞，aio 为异步非阻塞。其他的因为我不会 Java，所以也不会…

参考

• 《计算机网络》 - 电子工业出版社 谢希仁著

数据库

数据库常用的操作

这个问题太笼统了，最常规的肯定就是各种 CURD 了。

• Create: 创建
• Update: 更新
• Retrieve: 读取
• Delete: 删除

当然这只是基础中的基础，我的数据库水平不怎么样，这里就不再献丑了。

什么是左连接，什么是右连接，什么是全连接，什么是内连接？

创建表

创建两个表，表结构如下：

student

| name | type | | - | - | | student_id | int | | name | varchar | | class | varchar |

插入数据

| student_id | name | class | | - | - | - | | 1 | 张三 | 一班 | | 2 | 李四 | 一班 | | 3 | 王五 | 二班 |

score

| name | type | | - | - | | score_id | int | | student_id | int | | name | varchar | | score | double |

插入数据

| score_id | student_id | name | score | | - | - | - | - | | 1 | 1 | 英语 | 38 | | 2 | 2 | 英语 | 59.5 | | 3 | 4 | 数学 | 98 |

内连接

内连接也叫连接，是最早的一种连接。还可以被称为普通连接或者自然连接，内连接是从结果表中删除与其他被连接表中没有匹配行的所有行，所以内连接可能会丢失信息。

连接时也可以指定条件为 >、< 等。

select
  student.name as student,
  score.name,
  score
from student, score
where student.student_id = score.student_id;

or

select
  student.name as student,
  score.name,
  score
from student
  inner join score on student.student_id = score.student_id;

查询结果

student	name	score
张三	英语	38
李四	英语	59.5

左连接

以左表为基准进行连接，会显示左表的所有列。如果右表无相应数据，则显示 null。

select
  student.name as student,
  score.name,
  score
from student
  left join score on student.student_id = score.student_id;

查询结果

student	name	score
张三	英语	38
李四	英语	59.5
王五	<null>	<null>

右连接

与左连接相反，显示右表所有列。

select
  student.name as student,
  score.name,
  score
from student
  right join score on student.student_id = score.student_id;

student	name	score
张三	英语	38
李四	英语	59.5
<null>	数学	98

全连接

同时显示左表与右表所有列，不能匹配的显示 null。

MySQL 不支持全连接。

数据库的事务有哪些特性？

数据库中事务的四大特性（ACID）

• Atomicity: 原子性 事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。
• Consistency: 一致性 事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。
• Isolation: 隔离性 多个事务并发执行时，一个事务的执行不应影响其他事务的执行。
• Durability: 持久性 已被提交的事务对数据库的修改应该永久保存在数据库中。

数据库中的隔离等级有哪些？

MySQL 有四个隔离级别，级别越高隔离性越强，但是性能也越差。

1. Read uncommitted: 未提交读
2. Read committed: 已提交读
3. Repeatable read: 可重复读
4. Serializable: 可串行化

未提交读

这种级别下有可能产生脏读，脏读就是指一个事务正在访问数据，并且对数据进行了修改，而这种修改还没有提交到数据库中，这时，另外一个事务也访问这个数据，然后使用了这个数据。如果第一个事务最终回滚了，那么另一个事务就会读到错误的数据。

已提交读

这个级别避免了脏读，但是会产生不可重复读。

不可重复读是指在一个事务内，多次读同一数据。在这个事务还没有结束时，另外一个事务也访问该同一数据。那么，在第一个事务中的两次读数据之间，由于第二个事务的修改，那么第一个事务两次读到的的数据可能是不一样的。这样就发生了在一个事务内两次读到的数据是不一样的，因此称为是不可重复读。

可重复读

这个级别避免了不可重复读，但是会产生幻读。

幻读是指第一个事务对一个表中的数据进行了修改，这种修改涉及到表中的全部数据行。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入一行新数据。那么，以后就会发生操作第一个事务的用户发现表中还有没有修改的数据行，就好象发生了幻觉一样。

可串行化

解决了脏读、不可重复读、幻读的问题。但是正如上面提到的，这个隔离级别也是性能最差的。

数据库的索引有什么作用？用什么来实现的？

• 可以极大的加快数据检索的速度
• 可以加速表之间的连接
• 唯一索引可以保证每行数据的唯一性
• 聚集索引可以极大的加快范围检索的速度

MySQL 使用 B+ 树实现的索引

B 树和 B+ 树有什么区别？为什么索引不用 B 树

B+/- 树是一种自平衡的树，与二叉树不同的是它的每一层的节点更多，从而深度较浅，更加适合磁盘 IO。

B 树的每个节点都存有数据，而 B+ 树只在叶子节点存储数据，因此：

• 由于 B+ 树内节点没有 data， 因此一个结点可以存储更多的内结点，每个节点能索引的范围更大更精确，也意味着单次磁盘 IO， B+ 树获得的信息量要大于 B 树

• B+ 树叶节点增加的链指针可进行范围区间查询， B 树每个节点 key 和 data 在一起，无法区间查找。

什么是乐观锁，什么是悲观锁？

乐观锁

乐观锁（Optimistic Lock），顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在提交更新的时候会判断一下在此期间别人有没有去更新这个数据。乐观锁适用于读多写少的应用场景，这样可以提高吞吐量。

乐观锁：假设不会发生并发冲突，只在提交操作时检查是否违反数据完整性。

悲观锁

悲观锁（Pessimistic Lock），顾名思义，就是很悲观，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会 block 直到它拿到锁。

悲观锁：假定会发生并发冲突，屏蔽一切可能违反数据完整性的操作。

参考

• 《MySQL 四种事务隔离级的说明》 - 博客园
• 《由 B-/B+树看 MySQL索引结构》 - segmentfault
• 《MySQL 乐观锁与悲观锁》 - 简书

操作系统

进程和线程的区别是什么？

进程是CPU分配资源的最小单元，线程是CPU调度的基本单元、一个进程可以包含多个线程、巴拉巴拉。

确实没啥好说的…线程比进程要更轻，线程切换的开销小于进程切换的开销。感觉如果遇到这个问题更多的要扯一下具体应用。

进程间通信的方式有什么？线程间通信的方式有什么？

这个问题可大可小，UNPv2 整书都讲的是进程间通信，但从大体上来说，大概有：

• 管道（pipe）,流管道(s_pipe)和有名管道（FIFO）
• 信号（signal）
• 消息队列
• 共享内存
• 信号量
• 套接字（socket)

至于线程间通信，因为同一个进程的不同线程还是在同一个程序的空间内运行，因此可以直接使用共享变量的方式；或者也可以把两个线程作为单独的个体，使用进程间通信的一些方法。

什么是缓存？有哪些缓存的更新算法？

由于CPU的读取速度比内存的读取速度快，如果持续在CPU和内存之间一直来回不停的交换的话，那么CPU的运转周期就会出现了很大的浪费，所以出现了高速缓存,提供缓存的目的一般是为了让数据访问的速度适应CPU的处理速度，一般是使用硬件实现的指令预测与数据预取技术—-尽可能的将要使用的数据预先从内存中取到缓存中。

如今缓存的概念已经扩充，不仅是CPU和主内存之间有Cache,而且在内存和磁盘之间也有Cache,乃至在硬盘与网络之间也有某种意义上的Cache–称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间，用于协调两者数据传输速度差异的结构，均可称为Cache。

缓存的更新算法有：

• 最佳置换算法（OPT） 只存在于理论之中的算法，如果缓存已满，那么就将最后需要使用的内存置换出去。但是这种算法是无法实现的，因为在当前时间不可能知道以后会最晚用到哪些内存。
• 先进先出置换算法（FIFO） 当缓存已满的时候，替换掉最早进入的页。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。
• LFU（Least Frequently Used）最近最少使用算法 这个算法认为之前使用较少的内存在之后被使用的概率也很小，因此会优先替换之前使用最少的内存页。
• 最近最久未使用（LRU）算法 顾名思义，就是把到当前时间为止最久没有用过的内存置换出去。
• Clock置换算法（LRU算法的近似实现） LRU 算法需要的条件较多，因此为了减少复杂度，很多时候应用的是 Clock 置换算法。Clock 置换算法给每个页帧关联一个使用位。当该页第一次装入内存或者被重新访问到时，将使用位置为1。每次需要替换时，查找使用位被置为0的第一个帧进行替换。在扫描过程中，如果碰到使用位为1的帧，将使用位置为0，在继续扫描。如果所谓帧的使用位都为0，则替换第一个帧。

你用过什么linux命令？

这，各抒己见吧。

常用的 cd、ps、top、vim、df、grep、lsof、mv、cp、ls 等等这些是要会的，然后 tcpdump、crontab、time 等等这些也可以了解一下。

参考

• 《Linux进程间通信的几种方式总结》 - CSDN
• 《操作系统虚拟内存中的四种典型页替换算法》 - CSDN

数据结构与算法

重点应该是树和图，如果没有打过算法竞赛的话，感觉把计算机专业的数据结构课本学好，然后 LeetCode 做些题就没问题了。

如果打过算法竞赛的话，那就更没问题了…

总结

这篇面经大概就是这样了，后面还有些 Java 的题目，感兴趣的同学们可以去原链接看一下。因为我不是 Java 方向的，也就不继续深入下去了。

其实这几天心情是有点低落的，各种姿势找学长内推了五家公司，都是内推免笔试。然而免笔试也没有什么用，因为都被简历筛掉了…不知道是真的因为我简历上的内容水平不够，还是因为我来自一个非 985、非 211，甚至不是一本的二本学校。

我不清楚到底是什么原因，我只知道，哪怕内推失败、秋招失败，最后 0 offer，也没什么大不了的。我更希望的是能一直学习下去，参加秋招也是我检验自己学习成果的一种方式。如果真的 0 offer 收场，也就代表着我学习的还不够，那我就回来继续学习就是了。