操作系统部分

线程调度算法

尴尬。。。第一遍没听懂，还寻思线程调度是啥。。。还让面试官解释了一遍，可是一般不都是说进程调度吗

  1. FCFS: 先来先服务，但是如果前边的是长任务就后边的短任务一致等待
  2. 多级反馈队列
  3. 时间片轮转
  4. 短作业优先： 短作业优先，但是当有长作业的时候，就会导致短作业等待时间过长。

补充

  1. 多级反馈队列
    1. 线程被分配到多个优先级队列，每个队列对应不同的时间片或调度策略。
    2. 高优先级的队列先运行，低优先级队列后运行。
    3. 如果线程未完成且耗尽时间片，则会被移动到更低优先级的队列中（动态调整优先级）。
    4. 可以结合 时间片轮转 或其他策略在每个队列中执行。 5） 实现复杂，但是调度灵活
  2. 时间片轮转
    1. 每个线程被分配一个固定的时间片（时间片长度可以调节）, 时间片用完后，如果线程未完成，则被放回队列尾部等待下一轮调度。
    2. 时间片选择会影响到效率
  3. 优先级调度
    1. 每个线程分配一个优先级，调度时优先调度高优先级
    2. 分为抢占式和非抢占式。非抢占式，需要等待当前任务执行结束主动放弃CPU；抢占式，如果有更高优先级的线程到达，当前执行线程会被阻塞
  4. 最短剩余事件优先
    1. 如果新任务的预期运行时间小于当前任务剩余执行时间，则新任务优先执行
    2. 难以准确预测任务运行时间

如何设计一个时间片轮转算法

回答的不太好，说可以先预处理，对规模很大的任务做一个标记，其他任务使用平均，规模很大的任务自动调整 补充(GPT提供):

  1. 设计一个FIFO的任务队列，每个任务分配固定时间片
  2. 按照队列顺序执行任务，如果任务完成，则继续执行
  3. 大任务耗费时间片比较多，可能阻塞小任务，小任务多次切换浪费时间，可以与处理任务，识别规模大的任务，预先为其分配动态调整的时间，避免频繁上下文切换
  4. 对小任务使用固定时间片

线程安全

  1. 互斥锁：避免数据竞争，同一时刻只能有一个线程拿到锁的所有权，需要注意避免死锁
  2. 信号量：通过计数器的方式，控制可访问资源的数量
  3. 原子变量：硬件上可以通过总线锁的方式，保证同一个时刻只有一个线程可以读写数据；又扯了一下C++的内存序，内存屏障。。。
  4. 自旋锁：当等待的事件明显少于加锁的事件，可以使用自旋锁，自选锁就是一直尝试获取锁，直到成功拿到
  5. 读写锁：同一时刻可以有多个线程同时读，但是写只能有一个线程写，写完后其他线程才能读
  6. 互斥锁与信号量的区别：线程需要拿到锁才能执行，信号量是计数器大于0，线程就可以消耗资源

补充：

  1. 递归锁：递归锁，递归调用，线程安全，但效率不高，因为每次递归都需要加锁，所以递归锁适合在函数调用深度比较深的场景。
  2. C++内存序：内存序保证了多线程读写操作的可见性和顺序性。原子性虽然保证了操作不可分割，但是不能保证操作的执行顺序，内存序扩展了原子性的概念。 即使是原子操作，如果使用了松散内存序，也可能导致其他线程观察到非预期的顺序。
  3. C++内存屏障：内存屏障阻止了指令重排，C++的atmoc隐式包含了内存屏障，保证正确性
  4. 自旋锁：自选锁有可能导致活锁问题， 活锁：线程忙等待，彼此干扰
  5. 读写锁： 写操作可能会被长时间阻塞
  6. 条件变量：通过条件变量，实现内存同步

Linux内存管理

