网易一面笔试题
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);
}
}
}
运行结果：
