代码

快速排序

注意一共3个函数，主函数、quickSort()、partition();

• 主函数负责将初始区间给quickSort()；
• quickSort()负责进行递归调用；
• partition()负责返回下一个pivot，将传入的数据段按pivot大小分开。

代码

class Solution {
public:
    vector<int> MySort(vector<int>& arr) { //**1
        // write code here
        if ( arr.empty() ) {
            return arr;
        }
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }

    void quickSort(vector<int> & arr, int start, int end) {//**2
        if ( start < end ) {
            int mid = partition(arr, start, end);
            quickSort(arr, start, mid -1);
            quickSort(arr,  mid +1, end);
        }
    }

    int partition(vector<int> & arr, int start, int end) {//**3
        int pivot = arr[end];
        int i = start;
        for ( int j = start; j < end; j++ ) {
            if ( arr[j] < pivot ) {
                swap(arr[i], arr[j]);
                i++;
            }
        }
        swap(arr[i], arr[end]);

        return i;
    }

    int randomPartition(vector<int> & arr, int start, int end) {//仅作为提高速度防止最坏情况
        srand(time(NULL));
        int pi = start + rand() % (end - start);
        swap(arr[pi],arr[end-1]);
        return partition(arr, start, end);
    }

};

归并排序

注意一共3个函数，主函数、divide()、merge();

• 主函数负责输入参数初次调用divide()；
• divide()负责递归，先调用两次divide()(左右分边)，再调用merge();
• merge()负责将输入的数据按大小次序安排好 ( 注意区间分的是 [start,mid]和[mid+1,end] )。

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if ( arr.empty() ) {
            return arr;
        }
        mergeSortDivide(arr, 0, arr.size() - 1);
        return arr;
    }

    void mergeSortDivide(vector<int> & arr, int start, int end) {
        if ( start < end ){
            int mid = start + (end - start) / 2;
            mergeSortDivide(arr, start, mid);
            mergeSortDivide(arr, mid+1, end);

            merge(arr,start,mid,end);
        }
        return;
    }

    void merge(vector<int> & arr, int start, int mid, int end) {
        vector<int> tmp(end-start+1);
        int i = start, j = mid+1; //注意此处分配
        int K = 0;
        while ( i <= mid && j <= end ) {
            if ( arr[i] <= arr[j] ) {
                tmp[K++] = arr[i++];
            } else if ( arr[j] <= arr[i]) {
                tmp[K++] = arr[j++];
            }
        }

        while ( i <= mid ) {
            tmp[K++] = arr[i++];
        }
        while ( j <= end ) {
            tmp[K++] = arr[j++];
        }
        for ( int index = 0; index < tmp.size(); index++){
            arr[index + start] = tmp[index];
        }

    }
};

设计LRU(最近最少使用)缓存结构

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

思路

详见代码

代码

class Solution {
public:
    int cap;
    list<pair<int, int>> dataList;
    unordered_map<int, list<pair<int, int>>::iterator> mp;

    Solution(int capacity){
        cap = capacity;        
    }

    int get(int key) {
        // 1、查询是否在缓存中
        auto itermp = mp.find(key);
        if ( itermp != mp.end() ) {
            // 2、在缓存中，需要在链表中擦除。
            int value = mp[key]->second; //注意这里直接使用mp[key]->second
            dataList.erase(mp[key]);
            // 3、把数据放到链表头
            dataList.push_front(make_pair(key, value));
            // 4、hash原来存储的失效，需要重新设置
            mp[key] = dataList.begin();
            // 5、返回value值
            return value;
        } else {
            return -1;
        }
    }

    void set(int key, int value){
        // 1、查询是否在缓存中
        auto itermp = mp.find(key);
        if ( itermp != mp.end() ) {
            // 2、在缓存中，需要在链表中擦除。
            dataList.erase(mp[key]);
        }
        // 4、缓存已经满了
        else if ( dataList.size() >= cap ) {
            // 4.1 hash处要删除
            mp.erase(dataList.back().first);
            // 4.2 链表也要删除尾巴部分
            dataList.pop_back();
        }
        // 3、把数据放到链表头
        dataList.push_front(make_pair(key, value));
        // 4、hash原来存储的失效，需要重新设置
        mp[key] = dataList.begin();
    }
};

概念

红黑树

红黑树的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。

先给图：

由上图可以很明显的看到红黑树可以完全代替2-3树，下面给出红黑树的定义：

