模拟面试一（Java）
模拟面试一
常见linux命令
ls 查看当前目录下文件和文件夹
cd 进入当前目录
mkdir 创建文件夹
touch 创建文件
su 进入root权限
rm 删除文件或文件夹
cp 复制文件
mv 移动文件
git使用
首先初始化仓库：
git init - 初始化仓库。
或者下载远程代码库
git pull 下载远程代码并合并
其次添加文件
git add . - 添加文件到暂存区。
git commit - 将暂存区内容添加到仓库中。
最后推向远程代码库
git push 上传远程代码并合并
重写重载区别
重写即子类重写父类的方法，方法对应的形参和返回值类型都不能变。
重载即在一个类中，方法名相同，参数类型或数量不同。
springboot和spring区别
spring框架是一个基于DI和AOP模型设计的一系列应用组件，并且基于该组件，设计了MVC框架，配置文件较为繁琐。
为了简化设计流程，springboot横空出世，利用springboot的默认方式，能很快开发出新的WEB应用。
redis整合到springboot
pom文件添加依赖项spring-boot-starter-data-redis
Springboot中application.properties添加redis服务器ip账户与密码端口号
利用Autowired注入redisTemplate
利用redisTemplate进行相关操作
springboot怎么解析一个url
springboot starter集成了springmvc，因此解析url方式与springmvc一致。
- 客户端发送url
- 核心控制器
Dispatcher Servlet接收该请求，通过映射器配置Handler mapping，将url映射的控制器controller返回给核心控制器。 - 通过核心控制器找到适配器，调用实现对应接口的处理器，并将结果返回给适配器，
- 适配器将获取的数据返回给
核心控制器 - 核心控制器将获取的数据传递给
视图解析器，并获取解析得到的结果 - 核心控制器将结果返回给客户端
tcp和udp区别
TCP作为面向流的协议，提供可靠的、面向连接的运输服务，并且提供点对点通信
UDP作为面向报文的协议，不提供可靠交付，并且不需要连接，不仅仅对点对点，也支持多播和广播
http和https区别
http所有传输的内容都是明文，并且客户端和服务器端都无法验证对方的身份。https具有安全性的ssl加密传输协议，加密采用对称加密， https协议需要到ca申请证书，一般免费证书很少，需要交费。
简述栈和队列
栈是一种线性表，其限制只能在表尾进行插入或删除操作。由于该特性又称为后进先出的线性表。队列是一种先进先出的线性表。其限制只能在线性表的一端进行插入，而在另一端删除元素。
hashmap数据结构 链表转红黑树
JDK8 之前底层实现是数组 + 链表，JDK8 改为数组 + 链表/红黑树。主要成员变量包括存储数据的 table 数组、元素数量 size、加载因子 loadFactor。HashMap 中数据以键值对的形式存在，键对应的 hash 值用来计算数组下标，如果两个元素 key 的 hash 值一样，就会发生哈希冲突，被放到同一个链表上。
table 数组记录 HashMap 的数据，每个下标对应一条链表，所有哈希冲突的数据都会被存放到同一条链表，Node/Entry 节点包含四个成员变量：key、value、next 指针和 hash 值。在JDK8后链表超过8会转化为红黑树。
mysql的操作 增删改查
增：INSERT INTO 表名（字段名1，字段名2，…）VALUES（值1，值2，…）
删：DELETE FROM 表名 [WHERE 条件表达式] TRUNCTE [TABLE ] 表名（删除整张表数据）
改：UPDATE 表名 SET 字段名1=值1，[ ，字段名2=值2，…] [ WHERE 条件表达式 ]
查：SELECT 字段名1，字段名2，… FROM 表名 [ WHERE 条件表达式 ]
mysql的查询语法顺序
where、group by、having、order by、limit
mysql索引数据结构 为什么快
mysql通常采用B+树作为索引结构实现
B+树也是是一种自平衡的多叉树。其基本定义与B树相同，不同点在于数据只出现在叶子节点，所有叶子节点增加了一个链指针，方便进行范围查询。
B+树中间节点不存放数据，所以同样大小的磁盘页上可以容纳更多节点元素，访问叶子节点上关联的数据也具有更好的缓存命中率。并且数据顺序排列并且相连，所以便于区间查找和搜索。
delete和truncate区别
delete是数据操纵语言（DML），其按行删除，支持where语句，执行操作采用行锁，执行操作时会将该操作记录在redo和undo中，因此支持回滚。
truncate是数据定义语言（DDL），其操作隐式提交，不支持回滚，不支持where，删除时采用表级锁进行删除
请描述避免多线程竞争时有哪些手段？
- 不可变对象；
- 互斥锁；
- ThreadLocal 对象；
- CAS；
六度人脉理论
1929年，匈牙利作家Frigyes Karinthy在短篇故事‘Chains’中首次提出的“六度人脉理论”，是指地球上所有的人都可以通过六层以内的熟人链和任何其他人联系起来。我们定义A的‘一度好友’为A直接相识的好友，A的‘二度好友’为A一度好友的好友且与A不是一度好友，A的‘三度好友’为A二度好友的好友且与A不是一度好友、二度好友，以此类推。
在美团点评，小美、小团、小卓、小越、小诚、小信的好友关系见下图。
以‘小点’为起始点，广度优先遍历，生成遍历树（无权图可以生成最小生成树），输出层数为6的结点。 数据结构使用邻接表，边表节点由 一度好友 组成。 java 中，邻接表可以用 linkedlist（边表） 加 hashmap、ArrayList （顶点表）实现。
用邻接表及广度优先算法
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Graph {
//边
public class EdgeNode{
int index; //存储该顶点对应的下标
int weight; //存储权重
}
ArrayList<String> pointList; //顶点数组
LinkedList<EdgeNode> edjList[]; //邻接表
int pointNum; //顶点数
int edgeNum; //边数
public Graph(int n){
pointList = new ArrayList<>(n);
edjList = new LinkedList[n];
for (int i = 0; i < n; i++) {
edjList[i] = new LinkedList<>();
}
pointNum = n;
}
//添加一条顶点
public void addPoint(String name){
if(pointList.size() >= pointNum){
System.out.println("point array full");
return ;
}
if(pointList.indexOf(name) != -1){
System.out.println("已经存在"+name);
return ;
}
pointList.add(name);
}
public String getName(int index){
return pointList.get(index);
}
//添加一条边
public void addEdge(String name1, String name2, int weight){
int i = pointList.indexOf(name1);
if(i == -1){
System.out.println("not find nam1="+name1);
return ;
}
int j = pointList.indexOf(name2);
if(j == -1){
System.out.println("not find name2="+name2);
return ;
}
EdgeNode edge = new EdgeNode();
edge.index = j;
edge.weight = weight;
edjList[i].add(edge);
edgeNum++;
//加入另一个边 （无向边 两边都加）
edge = new EdgeNode();
edge.index = i;
edge.weight = weight;
edjList[j].add(edge);
edgeNum++;
}
public void printAll(){
for (String s : pointList) {
}
for (int i=0;i<pointList.size();i++) {
System.out.print("节点"+pointList.get(i) +"边为:");
for (EdgeNode edgeNode : edjList[i]) {
System.out.print(pointList.get(edgeNode.index)+" ");
}
System.out.println("");
}
}
/**
* 广度遍历
* @param name
*/
public void BSTTraverse(String name){
LinkedList<Integer> queue = new LinkedList();
//找到name
int i = pointList.indexOf(name);
if(i == -1){
System.out.println("not find name="+name);
return ;
}
int[] a = new int[pointNum];
for (int j = 0; j < pointNum; j++) {
a[j] = 0;
}
a[i] = 1;
LinkedList<EdgeNode> list = edjList[i];
for (EdgeNode edgeNode : list) {
queue.addLast(edgeNode.index);
a[edgeNode.index] = 1;
}
while(queue.size() != 0){
//从queue中拿出一个节点
i = queue.removeFirst();
System.out.println("遍历 " + pointList.get(i));
list = edjList[i];
for (EdgeNode edgeNode : list) {
if(a[edgeNode.index] != 1){
queue.addLast(edgeNode.index);
a[edgeNode.index] = 1;
}
}
}
}
public class Node{
int index;
int deep;
}
/**
* 根据深度获取好友队列
* @param name
* @param deep 获取1度好友 则深度为2
* @return
* 采用广度优先算法
*/
public LinkedList<Node> getQueueByDeep(String name, int deep){
LinkedList<Node> queue = new LinkedList();
//找到name
int i = pointList.indexOf(name);
if(i == -1){
System.out.println("not find name="+name);
return null;
}
int[] a = new int[pointNum];
for (int j = 0; j < pointNum; j++) {
a[j] = 0;
}
Node node = new Node();
node.index = i;
node.deep = 1;
queue.addLast(node);
a[i] = 1;
while(queue.size() != 0){
//从queue中拿出一个节点
node = queue.getFirst();
if(node.deep == deep){
return queue;
}
queue.removeFirst();
//System.out.println("遍历 " + pointList.get(node.index).data);
List<EdgeNode> list = edjList[node.index];
for (EdgeNode edgeNode : list) {
if(a[edgeNode.index] != 1){
Node temp = new Node();
temp.index = edgeNode.index;
temp.deep = node.deep+1;
queue.addLast(temp);
a[edgeNode.index] = 1;
System.out.println("deep="+temp.deep + pointList.get(edgeNode.index));
}
}
}
return null;
}
public static void main(String[] args) throws Exception{
Graph g = new Graph(7);
g.addPoint("小团");
g.addPoint("小美");
g.addPoint("小诚");
g.addPoint("小信");
g.addPoint("小卓");
g.addPoint("小越");
g.addPoint("小孩");
g.addEdge("小团", "小美", 1);
g.addEdge("小卓", "小美", 1);
g.addEdge("小诚", "小美", 1);
g.addEdge("小团", "小卓", 1);
g.addEdge("小诚", "小信", 1);
g.addEdge("小信", "小越", 1);
g.addEdge("小卓", "小越", 1);
g.addEdge("小信", "小孩", 1);
g.printAll();
g.BSTTraverse("小美");
int deep = 4;
LinkedList<Node> queue = g.getQueueByDeep("小美", 4);
if(queue == null){
System.out.println("没有"+(deep-1)+"度好友");
}else{
for (Node node : queue) {
System.out.println(node.deep+"度好友为 "+ g.getName(node.index));
}
}
}
}
请简述HTTP的5个常用Method及其含义，以及5个常用Status Code及其含义？HTTP与HTTPS的区别是什么，简述一下HTTPS的实现原理。
get 从服务器端获取资源 put 提交资源 post 更新资源 delete 删除资源 connect 建立tunnel隧道 100 请求已收到，正等待后续资源 200 ok 成功 206 partial content 部分资源 301 永久重定向 400 bad request 客户端请求语法错误 500 Not Implement 服务器内部错误 502 Bad Getaway 网关错误
HTTP与HTTPS区别： HTTPS是HTTP经由加入SSL层来提高数据传输的安全性。其中SSL依靠证书来验证服务器的身份，并对浏览器与服务器之间的 通信进行数据加密。HTTP不适合传输敏感信息。
HTTPs实现原理： 发起请求：客户端通过TCP和服务器建立连接后，发出一个请求证书的消息给到服务器。 证书返回：服务器端在收到请求后回应客户端并且返回证书。
给出一个布尔表达式的字符串，比如：true or false and false，表达式只包含true，false，and和or，现在要对这个表达式进行布尔求值，计算结果为真时输出true、为假时输出false，不合法的表达时输出error（比如：true true）。表达式求值是注意and 的优先级比 or 要高，比如：true or false and false，等价于 true or (false and false)，计算结果是 true。
将字符串分割后分别压栈，若遇到顶层为and时候进行弹出对比，最后保证栈中只有true、false、or字符串，再对栈中符号进行判断
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String[] ss=scanner.nextLine().split(" ");
Stack<String> stack=new Stack<>();
for(int i=0;i<ss.length;i++){
String curr=ss[i];
//当前值为true或false时
if(curr.equals("true")||curr.equals("false")){
if(stack.isEmpty()){
stack.push(curr);
}else{
String top=stack.peek();
if(top.equals("true")||top.equals("false")){
System.out.println("error");
return;
}else{
if(top.equals("or")) stack.push(curr);
else{
stack.pop();
String pre=stack.pop();
if(curr.equals("false")||pre.equals("false")) stack.push("false");
else stack.push("true");
}
}
}
}
//当前值为and或or时
else{
if(stack.isEmpty()){
System.out.println("error");
return;
}else{
String top=stack.peek();
if(top.equals("and")||top.equals("or")){
System.out.println("error");
return;
}
stack.push(curr);
}
}
}
if(!stack.isEmpty()&&(stack.peek().equals("or")||stack.peek().equals("and"))){
System.out.println("error");
return;
}
while(!stack.isEmpty()){
String curr=stack.pop();
if(curr.equals("true")){
System.out.println("true");
break;
}
if(stack.isEmpty()) System.out.println("false");
}
}
给出两个字符串，分别是模式串P和目标串T，判断模式串和目标串是否匹配，匹配输出 1，不匹配输出 0。模式串中‘？’可以匹配目标串中的任何字符，模式串中的 ’*’可以匹配目标串中的任何长度的串，模式串的其它字符必须和目标串的字符匹配。例如P=a?b，T=acb，则P 和 T 匹配。
力扣44原题
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String p = sc.next();
String s = sc.next();
// System.out.println(s + " - " + p);
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for(int i = 1; i <= n; i++) dp[0][i] = dp[0][i - 1] && p.charAt(i - 1) == '*';
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?'){
dp[i][j] = dp[i - 1][j - 1];
}
if(p.charAt(j - 1) == '*'){
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
System.out.println((dp[m][n] ? 1 : 0));
}
}