尴尬，答成内存分配了。。。再次回答了

  1. 页式： 页面固定大小，页内地址与物理页地址一致，通过页表查找物理页框号，页表存储页号到物理页框的映射关系。现代计算机使用TLB快表加快页表项查询速度
  2. 段式：段大小不固定，与程序段的概念类似，一段程序存储在一个段内，逻辑地址由段号和段内地址组成
  3. 段页式：综合段式、页式特点，有段号，页号，页内偏移。进一步将段划分为固定大小的页
  4. 虚拟内存往往比可用的实际内存大，如果访问的页不在内存怎么办？ 触发缺页中断，通过页面调度算法如FIFO，LRU等算法调出一个页面，将新数据加载到页内 补充：
  5. 不常用的资源会保存在磁盘上。
  6. 缺页中断的过程
    1. 触发缺页中断
    2. 查找所需页是否在磁盘，如果不存在发生段错误，如果存在，使用页面置换算法选择一个页面替换，
  7. FIFO 选择最早加载的页面进行替换；
  8. LRU 选择最近最少使用的页面替换
  9. LFU 选择使用频率最少的页面替换
  10. OPT 选择最近最远使用的页面替换

设计模式

回答掌握的只有单例，其他的只是概念上知道一些

  1. 单例模式： 将构造设置为私有的，拷贝构造拷贝赋值删除，可以将析构设置为public的，也可以将析构设置为私有的通过手动指定一个删除器，管理。C++11提供了call_once保证多线程只会实例化一次，也可以通过两次判断空的方式，保证只实例化一次
  2. 观察者模式：观察者模式可以观察到被观察者的状态，被观察者状态更新时，观察者可以同步更新
  3. 工厂模式：需要有一个抽象基类，其他类继承实现具体的类。 补充：
  4. 观察者模式：当被观察对象（Subject）的状态发生改变时，自动通知所有依赖的观察者（Observer）。
  5. 工厂模式：抽象基类提供同一接口，工厂类根据传入参数返回不同具体类的实例。

项目相关

  1. 对客户端，后端的看法
  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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

// O(m*n)
#include <vector>
int getMaxSum(const std::vector<std::vector<int>> &arr) {
  int m = arr.size();
  if (m == 0)
    return INT_MAX;
  int n = arr[0].size();
  if (n == 0)
    return INT_MAX;
  std::vector<std::vector<int>> dp(m, std::vector<int>(n));
  dp[0][0] = arr[0][0];
  for (int i = 1; i < m; i++) {
    dp[i][0] = dp[i - 1][0] + arr[i][0];
  }
  for (int j = 1; j < n; j++) {
    dp[0][j] = dp[0][j - 1] + arr[0][j];
  }
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
    }
  }
  return dp[m - 1][n - 1];
}
// 尝试O(m+n) 
int getMaxSum(const std::vector<std::vector<int>> &arr) {
  int m = arr.size();
  if (m == 0)
    return INT_MAX;
  int n = arr[0].size();
  if (n == 0)
    return INT_MAX;
  std::vector<int> f1(m);
  std::vector<int> f2(n);
  f1[0] = arr[0][0];
  for (int i = 1; i < m; i++) {
    f1[i] = f1[i - 1] + arr[i][0];
  }
  f2[0] = arr[0][0];
  for (int i = 1; i < n; i++) {
    f2[i] = f1[i - 1] + arr[0][i];
  }
  for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
      int curr = std::max(f1[i - 1], f2[j - 1]) + arr[i][j];
      f1[i] = curr;
      f2[j] = curr;
    }
  }
  return f1.back();
}
// 正确的O(m+n)
int getMaxSum(const std::vector<std::vector<int>> &arr) {
    int m = arr.size();
    if (m == 0)
        return INT_MIN;
    int n = arr[0].size();
    if (n == 0)
        return INT_MIN;

    std::vector<int> dp(n, 0);

    dp[0] = arr[0][0];
    for (int j = 1; j < n; j++) {
        dp[j] = dp[j - 1] + arr[0][j]; // 初始化第一行
    }

    for (int i = 1; i < m; i++) {
        dp[0] += arr[i][0]; // 更新第一列
        for (int j = 1; j < n; j++) {
            dp[j] = std::max(dp[j], dp[j - 1]) + arr[i][j];
        }
    }

    return dp[n - 1];
}