八股

数据结构

树

AVL树

1
2
3
4
5
6
7
8
9
/* AVL 树节点类 */
struct TreeNode {
    int val{};          // 节点值
    int height = 0;     // 节点高度
    TreeNode *left{};   // 左子节点
    TreeNode *right{};  // 右子节点
    TreeNode() = default;
    explicit TreeNode(int x) : val(x){}
};

一棵 AVL 树的任意节点的平衡因子皆为 -1，0，1
四种失衡情况，分别需要采用右旋、先左旋后右旋、先右旋后左旋、左旋的操作。

B-树

特点：

  1. 多路，非二叉树
  2. 每个节点既保存索引，又保存数据
  3. 搜索时相当于二分查找

B+树

  1. 多路非二叉
  2. 只有叶子节点保存数据
  3. 搜索时相当于二分查找
  4. 增加了相邻节点的指向指针。

B+树由于数据全部存储在叶子节点，并且通过指针串在一起，这样就很容易的进行区间遍历甚至全部遍历

堆

二叉堆

就是完全二叉树，定点开始为 1，k 的左子为 2k，右子 2k+1，父 k << 1。

优先队列/最小堆

保留顶点有序。三个特性：

  1. 每个父节点都大于等于其所有后代结点。
  2. 堆的根节点含有堆中最大（或者最小）的对象。
  3. 堆中以任意节点为根节点的子树仍然是堆。
  • 插入：新元素放在最后，向上浮
  • 删除：顶端元素移除后，把堆的最后一个元素放到堆顶，然后不断向下维护堆的特性

堆排序

堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

图

最小生成树（MST）

Prim算法

算法简单描述

  1. 输入：一个加权连通图，其中顶点集合为V，边集合为E；
  2. 初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
  3. 重复下列操作，直到Vnew = V：
    a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4. 输出：使用集合Vnew和Enew来描述所得到的最小生成树。

用反证法证明：如果不是，有更短的，加入生成环，与每次生成最短矛盾。

Kruskal算法

  1. 记Graph中有v个顶点，e个边

  2. 新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

  3. 将原图Graph中所有e个边按权值从小到大排序

  4. 循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中。如果这条边连接的两个节点于图Graphnew中不在同一个连通分量中，添加这条边到图Graphnew中

证明用数学归纳法。

Dijkstra

带权的单源最短路径问题。通过保留目前为止所找到的每个顶点v，从s出发到v的最短路径来工作。

DV问题

毒性逆转。。。

网络

七层网络模型

请不要把暗号告诉任何人（Please Do Not Tell the Secret Password to Anyone）。
Please 物理层（Physical Layer） IEEE 802.1A, IEEE 802.2到IEEE 802.11
Do 数据链路层（Data Link Layer） FDDI, Ethernet, Arpanet, PDN, SLIP, PPP
Not 网络层（Network Layer） IP, ICMP, ARP, RARP, AKP, UUCP
Tell （the） 传输层（Transport Layer） TCP, UDP
Secret 会话层（Session Layer） SMTP, DNS
Password （to） 表示层（Presentation Layer） Telnet, Rlogin, SNMP, Gopher
Anyone 应用层（Application Layer） HTTP、TFTP, FTP, NFS, WAIS、SMTP

TCP UDP

websocket

I/O 多路复用机制

select

最基本的 I/O 多路复用方式，缺点是

  1. 每次调用 select 都需要在内核遍历传递进来的所有fd，在fd很多时开销也很大；
  2. 有最大描述符限制。单个进程能够监视的文件描述符的数量存在最大限制，在Linux上一般为1024，可以通过修改宏定义甚至重新编译内核的方式提升这个限制，但是这样也会造成效率的降低；
  3. 每次都要调用 select ，都需要把 fd 集合从用户态拷贝到内核态，在fd很多时开销会很大；

int select(int numfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);

函数参数

  • numfds：文件描述符的最大值＋1（为了限制检测文件描述符的范围）
  • readfds：包含所有因为状态变为可读而触发select函数返回文件描述符
  • writefds：包含所有因为状态变为可写而触发select函数返回文件描述符
  • exceptfds：包含所有因为状态发生特殊异常而触发select函数返回文件描述符
  • timeout：表示阻塞超时时限

返回值

  • 当为-1的时候表示出错
  • 当为0的时候表示超时
  • 当大于0则成功

