参考面经 | 雷凯博的博客

各公司面试题整理

一、前两道要求写出代码

后两道说思路即可

第一题是自己设计一个双向链表，并实现插入删除一开始忘了处理头尾节点的情况，面试官让再检查，然后补上了

第二题是字符串替换，在字符串s中找到字符串p，并替换成e 这个题问了面试官说可以用暴力，就直接暴力解了，但是忘了string的insert和erase怎么用了，太菜了…

第三题如何找链表的第k个节点，思路：倒数第k个就是正数第l-k+1个，即l-(k-1),也就是说让一个游标先走k-1步，到达第k个节点，再有另一个游标从头开始，这样当第一个游标到达最后一个节点的时候，第二个游标正好在第l-(k-1)个节点，即倒数第k个节点上

第四题场景：服务器可能被IP重放攻击，要找出访问量最大的k个IP并处理，抽象成topK问题，先哈希去重，再创建小顶堆维护k个节点即可，后面又问了需要多少内存，堆需要维护的内存直接忽略不计了，因为主要的内存消耗在创建哈希表上，当时脑子有点乱，太迷了…第一次说了个8G，后来一想肯定不对，重新算了下，应该是2^32 *8B左右

二、

二维矩阵中寻找元素，二维数组满足从左到右从上到下非递减，从右上角或者左下角扫描，每次砍掉一行或者一列，时间复杂度max（m,n）

数据库的一些知识，mysql和redis，可以看我其他的面经，就不多提了

http 0.9 1.0 1.1 2.0 https tcp/udp等等

三、

https://blog.nowcoder.net/n/e5fe3fa16b774b469241029a6de4e65a#一java

这个链接比较详细

但是觉得这些参考价值一般，一和二都是直接内推的面试，注重了编程。

325搜狗

1项目经验

2poi限制输入

3final

4hashmap currenthashmap

5spring特征spring事务

6mysql死锁

7jvm G1 CMS

8卷积神经网络

9linux操作

325美团

1项目

2 mybitits hibenite 区别，哪个效率更高

3数据链路层和网络层设备和协议

4数据库左右连接，内连接自然连接，

5数据库二级索引数据结构数据怎么保存

6虚拟地址为什么是2的64次方

7http的状态码

1gc

2三次握手为什么三次握手

3http长连接短连接

4io多路复用

5数据库索引结构为什么用b+树

6tcp怎么保证可靠的

7将字符串空格变为%23，从后往前解决

字节414

1==和equals

2重写equals和hashcode

3hashmap

4static和volatile

5第K大的数

6TCP可靠

7网络拥塞避免

8time-wait状态

阿里414

项目，excel面向任务流

最小生成树和图

Int long大小

贪心算法

红黑树

携程

1int大小integer

2gc

3jdk jre

4String stringbuilder 字符串常量池

5sychronized和volitile

6ssh

京东

1多线程锁区别

2设计模式，单例（保证方法无状态无状态）

3数据库优化，数据库索引哪种情况需要建立索引失效 mysql日志执行过程

4redis 要注意key不能过大

5线程池参数

6oom 栈溢出，堆溢出，常量池溢出

阿里文娱实习一面 3.12 50nin

自我介绍
spring 是否看过源码

Bean生命周期
项目中一个难点
jdk看过源码树在Java的应用红黑树 b树b+树区别使用场景

协程与线程的关系
设计一个上亿用户的登录模块
设计一个单点登录
排查后端性能思路
小组协同开发，编码规则
pb级集群日志里找重复行

编程邮件

蘑菇街金融风控部门实习一面 3.13 40min

项目经历

订单管理，订单快照实现

为什么使用ES

Activity 工作流模板、嵌入、离开

工作分配换人怎么实现

面向对象

注解怎么自己实现？都有哪些注解

Threadlocal

Start方法与run方法，start方法底层实现

Java线程状态 new、running、waitting、time-waitting、阻塞、终结

反射的一些方法

Spring

两种反射区别接口 cglib

Mybatis # $区别

SQL注入有哪些？可以怎么防范？从哪一层可以进行实现

Limit 参数使用

索引什么时候失效

左连接右连接

腾讯电脑管家深圳简历面 3.16 20min

项目中ES、MySQL、redis的使用关系

保证redis一致性

为什么使用srio，与spring security的区别

处理大量读写请求

处理大量写请求

TF-IDF算法

阿里企业智能事业部 3.16 20min

