面试经验——小米_小米 交叉面试

一面：
1. 快速排序，手写代码。
2. 堆排序，描述过程，纸上画出来。
3. 单例模式：懒汉模式和饿汉模式。
4. 线程池的实现原理，用到的数据结构，如何调度池内资源。
5. 用什么命令查找某个文件名？
6. 用什么命令删除某个文件和下面的所有东西？
7. sql语句：创建一个table。
二面：
8. 给定一个数组，数组中存放着线程的引用，根据该数据结构，设计一个线程池的方案，要求在取出空闲线程和归还线程的时候，复杂度为O（1），并且申请的辅助空间为常数级。
9. 实现双链表查找相交节点。（我实现了3种方法）

解答：

1.快排

private void sort(int start, int end, int[] num){
        if(start<end){
            int begin = start,last = end;
            int tree = num[start];
            while(start<end){
                for(;end>start && num[end]>=tree;end--);
                num[start] = num[end];
                for(;end>start && num[start]<=tree;start++);
                num[end] = num[start];
            }
            num[start] = tree;
            sort(begin,start-1,num);
            sort(start+1,last,num);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.堆排序
堆排序算法，没有比这一篇讲的再透彻的了，分析的很到位。

存储堆的最好的数据结构就是数组，可以直接找到父节点或者对应的两个子节点，进行操作。
在面试的过程中，面试官仅仅问了我建立小顶堆的过程；该过程总体由“一上一下”两个方面构成：

• 一上：当前节点和兄弟以及其父元素的比较，和交换（如果有必要的话）；
• 一下：交换过后，当前位置的值跟以它为父节点的子节点的值进行调整疏导，并一直梳理到大小层次合适为止；

3.单例模式：
懒汉模式(第一次使用的时候才会生成单例，类被加载的时候是不会生成单例对象的，此时为null)：

public class Singleton {
    private static Singleton singleton = null;
    private Singleton() {//私有构造方法，防止该类被实例化。
    }
    public static Singleton getInstance(){
        if(singleton==null){
        sychronized(singleton){
        singleton=new Singleton();
        }
        }
        return singleton;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

饿汉模式：在类首次被加载（注意，不是使用）的时候就生成了单例对象。

public class Singleton {
    private static Singleton singleton = new Singleton();
    private Singleton() {//私有构造方法，防止该类被实例化。
    }
    public static Singleton getInstance(){
        return singleton;
    }
}
1
2
3
4
5
6
7
8

4.线程池的实现要素：

队列、数组、线程（Thread）、get和giveback方法等。

• 数组实现了对线程个数的控制和对每个线程的跟踪管控；
• 队列指任务队列，表示将要分配给线程池工作的候选任务；
• 线程（Thread）是存放在线程池中的每一个线程，需要使用时候拿出
• 运行、运行完之后放回池中待命；
• get方法：当线程池中仍拥有空暇线程时，得到一个空闲线程，加载任务运行，空闲记录中将其标记为busy；
• giveback方法用于当线程池中空闲线程未达到池容量时，在某线程执行完处于空闲时，放回到线程池中待命，空闲记录中增加该线程；

5.使用find命令查找某个名字的文件

当时没有答上。详见find命令。

6.删除某个文件夹及下面的所有文件命令：rm -rf

7.sql语句创建一张表student，id为自增主键，name为字符串， age为int类型。

当时也没答对。应该是：

CREATE TABLE student(
id int identity(1,1) PRIMARY KEY,
name varchar(32)  NOT NULL, 
age int NOt NULL
) 
1
2
3
4
5

8.给定一个数组，数组中存放着线程的引用，根据该数据结构，设计一个线程池的方案，要求在取出空闲线程和归还线程的时候，复杂度为O（1），并且申请的辅助空间为常数级。

按照要求，需要在O（1）时间内放回或者取出，而且不能申请O（n）的辅助空间，但是在任务中可以有一些标记字段（isBusy<是否忙碌>，originIdx<对应数组位置下标>等）。
经过考虑，我可以这样做：
在每次取出和放回 的时候都按照顺序依次存放，但由于每个任务中都记录了数组下标，而数组对应下标都存着该任务的引用，则当任务没有按照次序归还线程时，可将该线程和另外一个正在运行着的线程位置进行互换，从而达到按顺序归还的效果，同时修改两个互换线程关于busy和所属下标的值，这样，在取出的时候可以做到按照顺序取，达到O（1），放回的时候可以按照顺序放，在O（1）的复杂度内，交换两个线程的所属位置即可解决。
分析图如下：

• 开始的时候，0到10都是空闲，则设立pointer指向busy区和free区的边界线，则此时的pointer应为0；
• 当分配的时候，pointer++，变为1，然后把pool[0]分配出去；
  若还需要，则将pointer指向的分配出去，然后pointer++；
• 某一时刻，假设pointer指向了5，则说明0到4都在忙；
  此时，若pool[2]对应的任务类回来了，则应该将其放入pool[4]中，pointer–，代表空闲的从4号开始。
• 同时，假设Task4对应着原本从pool[4]中分配出去的任务，而4还没有回来，2先回来占用了4的位置，那么需要交换Task2和Task4的originIdx信息，让Task2的指向4，让Task4的指向2；并且让pool[2]和pool[4]的引用也调换过来，从而能在每次回收的时候通过这种交换位置操作达到O（1）。
• 按照该思想写出get（）和giveBack（）方法。

9.双链表判断是否有交叉

• 方法1：使用Set存放ListNode的引用；遍历每一个节点都在set中查找是否已有该节点，若遍历一遍之后没有找到重复的，则没有相交；否则有交叉；

  考官提出，若不许有额外的O（n）的辅助内存：

• 方法2：将最后一个节点链到第二个头上，从而将问题转化为判断是否有环路的问题上，设置快慢指针，快指针一次2步，慢指针一次1步，直到快指针为null或快指针==慢指针。为null说明无环，相等则说明快慢指针相遇，有环路，因此有交叉。

  考官又提出，不能改变原有链表的结构

• 方法3：首先分别求出两个链表的长度，抛开长度的差值，然后定义两个指针分别同时向下走，没走一次都相互比较，直到走到null或者相等为止。若为null则无相交；否则有交叉。

至此，两轮面试结束。考的问题都很基础，没有偏难怪，基础还需要打扎实。