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匹马的速度排序,那么最少需要多少次比赛?
- 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),请问从哪些角度可以射入洞内(可无限次碰撞)?
- 把洞镜像对称,将这个桌面在这个平面无限延展,可类比成无限张球桌紧密放置,那么每一个和球洞的连线都是合法路径。