首页 秋招复盘9.10：大复盘
文章
取消

秋招复盘9.10：大复盘

发表于 2023/09/12
作者 Olimi
阅读量: 32 分钟阅读

图推

学习到的新规律：

  1. 叠加消解。第一个图+第二个图叠加到一起，消解部分是第三个图。
  2. 相加异或。比如黑+白。
  3. 旋转。

刷题：粉笔网题库 (fenbi.com)（会刷吗）

系统：IO多路复用

IO多路复用。poll、select、epoll，区别和异同。不同模式分别在什么情况下进行选择。比如遇到什么样的编程场景，会选择其中一个而不是另一个。

原理和实现：

IO多路复用是一种允许单个线程监视和管理多个IO流的技术。poll、select 和 epoll 都是实现IO多路复用的系统调用。

以下是它们的区别和异同：

1. select

  • select 是最早的IO多路复用解决方案，支持的平台最广。
  • 它的接口设计相对简单，使用起来较为方便。
  • select 使用一个位图来表示需要监视的文件描述符，因此它的最大连接数受限于FD_SETSIZE的大小，通常为1024。
  • 每次调用 select 时，都需要在用户空间和内核空间之间复制文件描述符，当连接数非常大时，效率较低。

2. poll

  • poll 解决了 select 的最大连接数限制问题，因为它不是使用位图，而是使用一个链表来存储文件描述符。
  • 但 poll 仍然存在效率问题。每次调用 poll 时，都需要遍历所有的文件描述符，即使大部分文件描述符都没有就绪。

3. epoll

  • epoll 是Linux特有的IO多路复用解决方案，它没有最大连接数的限制，也没有效率问题。
  • epoll 使用一个事件表来保存就绪的事件，因此无需遍历所有的文件描述符。
  • epoll 还支持“边缘触发”模式，这使得它能够更好地处理大量并发的连接。

以下是在不同场景下选择不同解决方案的一些指导：

  • 如果你的程序需要在各种平台上运行，包括非Linux平台，那么 select 或 poll 可能是更好的选择，因为 epoll 只在Linux上可用。
  • 如果你的程序需要处理大量的并发连接，那么 epoll 是最好的选择，因为 select 和 poll 在处理大量连接时效率低。
  • 如果你的程序只需要处理少量的并发连接，那么 select 和 poll 都可以满足需求，你可以根据API的易用性来选择。

总的来说，epoll 通常是最高效的解决方案，但是它的使用也最为复杂，而且只能在Linux上使用。select 和 poll 的性能较差，但是使用起来更简单，且跨平台。

但是问题还是不知道什么场景会只使用其中一种技术而不是用另一种，上面回答面试官是不满意的。

select/poll/epoll适用场景

  1. select 应用场景

    select 的 timeout 参数精度为微秒，而 poll 和 epoll 为毫秒，因此 select 更加适用于实时性要求比较高的场景，比如核反应堆的控制。

    select 可移植性更好，几乎被所有主流平台所支持。

  2. poll 应用场景

    poll 没有最大描述符数量的限制，如果平台支持并且对实时性要求不高，应该使用 poll 而不是 select。

  3. epoll 应用场景

    只需要运行在 Linux 平台上，有大量的描述符需要同时轮询，并且这些连接最好是长连接。

需要同时监控小于 1000 个描述符，就没有必要使用 epoll，因为这个应用场景下并不能体现 epoll 的优势。

需要监控的描述符状态变化多，而且都是非常短暂的，也没有必要使用 epoll。因为 epoll 中的所有描述符都存储在内核中，造成每次需要对描述符的状态改变都需要通过 epoll_ctl() 进行系统调用，频繁系统调用降低效率。并且 epoll 的描述符存储在内核，不容易调试

cpp

cpp字符串分割

在C++中，我们可以使用多种方法来分割字符串。以下是一些常见的方法：

方法一：使用 std::istringstream 和 std::getline

这种方法不依赖于任何第三方库，只需要标准库即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <vector>
#include <sstream>
#include <string>

