Shopee面试问题整理

三握手四挥手 及其状态

Go操作redis

github 上面的rediGo

什么是平衡二叉树

编程：实现反转链表

MySQL复合索引

set的使用场景 有序set的使用场景

有序且去重的场景

1、 排行榜：有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜，榜单维护可能是多方面：按照时间、按照播放量、按照获得的赞数等。

2、用Sorted Sets来做带权重的队列，比如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

反射 反射的弊端

优点：运行期类型的判断，动态类加载，动态代理使用反射。

缺点：性能是一个问题，反射相当于一系列解释操作，通知jvm要做的事情，性能比直接的java代码要慢很多。

进程调度算法

先来先服务 时间片轮转算法 短作业优先 最短剩余时间 高响应比 优先级

进程间怎么通信

管道 有名管道 套接字 消息队列 信号量

线程间通信

主要分为共享内存和消息传递

volatile关键字 wait/notify机制

事务隔离级别

隔离级别 脏读（Dirty Read） 不可重复读 幻读（Phantom Read）

未提交读（Read uncommitted） 可能 可能 可能

已提交读（Read committed） 不可能 可能 可能

可重复读（Repeatable read） 不可能 不可能 可能

可串行化（Serializable ） 不可能 不可能 不可能

MyISAM和InnoDB差别

MyISAM不支持事务，InnoDB支持。MyISAM不支持行锁，只支持表锁，InnoDB支持行锁。

InnoDB没有保存具体的行数，所以在统计行数的时候回扫描全表，MyISAM有保存。

myisam的索引以表名+.MYI文件分别保存。innodb的索引和数据一起保存在表空间里。

LINUX kill命令

在Linux/unix下，中止一个Java进程有两种方式，一种是kill -9 pid，一种是kill -15 pill（默认）。

SIGNKILL（9） 的效果是立即杀死进程. 该信号不能被阻塞, 处理和忽略。

SIGNTERM（15） 的效果是正常退出进程，退出前可以被阻塞或回调处理。并且它是Linux缺省的程序中断信号(默认是15)。

TCP四次挥手的TIME_WAIT

在第三次挥手的时候，服务端发FIN给客户端，然后客户端再发ACK命令给客户端，然后进入TIME_WAIT状态，2MSL之后，进入CLOSED状态，从客户端的角度来说，第四次挥手是为了告诉服务端，我收到了你的FIN信号，一切正常，等待2MSL是为了确保服务端收到了ACK，如果因为网络波动导致服务端没收到ACK，那么服务端会重传FIN信号。从服务端的角度老说，第四次挥手能确保客户端收到FIN信号。

TCP UDP

TCP面向连接，UDP是无连接的，TCP能通过校验和，重传控制等，保证可靠传输，UDP不能保证可靠传输，但UDP实时性高且UDP对资源需要的少。

TCP 如何保证数据传输的可靠性

校验和 确认应答+序列号 超时重传 流量控制 拥塞控制

TCP3次握手的过程，为什么要3次 ，SYN攻击

大文件为什么越下载越快？

滑动窗口，慢启动算法，越传越快。

前面说过，还有一个ssthresh（slow start threshold），是一个上限，当cwnd >= ssthresh时，就会进入“拥塞避免算法”。一般来说ssthresh的值是65535，单位是字节，当cwnd达到这个值时后，算法如下：

1）收到一个ACK时，cwnd = cwnd + 1/cwnd

2）当每过一个RTT时，cwnd = cwnd + 1

这样就可以避免增长过快导致网络拥塞，慢慢的增加调整到网络的最佳值。很明显，是一个线性上升的算法。

Innodb 自增主键

上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。

如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。

HTTP 无状态 无连接

无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。为请求时建连接、请求完释放连接，以尽快将资源释放出来服务其他客户端，可以加KeepAlive弥补无连接的问题

无状态是指协议对于事务处理没有记忆能力，服务器不知道客户端是什么状态。即我们给服务器发送 HTTP 请求之后，服务器根据请求，会给我们发送数据过来，但是，发送完，不会记录任何信息。 可以通过Cookie和Session来弥补这个问题。

Cookie 和 Session

cookie 是一种发送到客户浏览器的文本串句柄，并保存在客户机硬盘上，可以用来在某个WEB站点会话间持久的保持数据。

Session的本质上也是cookie，但是不同点是存在服务器上的。这就导致，你如果使用cookie，你关闭浏览器之后，就丢掉Cookie了，但是如果关掉浏览器，重新打开之后，发现还有相应的信息，那就说明用的是Session。因为cookie是存在本地的，所以也会有相应的安全问题，攻击者可以去伪造他，填写相应的字段名，就能登录你的账户，还有如果cookie的有效期很长的话，也不安全。

session 由服务器产生，对于客户端，只存储session id在cookie中。

LRU算法是如何实现的？