项目的一个技术难点

cookie session

http tcp

Tcp拥塞

浏览器发送cookie流程

如何保证cookie安全

面向对象、解释其三个特点

数据结构快排、插入、堆排序

核心平台

人人车核心平台 3.24 35min

类加载机制

JVM数据区域

各个回收器

确定回收对象

MySQL存储引擎

Innodb mylsam分别哪种场景使用

建索引需要注意

索引失效的情况，explan

Java封装继承多态

怎么实现多继承

Java各种基本类型

自动拆箱、装箱

String为什么不可变类，为何这样设计

Java里的数据结构

怎么理解线程安全

实现线程几种方式

Runable 与 callable区别

Spring IOC与Spring AOP

动态代理

Spring bean 单例、多例

作业帮一面 3.25 50min

数组Top k

快排

订单模块流程

购物车怎么实现

Redis 秒杀 watch 事务

知识图谱

短文本相似度计算

作业帮二面 3.27 50min

订单流程

减库存与生成订单顺序

elasticSearch

MySQL与ES的同步

ES快20%是怎么得到的

TF-IDF详细步骤

192.168.255.255\28 有多少个IP

自己显示器坏了，怎么得到IP

1 2 3 4 5 1 2 3的页面序号访问，内存中有4页大小的空间，LRU替换策略，最后内存里面保留的是哪几页内容

消费端1s消费一个指令，但60s最多消化10个，怎么实现？

编程：A-Z AA-ZZ 一个整数对应列号

还了解哪些相似度计算算法

腾讯后台小程序 3.30 100min

商品库存存在哪

redis存哪些数据、如何解决库存问题

请求读多写少，如何设计？（分布式锁、手动过期、本地缓存）

在后台使用一个异步线程的时候，如何确保不同的服务只建立、运行一个线程，而不是多个线程呢？

Redis 本地缓存 MySQL的关系

不硬件扩容的基础上，如何提高redis性能

Redis RDB，AOF以及项目中怎么用

Redis集群的配置情况

Redis 分片节点如何操作

Reids 主从同步、新master选取

ES的使用情况（项目中如何使用、使用版本、单机or集群）

ES全文检索的底层原理

一个商品的不同信息是存在一个document中吗？（回答是，说我用的不是全文检索）

MySQL索引方式（b树与hash索引）

B树的应用，Innodb Mysriam存储引擎里索引的具体情况

Tcp接收端一直不处理收到的字节，会发生什么情况？（回答缓存、窗口，又问这些时间长会过期吗？）

服务端发送数据发给客户端后，数据经过了几次复制（用户态到内核态）

Tcp协议之上的有哪些协议

HTTP与HTTPS区别与两者端口

HTTPS过程

中间人攻击是什么？https如何解决中间人攻击？

原来使用http协议，后来升级为https，如何确保使用http时仍能访问到站点（307）

10个线程，每个加100，结果与1000的关系，如何解决？如何不适用代码块加锁（synchronized）的方式解决?

进程与线程有什么区别？

如何控制一个进程独占一个文件？

协程

编程：

1、有序链表去重

\2. 给定一个数组，有正数，负数，求和最大的连续子序列（动态规划，三种情况）

腾讯后台小程序二面 3.31 80min

Java运行时数据区域

方法区放的有什么数据

类加载机制

加载、双亲委派

静态变量什么时候初始化

解析过程

Java里的锁，synchronized的锁实现

Synchronized锁升级

Mysql索引的方式，除了hash B树还能有什么

介绍不同的存储引擎

B+树为什么比B树快

树索引的缺点

Redo undo

接收窗口（和一面类似）

Tcp拥塞控制

四次挥手二三次之间、2msl 最大报文时间

Socket编程？

虚拟内存、段、页

Spring IOC，AOP的实现方式

Spring用到的设计模式

Redis主从同步

编程：删除倒数第n个节点

系统设计：实时输出最近一个小时内访问频率最高的10个IP，要求：

1、实时输出

2、从当前时间向前数的1个小时

3、QPS可能会达到10W/s

广联达大数据部门一面 30min

项目中是怎么做的Mysql优化

Explain filesort？

解释Spring IOC 与 AOP

Spring 有哪些注入方式

Spring mvc 怎么做事务？

MySQL事务特点、隔离级别

MySQL锁，ABA问题

MySQL索引具体细节

http 常用方法

https

重载与重写

