19. Interview-Algorithm

2020-08-05  本文已影响0人  allen锅
O(n) 常用数据结构时间复杂度

1 一致性算法

一致性的分类

一致性算法实现举例

1.1 Paxos

分布式系统对某个决议达成一致。大于n/2

3种角色

两个阶段

1.2 ZAB

1.3 Raft

动画演示Raft：http://thesecretlivesofdata.com/raft/

三种角色

两个阶段

Raft与ZAB区别

1.4 NWR

1.5 Gossip

1.6 一致性hash算法

2 加密算法

加密算法对比

2.1 MD5

MD5 用的是 哈希函数，它的典型应用是对一段信息产生 信息摘要，以 防止被篡改。严格来说，MD5 不是一种 加密算法 而是 摘要算法。无论是多长的输入，MD5 都会输出长度为 128bits 的一个串 (通常用 16 进制 表示为 32 个字符)。

2.2 SHA1

SHA1 是和 MD5 一样流行的 消息摘要算法，然而 SHA1 比 MD5 的 安全性更强。对于长度小于 2 ^ 64 位的消息，SHA1 会产生一个 160 位的 消息摘要。基于 MD5、SHA1 的信息摘要特性以及 不可逆 (一般而言)，可以被应用在检查 文件完整性 以及 数字签名 等场景。

2.3 HMAC

HMAC 是密钥相关的 哈希运算消息认证码（Hash-based Message Authentication Code），HMAC 运算利用 哈希算法 (MD5、SHA1 等)，以 一个密钥 和 一个消息 为输入，生成一个 消息摘要 作为 输出。

HMAC 发送方 和 接收方 都有的 key 进行计算，而没有这把 key 的第三方，则是 无法计算 出正确的 散列值的，这样就可以 防止数据被篡改。

2.4 CRC

CRC，Cyclic Redundancy Check，循环冗余校验，利用网络数据包或电脑文件产生固定位数的校验码的散列函数，利用除法及余数的原理来做错误侦测。

2.5 DES

DES 加密算法是一种 分组密码，以 64 位为 分组对数据 加密，它的 密钥长度 是 56 位，加密解密 用 同一算法。

DES 加密算法是对 密钥 进行保密，而 公开算法，包括加密和解密算法。这样，只有掌握了和发送方 相同密钥 的人才能解读由 DES加密算法加密的密文数据。因此，破译 DES 加密算法实际上就是 搜索密钥的编码。对于 56 位长度的 密钥 来说，如果用 穷举法 来进行搜索的话，其运算次数为 2 ^ 56 次。

2.6 3DES

是基于 DES 的 对称算法，对 一块数据 用 三个不同的密钥 进行 三次加密，强度更高。

2.7 AES

AES，Advanced Encryption Standard，高级加密标准，对称加密算法。AES 加密算法是密码学中的 高级加密标准，该加密算法采用 对称分组密码体制，密钥长度的最少支持为 128 位、 192 位、256 位，分组长度 128 位，算法应易于各种硬件和软件实现。这种加密算法是美国联邦政府采用的 区块加密标准。

AES 本身就是为了取代 DES 的，AES 具有更好的 安全性、效率 和 灵活性。

AES

2.8 RSA

RSA，非对称加密算法，公钥加密、私钥解密，基于大质数的因式分解。RSA 加密算法是目前最有影响力的 公钥加密算法，并且被普遍认为是目前 最优秀的公钥方案 之一。RSA 是第一个能同时用于 加密 和 数字签名 的算法，它能够 抵抗 到目前为止已知的 所有密码攻击，已被 ISO 推荐为公钥数据加密标准。

RSA 加密算法 基于一个十分简单的数论事实：将两个大 素数 相乘十分容易，但想要对其乘积进行 因式分解 却极其困难，因此可以将 乘积 公开作为 加密密钥。

非对称加密算法流程 RSA加密过程

2.9 ECC

ECC 也是一种 非对称加密算法，主要优势是在某些情况下，它比其他的方法使用 更小的密钥，比如 RSA 加密算法，提供 相当的或更高等级 的安全级别。不过一个缺点是 加密和解密操作 的实现比其他机制 时间长 (相比 RSA 算法，该算法对 CPU 消耗严重)。

为什么质数能用于加密算法？

这个问题就要涉及到大数的质因数分解。如果把一个由较小的两个质数相乘得到一个合数，将其分解成两个质数（除了1和自身的组合之外）很容易，例如，51的两个质因数为3和17。然而，如果两个很大的质数相乘之后得到一个非常大的合数，想要逆过来把该数分解成两个质数非常困难。例如，511883，分解成两个质因数之后为557和919；2538952327（超过25亿），分解成两个质因数之后为29179和87013，这个难度明显要比上一个数大得多。

截至2019.01，目前已知最大的质数是2^825899331，这个数拥有超过2486万位。即便是超级计算机，也很难有效对两个质数相乘得到的合数进行质因数分解，所以这样的原理可以用于加密算法。

3 排序算法(10种)

排序算法的时间复杂度

