技术终面-很看好的一位朋友-捞面又挂了。。。

教育复捞失败，已转基础架构。（我们会为能力强的候选人争取一次捞面的机会，希望大家投递的时候有限参考我这边，靠谱+响应及时）

感谢hky1999提供的面经；

第一场：2021/1/19

• 16:02:35 系统: 面试官已经进入1463587号房间

• 16:12:45 对方: MaxStack

• 16:12:51 对方: pop push

• 16:12:54 对方: getMax

• 16:13:05 对方: O(1)

• 16:23:47 对方: 协程

• 16:24:59 对方: student_score

• 16:25:06 对方: id, course, score

• 16:25:12 对方: 求每个学生最擅长的科目

• 16:25:19 对方: 及成绩

cache，缓存算法

lru实现？队列？如何优化？

为什么要采用B+树，相比B树和平衡二叉树有什么优劣

最大栈

登录过程

webserver 线程和进程（webserver不会）

进程通信方法

协程（不知道）

协程，英文Coroutines，是一种比线程更加轻量级的存在。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。

最重要的是，协程不是被操作系统内核所管理，而完全是由程序所控制（也就是在用户态执行）。

这样带来的好处就是性能得到了很大的提升，不会像线程切换那样消耗资源。

协程的开销远远小于线程的开销。

Lua语言

Lua从5.0版本开始使用协程，通过扩展库coroutine来实现。

Python语言

正如刚才所写的代码示例，python可以通过 yield/send 的方式实现协程。在python 3.5以后，async/await 成为了更好的替代方案。

Go语言

Go语言对协程的实现非常强大而简洁，可以轻松创建成百上千个协程并发执行。

Java语言

如上文所说，Java语言并没有对协程的原生支持，但是某些开源框架模拟出了协程的功能，有兴趣的小伙伴可以看一看Kilim框架的源码：

https://github.com/kilim/kilim

sql语句（写不出来）

第二场：2021/1/19

四次握手，为什么要多中间两次

TCP可靠传输，怎么实现？

ip协议工作在哪个层？他的作用

操作系统，内核态，用户态，什么是零拷贝？（不知道）

fork后的父子进程共享什么资源？

一、文件流缓冲区的资源位于用户空间，所以全部复制。即如果流缓冲区中有临时信息，都会复制到子进程的用户空间流缓冲区中。

二、子进程复制父进程的数据段，BSS段，代码段，堆空间，栈空间，文件描述符，但是对于文件描述符关联的内核文件表项（即struct file结构体）则是采用共享的方式

写时复制机制

虚拟内存

页表，实现机制

对数组进行堆排序

二分查找，1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 8, 10, 12——递增数列中某个数出现的次数

第三场：2021/1/25 （挂 |>_<|）

首先问具体情况，比如保研之后的安排；

问hypervisor和docker之间的不同；

问到了之前面试中没答上来的问题，什么是协程；

线程和进程的区别；

重写和重载的区别；

http get 和post请求分别是什么含义

http报文头部有几种类型

智力题

核酸检测，如何更快做完一群人的核酸检测？（可以把一堆样本放在一起检测）

答：logn，二分查找

问：有没有更优的方法

答：不知道

比如m个人，每个人患病率为p

每人平均的的核酸次数为 (1+m*p^m)/m；

1次是把这些人的采样放在一起做一个检测；

如果为阳性的概率为p^m，然后每人都做一次需要m次；

大概是这个意思，列个数学模型出来，然后求导算最小值。

coding:

整型升序的数组，a+b = m的对数。

1, 2, 3, 3, 4, 5, 5, 7,8, 10, 12

m=8

cnt=5

 #include <iostream>  using namespace std;    #define LEN (100)  #define TARGET (8)    int main() {      //int a;      //cin >> a      int num[LEN] = {1, 2, 3, 3, 4, 4, 4, 7,8, 10, 12};      int start = 0;      int end =11;      int l = start;      int r = end-1;      int target = TARGET;      int cnt = 0;      while(l<r){          if(num[l] + num[r] < target){              l++;          }          else if(num[l] + num[r] > target){              r--;          }          else{              int cur = r;              // 这里需要修改，遇到num[l] + num[r]的时候需要特殊判断              while(cur > l && num[l] + num[cur] == target){                  printf("fine pari [%d]%d [%d]%d\n",l,num[l],cur,num[cur]);                  cnt++;                  cur--;              }              l++;          }      }      cout << cnt << endl;      return 0;  }