​ (1) 每个节点或者是黑色，或者是红色。
​ (2) 根节点是黑色。
​ (3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
​ (4) 如果一个节点是红色的，则它的子节点必须是黑色的。【红属性】
​ (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。【黑属性】

先给出红黑树Node的定义：

private class Node<T> {
        T key;
        Node leftChild = null;
        Node rightChild = null;
        boolean color;

        Node(T key,boolean color) {
            this.key = key;
            this.color = color;
        }
    }

红黑树高度最多 2log(n+1)，可得时间复杂度为log(n)。

当插入一个元素到红黑树中时，需要沿着插入点到根节点的路径上向上移动，对于经过的每个结点，有如下操作：

1. 如果右子节点是红色的而左子节点也是红色的，进行右旋转。(右，左)
2. 如果左子节点是红色的且它的左子节点也是红色的，进行右旋转（左，左）
3. 如果左右子节点均为红色，进行颜色转换。

	现象说明	处理策略
Case 1	当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。	(01) 将“父节点”设为黑色。 (02) 将“叔叔节点”设为黑色。 (03) 将“祖父节点”设为“红色”。 (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
Case 2	当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子	(01) 将“父节点”作为“新的当前节点”。 (02) 以“新的当前节点”为支点进行左旋。
Case 3	当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子	(01) 将“父节点”设为“黑色”。 (02) 将“祖父节点”设为“红色”。 (03) 以“祖父节点”为支点进行右旋。

1. (Case 1)叔叔是红色

2. (Case 2)叔叔是黑色，且当前节点是右孩子

3. (Case 3)叔叔是黑色，且当前节点是左孩子

当删除一个结点的时候：

将x所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：
a) x指向一个”红+黑”节点。此时，将x设为一个”黑”节点即可。
b) x指向根。此时，将x设为一个”黑”节点即可。
c) 非前面两种姿态。

30张图带你彻底理解红黑树

红黑树平均插入效率：lgN

红黑树平均查询效率：lgN

排序算法

排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，对基于比较的排序算法而言，元素交换的次数可能会少一些。

堆栈区别

数据结构方面

栈，它是一种具有后进先出性质的数据结构，也就是说后存放的先取，先存放的后取。这就如同我们要取出放在箱子里面底下的东西（放入的比较早的物体），我们首先要移开压在它上面的物体（放入的比较晚的物体）。

堆就不同了，堆是一种经过排序的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆（完全二元树或者是近似完全二元树）。堆的特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆。由于堆的这个特性，常用来实现优先队列，堆的存取是随意，这就如同我们在图书馆的书架上取书，虽然书的摆放是有顺序的，但是我们想取任意一本时不必像栈一样，先取出前面所有的书，书架这种机制不同于箱子，我们可以直接取出我们想要的书。

C++内存方面

内存中的栈区处于相对较高的地址以地址的增长方向为上的话，栈地址是向下增长的。

栈中分配局部变量空间，堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量，全局变量空间的；只读区是分配常量和程序代码空间的；以及其他一些分区。

申请方式和回收方式不同

栈（英文名称是stack）是系统自动分配空间的，例如我们定义一个 char a；系统会自动在栈上为其开辟空间。

而堆（英文名称是heap）则是程序员根据需要自己申请的空间，例如malloc（10）；开辟十个字节的空间。

由于栈上的空间是自动分配自动回收的，所以栈上的数据的生存周期只是在函数的运行过程中，运行后就释放掉，不可以再访问。而堆上的数据只要程序员不释放空间，就一直可以访问到，不过缺点是一旦忘记释放会造成内存泄露。

申请后系统的响应

栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆。

申请效率的比较

栈：由系统自动分配，速度较快。但程序员是无法控制的。

堆：是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

内存泄露如何检测

Linux平台下的内存泄漏检测

mtrace 工具的主要思路是在我们的调用内存分配和释放的函数中装载 “钩子（hook）” 函数，通过 “钩子（hook）” 函数打印的日志来帮助我们分析对内存的使用是否存在问题。对该工具的使用包括两部分内容，一个是要修改源码，装载 hook 函数，另一个是通过运行修改后的程序，生成特殊的 log 文件，然后利用 mtrace 工具分析日志，判断是否存在内存泄露以及定位可能发生内存泄露的代码位置。

1. 修改源码，装载 “hook” 函数（mcheck.h头文件以及 mtrace() 函数用于开启内存分配跟踪，muntrace() 用于取消内存分配跟踪。）；

2. 生成日志文件并分析定位问题（在实际运行程序之前还有一件要做的事情是需要告诉 mtrace （即前文提到的 hook 函数）生成日志文件的路径）；

3. 利用 addr2line 这个工具，基于该机器码（0x400624）反推出源文件的行数。