基本思路，把要检测的文件描述符加载到 fd_set 类型的集合中，然后调用 select 函数检测加载到集合中的文件描述符；

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
#include <stdio.h>
#include <stdlib.h>
#include <sys/select.h>
#include <unistd.h>

int main() {
    fd_set readfds;
    struct timeval timeout;
    int ret;

    // 初始化文件描述符集合
    FD_ZERO(&readfds);
    FD_SET(STDIN_FILENO, &readfds);

    // 设置超时时间
    timeout.tv_sec = 5;
    timeout.tv_usec = 0;

    printf("Waiting for input, timeout in 5 seconds...\n");
    // 调用 select 函数，监控文件描述符
    ret = select(STDIN_FILENO + 1, &readfds, NULL, NULL, &timeout);

    if (ret == -1) {
        perror("select");
        exit(EXIT_FAILURE);
    } else if (ret == 0) {
        printf("Timeout occurred! No data after 5 seconds.\n");
    } else {
        if (FD_ISSET(STDIN_FILENO, &readfds)) {
            char buffer[1024];
            read(STDIN_FILENO, buffer, sizeof(buffer));
            printf("Data read: %s\n", buffer);
        }
    }

    return 0;
}

poll

int poll(struct pollfd *fds, unsigned int nfds, int timesout);

函数参数：

  • fds 表示一个pollfd结构的数组。用来保存想要监听的文件描述符及其注册（绑定）的相应事件
  • nfds 表示监听事件集合的大小
  • timeout 指定poll的超时值。当timeout为-1时，就会一直阻塞，直到某个事件发生；当timeout为0时，表示立即返回。

返回值：

当为-1的时候表示失败，当为0的时候表示超时，当为大于0的整数的时候表示执行成功，表示文件描述符的个数。

不同与select使用三个位图来表示三个fdset的方式，poll使用一个 pollfd的指针实现。

1
2
3
4
5
struct pollfd {
    int fd; /* file descriptor */
    short events; /* requested events to watch */
    short revents; /* returned events witnessed */
    };
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
#include <stdio.h>
#include <stdlib.h>
#include <poll.h>
#include <unistd.h>

int main() {
    struct pollfd fds[1];
    int ret;

    // 设置文件描述符和事件
    fds[0].fd = STDIN_FILENO;
    fds[0].events = POLLIN;

    printf("Waiting for input, timeout in 5 seconds...\n");
    // 调用 poll 函数，设置 5 秒超时
    ret = poll(fds, 1, 5000);

    if (ret == -1) {
        perror("poll");
        exit(EXIT_FAILURE);
    } else if (ret == 0) {
        printf("Timeout occurred! No data after 5 seconds.\n");
    } else {
        if (fds[0].revents & POLLIN) {
            char buffer[1024];
            read(STDIN_FILENO, buffer, sizeof(buffer));
            printf("Data read: %s\n", buffer);
        }
    }

    return 0;
}

epoll

epoll 使用一个事件通知机制，避免了每次调用时遍历整个文件描述符集合。

int epoll_create(int size);

int epoll_ctl(int epfd, int op, int fd, struct epoll_event* event);
函数参数

  • epfd：事件表的文件描述符
  • op：何种操作，包括 EPOLL_CTL_ADD，EPOLL_CTL_DEL，EPOLL_CTL_MOD，分别实现对fd的监听事件进行添加、删除、修改
  • fd：需要监听的文件描述符
  • event：告诉内核需要监听什么事epoll_event 结构如下：

int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout)

函数参数：

  • epfd：事件表的文件描述符
  • events：从内核得到事件的集合
  • maxevents：事件集合的大小（不能大于创建时的size）
  • timeout：超时时间
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
#include <stdio.h>
#include <stdlib.h>
#include <sys/epoll.h>
#include <unistd.h>

int main() {
    int epfd = epoll_create1(0);
    struct epoll_event event, events[1];
    int ret;

    if (epfd == -1) {
        perror("epoll_create1");
        exit(EXIT_FAILURE);
    }

    // 设置事件
    event.events = EPOLLIN;
    event.data.fd = STDIN_FILENO;

    if (epoll_ctl(epfd, EPOLL_CTL_ADD, STDIN_FILENO, &event) == -1) {
        perror("epoll_ctl");
        exit(EXIT_FAILURE);
    }

    printf("Waiting for input, timeout in 5 seconds...\n");
    // 调用 epoll_wait，等待事件
    ret = epoll_wait(epfd, events, 1, 5000);

    if (ret == -1) {
        perror("epoll_wait");
        exit(EXIT_FAILURE);
    } else if (ret == 0) {
        printf("Timeout occurred! No data after 5 seconds.\n");
    } else {
        if (events[0].data.fd == STDIN_FILENO) {
            char buffer[1024];
            read(STDIN_FILENO, buffer, sizeof(buffer));
            printf("Data read: %s\n", buffer);
        }
    }

    close(epfd);
    return 0;
}