std::vector<std::string> split(const std::string &s, char delimiter) {
    std::vector<std::string> tokens;
    std::string token;
    std::istringstream tokenStream(s);
    while (std::getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

方法二：使用 std::strtok

尽管 std::strtok 是一个C库函数，但是它也可以在C++中使用。这个函数会修改原始字符串，所以如果你不希望原始字符串被修改，你需要复制一份。

注意：std::strtok 不是线程安全的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <vector>
#include <cstring>
#include <string>

std::vector<std::string> split(char *str, const char *delimiters) {
    std::vector<std::string> tokens;
    char *token = std::strtok(str, delimiters);
    while (token != nullptr) {
        tokens.push_back(std::string(token));
        token = std::strtok(nullptr, delimiters);
    }
    return tokens;
}

方法三：使用 Boost 库的 boost::split

如果你的项目已经使用了 Boost 库，你可以使用 boost::split 函数来分割字符串。

1
2
3
4
5
6
7
8
9

#include <vector>
#include <boost/algorithm/string.hpp>

std::vector<std::string> split(const std::string &s, const std::string &delimiters) {
    std::vector<std::string> tokens;
    boost::split(tokens, s, boost::is_any_of(delimiters));
    return tokens;
}

以上三种方法都可以用来分割字符串，你可以根据你的项目需求和你的编程环境来选择最适合的一种。

算法

Dijkstra算法

迪杰斯特拉（Dijkstra）算法是一种用于在图中找到最短路径的算法。这个算法用于找到从起始节点到所有其他节点的最短路径。以下是该算法的一般步骤：

  1. 创建两个集合，已访问节点集合（visited）和未访问节点集合（unvisited）。起始节点加入未访问节点集合。
  2. 设置起始节点的距离为0，所有其他节点的距离为无穷大（在实际应用中，这可以是一个很大的值）。
  3. 选择未访问节点集合中距离最小的节点，访问该节点的所有未访问邻居。对于每个邻居，计算从当前节点到邻居节点的距离，并更新邻居节点的距离值（如果计算出的新距离小于原来的距离值）。
  4. 当前节点加入已访问节点集合，从未访问节点集合中移除。
  5. 如果目标节点已被访问，或者未访问节点集合中最小距离为无穷大（这意味着没有路径连接到目标节点），则算法结束。
  6. 否则，回到第3步。
    • 算法实现1，邻接图，通过优先队列：
    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

     #include <queue>
 #include <vector>
 #include <utility> // for pair
 #include <iostream>
 #include <limits> // for numeric_limits
    
 using namespace std;
    
 typedef pair<int, int> Pair;
    
 vector<int> dijkstra(vector<vector<Pair>> graph, int start) {
     int n = graph.size();
     priority_queue<Pair, vector<Pair>, greater<Pair>> pq; // min heap
     vector<int> distances(n, numeric_limits<int>::max());
    
     pq.push(make_pair(0, start));
     distances[start] = 0;
    
     while (!pq.empty()) {
         int dist = pq.top().first;
         int prev = pq.top().second;
         pq.pop();
    
         vector<Pair>& neighbors = graph[prev];
    
         for (auto& neighbor : neighbors) {
             int next = neighbor.first;
             int nextDist = neighbor.second;
    
             if (distances[prev] + nextDist < distances[next]) {
                 distances[next] = distances[prev] + nextDist;
                 pq.push(make_pair(distances[next], next));
             }
         }
     }
    
     return distances;
 }
    
 int main() {
     vector<vector<Pair>> graph = {
         { make_pair(1, 3), make_pair(2, 1) },
         { make_pair(2, 3) },
         { make_pair(0, 2), make_pair(1, 1), make_pair(3, 2) },
         { make_pair(0, 4), make_pair(2, 5) }
     };
        
     vector<int> distances = dijkstra(graph, 0);
    
     for (int i = 0; i < distances.size(); i++)
         cout << "The shortest distance from node 0 to node " << i << " is " << distances[i] << endl;
    
     return 0;
 }

  • 算法实现2，邻接矩阵：

    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

      #include <limits>
  #include <vector>
  #include <iostream>
  #include <queue>
    
  using namespace std;
    
  const int INF = numeric_limits<int>::max();
    
  vector<int> dijkstra(vector<vector<int>> graph, int start) {
      int n = graph.size();
      vector<int> distances(n, INF);
      vector<bool> visited(n, false);
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
      distances[start] = 0;
      pq.push({0, start});
    
      while (!pq.empty()) {
          int u = pq.top().second;
          pq.pop();
          if (visited[u])
              continue;
          visited[u] = true;
    
          for (int v = 0; v < n; v++) {
              if (graph[u][v] != INF && distances[u] != INF && distances[u] + graph[u][v] < distances[v]) {
                  distances[v] = distances[u] + graph[u][v];
                  pq.push({distances[v], v});
              }
          }
      }
    
      return distances;
  }
    
  int main() {
      vector<vector<int>> graph = {
          {0, 4, INF, 2, INF},
          {4, 0, 4, 1, INF},
          {INF, 4, 0, 1, 3},
          {2, 1, 1, 0, 7},
          {INF, INF, 3, 7, 0}
      };
    
      vector<int> distances = dijkstra(graph, 0);
    
      for (int i = 0; i < distances.size(); i++)
          cout << "The shortest distance from node 0 to node " << i << " is " << distances[i] << endl;
    
      return 0;
  }

  • m*n的二维矩阵？不是很懂。

    如果你有一个m*n的邻接矩阵（也就是说，你的图不是一个完全图，而是一个有向图），你仍然可以使用Dijkstra算法，但是你需要对算法做一些小的修改。

    你可以将m*n的邻接矩阵看作是一个图，其中每个格子是一个节点，每个节点与其上下左右的邻居相连。然后，你可以将这个图转换为一个一维的邻接矩阵，然后在这个一维的邻接矩阵上运行Dijkstra算法。

    以下是一个基本的实现：

    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
59
60
61
62
63

      #include <limits>
  #include <vector>
  #include <iostream>
  #include <queue>
    
  using namespace std;
    
  const int INF = numeric_limits<int>::max();
  const vector<pair<int, int>> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
  vector<int> dijkstra(vector<vector<int>> graph, pair<int, int> start) {
      int m = graph.size();
      int n = graph[0].size();
      vector<vector<int>> distances(m, vector<int>(n, INF));
      vector<vector<bool>> visited(m, vector<bool>(n, false));
      priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    
      distances[start.first][start.second] = graph[start.first][start.second];
      pq.push({graph[start.first][start.second], start});
    
      while (!pq.empty()) {
          pair<int, int> u = pq.top().second;
          pq.pop();
          if (visited[u.first][u.second])
              continue;
          visited[u.first][u.second] = true;
    
          for (auto& direction : directions) {
              int x = u.first + direction.first;
              int y = u.second + direction.second;
              if (x >= 0 && x < m && y >= 0 && y < n && distances[u.first][u.second] + graph[x][y] < distances[x][y]) {
                  distances[x][y] = distances[u.first][u.second] + graph[x][y];
                  pq.push({distances[x][y], {x, y}});
              }
          }
      }
    
      // Convert 2D distances matrix to 1D distances array
      vector<int> res(m * n);
      for (int i = 0; i < m; ++i) {
          for (int j = 0; j < n; ++j) {
              res[i * n + j] = distances[i][j];
          }
      }
    
      return res;
  }
    
  int main() {
      vector<vector<int>> graph = {
          {1, 3, 1},
          {1, 5, 1},
          {4, 2, 1}
      };
    
      vector<int> distances = dijkstra(graph, {0, 0});
    
      for (int i = 0; i < distances.size(); i++)
          cout << "The shortest distance from node (0, 0) to node (" << i / graph[0].size() << ", " << i % graph[0].size() << ") is " << distances[i] << endl;
    
      return 0;
  }

    在这个实现中，dijkstra函数首先初始化所有节点到起始节点的距离为无穷大，除了起始节点本身到自己的距离为0。然后，它使用一个优先队列来保存所有已经找到但还未访问的节点，并按照这些节点的最短路径长度进行排序。每一步，它都会从优先队列中取出一个未访问的节点，然后更新所有从这个节点直接可达的节点的最短路径长度。这个过程会一直持续，直到优先队列为空，也就是说所有可达的节点都已经被访问过。

    在main函数中，我们创建了一个图，并调用dijkstra函数来计算从节点0到所有其他节点的最短距离。

LRU Cache

使用STL的list和unorder_map，考虑大规模数据量下重复删除、添加的问题。另外可以自行设计链表和哈希表等数据结构更高效地自定义。懒得弄了。

  • 实现参考

    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

      class LRUCache {
  public:
      LRUCache(int capacity) {
          this->capacity = capacity;
      }
    
      int get(int key) {
          if (cache.find(key) == cache.end()) {
              return -1;
          } else {
              // 将key对应的node移到链表头部
              lru.splice(lru.begin(), lru, cache[key]);
              auto v = *cache[key];
              cache[key] = lru.begin();
              return cache[key]->second;
          }
      }
    
      void put(int key, int value) {
          if (cache.find(key) == cache.end()) {
              if (lru.size() == capacity) {
                  auto &lru_back = lru.back();
                  cache.erase(lru_back.first);
                  // 修改尾部的节点，改为新的键值对
                  lru_back.first = value;
                  lru_back.second = value;
                  lru.splice(lru.begin(), lru, --lru.end());
                  cache[key] = lru.begin();
              } else {
                  // 插入新的节点
                  lru.emplace_front(key, value);
                  cache[key] = lru.begin();
              }
    
          } else {
              // 更新，移动
              cache[key]->second = value;
              lru.splice(lru.begin(), lru, cache[key]);
          }
      }
    
  private:
      int capacity;
      list<pair<int, int>> lru;
      unordered_map<int, list<pair<int, int>>::iterator> cache;
  };

中位数

给一个数组，再给一个这个数组下标作为元素的数组，逐个删除元素，计算中位数。

  • 代码

    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
59
60
61
62
63
64
65

      int main() {
      int t;
      cin >> t;
      while (t--) {
          int n;
          cin >> n;
          vector<int> a(n), b(n - 1);
          for (int i = 0; i < n; ++i) {
              cin >> a[i];
          }
          // 找到不在b中的那个index，使用位图法标记所有在b中的index。
          vector<bool> flag(n, false);
          for (int j = 0; j < n - 1; ++j) {
              cin >> b[j];
              flag[b[j] - 1] = true;
          }
          int index = 0;
          for (int i = 0; i < n; ++i) {
              if (!flag[i]) {
                  index = i;
                  break;
              }
          }
    
          // Reverse b
          reverse(b.begin(), b.end());
    
          multiset<int> data;
          data.insert(a[index]);
    
          vector<double> medians;
          medians.push_back(a[index]);
    
          auto mid = data.begin();
    
          for (int i: b) {
              auto idx = i - 1;
              data.insert(a[idx]);
    
              // Adjust mid iterator
              if (data.size() == 1) {
                  mid = data.begin();
              } else if (a[idx] < *mid) {
                  if (data.size() % 2 != 0) --mid;
              } else {
                  if (data.size() % 2 == 0) ++mid;
              }
    
              // Compute median
              if (data.size() % 2 != 0) {
                  medians.push_back(*mid);
              } else {
                  medians.push_back((*mid + *prev(mid)) / 2.0);
              }
          }
    
          // Print medians in reverse order
          reverse(medians.begin(), medians.end());
          for (auto median: medians) {
              cout << median << endl;
          }
      }
    
      return 0;
  }

其他

编译

编译器在将源代码转换为目标代码的过程中，常常会生成一种或多种中间表示（Intermediate Representation, IR）。这些中间表示有多种形式，包括但不限于以下几种：

  1. 抽象语法树（Abstract Syntax Tree, AST）：这是源代码的高级表示，它基本上保留了源代码的结构信息。这种形式的中间表示在语法分析阶段生成。
  2. 三地址代码（Three-Address Code, TAC）：这是一种低级表示，每条指令最多包含三个操作数。逻辑上，每个操作数可以是一个变量、一个常量或者一个间接引用。三地址代码是一种更接近于目标代码的中间表示，通常在优化阶段使用。
  3. 四元式（Quadruples）：四元式是一种特殊的三地址代码，它明确地将每个操作符和它的操作数分开。因此，四元式的每条指令都包含四个部分：操作符、两个源操作数和一个目标操作数。
  4. 逆波兰表示（Reverse Polish Notation, RPN）：逆波兰表示是一种没有括号的算术表示方法，它将操作符放在操作数的后面。这种表示方法的优点是它消除了运算优先级和括号的需要。
  5. N元表示（N-Tuples）：N元表示是一种更一般的方式，它可以表示包含任意数量操作数的操作。这种表示方法通常用于更复杂的编程语言和机器语言。

这些中间表示从不同的角度抽象了源代码的信息，可以帮助编译器进行诸如优化这样的操作。它们的选择和设计取决于编译器的目标和源语言的特性。

系统中断

中断是来自硬件设备或软件的信号，用于通知处理器停止当前的工作并执行特定的中断处理程序。以下是你提到的各种可能的中断源：

  1. I/O（输入/输出）：这是一种常见的中断源。当外部设备（如键盘、鼠标、打印机等）需要处理器的注意时，它们会发送一个I/O中断。例如，当用户按下键盘上的一个键时，键盘会发送一个I/O中断来通知处理器。
  2. 数据通路（Data Path）：数据通路是处理器内部的数据流动路径，它不直接产生中断。然而，处理器内部的某些操作可能会导致中断，例如，一个算术运算可能会导致溢出中断。
  3. 软件（Software）：软件可以通过执行特殊的中断指令来触发中断。这种中断通常被称为软件中断或陷阱（trap）。例如，操作系统可能会使用软件中断来实现系统调用。
  4. 时钟（Clock）：时钟是另一种常见的中断源。处理器的时钟生成周期性的信号，这些信号可以触发时钟中断。时钟中断通常用于实现处理器的时间片轮转调度。

所以，I/O、软件和时钟都可以作为中断源。数据通路本身不直接生成中断，不是中断源。

树的遍历

一个单独的前序或后序遍历序列不能唯一确定一棵二叉树，因为我们不知道何时应该从左子树移动到右子树。然而，如果我们有一个中序遍历序列与前序或后序遍历序列配对，那么我们可以唯一地确定一棵二叉树。这是因为中序遍历序列可以告诉我们哪些节点在根节点的左边（即在左子树中），哪些节点在根节点的右边（即在右子树中）。

因此，一个中序遍历序列与一个前序或后序遍历序列的组合可以唯一确定一棵二叉树。

UML

认识UML类关系——依赖、关联、聚合、组合、泛化-腾讯云开发者社区-腾讯云 (tencent.com)

  • 依赖关系：虚线、普通箭头
  • 关联关系：实线、普通箭头
  • 聚合关系：大对象处有空心菱形、实线
  • 组合关系：大对象处有实心菱形、虚线
  • 泛化关系：继承、空心三角形、实线
  • 实现关系：接口、空心三角形、虚线

统计量

在统计学和线性回归中，标准差、T统计量、F统计量和修正R方都是重要的概念。下面是它们各自的解释：

  1. 标准差（Standard Deviation）：标准差是一个度量，用于表示数据值与平均值的偏离程度。在回归分析中，标准差可以用来测量预测误差或残差的程度。较小的标准差意味着数据点更接近预测线，而较大的标准差则表示数据点在预测线周围有更大的分散。
  2. T统计量（T-Statistic）：在回归分析中，T统计量用于检验一个变量的系数是否显著不等于零。这对于理解哪些变量对预测结果有显著影响非常重要。
  3. F统计量（F-Statistic）：F统计量是用于检验整个回归模型是否显著的统计度量。基本上，它是模型中所有回归系数的T统计量的平方和。如果F统计量显著，那么我们可以拒绝“所有回归系数都等于零”的零假设，这意味着我们的模型至少有一个自变量是有用的。
  4. 修正R方（Adjusted R-squared）：修正R方是R方的一个版本，它考虑了模型中自变量的数量。R方是一个衡量模型拟合度的度量，它的取值范围是0到1，值越接近1，表示模型的拟合度越好。但是，R方的一个问题是，当我们向模型中添加更多的自变量时，即使这些变量对预测结果没有帮助，R方的值也会上升。修正R方就是为了解决这个问题，当添加的自变量没有显著提高模型的预测能力时，修正R方的值会下降。

以下是计算标准差、T统计量、F统计量和修正R方的基本算法，每个算法都伴有具体的示例。

  1. 标准差：标准差是数据值的平均偏差的平方根。这是计算步骤：
    • 计算所有值的平均值。
    • 对于每个值，计算其与平均值的差，然后平方。
    • 计算这些平方差的平均值，即方差。
    • 计算方差的平方根，即标准差。

    例如，考虑这个数据集：[1, 2, 3, 4, 5]，其平均值是3。每个值与平均值的差的平方是：[4, 1, 0, 1, 4]。这些平方差的平均值（方差）是2，其平方根（标准差）是根号2，约等于1.41。

  2. T统计量：T统计量的计算需要回归系数的估计值和标准误差。以下是计算步骤：
    • 对于每个回归系数，计算其估计值与零的差（通常就是系数的估计值本身）。
    • 将这个差除以系数的标准误差。

    假设我们有一个回归系数的估计值为2，其标准误差为0.5，那么T统计量就是2/0.5=4。

  3. F统计量：F统计量的计算需要模型的平方和（SSR）和残差的平方和（SSE），以及模型中的自由度。以下是计算步骤：
    • 计算模型的平方和（SSR）除以模型的自由度（通常是模型中预测变量的数量）。
    • 计算残差的平方和（SSE）除以残差的自由度（通常是数据点的数量减去预测变量的数量减1）。
    • 将第一步的结果除以第二步的结果。

    假设我们有一个模型，其SSR为10，有2个预测变量，SSE为5，有3个数据点，那么F统计量就是(10/2) / (5/(3-2-1)) = 10。

  4. 修正R方：修正R方的计算需要原始的R方，以及数据点的数量（n）和模型中预测变量的数量（k）。以下是计算步骤：
    • 计算1减去原始的R方。
    • 计算n减1除以n减k减1。
    • 将第一步的结果乘以第二步的结果。
    • 计算1减去第三步的结果。

    假设我们有一个模型，其R方为0.8，有20个数据点，2个预测变量，那么修正R方就是1 - (1-0.8) * ((20-1) / (20-2-1)) = 0.771。

随笔
总结 招聘
本文由作者按照 CC BY 4.0 进行授权
最近更新
文章内容

2023年8月30日分享：润

恐狂？在中国动不动就劝打狂犬疫苗之我看