程序崩溃如何检测

当程序crash的时候使用gdb产生core dump文件对于调试程序是很有帮助的，特别对于难以复现的crash，准确定位crash的位置对分析crash原因更有意义。

之后调试core dump文件，调试方法为：gdb program coredump文件

MySQL一条语句执行过程

查询语句

1. 先检查该语句是否有权限，如果没有权限，直接返回错误信息，如果有权限，在 MySQL8.0 版本以前，会先查询缓存，以这条 sql 语句为 key 在内存中查询是否有结果，如果有直接缓存，如果没有，执行下一步。

2. 通过分析器进行词法分析，提取 sql 语句的关键元素，比如提取上面这个语句是查询 select，提取需要查询的表名为 tb_student,需要查询所有的列，查询条件是这个表的 id=‘1’。然后判断这个 sql 语句是否有语法错误，比如关键词是否正确等等，如果检查没问题就执行下一步。

3. 接下来就是优化器进行确定执行方案，上面的 sql 语句，可以有两种执行方案：

   a. 先查询学生表中姓名为“张三”的学生，然后判断是否年龄是 18。
   b. 先找出学生中年龄 18 岁的学生，然后再查询姓名为“张三”的学生。

   那么优化器根据自己的优化算法进行选择执行效率最好的一个方案（优化器认为，有时候不一定最好）。

4. 那么确认了执行计划后就准备开始执行了。进行权限校验，如果没有权限就会返回错误信息，如果有权限就会调用数据库引擎接口，返回引擎的执行结果。

更新语句

以上就是一条查询 sql 的执行流程，那么接下来我们看看一条更新语句如何执行的呢？sql 语句如下：

update tb_student A set A.age='19' where A.name=' 张三 ';

我们来给张三修改下年龄，在实际数据库肯定不会设置年龄这个字段的，不然要被技术负责人打的。其实条语句也基本上会沿着上一个查询的流程走，只不过执行更新的时候肯定要记录日志啦，这就会引入日志模块了，MySQL 自带的日志模块式 binlog（归档日志） ，所有的存储引擎都可以使用，我们常用的 InnoDB 引擎还自带了一个日志模块 redo log（重做日志），我们就以 InnoDB 模式下来探讨这个语句的执行流程。

​ 流程如下：

先查询到张三这一条数据，如果有缓存，也是会用到缓存。
然后拿到查询的语句，把 age 改为 19，然后调用引擎 API 接口，写入这一行数据，InnoDB 引擎把数据保存在内存中，同时记录 redo log，此时 redo log 进入 prepare 状态，然后告诉执行器，执行完成了，随时可以提交。
执行器收到通知后记录 binlog，然后调用引擎接口，提交 redo log 为提交状态。
更新完成。

进程和线程

• 进程是系统资源分配的最小单位；
• 线程是cpu操作和调度的最小单位，本质是一组寄存器的状态，是操作系统对寄存器状态的抽象。

进程和线程独有的特点

进程

1. 一个线程只能属于一个进程，而一个进程可以有多个线程。
2. 进程编程调试简单可靠性高，但是创建销毁开销大；线程正相反，开销小，切换速度快，但是编程调试相对复杂。
3. 进程间不会相互影响 ；线程一个线程挂掉将导致整个进程挂掉。

进程间通信：

进程间通信主要包括管道（匿名、命名）、系统IPC（包括消息队列<消息的链接表，存放在内核中。>、信号量、信号、共享内存<最快的一种IPC，因为进程是直接对内存进行存取>等）、以及套接字socket。

线程

1. 进程中的线程共享地址空间，也就是同样的动态内存，映射文件，目标代码等等），打开的文件队列和其他内核资源，进程间的通信的代价远大于线程间的通信，。
2. 线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

线程共享的资源：

代码区（编译后的代码）

数据区（全局变量，静态变量。）

堆区（C/C++中用malloc或者new出来的数据就存放在这个区域，只要知道指针，任何一个线程都可以访问指针指向的数据，因此堆区也是线程共享的属于进程的资源。）

栈区（如果一个线程能拿到来自另一个线程栈帧上的指针，那么该线程就可以改变另一个线程的栈区，也就是说这些线程可以任意修改本属于另一个线程栈区中的变量。）

动态链接库（动态链接的部分生成的库就是我们熟悉的动态链接库，在Windows下是以DLL结尾的文件，在Linux下是以so结尾的文件。）

文件（如果程序在运行过程中打开了一些文件，那么进程地址空间中还保存有打开的文件信息，进程打开的文件也可以被所有的线程使用，这也属于线程间的共享资源。）