水平触发
当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序可以不立即处理该事件。下次调用epoll_wait时，会再次响应应用程序并通知此事件。

边缘触发
当epoll_wait检测到描述符事件发生并将此事件通知应用程序，应用程序必须立即处理该事件。如果不处理，下次调用epoll_wait时，不会再次响应应用程序并通知此事件。所以在ET模式下，read一个fd的时候一定要把它的buffer读完，即读到read返回值小于请求值或遇到EAGAIN错误。

水平触发是只要读缓冲区有数据，就会一直触发可读信号，而边缘触发仅仅在空变为非空的时候通知一次

ET模式在很大程度上减少了epoll事件被重复触发的次数，因此效率要比LT模式高。epoll工作在ET模式的时候，必须使用非阻塞套接口，以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。

kqueue

kqueue 是 BSD 系统（包括 macOS）中的高效 I/O 事件通知机制。与 epoll 类似，kqueue 使用事件通知的机制来避免每次遍历整个文件描述符集合。(Ubuntu 没有)

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
#include <stdio.h>
#include <stdlib.h>
#include <sys/event.h>
#include <sys/time.h>
#include <unistd.h>

int main() {
    int kq = kqueue();
    struct kevent change, event;
    int ret;

    if (kq == -1) {
        perror("kqueue");
        exit(EXIT_FAILURE);
    }

    // 设置事件
    EV_SET(&change, STDIN_FILENO, EVFILT_READ, EV_ADD, 0, 0, NULL);

    printf("Waiting for input, timeout in 5 seconds...\n");
    // 调用 kevent，设置 5 秒超时
    struct timespec timeout = {5, 0};
    ret = kevent(kq, &change, 1, &event, 1, &timeout);

    if (ret == -1) {
        perror("kevent");
        exit(EXIT_FAILURE);
    } else if (ret == 0) {
        printf("Timeout occurred! No data after 5 seconds.\n");
    } else {
        if (event.ident == STDIN_FILENO) {
            char buffer[1024];
            read(STDIN_FILENO, buffer, sizeof(buffer));
            printf("Data read: %s\n", buffer);
        }
    }

    close(kq);
    return 0;
}

WSAEventSelect IOCP

windows

LibEvent

Libevent 之所以效率高，主要归功于其事件驱动模型和对多种高效 I/O 多路复用机制的支持。

基于事件驱动的非阻塞 I/O

Libevent 使用 事件驱动模型 来处理网络连接、文件描述符、定时器等异步事件。与传统的同步或阻塞 I/O 模型不同，事件驱动模型不会等待某个 I/O 操作完成后再处理下一个任务，而是通过事件的回调机制进行非阻塞处理。这种机制极大地提高了处理大量并发连接的效率，尤其是在高并发的网络服务中。由于 Libevent 使用事件驱动模型，它能够在事件触发时立即处理，减少了传统模型中等待或阻塞所导致的延迟。

I/O 多路复用机制

Libevent 能够自动选择操作系统上最有效的 I/O 多路复用机制

nginx

正则表达式

优先级从高到低

  • = ：进行普通字符精确匹配，也就是完全匹配。
  • ^~ ：表示普通字符匹配。使用前缀匹配。如果匹配成功，则不再匹配其它 location。
  • ~ ：区分大小写的匹配。
  • ~* ：不区分大小写的匹配。
  • !~ ：区分大小写的匹配取非。
  • !~* ：不区分大小写的匹配取非。
1
2
3
4
5
6
7
8
9
10
11
. 匹配任意单个字符（除了换行符）
^ 匹配字符串开始位置
$ 匹配字符串结束位置
* 重复前面的字符零次或多次
+ 重复前面的字符一次或多次
? 使前面的字符变为可选，出现零次或一次
[]字符集，匹配其中任一字符
\d 匹配数字
\w 匹配字母、数字或下划线
\s 匹配空白字符
() 用于创建捕获组，可以在后面用 $n 引用捕获的内容
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
location  = / {
  # 精确匹配 / ，主机名后面不能带任何字符串
  [ 规则 A ] 
}
 
