面试实战第三期

介绍下我自己，我是王星星，2021届校招生，目前在阿里巴巴做Java开发。去年秋招的时候拿到了阿里，微信，拼多多，百度，美团，携程等互联网公司的offer。这个系列文章主要是通过总结牛客上的面经，自己梳理答案，然后分享出来，帮助广大实习和秋招同学稳拿offer，成功上岸！（本系列文章问题均得到牛客网友授权，更多面经答案请访问公众号：王星星的魔灯）

原文地址：https://www.nowcoder.com/discuss/708040

自我介绍

1. 交代自己的姓名，院校，学历，开源项目，感兴趣的方向
2. 三分钟即可

数组、链表、栈、堆比较

1. 数组和链表是最基本的数据结构，几乎每个编程语言都天生支持这两种数据结构。这是因为操作系统从内存上来说，连续访问的就是数组，不连续访问的就是链表，这也是数组和链表本质的区别。
2. 对于数组来说，它的查询是O(1)的，修改是O(n)的；对于链表来说，则刚刚相反。在使用场景上，数组的内存分配方式容易产生内存碎片，而链表就不会这样。
3. 对于C来说，它有原生数组，C的链表是通过指针实现的；对于Java来说，它则是数组即对象，同时，Java的链表是通过引用实现的（这里可以引申出C和Java数组的实现方式）
4. 如果说数组和链表是物理上的实现，那么栈和堆从数据结构上来说就是理论上的概念。一般来讲，堆由链表或数组实现，栈可以通过数组实现。栈是先进先出的，体现了FILO的思想（这里可以引申出FILO算法的应用）。堆则是满足父子节点大小的完全二叉树，常见的有最大堆和最小堆
5. 从应用角度讲，进程空间中就会有栈（如方法栈）和堆（程序运行时数据的存放位置）的概念，这和数据结构中的是不同的。

什么是哈希表

1. 散列表，也叫哈希表，是根据key而直接访问在内存储存位置的数据结构。从理论上来说，哈希表是一种映射关系，所以我们常把哈希表在代码中用map来表示。因为通过这种映射关系可以一对一的直接拿到映射结果，所以它的查询复杂度是O(1)
2. 因为不同的key通过散列函数映射的时候，可能会映射到一个记录中，所以就会产生哈希冲突的。当差生哈希冲突的时候，查询复杂度就是大于O(1)
3. 处理哈希冲突的方式有很多中，常见的有开放定址法，单独链表法，再散列法或者建立一个公共溢出区等
4. 如何降低哈希冲突，提高查找效率呢？我们可以使用更均匀的散列函数降低冲突，使用拉链法处理冲突，减小负载因子降低冲突（Java中的最佳负载因子是0.75）

MySQL聚簇索引与非聚簇索引、覆盖索引、联合索引

1. 聚簇索引：key为主键，value为其余列的数据。一个表只能有一个聚簇索引

2. 非聚簇索引：除了聚簇索引外的都叫非聚簇索引

   • 对于MyISAM的主键索引来说，它的非聚簇索引是key为主键，value为行号(不一定)
   • 对于MyISAM的二级索引来说，它的非聚簇索引是key为其他列，value为行号(不一定)
   • 对于InnoDB的二级索引来说，它的非聚簇索引是key
   • 注意：MyISAM无论主键索引还是二级索引都是非聚簇索引，而InnoDB的主键索引是聚簇索引，二级索引是非聚簇索引。我们自己建的索引基本都是非聚簇索引

3. 所谓的覆盖索引，就是指如果一个索引包含（覆盖）所有需要查询字段的值，我们就称之为覆盖索引

4. 因为每个select只能选择一个索引，当where条件过多时，我们可以考虑建立联合索引，即把多个列作为索引

5. 联合索引一般需要考虑最左前缀原则，但是我们在查询的时候不用严格按照最左原则排序，解析器会帮我们优化的

一般如何构建联合索引，怎么考虑联合索引的顺序

1. 即是最左前缀原则，同时，我们不用在写sql时严格按照最左原则的顺序，因为sql的优化器会去优化。不过笔者建议还是按照顺序写sql比较好，这样可读性更高一点

2. 为什么要遵循最左前缀原则呢？是因为存储引擎在构造联合索引的时候，它会先根据最开始的构建b+tree，当最开始的相等的时候，它才会通过第二个去构建对应的b+tree，这样依次构建下来，所以我们在查询的时候，也需要尊旭最左前缀原则

   MySQL 索引数据结构，为什么用 B+ 树

3. MySQL常见的两种存储引擎如InnoDB，MySIAM都是使用B+树作为索引的数据结构的，除了B+Tree之外，还有Hash索引，全文索引，R-Tree索引

4. B-Tree索引

   • 因为存储引擎不用进行全表扫描来获取数据，直接从索引的根节点开始搜索，从而能加快访问数据的速度
   • B-Tree对索引是顺序组织存储的，很适合查找范围数据
   • 适用于全键值、键值范围或者键前缀查找（根据最左前缀查找）
   • 限制：对于联合索引来说，如果不是从最左列开始查找，则无法使用索引；不能跳过索引中的列

5. B+Tree索引

   • 是B-Tree索引的变种，现在主流的存储引擎都不用单纯的B-Tree，而是其变种B+Tree或者T-Tree等等
   • 和B-Tree最主要的区别就是B+Tree的内节点不存储data，只存储key，叶子节点不存储指针