String 为什么是不可变？优点是什么？

Stringbuilder 与 stringbuffer区别

Hashcode

腾讯后台 3面 4.1 50min

项目中怎么用到的事务

Redis怎么存数据

Es在项目中怎么用？与MySQL的区别在哪里？

上次未回答出来的统计IP

100亿个数，找出中位数，4G内存

\3**输入两棵二叉树A，B，判断B是不是A的子结构。



递归调用，
public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return judgeSubTree(root1, root2) ||
               judgeSubTree(root1.left, root2) ||
               judgeSubTree(root1.right, root2);
    }
 
    private boolean judgeSubTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return judgeSubTree(root1.left, root2) ||
                   judgeSubTree(root1.right, root2);
        }
        return judgeSubTree(root1.left, root2.left) &&
               judgeSubTree(root1.right, root2.right);
    }
}

操作给定的二叉树，将其变换为源二叉树的镜像。


递归方案：交换左右子树的节点，然后递归调用该方法。
非递归：压入栈进行操作
6输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
新建一个栈，将数组A压入栈中，当栈顶元素等于数组B时，就将其出栈，当循环结束时，判断栈是否为空，若为空则返回true.

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径


路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
递归做法
public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null)return result;
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null)
            result.add(new ArrayList<Integer>(list));
//因为在每一次的递归中，我们使用的是相同的result引用，所以其实左右子树递归得到的结果我们不需要关心，
        ArrayList<ArrayList<Integer>> result1 = FindPath(root.left, target);
        ArrayList<ArrayList<Integer>> result2 = FindPath(root.right, target);
        list.remove(list.size()-1);
        return result;
    }
}

\17二叉树深度**

public int TreeDepth(TreeNode root) {//递归
    if(root==null){
        return 0;
    }
    int left=TreeDepth(root.left);
    int right=TreeDepth(root.right);
    return Math.max(left,right)+1;
}
非递归

\36 赛车问题**



你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）
你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶 。
当车得到指令 "A" 时, 将会做出以下操作： position += speed, speed *= 2。
当车得到指令 "R" 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1 ；否则将车速调整为 speed = 1。  (当前所处位置不变。)
例如，当得到一系列指令 "AAR" 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。
现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。
使用一个一维数组dp，dp[i]代表走到位置i处所需要的最小步数。因为先向前走forword步再向后走back步与先向后走back步再向前走forword步最后到达的位置相同，所以可以假设永远保持第一步是向前走的。第一步有三种情况：
第一种是刚好走forword步后到达了目标位置i，则dp[i] = forword。
第二种情况是向前走forword步后到达了位置i后面，这时需要再往回走，再加上回头的那一步，此时dp[i] = Math.min(dp[i], forword + 1 + dp[j - i]);（注意这里的上限是走到2 * i处）
第三种情况是向前走forword步后未到达位置i处就需要返回，此时在保证返回的步数back < forword的条件下遍历back，此时dp[i] = Math.min(dp[i], forword + 1 + back + 1 + dp[i - j + k])。
得到转移方程后递归i，最后dp[target]即为所求值。
class Solution {
    public int racecar(int target) {
        int[] dp = new int[target + 1];
        for (int i = 1;i <= target; i++){
            dp[i] = Integer.MAX_VALUE;
            for (int forword = 1;(1 << forword) - 1 < 2 * i; forword++) {
                int j = (1 << forword) - 1;
                if(j == i) 
                    dp[i] = forword;
                else if (j > i)
                    dp[i] = Math.min(dp[i], forword + 1 + dp[j - i]);
                else
                    for(int back = 0; back < forword; back++) {
                        int k = (1 << back) - 1;
                        dp[i] =Math.min(dp[i], forword + 1 + back + 1 + dp[i - j + k]);
                    }
            }
        }
        return dp[target];
    }
}

\42回溯法寻找二维数组中字符串**