location  / {
  # 因为所有的地址都以 / 开头，所以这条规则将匹配到所有请求
  # 但是正则和最长字符串会优先匹配
  [ 规则 B ] 
}
 
location /documents/ {
  # 匹配任何以 /documents/ 开头的地址，匹配符合以后，还要继续往下搜索
  # 只有后面的正则表达式没有匹配到时，这一条才会采用这一条
  [ 规则 C ] 
}
 
location ~ /documents/Abc {
  # 匹配任何以 /documents/ 开头的地址，匹配符合以后，还要继续往下搜索
  # 只有后面的正则表达式没有匹配到时，这一条才会采用这一条
  [ 规则 D ] 
}
 
location ^~ /images/ {
  # 匹配任何以 /images/ 开头的地址，匹配符合以后，停止往下搜索正则，采用这一条。
  [ 规则 E ] 
}
 
location ~* \.(gif|jpg|jpeg)$ {
  # 匹配所有以 gif,jpg或jpeg 结尾的请求
  # 然而，所有请求 /images/ 下的图片会被 [规则 E] 处理，因为 ^~ 优先级更高
  [ 规则 F ] 
}
 
location /images/ {
  # 字符匹配到 /images/，继续往下，会发现 ^~ 存在
  [ 规则 G ] 
}
 
location /images/abc {
  # 最长字符匹配到 /images/abc，继续往下，会发现 ^~ 存在
  [ 规则 H ] 
}
 
location ~ /images/abc/ {
  # 只有去掉 [规则 E] 才有效：先最长匹配 [规则 H] 开头的地址，继续往下搜索，匹配到这一条正则，采用
  [ 规则 I ] 
}

配置proxy_pass时路径拼接规则

在nginx中配置proxy_pass时，如果是按照^~匹配路径时,要注意proxy_pass后的url最后的/

  • 当加上了/，相当于是绝对根路径，则nginx不会把location中匹配的路径部分代理走;
  • 如果没有/，则会把匹配的路径部分也给代理走
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

server {
    listen 80;
    server_name test.xxx.com;
    
    location ^~ /abc {
        proxy_set_header    Host $host;
        proxy_set_header    X-Real-IP  $remote_addr;
        proxy_pass http://127.0.0.1:8081/;
    }
    # 加上/ 请求地址http://test.xxx.com/abc/index，会转发到http://127.0.0.1:8081/index
}

server {
    listen 80;
    server_name test.xxx.com;
    
    location ^~ /abc {
        proxy_set_header    Host $host;
        proxy_set_header    X-Real-IP  $remote_addr;
        proxy_pass http://127.0.0.1:8081;
    }
    # 不加/ 请求地址http://test.xxx.com/abc/index，会转发到http://127.0.0.1:8081/abc/index
}

异步 IO

C++

多态

虚函数

引用与转发

int & 左值引用，int && 右值引用，T && 万能引用。

std::move 修改对象的所有权，不是拷贝，原先对象继续用要小心。

std::forward<T>(v) 将参数完美转发给另一个函数的技术。

可变参数模板

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
55
56
57
58
#include <iostream>

template <typename T>
void print(T& t) {
  std::cout << "左值" << std::endl;
}

template <typename T>
void print(T&& t) {
  std::cout << "右值" << std::endl;
}

template <typename T>
void testForward(T&& v) {
  print(v);
  print(std::forward<T>(v));
  print(std::move(v));
}

void func(int a, int b, int c) {
  std::cout << a << " " << b << " " << c << std::endl;
}

template <typename... Args>
void wrapper(Args&&... args) {
  func(std::forward<Args>(args)...);
}

template <typename Func, typename... Args>
auto bind_and_call(Func&& func, Args&&... args)
    -> decltype(func(std::forward<Args>(args)...)) {
  return func(std::forward<Args>(args)...);
}
int sum(int a, int b, int c) { return a + b + c; }

class MyClass {
 public:
  MyClass(int x, double y) : _x(x), _y(y) {}

 private:
  int _x;
  double _y;
};

int main() {
  testForward(1);
  std::cout << "======================" << std::endl;
  int x = 1;
  testForward(x);

  std::cout << std::endl;
  wrapper(1, 2, 3);

  std::cout << std::endl;
  std::cout << bind_and_call(sum, 1, 2, 3) << std::endl;

  return 0;
}

OS

进程调度

数据库和分布式