第四场 1/28：

首先问你觉得自己对于这个岗位的优势是什么？

问几个技术问题：

数据结构：     最小生成树算法

    最大栈问题，如何不用辅助栈实现

操作系统：

    I/O方面的问题

数据库：

    我直接说我不熟悉

开发过的项目：

    之前的软工作业，前后分离

Coding:

根据二叉树前序中序遍历写出后序遍历

 vector<int> res;  void find(vector<int>& preOrder, vector<int>& inOrder){      if(preOrder.empty() || inOrder.empty() || preOrder.size() != inOrder.size()){          return;      }      if(preOrder.size() == 1){          res.push_back(preOrder[0]);          return;      }      int root = preOrder[0];      int rootPos;      for(int i = 0;i<inOrder.size();i++){          if(root == inOrder[i]){              rootPos = i;              break;          }      }      //printf("Find root %d rootPos %d\n",root,rootPos);      //这里改成for循环就好了，我面试的时候为啥要用这个呢……      vector<int> leftInOrder(inOrder.begin(),inOrder.begin() + rootPos);      vector<int> rightInOrder(inOrder.begin()+rootPos,inOrder.end());      vector<int> leftPreOrder(preOrder.begin()+1,preOrder.begin() + rootPos +1);      vector<int> rightPreOrder(preOrder.begin()+1+rootPos,preOrder.end());      find(leftPreOrder,leftInOrder);      find(rightPreOrder, rightInOrder);      res.push_back(root);  }    vector<int> findOrder(vector<int>& preOrder, vector<int>& inOrder) {      if(preOrder.empty() || inOrder.empty() || preOrder.size() != inOrder.size()){          return res;      }      find(preOrder,inOrder);      return res;  }

预测智力题：

1、用随机数012来生成012345

这个题的难点在于如何保证 数字出现的概率都是相等 的 。

0-6通过对7取余可以得到，那么就想办法凑对7取余的场景。

 public class Frequency {      public static int rand7(){          while(true){              int num=5*rand5()+rand5();//0-24              if(num<21)                  return num % 7;          }      }  }  //变形：如果用0-6随机生成器生成0-9随机数  public class Frequency {      public static int rand10(){          while(true){              int num=7*rand7()+rand7();              if(num<41)              //排除41-48，因为他们不能生成9，会造成各个数字出现的概率不同                  return num % 10;          }      }  }

2、海盗分金币

5个海盗抢到了100颗宝石，每一颗都一样的大小和价值连城。他们决定bai这么分： 1、抽签决定自己的号码（1，2，3，4，5） 2、首先，由1号提出分配方案，然后大家5人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则他将被扔入大海喂鲨鱼。 3、如果1号死后，再由2号提出分配方案，然后大家4人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则他将被扔入大海喂鲨鱼。 4、以此类推，直到最终得出一个分配方案。 条件：每个海盗都是很聪明的人，都能很理智的判断得失，从而做出选择。 问题：假如你是1号海盗，则你应该提出什么样的分配方案可以使自己的收益最大化（也就是在保命的前提下自己得到的宝石最多）？

3、一个线段切成三段，构成三角形的概率

1/4

4、从64匹马中找到最快的4匹马

11次

Linux文件系统、零拷贝

https://www.cnblogs.com/rickiyang/p/13265043.html#3920716807

文件读写基本流程

读文件

1. 进程调用库函数向内核发起读文件请求；

2. 内核通过检查进程的文件描述符定位到虚拟文件系统的已打开文件列表项；

3. 调用该文件可用的系统调用函数 read()；

4. read() 函数通过文件表项链接到目录项模块，根据传入的文件路径，在目录项模块中检索，找到该文件的 inode；

5. 在 inode 中，通过文件内容偏移量计算出要读取的页；

6. 通过 inode 找到文件对应的 address_space；

7. 在 address_space 中访问该文件的页缓存树，查找对应的页缓存结点：

   1. 如果页缓存命中，那么直接返回文件内容；

   2. 如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过inode 找到文件该页的磁盘地址，读取相应的页填充该缓存页；

   3. 重新进行第 6 步查找页缓存；

8. 文件内容读取成功。

总结一下：inode 管磁盘，address_space 接内存，两者互相指针链接。

Inode 是文件系统(VFS)下的概念，通过 一个 inode 对应一个文件 使得文件管理按照类似索引的这种树形结构进行管理，通过 inode 快速的找到文件在磁盘扇区的位置；但是这种管理机制并不能满足读写的要求，因为我们修改文件的时候是先修改内存里的，所以就有了页缓存机制，作为内存与文件的缓冲区。 address_space 模块表示一个文件在页缓存中已经缓存了的物理页。它是页缓存和外部设备中文件系统的桥梁。如果将文件系统可以理解成数据源，那么 address_space 可以说关联了内存系统和文件系统。

写文件

前5步和读文件一致，在 address_space 中查询对应页的页缓存是否存在；

1. 如果页缓存命中，直接把文件内容修改更新在页缓存的页中，写文件就结束了。这时候文件修改位于页缓存，并没有写回到磁盘文件中去。

2. 如果页缓存缺失，那么产生一个页缺失异常，创建一个页缓存页，同时通过 inode 找到文件该页的磁盘地址，读取相应的页填充该缓存页。此时缓存页命中，进行第 6 步。

3. 一个页缓存中的页如果被修改，那么会被标记成脏页，脏页需要写回到磁盘中的文件块。有两种方式可以把脏页写回磁盘：

   1. 手动调用 sync() 或者 fsync() 系统调用把脏页写回；

   2. pdflush 进程会定时把脏页写回到磁盘。

同时注意，脏页不能被置换出内存，如果脏页正在被写回，那么会被设置写回标记，这时候该页就被上锁，其他写请求被阻塞直到锁释放。

传统I/O

传统读操作

 read(file_fd, tmp_buf, len);

基于传统的 I/O 读取方式，read 系统调用会触发 2 次上下文切换，1 次 DMA 拷贝和 1 次 CPU 拷贝，发起数据读取的流程如下：

1. 用户进程通过read()函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态 (kernel space)；

2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间 (kernel space) 的读缓冲区 (read buffer)；

3. CPU 将读缓冲区 (read buffer) 中的数据拷贝到用户空间 (user space) 的用户缓冲区 (user buffer)。

4. 上下文从内核态 (kernel space) 切换回用户态 (user space)，read 调用执行返回。

传统写操作

当应用程序准备好数据，执行 write 系统调用发送网络数据时，先将数据从用户空间的页缓存拷贝到内核空间的网络缓冲区(socket buffer)中，然后再将写缓存中的数据拷贝到网卡设备完成数据发送。

 Copywrite(socket_fd, tmp_buf, len);

基于传统的 I/O 写入方式，write() 系统调用会触发 2 次上下文切换，1 次 CPU 拷贝和 1 次 DMA 拷贝，用户程序发送网络数据的流程如下：

1. 用户进程通过 write() 函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)。

2. CPU 将用户缓冲区 (user buffer) 中的数据拷贝到内核空间 (kernel space) 的网络缓冲区 (socket buffer)。

3. CPU 利用 DMA 控制器将数据从网络缓冲区 (socket buffer) 拷贝到网卡进行数据传输。

4. 上下文从内核态 (kernel space) 切换回用户态 (user space)，write 系统调用执行返回。

零拷贝方式

在 Linux 中零拷贝技术主要有 3 个实现思路：用户态直接 I/O、减少数据拷贝次数以及写时复制技术。

• 用户态直接 I/O：应用程序可以直接访问硬件存储，操作系统内核只是辅助数据传输。这种方式依旧存在用户空间和内核空间的上下文切换，硬件上的数据直接拷贝至了用户空间，不经过内核空间。因此，直接 I/O 不存在内核空间缓冲区和用户空间缓冲区之间的数据拷贝。

• 减少数据拷贝次数：在数据传输过程中，避免数据在用户空间缓冲区和系统内核空间缓冲区之间的CPU拷贝，以及数据在系统内核空间内的CPU拷贝，这也是当前主流零拷贝技术的实现思路。

• 写时复制技术：写时复制指的是当多个进程共享同一块数据时，如果其中一个进程需要对这份数据进行修改，那么将其拷贝到自己的进程地址空间中，如果只是数据读取操作则不需要进行拷贝操作。

用户态直接 I/O

mmap + write

1. 用户进程通过 mmap() 函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)；

2. 将用户进程的内核空间的读缓冲区 (read buffer) 与用户空间的缓存区 (user buffer) 进行内存地址映射；

3. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间 (kernel space) 的读缓冲区 (read buffer)；

4. 上下文从内核态 (kernel space) 切换回用户态 (user space)，mmap 系统调用执行返回；

5. 用户进程通过write() 函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)；

6. CPU 将读缓冲区 (read buffer) 中的数据拷贝到的网络缓冲区 (socket buffer) ；

7. CPU 利用 DMA 控制器将数据从网络缓冲区 (socket buffer) 拷贝到网卡进行数据传输；

8. 上下文从内核态 (kernel space) 切换回用户态 (user space) ，write 系统调用执行返回；

sendfile

1. 用户进程通过 sendfile() 函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)。

