算法

1. 快速排序原理

2. 二叉树转换为双向链表

3. 二分查找

4. 所有排序算法及稳定性

5. LRU算法

6. 最大公约数

数据结构

1. dp是什么

2. 为什么用平衡二叉树

3. 树的遍历

4. 哈夫曼树

数据库

1.MySQL的存储引擎有哪几种？

存储引擎 ：对于数据库文件的一种存储机制，如何实现存储数据，如何为存储的数据建立索引以及如何更新，查询数据等技术实现的方法。
MySQL中查看引擎：
**show engines;** // 查看mysql所支持的存储引擎，以及从中得到mysql的默认存储引擎。

show variables like '% storage_engine'; // 查看mysql默认的存储引擎
show create table <tablename>; // 查看具体一个表所使用的存储引擎
show table status from database where name="tablename"; // 准确查看某个数据库中的某一个表所使用的存储引擎

InnoDB存储引擎: 支持事务处理，支持外键，支持崩溃修复能力和并发控制。如果需要对事务的完整性要求比较高（比如银行），要求实现并发控制（比如售票），那选择InnoDB有很大的优势。如果需要频繁的更新、删除操作的数据库，也可以选择InnoDB，因为支持事务的提交（commit）和回滚（rollback）。 MyISAM存储引擎: 插入数据快，空间和内存使用比较低。如果表主要是用于插入新记录和读出记录，那么选择MyISAM能实现处理高效率。如果应用的完整性、并发性要求比 较低，也可以使用。 MEMORY存储引擎: 所有的数据都在内存中，数据的处理速度快，但是安全性不高。如果需要很快的读写速度，对数据的安全性要求较低，可以选择MEMOEY。它对表的大小有要求，不能建立太大的表。所以，这类数据库只使用在相对较小的数据库表。

注意，同一个数据库也可以使用多种存储引擎的表。如果一个表要求比较高的事务处理，可以选择InnoDB。这个数据库中可以将查询要求比较高的表选择MyISAM存储。如果该数据库需要一个用于查询的临时表，可以选择MEMORY存储引擎。

2. InnoDB和MyISAM的区别

3. 并发事务会发生的问题

参考

事务 Transaction：

并发控制的基本单位。它是一个操作序列，这些操作要么都执行，要么都不执行，它是一个不可分割的工作单位。例如，银行转账工作：从一个账号扣款并使另一个账号增款，这两个操作要么都执行，要么都不执行。
事务是数据库维护数据一致性的单位，再每个事务结束时，都能保持数据一致性。

事务的四大特性 ACID

• 原子性 Atomicity：一个事务是不可分割的，是最小的执行单位。
• 一致性 Consistency：在执行事务后，数据库状态保持一致，从一个一致性状态转换到另一个一致性状态。
• 隔离性 Isolation：在并发访问数据库时，一个事务不被其他事务所干扰，各并发事务之间数据库是独立的。隔离性是通过锁来实现的。
• 持久性 Durability：一旦事务提交，则其所做的修改就会永久保存到数据库中。即使数据库发生故障也不应该对其有任何影响。

丢失更新：

• 第一类丢失更新 (回滚丢失，Lost update)

  定义：A事务撤销时，把已经提交的B事务的更新数据覆盖了。

事务A的开始时间和结束时间包含事务B的开始和结束时间,事务A回滚事务的同时,把B的已经提交的事务也回滚的,这是避免的,这就是第一类丢失更新.

• 第二类丢失更新 (覆盖丢失/两次更新问题，Second lost update)

  定义：A事务提交时，把已经提交的B事务的更新数据覆盖了。

第二类丢失更新和第一类的区别实际上是对数据的影响是由A事务的撤销还是提交造成的，它和不可重复读(下面介绍)本质上是同一类并发问题，通常把它看做是不可重复读的一个特例。两个或多个事务查询同一数据。然后都基于自己的查询结果更新数据，这时会造成最后一个提交的更新事务，将覆盖其它已经提交的更新事务。

脏读：

定义：读到未提交更新的数据

数据表中的数据是实时改变的，事务只是控制数据的最终状态，也就是说如果没有正确的隔离级别，在更新操作语句结束后，即使事务未完成，其他事务就已经可以读取到改变的数据值了。

不可重复读：

定义：读到已经提交更新的数据，但一个事务范围内两个相同的查询却返回了不同数据。

**

幻读

数据库并发事务导致的五大问题，两类更新问题（回滚丢失，覆盖更新）和三类读问题（脏读，不可重复读，幻读）

