面试岗位

后端开发暑期实习

一面 (2021.0816）

临阵抱佛脚准备了一下八股，结果就问了三个算法题。

算法题

加密，给一个映射表，让把文本加密成密文
答：简单映射
两个字符串，找到最长公共字符串。
答： $O (MN)$ 的做 $d p$
给一个 Unix 风格路径如 /home/app/../a/./..，做简化
答：原题是这个《71.简化路径》，思路是搞一个栈然后每次push进去
- 3 这里扩展问了几个问题：
  1. 如果加入一个 throw，在异常时抛出，需要在哪些地方加？
    答：① 已经到达根目录，还要通过..回退到上一目录时
    ② 出现非法字符时
    ③ 字符串开头不为 / 或字符串为空时
  2. 两个斜杠表示什么 //
    答：和一个斜杠 / 一个意思
  3. 由于我一开始实现时，最后合并结果是循环执行 ans = s.top() + ans; 所以他问我这一步可以优化吗
    答：可以优化，两种形式，一种是再搞一个栈/数组，把整个栈中的元素都反转一下，然后用 ans += s.top()，还有一种办法就是 ans += 反转的s.top()，最后再做一次反转。并解释自己是图省事儿没有做这步优化，（自己其实知道）每次在stirng头部加内容性能很慢。
  4. 追问：如果有 $n$ 个字符串，每个字符串长度都是 $1$ ，通过头部累加的形式合并成一串，那么复杂度是多少？
    答：每次拼接时都会把以拼接部分拼接到新的字符后面，整个过程是 $1 + 2 + ... + n = O (N^{2})$ 的。

一面 (2021.0820)

可能是该部门那个组没有名额了，把我推荐给了同部门另一个组重新面试。这次面试时间是晚上 $8$ 点，能看出来小哥是真的渴望下班

基础题

如果有一个很大的数据流，想知道里面 top-k 的最大值，该怎么办？
答：搞一个大小为 $k$ 的堆
堆排序的一次查找过程时间复杂度多少？
答： $O (l o g K)$
堆排序时间复杂度多少，怎么算的？
答： $O (Nl o g N)$ ，遍历是 $O (N)$ ，建堆/调整堆都是 $O (l o g N)$
有其他 $O (Nl o g N)$ 复杂度的排序算法吗，他们分别是怎么算的？
答：归并：每次合并是 $O (N)$ 的，二分过程是 $O (l o g N)$ 的
快排：每次按照基础元素排序是 $O (N)$ 的，二分是 $O (l o g N)$ 的
内核态和用户态了解吗，是什么？
答：为了减少有限资源的访问和使用冲突，对不同的操作赋予不同的执行等级，就是所谓特权的概念。简单说就是有多大能力做多大的事，与系统相关的一些特别关键的操作必须由最高特权的程序来完成。Linux操作系统中主要采用了0和3两个特权级，分别对应的就是内核态和用户态。内核态切换到用户态的情况通常有系统调用、中断、和外围设备异常。
线程和进程区别？
答：……（此处太长省略）
进程间通信方式有哪些？
答：PIPE、有名管道、消息队列、信号量、信号、共享内存、套接字。
长连接短连接知道吗？

算法题

最长上升子序列
答：维护一个长度为 $O (M a xL e n)$ 的数组

#二面（2021.0824）
又临阵抱佛脚了一下八股，结果还是没问

基础题

说要实现一个发红包的算法怎么实现，比如 $n$ 个人， $a . b c$ 元钱。
答：可以搞一个 $[0, 1)$ 范围的随机数，然后每次从当前所有钱中计算拿到多少，剩下的继续下一轮，最后一个人拿走所有。（但这一步我不会证明是否是公平的）
如果春节期间，好多人都在抢红包发红包怎么办？
答：降级、削峰、限流。
- 降级指的是服务降级，这里指的是通过没那么高级的服务，来缓解瞬时压力。比方说可以不用上面的随机数，预先计算几千组随机序列，发红包时直接去套已有的随机序列模板，减少随机数生成计算等过程；更进一步的，可以把如 $8.88$ 这种吉利数字作为红包随机值，增加用户体验，试想谁大年三十抢到一个吉利数红包不开心呢。
- 削峰指的是把瞬时流量拉长，比如增加红包动画，或者增加复核操作等，让用户尽可能错峰的完成发红包抢红包这个过程。
- 限流是为了保护后台服务器不被冲爆，可以搞一个消息队列，把所有的请求放进去，按照服务器水平来取用。甚至可以提前做好备案，根据需求临时扩容服务器，等到需求回落了再把服务器缩减回去。
如果有人发现，自己发不了红包，你该怎么看是哪里出了问题。
答：这里我答的不好，因为我其实懂得不太透彻 K8S 那一套，所以我开始胡扯。我说可以把行为分段，即用户段，消息队列段，后台服务器段，以及数据库段。
- 用户段可以看是局部现象，还是一个全局现象，如果仅是某台用户设备，也说不定是网络不良；如果涉及到某一地区，分析是否是区域供电问题。
- 消息队列段，如果用户请求正确到达消息队列，说明用户行为没错，核实消息队列是否正确分发，是否异常丢失。
- 后台服务器段，如果消息队列正常分发，查看是否是某台服务器断线，比如与主机断连，或由于异常导致的无法服务等。这一步可以从主机查看从机状态，也可以使用如 Habor 等工具查看任务状态。
- 数据库段，如果后台服务器正常请求，并根据请求开始操作数据库（交易/转账等），检查数据库后台Log信息是否有误。
如果此时我们发现100台服务器，就其中的99号机器，所有分发到这台设备上的抢红包任务，都没有正常服务，我们该怎么做？
答：把主机上的所有任务重新放回到消息队列中，把他从主机上断连，先确保之后不会再出现未服务。然后 ping 一下测试是否有连接，这里我接着回答的是可以去看 $L o g$ 日志，是否有异常报错，在本地执行模拟任务，定位问题，不知道有没有更好的回答方式。

算法题

这里的算法题我忘了，放一个八月初阿里的面试算法题好了。说有一个字符串 A ，你每次可以把其中一个字符，拿出来放到字符串末尾，问想转换成字符串 B,最少需要移动几次（保证 A 和 B 构成元素相同）
答：用 A 中所有元素，去和 B 的前缀找到最大公共子序列。

int deal(string a, string b){
  int index = 0;
  for(auto p : a){
    if(b[index] == p){
      index++;
    }
  }
  return a.length() - index;
}

三面（2021.0830）

基础题

项目介绍
K8S 调优接触过吗？
答：没……
项目中系统如何实现用户的高并发？
答：让他们在消息队列里等着。做了一些用户等待交互。
我看到你项目里用到了 Django，有设计哪些表吗？
答：最基础的有用户表、任务表和算法表，然后他们之间分别有一对多关系，以及还有一些补充表，比方说用户昵称表这些与 User 相关的。
一个 Django 请求，是怎么发送给后端的？
答：我这里回答的是 HTTP 怎么发到后端，结果面试官说他想听的是，Django 是怎么接收请求的，问我知道 WSGI 做了什么吗？我回答不会。胡乱说了一些 MVC 的东西。
其他的忘了，但也不是八股的内容，属于两眼一抹黑，闷头就是吹的状态。

算法题

有一棵二叉搜索树，有一个范围 [a, b]，显式的把不在该范围的节点删除，返回删除后二叉搜索树。
答：这里我的做法是:

void delete_TreeNode(TreeNode* root){
  if(root == NULL) return;
  // 递归删除所有子树
  delete_TreeNode(root->left);
  delete_TreeNode(root->right);
  // 这里我是后来百度的才知道该这样删除
  delete root;
  root = NULL;
}
TreeNode* deal(TreeNode* root, int a, int b){
  // 判空
  if(root == NULL) return NULL;
  // root在左边界以左，则root及其左子树需全部删除
  if(root->val < a){
    delete_TreeNode(root->left);
    TreeNode* tmp = root->right;
    delete root;
    root = NULL;
    return deal(tmp, a, b);
  }
  // 同理root在右边界以右，则root及其右子树需全部删除
  if(root->val > b){
    delete_TreeNode(root->right);
    TreeNode* tmp = root->left;
    delete root;
    root = NULL;
    return deal(tmp, a, b);
  }
  // root在范围内，则递归清理两子树
  root->left = deal(root->left, a, b);
  root->right = deal(root->right, a, b);
}