2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间 (kernel space) 的读缓冲区 (read buffer)。

3. CPU 将读缓冲区 (read buffer) 中的数据拷贝到的网络缓冲区 (socket buffer)。

4. CPU 利用 DMA 控制器将数据从网络缓冲区 (socket buffer) 拷贝到网卡进行数据传输。

5. 上下文从内核态 (kernel space) 切换回用户态 (user space)，sendfile 系统调用执行返回。

sendfile + DMA gather copy

1. 用户进程通过 sendfile()函数向内核 (kernel) 发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)。

2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间 (kernel space) 的读缓冲区 (read buffer)。

3. CPU 把读缓冲区 (read buffer) 的文件描述符(file descriptor)和数据长度拷贝到网络缓冲区(socket buffer)。

4. 基于已拷贝的文件描述符 (file descriptor) 和数据长度，CPU 利用 DMA 控制器的 gather/scatter 操作直接批量地将数据从内核的读缓冲区 (read buffer) 拷贝到网卡进行数据传输。

5. 上下文从内核态 (kernel space) 切换回用户态 (user space)，sendfile 系统调用执行返回。

splice

1. 用户进程通过 splice() 函数向内核(kernel)发起系统调用，上下文从用户态 (user space) 切换为内核态(kernel space)；

2. CPU 利用 DMA 控制器将数据从主存或硬盘拷贝到内核空间 (kernel space) 的读缓冲区 (read buffer)；