6. Hash索引

   • 基于Hash表实现，只有Memory存储引擎显式支持哈希索引
   • 适合等值查询，如=、in()、<=>，不支持范围查询
   • 因为不是按照索引值顺序存储的，就不能像B+Tree索引一样利用索引完成排序
   • Hash索引在查询等值时非常快
   • 因为Hash索引始终索引的所有列的全部内容，所以不支持部分索引列的匹配查找
   • 如果有大量重复键值得情况下，哈希索引的效率会很低，因为存在哈希碰撞问题
   • 程序员可以在B+Tree索引的基础上创建自适应Hash索引

7. 全文索引

   MyISAM和InnoDB都支持全文索引
   有三种模式：自然语言模式，布尔模式和查询扩展模式

8. R-Tree索引

   MyISAM支持R-Tree索引，这个和全文索引基本不问

HTTP与HTTPS

1. HTTP协议是基于TCP协议的应用层协议，浏览器和部分RPC都是使用HTTP协议通信的。HTTP1.1可以通过cookie来保持状态，也可以通过Connection:keep-alive来保持链接，减少不断创建和销毁的TCP连接。HTTP的端口是80
2. 因为大部分HTTP的连接不仅时间短而且是突发性的，但是HTTP底层的TCP只有在长时间连接传输大块数据时效率才最高，所以在HTTP2.0时为了更有效的使用TCP连接，采用了多路复用，允许同时通过单一的 HTTP/2 连接发起多重的请求-响应消息。具体1.1和2.0的差别可以看这个网站演示
3. 对于HTTPS来说，它的端口是443，HTTPS是通过非对称加密的方式将请求的报文进行加密。加密过程主要分为四步：
   • client向server发送可以接受的ssl证书，server返回自己的公钥证书
   • client在本地通过ca验证server的正确性
   • 成功后通过公钥加密自己的密钥发送给server
   • server使用私钥解密，之后client和server使用密钥通信
4. 但是HTTPS也不是绝对安全的，可能会通过CA伪装攻击，不过这个攻击会在client的第二步去验证，浏览器会发出警告的

TCP如何保障可靠性

1. TCP的三次握手和四次挥手会保证建立连接和取消连接的可靠性
2. 其次，TCP通过首部校验和的方式来对消息的准确性进行校验
3. 最后，TCO通过ARQ协议来保证消息一定可以传送成功。即sender发送一个分组后收到ack再发送下一个。sender会自定义一个计时器，如果超时则重新发送。实际上是使用的连续ARQ协议，receiver只确认分组的最后一个报文即可

进程和线程区别

1. 进程是系统进行资源分配和保护的基本单位，线程是处理器调度和分配的基本单位
2. 对于内存占用来说，线程要比进程小的多。进程会包含数据段，代码段，堆栈段等，进程拥有一个完整的私有的基本运行的资源集合，而线程则共享大部分进程的空间
3. 对于通信来说，进程主要通信方式有IPC（共享内存，SOCKET，管道，消息队列，信号等），线程主要的通信方式则是通过共享变量和信号进行通信
4. 对于切换来说，进程因为包含的信息比较多，同时切换的时候也需要进行内核切换。而对于用户态线程来说，线程切换的速度则是会快的多

协程了解过吗

1. 协程也被称为用户态线程，相对来说，因为协程的切换不需要陷入内核态，协程的切换要比线程快很多
2. 不过协程其实跟线程进程是有本质上区别的，协程是指程序相互协作的意思，OS对协程是没有感知的，用户需要通过栈或者其他数据结构记录协程上下文切换要保存的信息，对协程进行调度
3. 从进程到线程再到协程, 其实是一个不断共享, 不断减少切换成本的过程

Linux熟悉吗，常用命令哪些

1. Linux常用的命令有vim, cd,tail,cat,pwd,mkdir,rm,top,touch,grep,ps
2. 一般查看日志的方式可以通过tail,cat来查看文本

Volatile作用

1. volatile是不会保障原子性的，它有两个作用，一个是通过屏障机制立刻读取，写入最新的值，保证了可见性。第二个作用是禁止CPU指令重排序
2. volatile的常见实用场景有是跟它的两个作用有关的
   • 线程安全的单例模式，使用volatile是为了防止指令重排序
   • AQS中state使用了volatile来修饰，是为了保证其状态的可见性

不加锁的情况下实现一个并发安全的加数器

1. 这个可以通过原子类实现
2. 原子类主要是通过CAS来实现的

二叉树最大路径和

int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
  if (root == null) {
    return 0;
  }
  dfs(root);
  return max;
}

public int dfs(TreeNode root) {
  if (root == null) {
    return 0;
  }
  //计算左边分支最大值，左边分支如果为负数还不如不选择
  int leftMax = Math.max(0, dfs(root.left));
  //计算右边分支最大值，右边分支如果为负数还不如不选择
  int rightMax = Math.max(0, dfs(root.right));
  //left->root->right 作为路径与已经计算过历史最大值做比较
  max = Math.max(max, root.val + leftMax + rightMax);
  // 返回经过root的单边最大分支给当前root的父节点计算使用
  return root.val + Math.max(leftMax, rightMax);
}