线程间通信：

临界区、互斥量Synchronized/Lock、信号量Semphare、事件(信号)Wait/Notify。

段页式内存管理

页式存储管理能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来，就形成了段页式存储管理方式。

段页式管理就是将程序分为多个逻辑段，在每个段里面又进行分页，即将分段和分页组合起来使用。这样做的目的就是想同时获得分段和分页的好处，但又避免了单独分段或单独分页的缺陷。

段长是可变的，页的大小是固定的。

分页、分段的优缺点分析

C++中的段

• BSS段：BSS段（bss segment）通常是指用来存放程序中未初始化的全局变量的一块内存区域。BSS是英文Block Started by Symbol的简称。BSS段属于静态内存分配。

• 数据段：数据段（data segment）通常是指用来存放程序中已初始化的全局变量的一块内存区域。数据段属于静态内存分配。

• 代码段：代码段（code segment/text segment）通常是指用来存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域通常属于只读, 某些架构也允许代码段为可写，即允许修改程序。在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等。

• 堆（heap）：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）

• 栈(stack)：栈又称堆栈， 是用户存放程序临时创建的局部变量，也就是说我们函数括弧“{}”中定义的变量（但不包括static声明的变量，static意味着在数据段中存放变量）。除此以外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区

C++中的五个区

1、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
2、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后有系统释放
4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。

C++中虚表位于只读数据段（.rodata），也就是C++内存模型中的常量区；而虚函数则位于代码段（.text），也就是C++内存模型中的代码区。

Linux网络故障排查

1. 检查网线、网卡 （是否都亮灯）
2. 确定网线是通的之后，再看物理网卡（ifconfig看网卡名，ethtool -i ethX看网卡驱动。）
3. 网卡物理层没有问题之后，再看网卡配置（ifconfig就可以看到ip、掩码，网卡信息在/etc/sysconfig/network-scripts/ifcfg-ethX）
4. 检查自身路由表是否正确（ping网关，可能默认网关是内网网卡，route delete/add default gw 命令。）
5. 检查DNS（nslookup诊断DNS服务器。）
6. 检查路由（traceroute是用来跟踪从发出数据包的主机到目标主机之间所经过的网关的工具。）
7. 端口检查（检查的是远端主机的服务端口是否打开。）
8. 防火墙问题（iptables -L可查看iptables的规则）

哈希表

哈希冲突解决方案：

1. 线性探测
2. 二次探测
3. 随机探测
4. 再散列法（不同的散列函数）
5. 链地址法（哈希表采用的方法，同义词子表）
6. 公共溢出区法（所有冲突的关键字建立一个公共的溢出区）

GET和POST差别

GET和POST本质上就是TCP链接，并无差别。但是由于HTTP的规定和浏览器/服务器的限制，导致他们在应用过程中体现出一些不同。

• GET参数通过URL传递，POST放在Request body中。

• GET请求只能进行url编码，而POST支持多种编码方式。

• GET产生一个TCP数据包；POST产生两个TCP数据包。

  • 对于GET方式的请求，浏览器会把http header和data一并发送出去，服务器响应200（返回数据）；
  • 而对于POST，浏览器先发送header，服务器响应100 continue，浏览器再发送data，服务器响应200 ok（返回数据）。

• 本质上没差别，都是TCP连接。只不过因为HTTP的规定和浏览器/服务器的限制和人们日常开发中的约定俗成，导致他们在应用过程中体现出一些不同。get获取资源，post传输资源

• get产生一个TCP数据包将http header和data一起发送，post产生两个数据包将http header和data分开发送，但是火狐就把post发送一次，说到底协议是协议，遵不遵守就是开发者的事情。

• GET参数通过URL传递，POST放在Request body中。通过这个差别可以引导出其他方面的，只需要对url和request body做分析即可。url回退安全，参数相对来说更容易暴露，数据类型只接受ASCII(空格是%20)，url有长度限制(http1.1协议没限制，浏览器有限制)，保存在浏览器历史，默认被浏览器Cache。

C++11新特性

auto

左值右值

众所周知C++11新增了右值引用，左值可以取地址、位于等号左边；而右值没法取地址，位于等号右边。

右值引用的标志是&&，顾名思义，右值引用专门为右值而生，可以指向右值，不能指向左值：

int &&ref_a_right = 5; // ok

int a = 5;
int &&ref_a_left = a; // 编译不过，右值引用不可以指向左值

ref_a_right = 6; // 右值引用的用途：可以修改右值

---