3. CPU 在内核空间的读缓冲区 (read buffer) 和网络缓冲区(socket buffer)之间建立管道 (pipeline)；

4. CPU 利用 DMA 控制器将数据从网络缓冲区 (socket buffer) 拷贝到网卡进行数据传输；

5. 上下文从内核态 (kernel space) 切换回用户态 (user space)，splice 系统调用执行返回。

写时复制 需要 MMU 的支持

缓冲区共享

fbuf 的思想是每个进程都维护着一个缓冲区池，这个缓冲区池能被同时映射到用户空间 (user space) 和内核态 (kernel space)，内核和用户共享这个缓冲区池，这样就避免了一系列的拷贝操作。

Linux零拷贝对比

无论是传统 I/O 拷贝方式还是引入零拷贝的方式，2 次 DMA Copy 是都少不了的，因为两次 DMA 都是依赖硬件完成的。下面从 CPU 拷贝次数、DMA 拷贝次数以及系统调用几个方面总结一下上述几种 I/O 拷贝方式的差别。

拷贝方式	CPU拷贝	DMA拷贝	系统调用	上下文切换
传统方式(read + write)	2	2	read / write	4
内存映射(mmap + write)	1	2	mmap / write	4
sendfile	1	2	sendfile	2
sendfile + DMA gather copy	0	2	sendfile	2
splice	0	2	splice	2

Coding