3.1 选择排序(SelectionSort)~O(n^2)不稳定

基本思路：每次找出最小的放最左边

  1. 遍历数组找出最小元素，移动到数组a[0]位置；
  2. 继续遍历数组找出最小元素，移动到数组a[1]位置；
  3. 依次遍历直到从小到大将整个数组排好序。

优缺点

  1. 最简单、最没用的排序算法，效率低，时间复杂度O(n^2)，不稳定。

改进点

  1. 外循环可以减少一次，只需要执行array.length-1次即可；
  2. 内循环可以减少一半次数，每次遍历可以找出最小值和最大值，最小值放数组左边，最大值放数组右边。

代码示例

3.2 冒泡排序(BubbleSort)~O(n^2)稳定

基本思路：两两比较交换

  1. 比较两个相邻元素，如果前一个比后一个大，则交换这两个元素，每次循环找出最大元素放到数组右边，依次循环，直到从小到大排好序。

优缺点

  1. 思路简单，效率低，时间复杂度O(n^2)，稳定。

代码示例

public static void bubbleSort1(int [] a, int n){
        int i, j;
        
        for(i=0; i<n; i++){//表示n 次排序过程。
            for(j=1; j<n-i; j++){
                if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换
                    //交换a[j-1]和a[j]
                    int temp;
                    temp = a[j-1];
                    a[j-1] = a[j];
                    a[j]=temp;
                }
            }
        }
    }

3.3 插入排序(InsertSort)~O(n^2)稳定

基本思路：每次插入与前面比较交换

  1. 每插入一个元素跟前一个元素比较，如果a[j]<a[j-1]就交换，依次比较交换，直到从小到大排好序；
  2. 对基本有序的数组最有用。

优缺点

  1. 思路简单，效率低，时间复杂度O(n^2)，稳定。

代码示例

public void sort(int arr[]) {
        for(int i =1; i<arr.length;i++) {
            //插入的数
            int insertVal = arr[i];
            //被插入的位置(准备和前一个数比较)
            int index = i-1;
            //如果插入的数比被插入的数小
            while(index>=0&&insertVal<arr[index]) {
                //将把arr[index] 向后移动
                arr[index+1]=arr[index];
                //让index 向前移动
                index--;
            }
            //把插入的数放入合适位置
            arr[index+1]=insertVal;
        }
    }

3.4 希尔排序(ShellSort)~O(n^1.3)不稳定

基本思路：按照缩进的间隔序列排序

  1. 希尔排序是改进的插入排序，比插入排序效率高，时间复杂度O(n^1.3)，不稳定；
  2. 每次按照一定间隔排序，间隔从大到小，最后要按照间隔为1排序。

优缺点

  1. 间隔大的时候移动次数少，间隔小的时候移动距离短，不稳定。

希尔排序间隔序列

代码示例

private void shellSort(int[] a) {
        int dk = a.length/2;
        while( dk >= 1 ){
            ShellInsertSort(a, dk);
            dk = dk/2;
        }
    }
    
    private void ShellInsertSort(int[] a, int dk) {
        //类似插入排序，只是插入排序增量是1，这里增量是dk,把1 换成dk 就可以了
        for(int i=dk;i<a.length;i++){
            if(a[i]<a[i-dk]){
                int j;
                int x=a[i];//x 为待插入元素
                a[i]=a[i-dk];
                for(j=i-dk; j>=0 && x<a[j];j=j-dk){
                    //通过循环，逐个后移一位找到要插入的位置。
                    a[j+dk]=a[j];
                }
                a[j+dk]=x;//插入
            }
        }
    }

3.5 归并排序(MergeSort)~O(nlogn)稳定

基本思路：不停合并排好序的子序列

  1. 待排序列按照两个或两个以上元素分为若干子序列，在各自子序列排好序；
  2. 继续扩大子序列继续排，直到整体有序
public class MergeSortTest {
    public static void main(String[] args) {
        int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
        print(data);
        mergeSort(data);
        System.out.println("排序后的数组：");
        print(data);
    }
    public static void mergeSort(int[] data) {
        sort(data, 0, data.length - 1);
    }
    public static void sort(int[] data, int left, int right) {
        if (left >= right)
            return;
// 找出中间索引
        int center = (left + right) / 2;
// 对左边数组进行递归
        sort(data, left, center);
// 对右边数组进行递归
        sort(data, center + 1, right);
// 合并
        merge(data, left, center, right);
        print(data);
    }
    /**
     * 将两个数组进行归并，归并前面2 个数组已有序，归并后依然有序
     *
     * @param data
     * 数组对象
     * @param left
     * 左数组的第一个元素的索引
     * @param center
     * 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引
     * @param right
     * 右数组最后一个元素的索引
     */
    public static void merge(int[] data, int left, int center, int right) {
// 临时数组
        int[] tmpArr = new int[data.length];
// 右数组第一个元素索引
        int mid = center + 1;
// third 记录临时数组的索引
        int third = left;
// 缓存左数组第一个元素的索引
        int tmp = left;
        while (left <= center && mid <= right) {
// 从两个数组中取出最小的放入临时数组
            if (data[left] <= data[mid]) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
// 剩余部分依次放入临时数组（实际上两个while 只会执行其中一个）
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
// 将临时数组中的内容拷贝回原数组中
// （原left-right 范围的内容被复制回原数组）
        while (tmp <= right) {
            data[tmp] = tmpArr[tmp++];
        }
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }
}

3.6 堆排序(HeapSort)~O(nlogn)不稳定

3.7 快速排序(QuickSort)~O(nlogn)不稳定

基本思路：小于基准值的放左边，大于基准值的放右边

快速排序最差情况会退化为冒泡排序，最坏情况下的时间复杂度为O(n^2)

快速排序思路

3.8 桶排序(BucketSort)~O(n+k)稳定

待排序列划分为n个大小相同的区间，区间叫做桶，每个桶内各自排序，最后合并。