4. 数据库隔离级别？ 如何选择需要的隔离级别

通过设置不同的事务隔离级别来避免并发事务问题。

SQL标准定义了4类隔离级别，包括一些具体规则，用来限定事务内务的哪些改变是可见的，哪些是不可见的，低级别的隔离级一般支持更高的并发处理，并拥有更低的系统开销。

4.1 SERIALIZABLE 串行化 最安全/最慢

一个事务在执行过程中完全看不到其他事务对数据库所作的更新，当事务AB同时操作数据库中相同数据D时，如果A正在访问D，B只能停下来等待，必须等到A结束才能恢复运行。因此AB是串行化方式运行。

4.2 REPEATABLE READ 可重复读 2

一个事务在执行过程中可以看到其他事务已经提交的新插入的记录，但是不能看到其他事务对已有记录的更新。

4.3 READ COMMITED 读已提交数据 3

一个事务在执行过程中可以看到其他事务已经提交的新插入记录，而且还能看到其他事务已经提交的对已有记录的更新

4.4 READ UNCOMMITED 读未提交数据 最不安全/最快

一个事务在执行过程中可以看到其他事务没有提交的新插入的记录，而且还能看到其他事务没有提交的对已有记录的更新。

如何选择隔离级别？

Mysql InnoDB默认使用Read repeatable的隔离级别

5. 主从复制 MySQL Replication

参考1 参考2

概念：

主从复制是指一台服务器充当主数据库服务器，另一台或多台服务器充当从数据库服务器，主服务器中的数据自动复制到服务器之中。从一个MySQL数据库服务器主节点复制到一个或多个从节点。 MySQL 默认采用异步复制方式，这样从节点不用一直访问主服务器来更新自己的数据，数据的更新可以在远程连接上进行，从节点可以复制主数据库中的所有数据库或者特定的数据库，或者特定的表。

为什么需要主从复制

• 做数据的热备份
• 如果主数据库宕机，可以快速将业务切换到从数据库中，避免数据丢失
• I/O访问频率过多，多库存储降低磁盘I/O访问频率，提高单个机器的I/O性能；如果对数据库的读写都在同一个数据库服务器中操作，业务系统性能降低。
• 主库负责写，从库负责读，在主库出现锁表的情况下也可以读从库保证业务正常运作；通过主从复制（读写分离）来减轻主数据库的负载

主从复制用途

• 读写分离——针对锁表
• 热备份——防宕机
• 高可用 (HA, High Availability)架构扩展——I/O性能

主从复制的类型：

• 基于语句的复制(默认)：时间上可能不完全同步造成偏差，执行语句的用于也可能不是同一个用户
• 基于行的复制：修改的行多会造成大开销

主从复制原理：

主服务器上的任何更改都会保存在二进制日志Binary log中，从从服务器上启动一个 I/O Thread，连接到主服务器上请求read Binary log，然后把读取的binary log存储到本地的一个Relay log(中继日志)中。在从服务器上开启一个SQL Thread定时检查Relay log，如果发现有更改立即把更改的内容在本机上执行。

主从复制过程：

• Slave上面的IO进程连接上Master，并请求从指定日志文件的指定位置（或者从最开始的日志）之后的日志内容。
• Master接收到来自Slave的IO进程的请求后，负责复制的IO进程会根据请求信息读取日志指定位置之后的日志信息，返回给Slave的IO进程。返回信息中除了日志所包含的信息之外，还包括本次返回的信息已经到Master端的bin-log文件的名称以及bin-log的位置。
• Slave的IO进程接收到信息后，将接收到的日志内容依次添加到Slave端的relay-log文件的最末端，并将读取到的Master端的 bin-log的文件名和位置记录到master-info文件中，以便在下一次读取的时候能够清楚的告诉Master从何处开始读取日志。
• Slave的Sql进程检测到relay-log中新增加了内容后，会马上解析relay-log的内容成为在Master端真实执行时候的那些可执行的内容，并在自身执行。

6. 主从复制的半同步和全同步

异步模式 async-mode (默认)

异步模式，主库将事务bin log写入到 Binary log中，此时主库只会通知Dump Thread发送新的Binary log，然后主库就会继续处理提交操作，而此时不能保证这些Binary log传到任何一个从库节点。这种模式下，主节点不会主动push bin log到从节点，这样有可能导致failover的情况下，也许从节点没有即时地将最新的bin log同步到本地。

半同步模式 semi-sync-mode 效率最高