最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

   双指针+哈希表 时间复杂度O(N) 空间复杂度O(1):字符的 ASCII 码范围为 0 ~ 127 ，  哈希表 dicdic 最多使用 O(128) = O(1)大小的额外空间。  class Solution {      public int lengthOfLongestSubstring(String s) {          Map<Character, Integer> dic = new HashMap<>();          int i = -1, res = 0;          for(int j = 0; j < s.length(); j++) {              if(dic.containsKey(s.charAt(j)))                  i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i              dic.put(s.charAt(j), j); // 哈希表记录              res = Math.max(res, j - i); // 更新结果          }          return res;      }  }

两数之和

一个有序数组，从随机一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数

用排序解决，问了下一般排序算法的复杂度，O(nlogn)

扫一遍，找出分界点，O(n)

提示我还有更快的方法，那肯定只有 二分 了，想了好久mid的判断条件后写了个解法，给面试官叙述了一遍跑样例的过程。

快排

     public void quickSort(int[] arr,int L,int R){      if (arr.length == 0) return;      int i = L;      int j = R;      int key = arr[(i + j)/2];      while (i <= j){          while (arr[i] < key)              i++;          while (arr[j] > key)              j--;          if (i <= j){              int temp = arr[i];              arr[i] = arr[j];              arr[j] = temp;              i++;              j--;          }      }      //上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。      //“左边”再做排序，直到左边剩下一个数(递归出口)      if (L < j)          quickSort(arr,L,j);      //“右边”再做排序，直到右边剩下一个数(递归出口)      if(i < R)          quickSort(arr,i,R);  }     public void quickSort(long[] array, int begin, int end){          if (begin>=end)              return;          int b = begin;          int e = end;          long sentry = array[begin];          while(begin<end){              while (begin<end && array[end]>sentry) --end;              array[begin] = array[end];              while (begin<end && array[begin]<=sentry) ++begin;              array[end] = array[begin];          }          array[begin] = sentry;             quickSort(array, b, begin-1);          quickSort(array, begin+1, e);      }

GIC中断控制器

对于GIC，它可以管理4种类型的中断：

（1）外设中断（Peripheral interrupt）。根据目标CPU的不同，外设的中断可以分成PPI（Private Peripheral Interrupt）和SPI（Shared Peripheral Interrupt）。PPI只能分配给一个确定的processor，而SPI可以由Distributor将中断分配给一组Processor中的一个进行处理。外设类型的中断一般通过一个interrupt request line的硬件信号线连接到中断控制器，可能是电平触发的（Level-sensitive），也可能是边缘触发的（Edge-triggered）。

（2）软件触发的中断（SGI，Software-generated interrupt）。软件可以通过写GICD_SGIR寄存器来触发一个中断事件，这样的中断，可以用于processor之间的通信。

（3）虚拟中断（Virtual interrupt）和Maintenance interrupt。

C++

• 重载 早绑定

• 重写 晚绑定，与多态相关

• 全局对象的构造函数会在main 函数之前执行

• static inline的内联函数，一般情况下不会产生函数本身的代码，而是全部被嵌入在被调用的地方。

• 一个"static inline"函数促使编译程序尝试着将其代码插入到所有调用它的程序中。

• 使用inline会增加二进制映像的大小，而这会降低访问CPU高速缓存的速度，所以不能在所有的函数定义中使用它。

• 注意当数组作为函数的参数进行传递时，该数组自动退化为同类型的指针。

• 纯虚函数不能再在基类中实现，编译器要求在派生类中必须予以重写以实现多态性。

C++ STL实现：

• vector 是动态数组。在堆上分配空间。

• vector 动态增加大小，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对 vector 的任何操作，一旦引起空间重新配置，同时指向原vector 的所有迭代器就都失效了。

• STL 中的list 底层是一个双向链表，而且是一个环状双向链表。这个特点使得它的随即存取变的非常没有效率，因此它没有提供 [] 操作符的重载。

• deque 是一种双向开口的连续线性空间，元素也是在堆中。所谓双向开口，意思是可以在队尾两端分别做元素的插入和删除操作。deque 和 vector 的最大差异，一在于 deque 允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接在一起。换句话说，像 vector 那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在 deque 是不会发生的。

C++实现临界区访问

•     win：CriticalSection 临界区

•     Linux： pthread 互斥量

http相关

时间复杂度

排序问题，数组

协程，并发