网易一面笔试题

1、项目介绍

2、bean声明周期（自己从bean注册、注入和bean范围三方面进行了介绍，创建过程自己不是特别熟悉，也没有硬背诵）

3、mysql中常用数据存储引擎中索引差异

4、多线程实现方式（创建单个线程和使用线程池创建线程）

5、如可控制mq消费速度和mq如何保证可靠性消费（自己理解消费速度根据自己预估峰值消息量，消息太多，为了防止单个队列消息溢出，使用针对一个topic设置多个队列，针对消息可靠性或者至少被消费一次，分别从消息失败重试、手动Ack和死信队列进行回答）

6、jvm 内存模式

算法题：

力扣原题：链接Offer 68 - II. 二叉树的最近公共祖先

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

相比于力扣解法，考虑在面试过程中可能需要自己创建二叉树，下面给出了自己的创建二叉树和求两个节点的公共祖先解法，了解基于java完成的树的创建，方便灵活面试官的各种要求。

注意点1：为了方便使用数组创建非完全二叉树，使用null表示节点为空，二叉树中节点值使用Integer类型，而不是使用int类型。

注意点2：由于java中参数是指传递，所有在使用先序递归方式创建树时，采用创建函数带返回值的方式。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Tree {
    private static TreeNode root;
    public Tree(TreeNode root){
        this.root = root;
    }
    public static void main(String[] args) {
        Integer[] data = {3,5,1,6,2,0,8, null,null,7,4};
        Tree tree = new Tree(new Tree.TreeNode());
        int index = 0;
        int len = data.length;
        tree.initTree(data,index);
       // tree.traverse();
        //计算树种两个节点的最小公共祖先
        int node1 = 7;
        int node2 = 4;
        int res = tree.lowestCommonAncestor(node1,node2);
        System.out.println(res);
    }

    public int lowestCommonAncestor(int  node1,int node2) {
        //求节点node1 和node2 的最近公共祖先
        List<List<Integer>> pathes = new ArrayList<>();
        findPath(root,node1,node2,new ArrayList(),pathes);
        List<Integer> path1 = pathes.get(0);
        List<Integer> path2 = pathes.get(1);
        int i = 0;
        for(;i < path1.size()&& i < path2.size();i++){
            if(!path1.get(i).equals(path2.get(i))){
                break;
            }
        }
        return path1.get(i-1);
    }
    private void findPath(TreeNode node,int node1,int node2,List curr,List<List<Integer>> pathes){
        if(node!=null){
            if(node.val == node1 || node.val == node2){
                curr.add(node.val);
                List temp = new ArrayList(curr);
                pathes.add(temp);
            }
            curr.add(node.val);
            findPath(node.left,node1,node2,curr,pathes);
            curr.remove(curr.size()-1);
            findPath(node.right,node1,node2,curr,pathes);
        }
    }

    /**
     * the definition of Tree Node
     */
    static class TreeNode{

        private Integer val;
        private TreeNode left;
        private TreeNode right;
        public TreeNode(){
        }
        public TreeNode(int val){
            this.val = val;
        }
        public TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public void initTree(Integer[] data, int index){
        root = createTree(data,0, data.length);

    }
    private TreeNode createTree(Integer[] data,int index,int len){
        //先序遍历创建树
        if(index < len && data[index]!=null){
            TreeNode node = new TreeNode(data[index]);
            node.left = createTree(data,index*2+1,len);
            node.right = createTree(data,index*2+2,len);
            return node;
        }else{
            return null;
        }
    }
    public void traverse(){
        preOrder(root);
        System.out.println();
    }
    private  void preOrder(TreeNode root){
        //先序遍历
        if(root!=null){
            System.out.print(root.val+"\t");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
}

运行结果：