主库只需要等待至少一个从库节点收到并且 Flush Binlog 到 Relay Log 文件即可，主库不需要等待所有从库给主库反馈。同时，这里只是一个收到的反馈，而不是已经完全完成并且提交的反馈，如此，节省了很多时间。 半同步复制有两种方案（用参数rpl_semi_sync_master_wait_point来控制）： 1)after_commit：旧的半同步方案，特殊情况下会出现幻读，导致有数据丢失。 2)after_sync: mysql5.7之后新的半同步方案，默认值为after_sync，可实现无损复制 可以提高数据安全性，性能上会有一定的降低，响应时间会变长。

全同步模式 sync-mode

全同步模式是指主节点和从节点全部执行了commit并确认才会向客户端返回成功。当主库提交事务之后，所有的从库节点必须收到、APPLY并且提交这些事务，然后主库线程才能继续做后续操作。但缺点是，主库完成一个事务的时间会被拉长，性能降低。

7. 数据库更新失败怎么办？

8. 数据库量增大怎么优化查询

单表优化

1 表分区

2 增加缓存

3 字段设计：

• 单表不要有太多字段；
• varchar的长度尽量只分配真正需要的空间；
• 尽量使用timestamp而非datetime；
• 避免使用NULL，可以通过设置默认值解决；

4 索引优化

• 索引不是越多越好，针对性地简历索引，索引会加速查询，但对新增、修改、删除会造成一定影响；
• 值域很少的字段不适合键索引；
• 尽量不用UNIQUE，不要设置外键，由程序保障；

表拆分

1 垂直拆分

把一个字段较多的表，拆分成多个字段较少的表

2 水平拆分

分表分库

9. 缓存数据一致性

10. 数据库三范式

参考

第一范式：1NF

1NF是**对属性的原子性**，要求属性具有原子性，不可再分解； 表：Field1，Field2(Field2.1, Field2.2), Field3 …

如学生（学号，姓名，性别，出生年月日），若出生年月日还可以分成（年，月，日），则他不是1NF；

第二范式：2NF

2NF是对**记录的唯一性，要求记录有唯一标识，即实体的唯一性，即不存在部分依赖**； 表：学号、课程号、姓名、学分；

这个表说明两个事务：学生信息，课程信息；非主键必须依赖主键，即学分依赖课程号 ，姓名依赖学号，所以不符合2NF；
可能存在问题：

• 数据冗余：每条记录都包含相同的信息
• 删除异常：删除所有学生成绩就会把课程信息全删除了
• 插入异常：学生未选课，无法记录进数据库
• 更新异常：调整课程学分，所有行都要调整

正确做法：

• 学生：Student(学号，姓名)
• 课程：Course(课程号，学分)
• 选课关系：StudentCourse(学号，课程号，成绩)

第三范式：3NF

3NF是对**字段的冗余性，要求任何字段都不可以由其他字段派生出来，要求字段没有冗余，即不存在传递依赖**； 表：学号，姓名，年龄，学院名称，学院电话

存在传递依赖：学号-学生-学院-学院电话
可能存在问题：

数据冗余：有重复值 更新异常：有重复的冗余信息，修改时需要同时修改多条记录，否则会出现数据不一致

正确做法：

学生：学号，姓名，年龄，所在学院 学院：学院，电话

范式化与反范式化的优缺点：

范式化：

优点 缺点
反范式化：
**
优点 缺点

11. SQL调优怎么操作

慢查询优化基本步骤

1. 先运行看看是否真的很慢，注意设置SQL_NO_CACHE
2. where条件单表查，锁定最小返回记录表。这句话的意思是把查询语句的where都应用到表中返回的记录数最小的表开始查起，单表每个字段分别查询，看哪个字段的区分度最高
3. explain查看执行计划，是否与1预期一致（从锁定记录较少的表开始查询）
4. order by limit 形式的sql语句让排序的表优先查
5. 了解业务方使用场景
6. 加索引时参照建索引的几大原则
7. 观察结果，不符合预期继续从0分析

https://www.jianshu.com/p/61d7cf35549d

12. 索引底层

链接

13. redis数据结构

14. 有两个任务对数据库里的数据分别进行更改，如何保证不重复更改，怎么设计表结构？写出SQL语句

# 查看隔离级别
DBCC USEROPTIONS;
select @@global.transaction_isolation;
select @@session.transaction_isolation;
show variables like '%iso%';
# 设置全局隔离级别
set global transaction isolation level REPEATBLE READ;
# or
set global transaction isolation level SERIALIZABLE;
# 设置会话隔离级别
set session transaction isolation level REPEATABLE READ;
set session transaction isolation level SERIALIZABLE;

