牛客上的一个阿里云面经
作者:止增笑耳哈哈哈
链接:https://www.nowcoder.com/discuss/842615?type=2
来源:牛客网
面试时间:电话面试 50 min
快排的原理
总体是利用分治的思想。先在数组中找一个基准数,例如第一个,或者随机选一个数和第一个数先进行交换,再选择第一个,来避免极端情况。将这个待排序数组中小于基准数的,移到左边,大于它的移到右边,这样,左右两个区间就相对有序了。接着把左右两个分区分别按照这个方法,找出基准数,然后移动,直到分区只剩一个数为止。
数组(奇数偶数)对于快排的影响
我的想法:没影响,本身就是找基准数、分区、然后在分区继续重复操作的问题,和奇偶数没啥关系。
Collections 中采用的排序方式是哪一种,具体是怎么使用的
题外话:
list便捷插入:
List<Integer> list = new ArrayList<Integer>() {
{// 这个大括号是构造代码块,会在构造函数之前调用
this.add(1); // this可省略
add(3);
add(2);
}
};
System.out.println(list); // [1, 3, 2]
它底层还是调用的Arrays.sort
。
// Collections.sort(list);
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}
// list.sort
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
用到的是对象数组排序。
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
// 一个默认关闭的选项,传统归并排序
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
Arrays.sort排序方法
对于基本数据类型它用的是DualPivotQuicksort
,也就是双轴快速排序。(对象数组用的是归并和timsort)。
另一张图:
//final class DualPivotQuicksort
static void sort(int[] a, int left, int right,
int[] work, int workBase, int workLen) {
// Use Quicksort on small arrays
if (right - left < QUICKSORT_THRESHOLD) { //286
sort(a, left, right, true);
return;
}
//...
}
评估数组无序程度用的是下面的run的概念。
最后的快排用的是:先选择五个分位点,各个分区相对排好序,然后比较5个分位点值,如果互不相同,就e2和e4作为双轴快速排序,否则,选e3为轴,进行快排。
但单轴很多时候可能会遇到较差的情况就是当前元素可能是最大的或者最小的,这样子元素就没有被划分区间。划分的区间由原来的两个变成三个,最坏最坏的情况就是左右同大小并且都是最大或者最小,但这样的概率相比一个最大或者最小还是低很多很多,所以双轴快排的优化力度还是挺大的。
TimSort
自适应、混合、稳定的排序算法,融合了归并算法和二分插入排序算法的精髓。
它之所以快,是因为充分利用了现实世界的待排序数据里面,有很多子串已经排好序。
小数组中直接二分插入排序。如[2,3,4,5,6,1]
,1是当前位,前面都是排好序的,直接二分,然后整体移动。
Run
先找严格递增或递减(会被反转成递增)的子序列,称为run。run的个数略小于或者等于2的幂次方时效率最高,所以要控制run的长度,如果长度太短,就通过二分插入到前面的run里。
合并
归并算法里是相邻两两合并,这里是把run放入栈里,来一个一个合并的。里面有一些合并条件,加速合并方法。
归并排序的应用场景、空间复杂度,快排的空间复杂度又是多少
待排序的数组随机分布时,快排的平均时间最短,不稳定。
归并排序:利用分治思想,稳定的排序算法。它将已经有序的子序列合并,来得到完全有序的序列。要想使子序列有序,就需要对子序列的子序列进一步操作,整体就是一个递归的过程。
应用场景
外排序中通常使用归并。它不能将整个数组放入内存,可以通过归并排序将中间结果写入到硬盘上,归并时再将硬盘上的中间结果组合成大的有序文件。在部分有序的数组中也可使用。
归并排序空间复杂度
归并排序分为分、合两个部分。
分的时候:假设数组长度为n,第一层分为两个子区间,每个子区间数目n/2,第二层四个子区间,每个子区间n/4,也就是log级别,有logn层,最后一层是一个元素一个区间。
合的时候,在第logn层,每两个子区间合并,也就是合并n/2次,每个元素都会被遍历。同理,每一层都会合并,在每一层都是每个元素都会被遍历。复杂度O(nlogn)。
快排复杂度
在理想情况,基准位位于中间,两边都是n/2个元素,每个元素都比较到了,所以单独比较一层是O(n),接下来对左右两个区间进行分别比较,每个区间n/2个元素,按照刚才说的规律,基准位位于中间,整个拆分成一个区间一个元素是logn层,每次都牵扯到各个区间里面元素的比较,一层O(n),总体时间复杂度O(nlogn)。
这个是比较理想的情况,但是实际上存在最坏情况就是基准位全部位于边缘,整个分治就是n层,每层还是牵扯到全部元素的比较,最坏复杂度O(n^2)。
Java 一次编译到处运行的原因
这个的前提是运行的平台上安装了虚拟机。JAVA编译产生的class文件能够被JAVA虚拟机在运行时转换为平台对应的机器码来运行。
字节码文件如何被JVM读取的
字节码文件被JVM加载到内存,然后对数据进行校验、转换解析和初始化。
加载:通过类的全限定名来获取二进制字节流,可以通过jar包或者网络方式获取。之后将字节流信息转换为方法区的运行时数据结构,在内存里生成代表这个类的class对象,作为访问该类的数据入口。
加载的时候有三层类加载器,从上到下是启动类加载器,扩展类加载器,应用程序类加载器。也可以自定义加载器。加载时的层次关系是双亲委派模型,收到类加载请求后,不是自己去加载,而是给父加载器,父类无法加载的时候,才会给子加载器。
验证:确保被加载类的正确性。例如文件格式:如魔数、版本号,常量池中的常量;元数据:父类,接口方法。。。
准备:为静态变量分配内存,并初始化默认值。
解析:把常量池里的符号引用转化为直接引用。
- 符号引用:就是以一组符号来描述所引用的目标,可以是任何形式的字面量。
- 直接引用:直接指向目标的指针、相对偏移量等。
初始化:它是执行类构造器clinit方法的过程,clinit由所有类变量的赋值动作和静态语句块合并而成。
编译的字节码文件中的主要内容是什么
常量池中是一些类型的组合:
常量项的第一个标识就是类型,然后是具体的数据。
JVM 优化:如何排查 OOM ,十分详细
就是程序申请的空间,JVM满足不了,程序崩溃。
哪些场景会产生OOM?
堆内存溢出,一直创建对象,爆了。
-Xmx20M -Xms20M -XX:+HeapDumpOnOutOfMemoryError 生成堆内存快照。如果有控制台输出,也会输出。
元空间溢出
例如大量使用反射,生成大量class信息存在于方法区中。
栈溢出
排查
一般排查方法是对dump出来的快照进行分析。具体说不清楚。
synchronized 与 lock 区别
synchronized是JVM层面的锁。Lock是一个接口,它的实现类例如可重入锁ReentrantLock,是API层面的锁。
synchronized使用完会自动释放,Lock需要手动释放。
synchronized的实现涉及到锁的升级,无锁,偏向锁,重量级锁,ReentrantLock是利用乐观锁CAS操作来实现锁功能的。
synchronized不可中断、非公平。Lock可中断(如设置超时),可以公平。
synchronized不能绑定condition,lock可以绑定condition实现线程的精确唤醒。
synchronized锁的是对象,锁保存在对象头里,根据对象头的标识判断锁,ReentrantLock锁的是线程。
ReentrantLock 绑定多个 Condition的原理
ReentrantLock 基于AQS来实现的。
AQS
绑定多个condition?
例子:
阻塞队列
public class MyQueue {
Lock lock = new ReentrantLock();
Condition putCondition = lock.newCondition();
Condition takeCondition = lock.newCondition();
private volatile int size = 0;
public MyQueue() {
size = 11;
};
public MyQueue(int size) {
this.size = size;
};
private List<Object> list = new ArrayList<Object>();
public void put(Object o) throws InterruptedException {
lock.lock();
try {
if (list.size() < size) {
list.add(o);
takeCondition.signal();
} else {
while (true) {
putCondition.await();
}
}
} finally {
lock.unlock();
}
}
public Object take() throws InterruptedException {
lock.lock();
Object obj;
try {
if (list.size() == 0) {
while (true) {
takeCondition.await();
}
} else {
obj = list.get(0);
list.remove(0);
putCondition.signal();
}
} finally {
lock.unlock();
}
return obj;
}
}
对象监视器只能有一个等待队列,使用Lock方式可以有多个等待队列,可以创建多个condition。
例子:
原子类的实现原理,为什么 i++ 不是线程安全的
i++,读取,+1,写入三个步骤,有线程安全问题。
原理CAS操作。
回答 CAS
CAS 的缺陷
自旋等待,这个通过设置自旋次数解决、还有一个就是ABA问题。
如何解决 ABA 问题
版本号 + 时间戳
版本号是如何实现的?
问:如果我目标版本是 100 ,当前版本是 99 ,能不能成功进行 CAS 操作?
问的有问题吧。总之就是读取的时候和设置修改的时候的版本号要一样。
多线程操作 static 变量会有影响吗?
静态变量不依赖于特定的类实例,它被所有类实实例共享。非线程安全。
最终一致性了解吗?(网络请求的事务)
系统中的所有分散在不同节点的数据,经过一定时间后,最终能够达到符合业务定义的一致的状态。
给 A、B、C三个人转钱,如何保证都成功
@Transaction 注释的原理
加上注解之后,spring启动会查看拥有注解的类和方法,生成代理,根据Transaction注解的配置进行诸如,在代理中把事务处理掉,像是开始、提交、回滚事务。
Spring IOC 与 AOP是什么,如何实现的
ioc是控制反转:常规的创建对象是需要的时候创建对象,如果对象里有个属性是对象还需要自己创建。ioc它把创建对象、查找依赖对象的控制权给了ioc容器,容器来组合对象,管理他们的生命周期。
AOP:面向切面编程,它是把对象剖开,把那些多次使用的代码放到一个模块,来减少重复代码,降低耦合。一般是基于代理模式,例如JDK和CGLIB。
三次握手与四次挥手
外键的优缺点
外键:在另一个关系中是主键。
优点:不适用外键,可能会导致数据冗余。
缺点:管理,开发难度大了。