JAVA后端面经总结——算法与数据结构
文章目录
一、算法与数据结构
- 栈和队列解决什么问题？
- 八大排序各自的复杂度，稳定性等
v
- 拓扑排序，无向图找闭环BFS
- 邻接矩阵：List<List< String >>
- 入度表：int[i - ‘A’]
- Queue进行BFS
尝试先转字母为数字：HashMap<String, Integer>
- topK问题？
分治/hash + 排序
- 大数加法，36 进制，‘0’ - ‘9’ 为阿拉伯数字 0 - 9，‘a’ - ‘z’ 为阿拉伯数字 10 - 35。
- 让hashmap线程安全有几种方式，你更推荐用哪种方式，为什么更好？
- 替换成Hashtable，Hashtable通过对整个表上锁实现线程安全，因此效率比较低
- 使用Collections类的synchronizedMap方法包装一下。方法如下：public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) 返回由指定映射支持的同步（线程安全的）映射
- 使用ConcurrentHashMap，它使用分段锁来保证线程安全
- 阻塞队列的底层源码
消费者-生产者模式：ReentrantLock
- 如何实现两个大数相加
- String
- ?? BigDecimal
- 找到数组中, 比左边所有数字都小, 比右边所有数字都大的 数字
- 解法
- 接雨水
- 单调栈
v
–
- 红黑树的左右旋
- 面试算法题
- 二叉树深度（递归+非递归两种方法）
- 买卖股票的最佳时机
- 环形链表
- 手写快排
- 二叉树的右视图
- 字符串转整数
- 旋转矩阵
- 翻转二叉树
- 编辑距离
- 最长不含重复字符的子字符串
- rand5 实现
- 合并K个升序链表
- 滑雪场（dfs）
- 面试算法题2
- 有序数组用最快的方法找到重复数>1000的数字序列：（二分法）
- 字符串通配符匹配的填空题。
- 逆序对
- 翻转链表
- 一道偏物理的题目。大概题意是一段路程分成平路和电梯两段，你可以跑 t 秒。问你在电梯上跑划算还是平路上跑划算
- 设计一个概率分布为 0.1，0.2，0.3，0.4 的算法。然后面试官问改成每次可以有放回地选两个数呢？在原代码上稍加修改就行了。
- 类似荷兰国旗问题
- 打印1-100 的质数
- 生成集合List<>；
- Random r = new Random();
- double d = r.nextDouble() * maxElement; //生成0 -（1 * maxElement）间的随机数，看落在哪个区间
- 面试算法题3
- implement a data structure to support two functions add()/search() efficiently
直接使用 Trie 树，search() 函数给了个 case 是有通配符‘*’的，所以 search 函数编写的时候写个 dfs 就 ok 了- Given a string, find out the length of the longest substring which contains at most two distinct characters
滑动窗口 + HashMap 直接秒，然后面试官问不用 HashMap 怎么做？(数组代替)- 一个链表，先打印顺序奇数位，再逆序打印偶数位
先顺序打印奇数位。用递归栈存储每个偶数位，递归回来后再打印该位置即可。
二、字节面试算法题
2.1 LC系列
- 寻找海量数据的前100大的数，分不限内存和限制内存，哪种排序算法最快
- 给出一个整形数组，找出其中最长的山峰的长度，如[2, 1, 3, 7, 6, 4, 5]，最长是[1, 3, 7, 6, 4]，所以返回5
- 蛇形输出二叉树
- 找到n个数的全排列的第m个数————LC.60
- 找排序数组中第一个出现的目标数字
- 二叉树的公共祖先
2.2 散系1
1.双指针遍历：解决有序数组的问题
- 排序数组，平方后，数组当中有多少不同的数字（相同算一个）。
- 如果不是排序数组，可以使用hashset来保存数字的平方，重复就存不进去，那么最后就可以直接返回set的大小size即可。时间空间复杂度都是O(n)。
- 头尾双指针遍历：这里是排序数组，既然有重复，肯定是有负数，0、1这些数字。 平方后两头大，中间小，可以用首尾指针共同向中间扫描 ，扫描时去掉重复元素，同时用一个sum来记录有多少个不同数字。
- 先递减再递增。
- 时间复杂度O(N)，空间复杂度O(1)。
- 一个数据先递增再递减，找出数组不重复的个数，比如 [1, 3, 9, 1]，结果为3，不能使用额外空间，复杂度o(n)
- 与上面一题一模一样，双指针从两头向中间逼近。
- 三种情况：当左右指针的数对应相等；左 < 右；左 > 右。每种情况都需要while去重。
- 给出一个数组nums，一个值k，找出数组中的两个下标 i，j 使得 nums[i] + nums[j] = k
- LC.2
- 排序 + 双指针：O(nlogn)
- HashMap：不能有重复元素；数字作为键，下标作为值
2.滑动窗口：解决连续序列问题
- （剑指offer57-II)
- 某一个大文件被拆成了N个小文件，每个小文件编号从0至N-1，相应大小分别记为S(i)。给定磁盘空间为C，试实现一个函数从N个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。
每次记录窗口内的总和，和小于C，记录剩余空间，再窗口右端右移，和大于C，就窗口左端右移，小于C情况下比较剩余空间取最小值。
- 给定m个不重复的字符 [a, b, c, d]，以及一个长度为n的字符串tbcacbdata，问能否在这个字符串中找到一个长度为m的连续子串，使得这个子串刚好由上面m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1。比如上面这个例子，acbd，3。 （2）
- 类 LC.438
- 要求不重复，或者对数量有要求：需要记录当前窗口包含的每个字符的数量
- 窗口严格保证为m
- 对于字符串的对比，可以考虑：substring() + indexOf()
3.哈希表/数组辅助解决数组问题
- 一个无序数组，从小到大找到第一个缺的数，比如[8 2 4 3 6 9 7 11 12]，第一个缺的就是5。
- LC.41
- 排序，时间复杂度O(NlogN)
- 用数组作为哈希表 ，将数字i放入数组中的i索引处，然后找中间没有存入数字的位置。时间和空间复杂度都是O(N)
- AB两个排序数组，原地合并数组。（A当中穿插一些无效数字怎么处理？）
- 思路：因为要原地合并数组，如果从前往后遍历，数组原来的值会被覆盖，所以只能从后往前遍历，将值从后往前存入。
- 存入时比较当前两个指针指向的数字大小，选较大的存入，然后往前移动指针。
4.排序相关
- 高考成绩2000万数据，分数0-750，如何快速知道排名，如何知道任一分数排名？
- 桶排序
- 先确定最大最小值，来确定范围
- 设置一个定量（751）的数组当作空桶（ArrayList<ArrayList< Integer >>）：(max - min) / scores.length + 1；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序，从不是空的桶里把排好序的数据拼接起来。
- 前缀树
5.二叉树
- 求完全二叉树的节点个数
- 首先统计二叉树左右子树的层数，left == right说明左子树一定是满二叉树，对右节点进行递归统计；left != right说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数，对左节点进行递归统计。
- 左子树的节点总数可以直接得到，是2 ^ left - 1，加上当前这个root节点，则正好是2^left。
- 同理，右子树节点+root节点，总数为2^right。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int left = countlevel(root.left);
int right = countlevel(root.right);
if(left == right){
// 移位运算，1 向左移动 left 次，相当于 1 * 2^n
return countNodes(root.right) + (1 << left);
}else{
return countNodes(root.left) + (1 << right);
}
}
// 完全二叉树特性：直接找最左的节点可得深度
private int countlevel(TreeNode root){
int level = 0;
while(root != null){
level++;
root = root.left;
}
return level;
}
}
- 判断完全二叉树
6.数学
- 写一个函数，求平方根，函数参数为目标数字和精度，测试案例 fn(4.1,0.001) fn(501.1,0.001) fn(0.045,0.001)
- 二分法：只有在区间[n-e, n+e]之间才能记录
- 给定一个 0-4随机数生成器 如何生成0-6随机数
- 用两个数组分别保存中文数字和中文单位，每次循环扫描给的中文数字，去匹配对应的数字。
- 中文数字数字可以用数组下标对应数字。
- 中文数字转阿拉伯数字，字符串处理问题。中文数字格式：一万三千五百四十一，阿拉伯数字格式：13541
- 用两个数组分别保存中文数字和中文单位，每次循环扫描给的中文数字，去匹配对应的数字。
- 中文数字数字可以用数组下标对应数字。
public class Solution{
static char[] cnArr = {'零','一', '二', '三', '四', '五', '六', '七', '八', '九'};
static char[] chArr = {'十', '百', '千', '万', '亿'};
public static int chineseNumToArabicNum(String chineseNum) {
int result = 0;
int temp = 1;//存放一个单位的数字如：十万
int count = 0;//判断是否有表示单位的文字
for (int i = 0; i < chineseNum.length(); i++) {
boolean b = true;//判断是否是单位
char c = chineseNum.charAt(i);
for (int j = 0; j < cnArr.length; j++) {//非单位，即数字
if (c == cnArr[j]) {
if (count != 0) {//添加下一个单位之前，先把上一个单位值添加到结果中
result += temp;
temp = 1;
count = 0;
}
// 下标+1，就是对应的值
temp = j;
b = false;
break;
}
}
if (b) {//单位{'十','百','千','万','亿'}
for (int j = 0; j < chArr.length; j++) {
if (c == chArr[j]) {
switch (j) {
case 0:
temp *= 10;
break;
case 1:
temp *= 100;
break;
case 2:
temp *= 1000;
break;
case 3:
temp *= 10000;
break;
case 4:
temp *= 100000000;
break;
default:
break;
}
count++;
}
}
}
if (i == chineseNum.length() - 1) {//遍历到最后一个字符
result += temp;
}
}
return result;
}
}
7. HashMap
- 一辆公交车，有m站，最多坐n人，输入一路上车票的信息（即上车下车站），输出会不会超载。
public class test48 {
public static boolean test(int[][] nums,int m,int n){
HashMap<Integer,Integer> map = new HashMap<>();
// 按照二维数组第一个元素排序
Arrays.sort(nums,(v1, v2)->v1[0]-v2[0]);
for(int i = 0; i < nums.length; i++){
// 在这段路程中，都会占有一个名额
for(int j = nums[i][0]; j <= nums[i][1]; j++){
if(!map.containsKey(j)){
map.put(j, 1);
}else{
if(map.get(j) + 1 > n){
return false;
}
map.put(j, map.get(j) + 1);
}
}
}
return true;
}
public static void main(String[] args) {
int m = 5;
int n = 5;
int[][] nums = {{1,5},{2,3},{2,4},{2,5},{4,5},{3,4},{1,2}};
System.out.println(test(nums,m,n));
}
}
- 有一个会议室里有一个录音麦，有n个人抢着说话，麦只能录到声音最大的人，给定每个人开始的说话时间s，结束的说话时间t，说话音量vol，然后求这个麦最后录到的声音序列。
三、多线程编程
- 用 synchronized 实现一个简单的死锁
- 互斥
- 循环等待
- 不剥夺
- 请求和保持
- 基本实现
public class D_Lock {
// 1、两把不同的锁
public static String str1 = "str1";
public static String str2 = "str2";
public static void main(String[] args) {
// 线程 a
Thread a = new Thread(() ->{
try{
// 2、无限循环
while(true){
synchronized(D_Lock.str1){
System.out.println(Thread.currentThread().getName() + "：str1");
// 3、睡眠保证线程 b 可以先获得
// 不会释放锁
Thread.sleep(1000);
// 4、循环请求锁
synchronized (D_Lock.str2){
System.out.println(Thread.currentThread().getName() + "：str2");
}
}
}
}catch (Exception e){
e.printStackTrace();
}
});
// 线程 b
Thread b = new Thread(() ->{
try{
while(true){
synchronized(D_Lock.str2){
System.out.println(Thread.currentThread().getName() + "：str2");
Thread.sleep(1000);
synchronized (D_Lock.str1){
System.out.println(Thread.currentThread().getName() + "：str1");
}
}
}
}catch (Exception e){
e.printStackTrace();
}
});
a.start();
b.start();
}
}
- 结果
- 实现基本的消息队列
- 一把锁：ReentrantLock()
- 两个条件：fullCondition、emptyCondition
- 在main()启动后传入同一个固定大小的任务容器（queue、数组等）
- run()中无限循环，获得锁
- 判断当队列已满，调用await()，否则往队列中加入数据
- 调用所有两个条件的signalAll() 唤醒线程
- 释放锁
public class ProducerConsumerByLock {
private static final int CAPACITY = 2;
// 同一把锁
private static final Lock lock = new ReentrantLock();
// 队列满的条件
private static final Condition fullCondition = lock.newCondition();
// 队列空的条件
private static final Condition emptyCondition = lock.newCondition();
public static void main(String[] args){
Queue<Integer> queue = new LinkedList<Integer>();
Thread producer1 = new Producer("P-1", queue, CAPACITY);
//Thread producer2 = new Producer("P-2", queue, CAPACITY);
Thread consumer1 = new Consumer("C1", queue, CAPACITY);
//Thread consumer2 = new Consumer("C2", queue, CAPACITY);
//Thread consumer3 = new Consumer("C3", queue, CAPACITY);
producer1.start();
producer2.start();
consumer1.start();
consumer2.start();
consumer3.start();
}
/**
* 生产者
*/
public static class Producer extends Thread{
private Queue<Integer> queue;
String name;
int maxSize;
int i = 0;
public Producer(String name, Queue<Integer> queue, int maxSize){
super(name);
this.name = name;
this.queue = queue;
this.maxSize = maxSize;
}
@Override
public void run(){
// 无限循环
while(true){
// 获得锁
lock.lock();
// 队列已满
while(queue.size() == maxSize){
try {
System.out .println("队列已经满了，生产者["+name+"]线程等待"+"消费者从队列中消费产品。");
// 条件不满足，生产阻塞
fullCondition.await();
} catch (InterruptedException ex) {
ex.printStackTrace();
}
}
System.out.println("[" + name + "] 生产产品 : +" + i);
queue.offer(i++);
// 唤醒其它所有生产者、消费者
fullCondition.signalAll();
emptyCondition.signalAll();
// 释放锁
lock.unlock();
try {
Thread.sleep(new Random().nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
/**
* 消费者
*/
public static class Consumer extends Thread{
private Queue<Integer> queue;
String name;
int maxSize;
public Consumer(String name, Queue<Integer> queue, int maxSize){
super(name);
this.name = name;
this.queue = queue;
this.maxSize = maxSize;
}
@Override
public void run(){
while(true){
// 获得锁
lock.lock();
while(queue.isEmpty()){
try {
System.out.println("队列是空的 消费者[" + name + "] 等待生产者生产");
// 条件不满足，消费阻塞
emptyCondition.await();
} catch (Exception ex) {
ex.printStackTrace();
}
}
int x = queue.poll();
System.out.println("[" + name + "] 消费产品 : " + x);
// 唤醒其太所有生产者、消费者
fullCondition.signalAll();
emptyCondition.signalAll();
//释放锁
lock.unlock();
try {
Thread.sleep(new Random().nextInt(1000));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
- 结果
- 输入一串数字，利用多线程按序打印
设计一个多线程打印程序，第i个线程只打印i-1数字，比如第1个线程打印数字0，第2个线程只打印数字1，依次类推。
- 开十个线程对应十个数字
- index作为待打印索引，volatile对所有线程可见
- 对于数字与线程号不等的，直接wait()
- 否则打印出数字，并唤醒所有线程
package jucCode;
import java.util.Scanner;
public class JUC_Main1 {
// 输入字符串索引
private static volatile int index = 0;
public static void main(String[] args) {
// 输入
Scanner scanner = new Scanner(System.in);
long num = scanner.nextLong();
String numStr = num + "";
// 类锁
Object object = JUC_Main1.class;
// 十个线程对应十个数字
for(int i = 0; i < 10; i++){
int finalI = i;
new Thread(() ->{
synchronized (object){
// 无限循环
while(true){
try{
// 48 为 0 的 ASCII
while (index < numStr.length() && (numStr.charAt(index) - '0') != finalI){
// 需要输出数字与当前线程不符合，进入等待
object.wait();
}
if (index == numStr.length()) {
// 控制结束,遍历完成退出
return;
}
System.out.println(">>>>>>>>>>>>>>>>>>>>> " + finalI);
// 当前下标数字已输出，唤醒所有线程，准备下一位数字输出
index++;
object.notifyAll();
}catch (Exception e) {
e.printStackTrace();
}
}
}
}).start();
}
}
}
- 三个线程循环打印A、B、C
- 双锁机制：一个是前一个线程的锁，用以保证顺序，第二个是自身锁；
- 先获取 prev 锁，再获取self锁；
- 打印后唤醒所有线程，释放self锁；
- 如果是最后一次打印，直接释放prev，否则，释放prev的同时进入休眠。
public class Synchronized_ABC {
public static class ThreadPrinter implements Runnable {
private String name;
// 双锁机制
private Object prev;
private Object self;
private ThreadPrinter(String name, Object prev, Object self) {
this.name = name;
this.prev = prev;
this.self = self;
}
@Override
public void run() {
int count = 10;
while (count > 0) {
synchronized (prev) { // 先获取 prev 锁
synchronized (self) {// 再获取 self 锁
System.out.print(name);
count--;
// 唤醒其它线程竞争 self 锁
// 此时 self 锁并未立即释放
self.notifyAll();
}
// 此时执行完 self 的同步块，这时 self 锁才释放
try {
// 如果 count==0,表示这是最后一次打印操作，通过 notifyAll 操作释放对象锁
if (count == 0) {
prev.notifyAll();
} else {
// 立即释放 prev 锁，当前线程休眠，等待唤醒
prev.wait();
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
public static void main(String[] args) throws Exception {
// 三把锁控制先后顺序
Object a = new Object();
Object b = new Object();
Object c = new Object();
ThreadPrinter pa = new ThreadPrinter("A", c, a);
ThreadPrinter pb = new ThreadPrinter("B", a, b);
ThreadPrinter pc = new ThreadPrinter("C", b, c);
new Thread(pa).start();
// 保证初始ABC的启动顺序
Thread.sleep(3);
new Thread(pb).start();
Thread.sleep(3);
new Thread(pc).start();
Thread.sleep(3);
}
}
四、单例
- 双重校验单例模式(DCL)
public class Singleton{
private volatile static Singleton singleton;
private Singleton(){}
public static Singleton getSingleton(){
if(singleton == null){
// 类对象加锁
synchronized (Singleton.class) {
if(singleton == null){
singleton = new Singleton();
}
}
}
return singleton;
}
}
- 饿汉式
public class Singleton{
// 直接构造
private static Singleton singleton = new Singleton();
private Singleton(){}
public static Singleton getSingleton(){
return singleton;
}
}
- 懒汉式——线程不安全
public class Singleton{
private static Singleton singleton = null;
private Singleton(){}
public static Singleton getSingleton(){
if(singleton == null){
singleton = new Singleton();
}
return singleton;
}
}
- 懒汉式——线程安全——静态内部类
public class Singleton{
private Singleton(){}
// 静态内部类保证线程安全
// 类装载的机制保证初始化实例时只有一个线程
private static class SingletonInstance{
private static final Singleton INSTANCE = new Singleton();
}
// 加锁保证线程安全
public static synchronized Singleton getSingleton(){
return SingletonInstance.INSTANCE;
}
}
五、智力题
- 25匹马，找出最快的3匹，但是只有5个赛道，每次比赛只能得到5匹马的速度排序，那么最少需要多少次比赛？
- 7次
- 分治
- 64匹马，8个跑道，选跑最快的4匹马需要比赛多少次
- 11次
- 一硬币，一面向上概率0.7，一面0.3，如何最高效地获得一个概率为0.5的事件？
- 信息论视角
- 每次掷两次硬币，如果结果是 01 或者 10 就 accept，结果是 00 或者 11 就 reject。这样做可能会一直 reject，但是 一直 reject 的概率足够小。
- 概率：两个人轮流抛硬币，先抛到正面的赢，问先抛的人赢的概率
- 2/3
- 每一轮抛硬币，A先抛赢得概率是1/2，B后抛赢得概率是（1/2）*（1/2）= 1/4。那么每一轮A赢得概率都是B赢得概率的2倍 ，总概率为1，所以A赢的概率是2/3。
- 两根香，一根烧完1小时，如何测量15分钟
- 香均匀的解法：开始时一根香两头点着，一根香只点一头，两头点着的香烧完说明过去了半小时，这时将只点了一头的香另一头也点着，从这时开始到烧完就是15分钟。
- 不均匀的解法：
- 在加勒比海上，有五个海盗，共同抢到了100枚金币， 每一个人按顺序依次提出自己的分配方案，如果提出的方案没有获得半数或半数以上的人的同意，则这个提出方案的人就被扔到海里喂鲨鱼，那么第一个提出方案的人要怎么做，才能使自己的利益最大化？（前提是海盗都是十分聪明和贪婪的）
- 倒着推，先考虑只剩两个人的情况。4号提出方案，自己一定会同意的，并且只要自己同意，这个方案就已经获得了半数的支持，就可以被实施。（100:0）
- 加入3号，3号只能拉拢5号，因为5号之前得不到金币，现在只要3号给5号一个金币就能够获得5号的支持，因为5号也知道，如果3号死亡，自己一定一枚金币都得不到。（99:0:1）
- 加入2号，必须再拉拢一个人，拉拢3号显示是不合适的，3号一定不会同意，3号知道，只要搞死了2号，有99枚金币都是自己的； 拉拢5号貌似是可以的，他已经有一个金币了，要让他支持自己只要再多给他一个金币就可以了；拉拢4号也是可以的，4号现在没有金币，只要给他一个就可以让他自持自己的提案。（99:0:1:0）
- 加入1号，2号一定不会同意，拉拢3号是可以的，3号现在没有金币，只要给他一个就可以让他自持自己的提案， 5号跟3号情况一至，同样没有金币，只要给他一个就可以了。（98:0:1:0:1）
- 海盗分金币，但这次要超过半数。
- 倒着推，当只有两个海盗的时候，4号一定会死，因为首先只要第一个海盗死了，剩下的5号便能获得全部的金币。（0:100）
- 加入3号，拉拢4号即可。（99:1:0）
- 加入2号，同样推理，可得：（97:0:2:1）
- 加入1号，有：（97:0:1:0:2）
- 坐标系中有一个球桌，四个角坐标：(0,0), (0,4), (2,4), (2,0)。一颗球在(1,1)，请问从哪些角度可以射入洞内（可无限次碰撞）？
- 把洞镜像对称，将这个桌面在这个平面无限延展，可类比成无限张球桌紧密放置，那么每一个和球洞的连线都是合法路径。