数据结构与算法面试题集

一次次的挂于一面让我筋疲力竭…意识到自己存在眼高手低的状态…准备重新上路夯实基础
本片文章Fork from android-interview

数据结构与算法通常也与Java的集合牵扯在一起考察，这里我们将两者放在一起来讲。

什么是算法？

算法是指令的集合，是为了解决特定问题而规定的一些列操作。

时间复杂度

算法的执行时间随着问题规模的增长而变化的规律。

算法的执行时间受到以下四个因素的影响：

硬件层面：计算机执行每条指令的速度
软件层面：编译产生的代码质量
算法策略：算法的好坏
问题规模

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

例如：插入排序的算法复杂度是O(1)。而一般递归算法的时间复杂度就是O(n)，因为每次递归都要存储结果。

常熟阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(nlogn)，平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n);

描述一下Java的集合体系，List、Set与Map有什么区别？

Java集合里使用接口来定义功能，是一套完善的继承体系。Iterator是所有集合的总接口，其他所有接口都继承于它，该接口定义了集合的
遍历操作，Collection接口继承于Iterator，是集合的次级接口（Map独立存在，除外），定义了集合的一些通用操作。

Java集合的类结构图如下所示：

👉 点击图片查看大图

List：有序、可重复；索引查询速度快；插入、删除伴随数据移动，速度慢；
Set：无序，不可重复；
Map：键值对，键唯一，值多个；

并发集合了解哪些？

ConcurrentHashMap：线程不安全的HashMap、效率低下的HashTable、线程安全且高效的ConcurrentHashMap。

ConcurrentHashMap存储元素的结构如下所示：

ConcurrentHashMap与HashMap一样适用数组加链表存储元素，适用链表定址法来解决哈希冲突，不同之处在于当链表长度大于8的时候会将链表转换为一棵红黑树，查找时间复杂度由O(N)变成O(lgN)。

ConcurrentHashMap并发控制的关键在于一个变量，如下所示：

1	private transient volatile int sizeCtl;

sizeCtl被volatile关键字修饰是一个多线程共享的变量，当它的值为负数的时候说明某个线程正在操作这个Map，想要去操作这个Map的线程就要一直去竞争这个sizeCtl，没有得到这个变量的值就要一直自旋等待这个变量，当占用
这个变量的线程操作完成后，要将这个变量的值设置回来，以便让其他线程走出自旋，竞争到该变量。

这种同步进制事实上是一种CAS的做法。

CAS（Compare and swap）比较和替换是设计并发算法时用到的一种技术。简单来说，比较和替换是使用一个期望值和一个变量的当前值进行比较，如果当前变量的值与我们期望的值相等，就使用一个新值替换当前变量的值。

Vector，ArrayList与LinkedList有什么区别，应用场景是什么？

Vector实现了基于动态Object数组的数据结构，线程安全，可以设置增长因子，效率比较低，不建议使用。
ArrayList实现了基于动态Object数组的数据结构，非线程安全，地址连续，查询效率比较高，插入和删除效率比较低。适合查询操作频繁的场景。
LinkedList实现了基于链表的数据结构，非线程安全，地址不连续，查询效率比较低，插入和删除效率比较高。适合插入和删除操作频繁的场景。

HashMap、LinkedHashMap、ConcurrentHashMap、TreeMap与ArrayMap有什么区别，应用场景是什么？

HashMap：基于HashMap.Node数组加单向链表实现，非线程安全，地址不连续，查询效率比较低，插入和删除效率比较高。适合插入和删除操作频繁的场景。
LinkedHashMap：基于
ConcurrentHashMap：基于hash表实现，线程安全且高效，分段锁的实现相对于HashTable的实现提高了很大的效率。
TreeMap：基于红黑树实现，非线程安全，可以按照自然顺序或者自定义顺序自动排序，不允许插入null值，查找效率比较高，适合需要排序的场景。

ConcurrentHashMap存储元素的结构如下所示：

ConcurrentHashMap并发控制的关键在于一个变量，如下所示：

1	private transient volatile int sizeCtl;

这种同步进制事实上是一种CAS的做法。

CAS（Compare and swap）比较和替换是设计并发算法时用到的一种技术。简单来说，比较

HashSet、LinkedHashSet与TreeSet有什么区别，应用场景是什么？

HashSet：基于HashMap实现，非线程安全，地址不连续，查询效率比较低，插入和删除效率比较高。适合插入和删除操作频繁的场景。
LinkedHashSet：

TreeSet基于红黑树实现，非线程安全，可以按照自然顺序或者自定义顺序自动排序，不允许插入null值。适合需要排序的场景。
HashSet基于hash表实现，非线程安全，允许插入null，查找效率高。适合查找操作频繁的场景。

HashMap是如何解决hash碰撞的？

开发定址法
链表法

HashMap基于数组实现，数组里的元素是一个单向链表。

HashMap具有以下特点：

基于数组实现，数组里的元素是一个单向链表。
键不可以重复，值可以重复，键、值都可以为null
非线程安全

HashMap实现了以下接口：

Map：以键值对的形式存取元素
Cloneable：可以被克隆
Serializable：可以序列化

查找流程

计算哈希值，根据哈希值与数组容量计算它所在的索引，根据索引查找它所在的链表。
在单向链表中查找该元素

删除流程

计算哈希值，根据哈希值与数组容量计算它所在的索引，根据索引查找它所在的链表。
从起始节点开始遍历，查找要删除的元素，删除该节点，将节点的后继添加为它前驱的后继