15. group by 和 order by 区别 与 注意点

order by :

一般是用来依照查询结果的某一列或者多列属性，进行排序（ASC，DESC） 当排序列为空时： ASC：排序列为空值的元组最后显示，DESC相反。

多列属性排序

选择多个列属性进行排序，然后排序的顺序是，从左到右，依次排序。 如果前面列属性有些是一样的话，再按后面的列属性排序。（前提一定要满足前面的属性排序，因为在前面的优先级高）。

group by :

按照查询结果集中的某一列（或多列），进行分组，值相等的为一组

细化集函数（count、sum、avg、max、min）的作用对象

未对查询结果分组，集函数将作用于整个查询结果 对查询结果分组后，集函数将分别作用于每个组

16. 幻读 以及 如何解决

定义：读到已提交插入数据，幻读与不可重复读类似，幻读是查询到了另一个事务已提交的新插入数据，而不可重复读是查询到了另一个事务已提交的更新数据。

A事务第一次查询时，没有问题，第二次查询时查到了B事务已提交的新插入数据，这导致两次查询结果不同。
不可重复读和幻读的区别：

不可重复读是优于数据修改引起的，幻读是由于数据插入或者删除引起；

幻读是指当事务不是独立执行时发生的一种现象，例如第一个事务对一个表中的数据进行了修改，比如这种修改涉及到表中的“全部数据行”。同时，第二个事务也修改这个表中的数据，这种修改是向表中插入“一行新数据”。那么，以后就会发生操作第一个事务的用户发现表中还有没有修改的数据行，就好象发生了幻觉一样.一般解决幻读的方法是增加范围锁RangeS，锁定检锁范围为只读，这样就避免了幻读。

17. 创建主键的原则

18. 自增主键的好处

AUTO_INCREMENT优点：

数据库自动编号，速度快，而且是增量增长，按顺序存放，对于检索非常有利； 数字型，占用空间小，易排序，在程序中传递也方便； 如果通过非系统增加记录时，可以不用指定该字段，不用担心主键重复问题。

AUTO_INCREMENT缺点：

因为自动增长，在手动要插入指定ID的记录时会显得麻烦，尤其是当系统与其它系统集成时，需要数据导入时，很难保证原系统的ID不发生主键冲突（前提是老系统也是数字型的）。特别是在新系统上线时，新旧系统并行存在，并且是异库异构的数据库的情况下，需要双向同步时，自增主键将是你的噩梦； 在系统集成或割接时，如果新旧系统主键不同是数字型就会导致修改主键数据类型，这也会导致其它有外键关联的表的修改，后果同样很严重； 若系统也是数字型的，在导入时，为了区分新老数据，可能想在老数据主键前统一加一个字符标识（例如“o”，old）来表示这是老数据，那么自动增长的数字型又面临一个挑战。

UUID

UUID含义是通用唯一识别码 (Universally Unique Identifier)，指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的。通常平台会提供生成的API。换句话说能够在一定的范围内保证主键id的唯一性。

优点

出现数据拆分、合并存储的时候，能达到全局的唯一性

缺点

影响插入速度， 并且造成硬盘使用率低 uuid之间比较大小相对数字慢不少， 影响查询速度。

uuid占空间大， 如果你建的索引越多， 影响越严重

19. varchar和char

varchar类型用于存储可变长得字符串，在存储得字符串是变长时更节约空间；

适用于：

• 字符串列得最大长度比平均长度要大很多时
• 字符串列得更新很少时，因为没有或很少有内存碎片得问题
• 使用UTF-8这样复杂得字符集，每个字符都使用不同得字节数进行存储

优点：

变长得字符类型兼容性更好

缺点：

• 可能会产生内存碎片
• 额外使用1到2个字节存储长度信息
• update语句可能会导致页分裂

char是定长得，在存储数据时会删除所有文末得空格。

适用于：

• 列得长度为定值，如MD5密文数据

优点:

• 定长的字符类型，减少内存碎片
• 无需额外空间区存储长度信息

缺点：

会删除末尾的空格信息

网络

1. TIME_WAIT有遇到过么？TIME_WAIT之后怎么去设置参数释放端口号

2. TCP三次握手/四次分手 （为什么要三次握手而不是两次四次）

3. 流量控制和拥塞控制

4. 拥塞控制怎么设置窗口大小

5. 慢启动

6. HTTPS的建立过程

7. HTTPS发送一个请求，中间有哪些协议？

