1、快速排序 O (nlogn)
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
sort方法底层排序逻辑：
第一个阈值286
小于286需要再与47比较 如果小于47 使用的是插入排序
如果是大于47小于286使用快速排序
大于286会进入归并排序
2、hashmap和hashtable区别
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对
继承的父类不同
Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口
线程安全性不同
javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。
是否提供contains方法
HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。
Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。
key和value是否允许null值
其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。通过上面的ContainsKey方法和ContainsValue的源码我们可以很明显的看出：Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。
HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。
数组和链表的区别；
数组元素在内存上连续存放，可以通过下标查找元素；插入、删除需要移动大量元素，比较适用于元素很少变化的情况
链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高
对于访问，数组和链表时间复杂度分别是O(1)与O(n)
内存管理：因为数组与链表的物理存储结构不同，在内存预读方面，内存管理会将连续的存储空间提前读入缓存（局部性原理），所以数组往往会被都读入到缓存中，这样进一步提高了访问的效率，而链表由于在内存中分布是分散的，往往不会都读入到缓存中
hashmap底层数据结构
HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找
算法题
1， 只使用一个辅助栈，对一个栈进行升序排列 ——通过
2， 数组中重复元素最多的称为度 求相同的度的子串 最短的
3， 单列表逆序，遇到k个节点再逆序
4， 两个单向链表, 可能有交叉节点. 实现一个方法, 输入两个链表头, 返回其交叉节点对象——通过
5，二叉树最大路径和
6，第一个是求数组中第k个位置的元素 需要先排序再查找
7，两数之和
8，手写单链表反转——通过
9，通过掷色子选择走路的步数，问走N步，有多少种不同的方案
10，实现LRU算法
11，链表 双向链表；
12，给定一个字符串，例如abcabcd，请你求得到该字符串中所有的长度大于等于2的子串，并统计每个字串出现的次数。
13，输出字符串的所有连续子字符串长度要求大于等于2。
14，java类的题目是字符串数组排序，譬如 a[] = {"sbg","dyh","yhjjjj"},进行排序
原文：https://www.cnblogs.com/songtianning/p/14012410.html