插入流程

根据key计算hash值，并根据hash值和数组容量，找到索引值，该位置即为存储该元素的链表所在处。
遍历table[i]位置的链表，查找相同的key，若找到则则用新的value替换掉oldValue.
若没有查找到相同的key，则添加key到table[i]位置，新添加的元素总是添加在单向链表的表头位置，后面的元素称为它的后继。

HashSet基于HashMap实现，也就是说它本质上也是一个数组，它以HashMap的key来存储元素，因为HashMap里的key是不会重复的，所以HashSet的元素时不重复且无序的。

SpareArray做了哪些优化？

优点

key保存在int mKeys[]数组中，相对于HashMap不再对key进行自动装箱，避免资源消耗。但是vaule是保存在Object[] mValues数组中还是需要自动装箱的。
相对于HashMap，不再使用额外的Entry对象来存储数据，减少了内存开销。
数据量小的情况下，随机访问效率更高。

缺点

插入操作需要复制数组，增删效率低。
数据量巨大时，复制数组成本巨大，gc()成本也巨大。
数据量巨大时，查询效率也会明显下降。

简单说一说SpareArray的插入流程？

SpareArray的key是一个int有序数组，查找过程使用的二分查找。

用二分查找法查找元素的key。
如果插入的数据冲突了，则直接覆盖原则。
如果当前插入的key上的数据为DELETE，则直接覆盖。
如果前面几步都失败了，则检查是否需要gc()并且在索引上插入数据。

N个无序树中查找最大的10个数？

手写代码遍历文件目录？

电梯运行的算法分析？

手写一下单链表的查询操作？

手写二分查找？

手写一个字符串翻转？

从长度为m的int数组中随机取出n个元素，每次取的元素都是之前未取过的，如何优化？

string:  Hello
  length:  5
  
          0 1 2 3 4 
  before: H e l l o
  after:  o l l e H
  
  index             sum
  0: H--->o  0-->4  4
  1: e--->l  1-->3  4
  2: l--->l  2-->2  4

解法一：使用数组

将字符串转换为char数组
遍历循环给char数组赋值

public static String strReverseWithArray2(String string){
    if(string==null||string.length()==0)return string;
    int length = string.length();
    char [] array = string.toCharArray();
    for(int i = 0;i<length/2;i++){
        array[i] = string.charAt(length-1-i);
        array[length-1-i] = string.charAt(i);
    }
    return new String(array);
}

解法二：使用栈

将字符串转换为char数组
将char数组中的字符依次压入栈中
将栈中的字符依次弹出赋值给char数组

public static String strReverseWithStack(String string){
    if(string==null||string.length()==0)return string;
    Stack<Character> stringStack = new Stack<>();
    char [] array = string.toCharArray();
    for(Character c:array){
        stringStack.push(c);
    }
    int length = string.length();
    for(int i= 0;i<length;i++){
        array[i] = stringStack.pop();
    }
    return new String(array);
}

解法三：逆序遍历

逆序遍历字符串中的字符，并将它依次添加到StringBuilder中


public static String strReverseWithReverseLoop(String string){
        if(string==null||string.length()==0)return string;
        StringBuilder sb = new StringBuilder();
        for(int i = string.length()-1;i>=0;i--){
            sb.append(string.charAt(i));
        }
        return sb.toString();
    }

单链表反转，合并多个单链表

单链表的结构就像一个火车的结构，火车头拉着许多车厢，实现链表翻转，可以利用递归翻转法，在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。简单的
说就是从尾结点开始，逆向反转各个结点的指针域指向，

public class LinkedListReverse {  
    
    public static void main(String[] args) {  
        Node head = new Node(0);  
        Node node1 = new Node(1);  
        Node node2 = new Node(2);  
        Node node3 = new Node(3);  
        head.setNext(node1);  
        node1.setNext(node2);  
        node2.setNext(node3);  
  
        // 打印反转前的链表  
        Node h = head;  
        while (null != h) {  
            System.out.print(h.getData() + " ");  
            h = h.getNext();  
        }  
        // 调用反转方法  
        head = Reverse1(head);  
  
        System.out.println("\n**************************");  
        // 打印反转后的结果  
        while (null != head) {  
            System.out.print(head.getData() + " ");  
            head = head.getNext();  
        }  
    }  
  
    /** 
     * 递归，在反转当前节点之前先反转后续节点 
     */  
    public static Node Reverse1(Node head) {  
        // head看作是前一结点，head.getNext()是当前结点，reHead是反转后新链表的头结点  
        if (head == null || head.getNext() == null) {  
            return head;// 若为空链或者当前结点在尾结点，则直接还回  
        }  
        Node reHead = Reverse1(head.getNext());// 先反转后续节点head.getNext()  
        head.getNext().setNext(head);// 将当前结点的指针域指向前一结点  
        head.setNext(null);// 前一结点的指针域令为null;  
        return reHead;// 反转后新链表的头结点  
    }  
}  
  
    class Node {  
        private int Data;// 数据域  
        private Node Next;// 指针域  
  
        public Node(int Data) {  
            // super();  
            this.Data = Data;  
        }  
  
        public int getData() {  
            return Data;  
        }  
  
        public void setData(int Data) {  
            this.Data = Data;  
        }  
  
        public Node getNext() {  
            return Next;  
        }  
  
        public void setNext(Node Next) {  
            this.Next = Next;  
        }  
    }

排序算法

以下排序算法内容来自：面试中的 10 大排序算法总结.md