面向面试查漏补缺

发表于 | 分类于

数组

数组相当于是一种数据结构，很多数据在进行存储的时候需要使用数组

排序算法

冒泡排序

时间复杂度： O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* 冒泡排序: 前一个数字与后一个数字比较，若后者大于前者，两者交换
* @param arr
*/
public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length -1 - i; j++) {
            if(arr[j] > arr[j+1]) {
                // 交换位置
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

选择排序

平均时间复杂度：O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 选择排序:
* 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
* 第二次遍历n-2个数，找到最小的数值与第二个元素交换；
* ...
* 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。
* @param arr
*/
public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int k = i;
        for (int j = i+1; j < arr.length; j++) {
            // 获取最小值下标
            if(arr[k] > arr[j]) {
                k = j;
            }
        }
        if(arr[i] > arr[k]) {
            int temp = arr[i];
            arr[i] = arr[k];
            arr[k] = temp;
        }
    }
}

插入排序

平均时间复杂度：O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 /**
* 插入排序：
* 假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。
* 如此反复循环，直到全部排好顺序
*/
public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        for (int j = i-1; j >= 0; j--) {
            if(arr[j+1] < arr[j]) {
                // 第n个数小于前n-1已排好序的数组的最后一位，换位
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }else {
                // 第n个数大于前n-1已排好序的数组的最后一位，直接跳过进入第n+1个数
                break;
            }
        }
    }
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

/**
 * 快速排序：
 * 采用分治策略
 * 1．先从数列中取出一个数作为基准数。
 * 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
 * 3．再对左右区间重复第二步，直到各区间只有一个数。
 * @param arr 需要排序的数组
 * @param begin 排序起始位置
 * @param end 排序最终位置
 */
public static void quickSort(int[] arr, int begin, int end) {
    int pivot = arr[begin];// 定义数组最左边一个数为基准值
    boolean rtl = true;
    int left = begin;
    int right = end;

    for (int i = begin; i < end+1; i++) {
        if(rtl) {
            // 从右往左移动，将右边的值与基准值比较
            if(arr[right] < pivot) {
                // 若右边的值小于基准值，将右边的值填入左边的位置上，左指针向后移动
                arr[left] = arr[right];
                left++;
                rtl = false;// 移动左指针
            }else {
                // 右边的值大于基准值，右指针向前移动
                right--;
            }
        }else {
            // 从左往右，将左边的值与基准值比较
            if(arr[left] > pivot) {
                // 若左边的值大于基准值，将左边的值填入右指针位置，右指针向前移动
                arr[right] = arr[left];
                right--;
                rtl = true;
            }else {
                left++;
            }
        }

        if(left == right) {
            arr[left] = pivot;
            // 分别对左右数组排序
            if(left-1 >= begin) {
                quickSort(arr, begin, left-1);
            }
            if(right+1 <= end) {
                quickSort(arr, right+1, end);
            }
            break;
        }
    }
}

集合

消息队列

常用的消息队列

ActiveMQ rabbitMQ rocketMQ kafka

activeMQ

面试题剖析

为什么要用消息队列

答题思路： 你们公司有什么业务场景，这个场景有什么技术挑战，如果不用MQ可能会很麻烦，但是你现在用了MQ之后带给了你很多好处

面试技巧： 考虑下你负责的系统中是否有类似场景，就是一个系统或者一个模块调用了多个系统或者模块，互相之间的调用很复杂， 维护起来很麻烦。但是其实这个调用是不需要直接同步调用接口的，如果用MQ给他异步化解耦，也是可以的。你就需要去考虑在你的项目中，是不是可以运用这个MQ去进行系统的解释

  • 消息队列的常用场景： 解耦、异步、削峰