  1. 找出待排序数组中的最大值max、最小值min
  2. 我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/
    arr.length+1
  3. 遍历数组 arr，计算每个元素 arr[i] 放的桶
  4. 每个桶各自排序
public static void bucketSort(int[] arr){
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < arr.length; i++){
            13/04/2018 Page 241 of 283
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
//创建桶
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
        for(int i = 0; i < bucketNum; i++){
            bucketArr.add(new ArrayList<Integer>());
        }
//将每个元素放入桶
        for(int i = 0; i < arr.length; i++){
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }
//对每个桶进行排序
        for(int i = 0; i < bucketArr.size(); i++){
            Collections.sort(bucketArr.get(i));
        }
    }

3.9 计数排序(CountingSort)~O(n+k)稳定

计数排序是桶排序的特殊情况，计数排序的每个桶里面只有一个元素。

3.10 基数排序(RadixSort)~O(n*k)稳定

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

public class radixSort {
        inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,2
            5,53,51};
        public radixSort(){
            sort(a);
            for(inti=0;i<a.length;i++){
                System.out.println(a[i]);
            }
        }
        public void sort(int[] array){
//首先确定排序的趟数;
            int max=array[0];
            for(inti=1;i<array.length;i++){
                if(array[i]>max){
                    13/04/2018 Page 242 of 283
                    max=array[i];
                }
            }
            int time=0;
//判断位数;
            while(max>0){
                max/=10;
                time++;
            }
//建立10 个队列;
            List<ArrayList> queue=newArrayList<ArrayList>();
            for(int i=0;i<10;i++){
                ArrayList<Integer>queue1=new ArrayList<Integer>();
                queue.add(queue1);
            }
//进行time 次分配和收集;
            for(int i=0;i<time;i++){
//分配数组元素;
                for(intj=0;j<array.length;j++){
//得到数字的第time+1 位数;
                    int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i);
                    ArrayList<Integer>queue2=queue.get(x);
                    queue2.add(array[j]);
                    queue.set(x, queue2);
                }
                int count=0;//元素计数器;
//收集队列元素;
                for(int k=0;k<10;k++){
                    while(queue.get(k).size()>0){
                        ArrayList<Integer>queue3=queue.get(k);
                        array[count]=queue3.get(0);
                        queue3.remove(0);
                        count++;
                    }
                }
            }
        }
    }

4 查找算法

查找算法的时间复杂度

4.1 顺序查找/线性查找~O(n)

无序查找的一种，适合于存储结构是顺序存储或链接存储的线性表，ASL=n(n+1)/2，时间复杂度为O(n)。

4.2 二分查找/折半查找~O(logn)

有序查找算法的一种，待查找序列如果不是有序的，先要进行排序操作。查找时候先和中间值比较，小则往左边比较，大则往右边比较。

4.3 插值查找~O(loglogn)

有序查找算法的一种，在二分查找/折半查找基础上改进的，查找点不是1/2开始，而是自适应的，插值查找的查找点mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

4.4 斐波那契查找~O(logn)

有序查找算法的一种，基于二分查找/折半查找改进的，查找基准点不是中间元素，而是斐波那契数-1。

4.5 树表查找~O(logn)

4.6 分块查找~O(logn)

分块查找，又称为索引顺序查找，是顺序查找的一种改进方法。

4.7 哈希查找~O(1)

哈希散列查找，时间和空间的折中。

5 TopK问题

5.1 TopK业务场景

常见TopK问题

  1. 有10000000个记录，这些查询串的重复度比较高，如果除去重复后，不超过3000000个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的10个查询串，要求使用的内存不能超过1GB。
  2. 有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。
  3. 有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。
  4. 提取某日访问网站次数最多的那个IP。
  5. 10亿个整数找出重复次数最多的100个整数。
  6. 搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。
  7. 有1000万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。

问题抽象

5.2 TopK解决方案

5.3 TopK实际业务场景解决方案

5.4 重复问题

在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题，一般可以通过位图法实现。例如，已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。 本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位，那么存储8位整数大约需要99MB。因为1B=8bit，所以99Mbit折合成内存为99/8=12.375MB的内存，即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

6 常用算法

上一篇 下一篇

猜你喜欢

热点阅读