用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        //标志位，初始化为false
        boolean[] flag = new boolean[matrix.length];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                 //循环遍历二维数组，找到起点等于str第一个元素的值，再递归判断四周是否有符合条件的----回溯法
                 if(judge(matrix,i,j,rows,cols,flag,str,0)){
                     return true;
                 }
            }
        }
        return false;
    }   
    //judge(初始矩阵，索引行坐标i，索引纵坐标j，矩阵行数，矩阵列数，待判断的字符串，字符串索引初始为0即先判断字符串的第一位)
    private boolean judge(char[] matrix,int i,int j,int rows,int cols,boolean[] flag,char[] str,int k){
        //先根据i和j计算匹配的第一个元素转为一维数组的位置
        int index = i*cols+j;
        //递归终止条件
        if(i<0 || j<0 || i>=rows || j>=cols || matrix[index] != str[k] || flag[index] == true)
            return false;
        //若k已经到达str末尾了，说明之前的都已经匹配成功了，直接返回true即可
        if(k == str.length-1)
            return true;
        //要走的第一个位置置为true，表示已经走过了
        flag[index] = true;
         
        //回溯，递归寻找，每次找到了就给k加一，找不到，还原
        if(judge(matrix,i-1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i+1,j,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j-1,rows,cols,flag,str,k+1) ||
           judge(matrix,i,j+1,rows,cols,flag,str,k+1)  )
        {
            return true;
        }
        //走到这，说明这一条路不通，还原，再试其他的路径
        flag[index] = false;
        return false;
    }
}

\48会场分配问题**

贪心算法，第一问题求出一个会场最大容纳数，每次贪心，选择可以进行的最早结束的会议当做下一次的选择

第二问题，最少需要多少会场，将开始时间和结束时间分别排序然后每次开始时间小于结束时间会场加一

int j=0;
       int count = 0;
       for (int i=0;i<n;i++){
           if (a[i]<b[j]){
               count++;
           }else{
               j++;
           }
       }

\49区间合并问题**

对1，3 2，5 6，7 三个区间进行合并

Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

首先使用指定排序，根据数组的第一个数据进行排序

使用list对已经合并好的区间进行存储

将list转换为数组res.toArray(new int[0][]);


class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if (intervals == null || intervals.length == 0) return res.toArray(new int[0][]);
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int i = 0;
        while (i < intervals.length) {
            int left = intervals[i][0];
            int right = intervals[i][1];
            while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
                i++;
                right = Math.max(right, intervals[i][1]);
            }
            res.add(new int[]{left, right});
            i++;
        }
        return res.toArray(new int[0][]);
    }
}

### 63求数组所有子集

采用经典回溯法，核心如下，加入新数字，递归，去掉加入的数字，回溯



private void process(List<Integer>list, int[] nums, int start){
        lists.add(new ArrayList(list));
        for(int i = start; i < nums.length; i++){
            list.add(nums[i]);
            process(list, nums, i+1);
            list.remove(list.size()-1);
        }
}

\64组合总和**

题目数组{2,3,5,7} 求和为7的组合，每个数字可以重复

和上面一样的思路，回溯法，每次加入新数字，递归，最后去除新数字



private void process(int[] candidates, int target, List<Integer> list) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(list));
        } else {
            for (int i = 0; i < candidates.length; i++) {
                list.add(candidates[i]);
                //因为每个数字都可以使用无数次，所以递归还可以从当前元素开始
                process( candidates, target - candidates[i], list);
                list.remove(list.size() - 1);
            }
        }

}

\67旋转数组**

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

输入: [1,2,3,4,5,6,7] 和 k = 3

输出: [5,6,7,1,2,3,4]

三次翻转数组解决，第一次7654321，第二次5674321，第三次，5671234

swap(nums,0,nums.length-1);

swap(nums,0,k-1);

swap(nums,k,nums.length-1);

\68回文链表**


public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }

\80乘积最大连续子数组**

动态规划，记录当前最大值和最小值，因为最小值负数乘以负数会成为最大值

public int maxProduct(int[] nums) {
        int result=nums[0];
        int min=nums[0];
        int max=nums[0];
        for(int i=1;i<nums.length;i++){
            int temp=max;
            max=Math.max(Math.max(max*nums[i],nums[i]),min*nums[i]);
            min=Math.min(Math.min(temp*nums[i],nums[i]),min*nums[i]);
            result=Math.max(max,result);
        }
        return result;
}

\81除自身外数组乘积**

结果等于该数前面数字的乘积乘以后面数据的乘积，先循环计算该位置前面数的乘积，再循环计算前面数乘积乘以后面数乘积


class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res=new int[nums.length];
        int k=1;
        for(int i=0;i<nums.length;i++){
            res[i]=k;
            k=k*nums[i];
        }
         k=1;
        for(int i=nums.length-1;i>=0;i--){
            res[i]=res[i]*k;
            k=k*nums[i];
        }
        return res;
    }
}