具体问题

使用栈实现一个队列（手写代码），考虑线程安全的实现
思路：使用2个栈，一个用于存放数据，另外一个用于辅助在取数据或者删除时临时存放。线程安全通过加锁来实现。
代码：

import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;
public class StackQueue<T> {
  Stack<T> data = null;
  Stack<T> temp = null;
  ReentrantLock lock = new ReentrantLock();

  public StackQueue() {
      data = new Stack<T>();
      temp = new Stack<T>();
  }

  public T pop() {
      lock.lock();
      if (temp.isEmpty())
          swap(data, temp);
      if (temp.isEmpty()) {
          lock.unlock();
          return null;
      }
      T top = temp.pop();
      lock.unlock();
      return top;

  }

  public T peek() {
      lock.lock();
      if (temp.isEmpty())
          swap(data, temp);
      if (temp.isEmpty()) {
          lock.unlock();
          return null;
      }
      T top = temp.peek();
      lock.unlock();
      return top;
  }

  public void push(T element) {
      lock.lock();
      if (data.isEmpty())
          swap(temp, data);
      data.push(element);
      lock.unlock();
  }
  void swap(Stack<T> src, Stack<T> dest) {
      while (!src.empty()) {
          dest.push(src.pop());
      }
  }
  public boolean isEmpty(){
      return data.isEmpty() && temp.isEmpty();
  }
}

java线程模型
线程实现：
- 内核级线程：轻量级进程，会消耗一定的内核空间，由内核来完成线程切换
- 用户线程：完全建立在用户空间上的线程，更加轻量级，开销更低
- 用户线程和内核线程混合
线程调度：
- 抢占式：线程的执行时间由线程自己决定，在自己执行完后需要主动通知系统进行进程切换
- 协同式：线程的切换由系统控制，运行时间由系统分配
线程状态：
- 就绪态 Ready：等待分配运行时间
- 运行态 Running：正在运行
- 阻塞态 Blocking：等待IO等操作
- 等待态 Waiting、Timed Waiting：CPU调度、手动通过sleep()进入等待
- 终止态 Terminated：运行结束
线程通信方式
- 共享变量
- 关键字：volatile、synchronized
- 锁：ReentrantLock
- 管道通信：PipedInputStream和PipedOutputStream
- 等待与通知：object.wait()/object.notify()
- 条件变量：Condition
- 倒计时协调器：CountDownLatch
- 复用栅栏：CyclicBarrier
- 信号量：Semaphore
- 阻塞队列：ArrayBolckingQueue
- 交换：Exchanger

jvm中，eden、s1、s2的作用
在分代回收的机制中，eden、s1、s2都用于保存新生代的数据（存活时间较短且不会占用很多空间的小对象），其中所分配的空间比例一般为 $8:1:1$ 。其中，eden用于存储新创建的对象，s1用于保存上一轮回收后存活的对象，s2用于下一次GC时的辅助空间。

所采用的GC算法是复制算法，具体机制为：在发生垃圾回收时，eden和s1中存活的对象复制到s2中并对eden和s1进行清理，然后交换s2和s1的角色。

在这样的机制下，虚拟机的空间利用率能达到 $90\%$ ，只有 $10\%$ 用于下一轮GC的辅助空间会被“浪费”，且由于会在s1和s2交替的使用复制算法，所以不会存在较大的内存碎片，整体的空间利用率较高，。
只用eden和s能否解决问题
能解决问题，但是效率较低。

对比使用eden、s1、s2进行处理的方法，如果去掉其中一个Survivor空间，则每一次GC都只能从eden复制到s中。如果对s本身没有优化处理的话，在s中容易产生内存碎片，导致eden中稍大的存活对象都无法存放于s，最终导致提前触发下一轮GC甚至报错。虽然空间是 $100\%$ 的用到了，但是整体的效率和可靠性还是较低。
TCP的拥塞控制机制
慢开始、拥塞控制、快重传、快恢复

TCP连接为什么要使用三次握手
用于确认通信双发的接收和发送能力

连接建立阶段	内容	发送方	接收方
1	发送方发送`SYN`	发送方：接收方：	发送方：发送能力接收方：接受能力
2	接收方发送`ACK`和`SYN`	发送方：接受能力、发送能力接收方：接受能力、发送能力	发送方：发送能力接收方：接受能力
3	发送方发送`ACN`和`SYN`	发送方：接受能力、发送能力接收方：接受能力、发送能力	发送方：接受能力、发送能力接收方：接受能力、发送能力