双向链表加 哈希表

数组中出现次数最高的K个数

map+优先队列

先用map统计每个数的出现次数，然后维护 一个大小为K的优先队列（堆）。

volatile 内存屏障

CPU有可能会把相应代码的CPU指令进行一次重排序，这虽然能提高运行的效率，但是也可能会影响一些数据的可见性，而volatile通过 内存屏障 这个指令，来保证了相应代码块的执行顺序。内存屏障还会强制更新一次CPU缓存。加载最新的内容。

快排的优化

快排有三个步骤：

1. 选择基准

2. 分割操作

3. 递归地对两个序列快速排列，直到序列为空或只有一个元素。

所以可以针对这三个方面做优化

选择基准:最理想的基准就是，每次划分都能分成登长的两个子序列。最坏的情况 就是基准是最大最小值。

可以选的基准有：固定位置，随机位置，三数取中。

三数取中是指 取 最左 最右 中间元素 三个数的中间值。

其他优化方式：

1. 当排序序列分割到一定大小的时候，可以使用插入排序

2. 如果有key相等的元素，可以聚在一起，下次排序的时候，就不用对相等的元素再排序了

3. 优化递归操作

4. 多线程

Mysql 的 redo undo

Undo日志记录某数据被修改前的值，可以用来在事务失败时进行回滚；Redo日志记录某数据块被修改后的值，可以用来恢复未写入data file的已成功事务更新的数据。

死锁的四个条件 和预防

互斥，不可剥夺，循环等待，请求和保持

预防，检测，避免死锁，接触死锁

银行家算法

多路IO模型 NIO

在多路复用IO模型中，会有一个线程（Java中的Selector）不断去轮询多个socket的状态，只有当socket真正有读写事件时，才真正调用实际的IO读写操作。因为在多路复用IO模型中，只需要使用一个线程就可以管理多个socket，系统不需要建立新的进程或者线程，也不必维护这些线程和进程，并且只有在真正有socket读写事件进行时，才会使用IO资源，所以它大大减少了资源占用。

五种网络IO模型

阻塞IO 非阻塞IO 多路IO复用，信号驱动IO（不常用），异步IO，

前四种都是同步IO

像listen()、send()、recv()这些接口都是阻塞的，一问一答型的。这就给网络编程带来了一个问题，如果在调用send的时候，线程将被阻塞，在此期间，无法执行任何运算或相应任何的网络请求。于是有了多路IO模型，一个socket可以多次accept多次，比如Java中的selcetor 不断轮询多喝socket的状态，只有当socket真正有读写事件的时候，才会调用实际的IO读写操作，还有想Golang里的select+多个channel，这样只需要一个线程就可以管理多个socket，能减少大量资源占用。

非阻塞IO模型

在非阻塞IO模型中，用户进程不需要主动询问对方是否准备好数据与否，比如进程发出read操作，如果对方没有准备好，会返回一个error，这表示对方没有准备好，但是进程并不会阻塞在这一步，而是继续执行，等对方准备好数据后，再去调用它。

异步IO

异步IO是真正意义上的非阻塞IO，用户进程发起read操作后，立刻就可以开始做其他事，而另一方面，当他收到一个异步请求时，会立即返回一个值，所以不会对用户进程产生任何阻塞，等数据准备完后，再将数据拷贝到用户内存，当这一切都完成后，再给用户进程发送一个signal，告诉他read操作完成了。

非阻塞IO和异步IO的区别

虽然非阻塞IO在大多时间内不会被阻塞，但是它要求进程去主动监察对方数据是不是准备好了，一旦准备好了，会再次要求进程调用接收函数将数据拷贝过来。而异步IO完全不管这些，就像吧IO操作外包掉，等他人做完再发信号通知，这个期间内，进程不要检查也不用主动的去拷贝。

Golang里的Sync包

互斥锁：Mutex，读写锁:RWMutex. WaitGoup,Cond实现一个条件变量，Once 使对象只执行一次。

Java线程的6种状态及切换

初始：新建一个线程对象

运行：调用了start后就是运行状态

阻塞：线程被锁阻塞

等待，进入该状态的线程需要等待其他线程做出一些动作（通知或者唤醒

超时等待：

终止：

虚拟内存

虚拟内存使得应用程序认为它拥有连续的可用内存，这样一来，就在逻辑层面上扩大了内存容量。但是实际上，只是把比较常用的内存片段取出来了而已，还有部分资源是放在磁盘存储器上的。需要的时候再进行数据交换。

调度方式有，分页式，段式，段页式。比较流行方式是段页式，他结合了前两者的优点，以页为单位替换，以段为单位使用。

常见的替换替换算法有4种，随机算法，先进先出算法，LRU算法，最优算法。 比较常使用的是LRU算法，他在redis里也有使用，当redis的内存满了的时候就是使用LRU算法替换掉旧内存。