8. HTTPS中响应到达缓慢，怎么解决（HTTP传输中间有哪些阶段）

9. HTTP和TCP的区别，一定要基于TCP嘛?（为什么不用UDP）

10. 常见http请求状态码

11. 客户端发送请求服务的不回应的原因

12. HTTP版本与特性

13. 微服务？

14. TCP如何保证可靠传输？ 如何确认编号

15. 丢包怎么办

16. 如何保证数据包中内容不丢失

17. 网络层协议有哪些？应用层？

操作系统

1. 进程和线程的区别

进程和线程都是一个时间段的描述，是CPU工作时间段的描述。是运行中的程序指令的一种描述，这需要与程序中的代码区别开。

进程：是系统分配的最小单位，所有进程数据不共享，开销大。

线程：又称作为轻量级进程，在同一个进程下执行，并享有相同的上下文。是CPU调度的最小单位，依赖进程存在。

协程：是一种用户态的轻量级线程

协程的调度完全由用户控制，协程拥有自己的寄存器上下文和栈。 协程调度时，将寄存器上下文和栈保存道其他地方，在切换回来的时候恢复先前保存的寄存器上下文和栈，直接操作栈则 基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换速度快。 协程的作用，是在执行函数A时，可以随时中断，去执行函数B，然后中断继续执行函数A（可以自由切换）。但这一过程并不是函数调用（没有调用语句），这一整个过程看似像多线程，然而协程只有一个线程执行. 协程由于由程序主动控制切换，没有线程切换的开销，所以执行效率极高。对于IO密集型任务非常适用，如果是cpu密集型，推荐多进程+协程的方式。

区别

同一进程中线程的共享与独占资源

共享资源：

• 内存空间：
  • 代码
  • 公共数据（全局遍历、静态变量）
  • 堆
• 文件描述符FD (File Descriptor)

Linux中把一切都看作是文件，当进程打开现有文件或者创建新文件时，内核向进程返回一个文件描述符，文件描述符就是内核为了高效管理已被打开的文件所创建的索引，用来指向被打开的文件，所有执行I/O操作的系统调用都会通过文件描述符。

• 信号处理器
• 进程ID/进程组ID
• …

独占资源

• 线程ID：在本进程中唯一，进程用来标识此线程
• 寄存器组的值

---

• 由于线程间是并发运行的，每个线程有自己不同的运行线索，当从一个线程切换成到另一个线程上时，必须将原有的线程寄存器集合的状态保存，以便将来该线程在被重新切换时能恢复。
  • 栈：
• 每个线程中的函数调用过程都是独立的，因此需要由独立的栈
  • 错误返回码：
• 系统调用或库函数发生错误时，会设置全面变量 **errno** ，各个线程返回的错误返回码应该是独立的
  • 信号屏蔽码
• 每个线程所感兴趣的信号不同，所以线程的屏蔽码应该由线程自己管理，但每个线程都共享本进程的信号处理器
  • 线程的优先级参数

2. 进程间通信

进程间通信

3. 死锁

死锁

4. epoll 和 select

link

5. 多路复用

6. 线程池如何实现和存储

7. 线程池参数

8. 守护线程和普通线程

非守护线程

9. 如果线程队列满了怎么办

10. 什么是内存泄漏

内存泄漏：memory leak

用动态存储分配函数动态开辟的空间，在使用完毕之后未释放，结果导致一直占据该内存单元直到程序结束。（内存空间未回收）

内存溢出：out of memory

指程序在申请内存时，没有足够的内存空间供其使用。比如申请了一个integer，但是给它存下了long才能存下的数

内存溢出的原因及解决方法：

溢出原因：

• 内存中加载的数据量过于庞大，如一次从数据库取出过多数据
• 集合类中由对对象的引用，使用完后未清空
• 代码中存在死循环或者循环产生过多重复的对象实体

**

Linux

1. 查看端口号占用并杀死进程

2. 查看进程

3. sort

4. 如何查询日志文件中的某个东西

C++

1. C++多态怎么实现

2. 虚函数表

Python

序列化与反序列化

后端

1. 幂等性？

2. 高并发

3. 如何设计一个登录功能

4. cookie保存哪些内容，如何保证cookie不被修改

设计模式

1. 常用的设计模式

2. 单例模式的用途

3. 工厂模式

4. 抽象工厂和简单工厂的区别

机器学习

1. 哪些聚类算法

2. 哪些数据挖掘算法

3. 降维的数学原理

4. 聚类怎么计算非数值的距离

5. k-means与KNN原理