解释一下servlet是什么
本质上就是一个实现了相关接口的类，运行在Tomcat容器中。

维基百科：Servlet（Server Applet），全称Java Servlet，未有中文译文。是用Java编写的服务器端程序。其主要功能在于交互式地浏览和修改数据，生成动态Web内容。狭义的Servlet是指Java语言实现的一个接口，广义的Servlet是指任何实现了这个Servlet接口的类，一般情况下，人们将Servlet理解为后者。
servlet单例吗？为什么
不一定。
默认的情况是单例，如果在web.xml中，给对一个Servlet类进行多个配置，则会有多个实例。但是大部分情况下，只会配置一个，所以是单例的。

对于映射到同一个Servlet类的多个请求，通过创建一个Servlet实例，多个线程执行这个Servlet的service方法的实现。所以在Servlet中，实例变量都不是线程安全的，只有局部变量（request、session等）才是线程安全的。
servlet在处理请求前，tomcat在底层做了些啥，或者说实现一个Tomcat的大致思路
Tomcat的结构主要分为Server、Service、Connector、Container四部分。
Server： Tomcat服务器本身
Service：服务，默认的是Catalina
Connector：用于处理网络连接，监听端口封装网络协议，屏蔽连接与处理的细节
Container：管理Servlet并处理请求，由Engine、Host、Context、Warrper四个部分（层级）组成。
参考：
- 聊聊Tomcat的架构设计
数据库索引
B+树索引和哈希索引
B＋树
非叶子节点中可以保存多个指针数据，每一个数据都是一个指向其子节点的指针。
叶子节点用于保存真正的数据，与非叶子节点相同，每个叶子节点也能保存多个数据，且相邻叶子节点之间存在指针连接。
聚簇索引与非聚簇索引
二者的数据结构都是B+树
聚簇索引：叶子节点保存实际的数据，所以索引的顺序决定了数据的顺序
非聚簇索引：叶子节点保存指向实际数据的指针，所以数据的顺序与索引无关
非聚簇索引怎么指向具体数据
首先需要明确的是，非聚簇索引（也叫 二级索引 ）中，叶子节点里面指向数据的“指针”，并不是真正意义上的指针，即 不是指向物理位置的指针。
在非聚簇索引中，数据和索引是分开存储的，索引的叶子节点保存的是索引列和数据列的主键值。在根据保存的主键，在聚簇索引中进行第二次查找。

参考自《高性能MySQL》第三版：
这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后更具这个值去聚簇索引中查找到对应的行。
什么时候需要建立索引
考虑如下因素：
- 查询频度：对于查询频度高或常用于连接查询的字段或组合字段，建立索引能提高查询的效率
- 删改频度：每一次删改都有可能需要对索引进行调整，频繁的删改会影响性能
- 重复程度：对于重复度较高的数据，其索引也具有较高的重叠性，对效率的提高不明显却要占用空间
- 数据类型：像blob、clob等用于保存较大对象的特殊类型，不适合建立索引；较大的文本字段，建立索引也会占用较大的空间且效率不高
- 表的规模：在表中数据较多时，使用索引一般能提高检索效率，表规模较小时，索引对效率的影响不大
- 存储介质：当数据保存在内存中时，索引对效率的提升不会很明显

如何不使用递归遍历一颗二叉树
中序遍历思路：对于每一个节点，优先遍历左孩子，一直到最左边的节点遍历完。处理右边的节点，栈中保存的是左子树正在被遍历的节点。当一个节点的子树遍历完后，从栈中取一个节点（该节点的父节点），遍历其右子树。
非递归中序遍历二叉树
中序遍历代码：

  public static void iterate(TreeNode root) {
      Stack<TreeNode> stack = new Stack<>();
      TreeNode node = root;
      while (true){
          // 不断往左下方遍历，中间的节点保存在栈中
          while (node.left != null) {
              stack.push(node);
              node = node.left;
          }
          // 处理最左边的节点
          process(node);

          // 从栈中取出父节点，并处理其右子树
          while (!stack.isEmpty() && node.right == null) {
              node = stack.pop();
              process(node);
          }
          if (node.right != null) {
              // 有右孩子，则处理右孩子
              node = node.right;
          } else {
              // 栈空，所有节点处理完毕
              break;
          }
      }
  }

  public static void process(TreeNode node) {
      System.out.print(node.val+ " ");
  }

美团：2019秋招 后台开发 现场面试

具体问题

美团：2019秋招后台开发现场面试