【题目内容】给定一棵二又树，试求这棵二叉树有多少个节点满足以该节点为根的子树是满二叉树? 我们定义一棵树是满二叉树，当且仅当每一层的节点数量都达到了最大值(即无法在这一层添加新节点)
【输入描述】第一行输入一个正整数 n，代表节点的数量。接下来的 n 行，第 i 行输入两个整数 l 和 r，分别代表节点 i 的左儿子和右儿子。请注意，如果一个节点没有左/右儿子，那么对应的 l/r 是 -1（1 <= n <= 1e5）
【输出描述】子树为满二叉树的节点数量
# 样例
# 输入：
5
2 3
4 5
-1 -1
-1 -1
-1 -1
# 输出：
4思路： 满二叉树就是指某个节点为根节点下的每一层都是满的，因此可以用DFS
- 可以自定义一个 struct 结构体，然后构建一个二叉树
- 也可以用一个二维 vector 存储编号为第i个节点的左右孩子节点的编号
- 题目没有规定根节点，所以需要记录节点的入度判断哪个是根（入度为0）
注意 dfs(u) 表示遍历节点 u 的节点，如果是满二叉树那么就返回其深度，否则就返回 0
代码参考： ali_0315_1.cpp
【题目描述】给定一个数组，请你计算有多少个三元组 <i, j, k> 满足 0 <= i < j < k < n 且 max(a[i], a[j], a[k]) - min(a[i], a[j], a[k]) = 1
【输入描述】第一行输入一个正整数 n，第二行输入 n 个正整数 a[i]（3 <= n <= 2e5, 1 <= a[i] <= 1e9）
【输出描述】输出一个整数代表合法的三元组的数量
# 样例
# 输入：
8
1 1 2 2 3 4 5 5
# 输出：
6思路： 排序之后处理，只有大小相邻的元素才有可能 max - min = 1，例如上面例子只要考虑 1 1 2 2、2 2 3、4 5 5 即可，另外可以使用 unordered_map + set 考虑
代码参考：ali_0315_2.cpp
【题目内容】给定一个大小为 n 组，你需要选择恰好 k 个元素使每个元素分别进行一次如下操作:
- 使该元素乘 2
- 使该元素除以 2，向下取整
请注意，对于每个元素只能进行两种操作中的一种，且只能操作一次。你需要使得k次操作后，数组的极差尽可能小。请你求出这个最小的极差。
提示：数组的极差指数组的最大值减去最小值
【输入描述】第一行输入两个正整数 n 和 k，代表数组长度以及选择的元素数量。第二行输入 n 个元素，代表给定的数组（1 <= k <= n <= 1e5，1 <= a[i] <= 1e9）
【输出描述】k 次操作后，数组极差的最小值
# 样例
# 输入：
4 2
1 2 5 8
# 输出：
3思路： 排序之后处理，贪心思想：一定是最小的 m 个元素乘 2 和最大的 k-m 个元素除 2，中间 n-k 个元素是没法改变的，想像成长度固定为 n-k 的窗口
代码参考：ali_0315_3.cpp
计算调度团队—2023.02.13
-
介绍团队主要的业务，主要是Java/Python，C/C++ 占 1/3
-
聊项目，30min
-
数据库中的 transaction
-
Python 中的协程和线程
-
进程(Process)：进程是计算机中的程序关于某数据集合的一次运行实例，是操作系统进行资源分配的最小单位
-
线程(Thread)：线程被包含在进程之中，是操作系统进行程序调度执行的最小单位
-
协程(Coroutine)：协程是用户态执行的轻量级编程模型，由单一线程内部发出控制信号进行调度
协程由单一线程内部发出控制信号进行调度，而非受到操作系统管理，因此协程没有切换开销和同步锁机制，具有极高的执行效率。
协程常用于IO密集型工作，例如网络资源请求等；而进程、线程常用于计算密集型工作，例如科学计算、人工神经网络等。
参考：https://blog.csdn.net/FRIGIDWINTER/article/details/124369567
-
-
算法题：15. 三数之和
-
根据上排给出0,1,2 …… n个数(n >= 3)组成的等差数列
在其下排填出对应的n+1个数, 要求下排每个数都是先前上排对应那个数在下排数中出现的次数 , 如：
// 1和2下面的数永远是2和1，0下面对应的数为n-3（n>=6），上排数n-3下面对应的数为1，其它上排数下面对应为0就ok了
// n = 9
0 1 2 3 4 5 6 7 8 9
6 2 1 0 0 0 1 0 0 0
// n = 10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
16 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
// n = 6
0 1 2 3 4 5 6
3 2 1 1 0 0 0
// n = 3
0 1 2 3
1 2 1 0
// n = 4
0 1 2 3 4
2 1 2 0 0
// n = 5 无解代码求解：只能求解 n=3 以及 n>=6 的情况，无法求解 n=4/5 的情况
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
class NumberTB {
int len;
bool success;
vector<int> top;
vector<int> bottom;
public:
NumberTB(int n) {
len = n < 3 ? 3 : n+1;
success = false;
top = vector<int>(len, 0);
bottom = vector<int>(len, 0);
// 赋初始值 0 1 2 3 ... n
iota(top.begin(), top.end(), 0);
}
vector<int> getBottom() {
int id = 0;
while(!success) {
success = true;
for (int i = 0; i < len; ++ i) {
int frequency = getFrequency(top[i]);
if (bottom[i] != frequency) {
bottom[i] = frequency;
success = false;
}
}
cout << "第 " << id++ << " 次尝试：";
for (auto& b: bottom) {
cout << b << ' ';
}
cout << endl;
}
return bottom;
}
// 计算 num 在 bottom 中出现的次数
int getFrequency(int num) {
int cnt = 0;
for (int i = 0; i < len; ++ i) {
if (bottom[i] == num) {
++ cnt;
}
}
return cnt;
}
};
int main()
{
int n;
cin >> n;
NumberTB tb(n);
vector<int> p = tb.getBottom();
for (int i = 0; i <= n; ++ i) cout << i << ' ';
cout << endl;
for (auto& x: p) cout << x << ' ';
cout << endl;
return 0;
}2023.02.15
-
介绍自己的技术栈以及聊项目，25min
-
进程、线程、协程区别？
-
重新开始学一门，多久能学会？
-
[场景题] 很多请求分配给10个服务器，如何分配
-
加一个负载均衡
-
负载均衡的算法有哪些？
- 轮询：负载均衡系统接收到请求后，按照顺序轮流分配给服务器。这种方式非常简单，只管按顺序分配，至于服务器当前负载情况、硬件能力等都不关心，只要服务器还能工作，就可以分配，除非服务器挂了。
- 加权轮询：是轮询方式的一种改进，轮询方式是无差别分配，但实际服务器的处理能力是有差异的，所以需要区别对待。为服务器设置权值，权值高的就多分配点。
- 负载最低优先：将任务分配给当前负载最低的服务器。例如 LVS 可以根据“连接数”判断服务器状态，NGINX 可以根据“HTTP请求数”来判断。这种方式比轮询高级很多，可以感知服务器的状态了，但其复杂度也大大提高了，要收集统计服务器的负载信息。
- 性能最优：优先将任务分配给处理速度最快的服务器，来达到最快响应客户端的目的。此方式也是感知服务器的状态，标准是响应时间。需要收集分析服务器的响应时间，这个工作本身消耗也不小，所以采用采样的方式，不统计所有任务的响应时间，统计一个周期（例如 10秒/1分钟/5分钟）内的状态。优缺点与负载最低优先相同。
- Hash：对请求中的关键信息（如IP）进行hash计算，hash 值相同的请求分配到同一台服务器，例如业务中希望同一用户的请求都由同一台服务器来处理。
-
这个一面二面都过了，但是最后填系统给拒绝了，至今0卧佛有点后悔，o(╥﹏╥)o
广域网团队：主要是路由设备中数据包的转发，主要语言是 C/Go/Python
2023.02.15
-
聊项目：30min
-
OSI 7层模型以及 TCP/IP 协议层
-
数据链路层、网络层、传输层具体负责什么工作，有哪些协议 🔥
- 应用层 ：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等协议。数据单位为报文。
- 传输层 ：为进程提供通用数据传输服务。由于应用层协议很多，定义通用的传输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服务，数据单位为用户数据报。TCP 主要提供完整性服务，UDP 主要提供及时性服务。
- 网络层 ：为主机提供数据传输服务。而传输层协议是为主机中的进程提供数据传输服务。网络层把传输层传递下来的报文段或者用户数据报封装成分组。[IP协议、ICMP协议（网际控制报文协议）、IGMP协议（组管理协议）、ARP协议（地址解析协议）、RARP协议、OSPF（开放的最短路径优先协议）]
- 数据链路层 ：网络层针对的还是主机之间的数据传输服务，而主机之间可以有很多链路，链路层协议就是为同一链路的主机提供数据传输服务。数据链路层把网络层传下来的分组封装成帧。[点对点协议（PPP），高级链路控制协议（HDLC）]
- 物理层 ：考虑的是怎样在传输媒体上传输数据比特流，而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异，使数据链路层感觉不到这些差异。
-
IP 地址是什么和什么之间的通信，端口号作用？
在计算机中，IP地址是分配给网卡的，每个网卡有一个唯一的IP地址，如果一个计算机有多个网卡，则该台计算机则拥有多个不同的IP地址，在同一个网络内部，IP地址不能相同。
由于IP地址不方便记忆，所以有专门创造了域名(Domain Name)的概念，其实就是给IP取一个字符的名字，例如163.com、sina.com等。IP和域名之间存在一定的对应关系。
那么，主机是怎样区分不同的网络服务呢？显然不能只靠IP地址，因为IP 地址与网络服务的关系是一对多的关系。实际上是通过“IP地址+端口号”来区分不同的服务的。
所以在网络编程中，可以使用IP或域名来标识网络上的一台设备。为了在一台设备上可以运行多个程序，人为的设计了端口(Port)的概念，类似的例子是公司内部的分机号码。规定一个设备有216个，也就是65536个端口，每个端口对应一个唯一的程序。
-
TCP、UDP的区别:fire:
无连接和面向连接、用途场景、拥塞控制
-
路由选择算法
- 自治区域内部：内部网关协议 IGP (Interior Gateway Protocol)
- RIP (Routing Information Protocol)：距离矢量协议，使用“跳数”来衡量到达目标地址的路由距离，有 15 跳的限制，所以只适用于小区域，RIP 用 UDP 数据报传送
- OSPF (Open Shortest Path First)：链路状态协议，使用“带宽”、“延迟”作为度量标准，使用 Dijkstra 算法找最短路径，OSPF 直接用 IP 数据报传送
- 自治区域外部：外部网关协议 EGP (External Gateway Protocol)
- BGP (Border Gateway Protocol)：边界网关路由协议是一种用于自治系统之间的外部网关协议。其功能是同其他的BGP系统交换网络可达信息，实现自治系统间无环路的路由信息交换。BGP的最新版本是BGP版本4(BGP-4)，它支持无类域间路由(CIDR)并使用路由聚合机制减小路由表的尺寸。在路由协议中，只有BGP使用TCP作为传输层协议
- 自治区域内部：内部网关协议 IGP (Interior Gateway Protocol)
-
如何查找路由表中的目的路由表项，IP 最长匹配算法 🔥
将目的IP与子网掩码相与，取最长匹配的表项，如果表项很大，可以先使用二叉线索树查找路由表
2023.02.18，整个差不多 55min
-
项目1：quic 建立连接过程
- 客户端发送一个 QUIC 连接请求到服务器。该请求包含客户端支持的协议版本，源 IP 地址和随机生成的连接 ID 等信息。
- 服务器接收到连接请求后，会返回一个包含协议版本、连接 ID、证书以及加密参数等信息的连接响应给客户端。
- 客户端接收到连接响应后，会验证服务器的证书，并使用服务器提供的加密参数建立加密通道。
- 如果客户端需要向服务器发送数据，则需要先发送一个包含数据流 ID 的流控制帧给服务器，告诉服务器该数据所属的流 ID。
- 服务器接收到数据后，会通过相应的数据流 ID 把数据发送回客户端。
在建立连接的过程中，QUIC 使用了 TLS 1.3 协议进行加密，同时支持 0-RTT 快速重连，可以在客户端和服务器之间建立可靠和高效的数据传输通道。
连接ID 和 数据流ID 都是QUIC连接中的重要标识符，但它们的用途和作用是不同的。连接ID用于标识QUIC连接本身，而数据流ID用于标识在连接中传输的单个数据流。参考-CSDN
-
项目2：视野预测中如何考虑容灾情况，WebSocket 处理异步的原理以及建立连接的方式
HTTP 和 WebSocket 都是基于 TCP 的，所以建立连接之前都会有 TCP 三次握手的过程，另外 WebSocket 基于 HTTP 协议握手之后就可以建立一个全双工的通信，即服务器可以主动的向客户端发送消息，HTTP 的建立连接也是需要经过三次握手
-
一个子网内 A 如何访问到 B，也就是 ping 的机制
TTL 字段存放在 IP 头，另外参考 [traceroute 的原理](https://github.com/EricPengShuai/Interview/blob/main/Guide/Guide_1.md#11-%E7%AE%80%E8%BF%B0-traceroute-%E5%91%BD%E4%BB%A4%E7%9A%84%E5%8E%9F%E7%90%86
-
HTTP 了解什么，HTTPS 如何保证输入 aliyun.com 就可以访问到阿里云的网站
关于 HTTPS 如何加密传输，数字证书
- 服务器得去公证人这里先登记，把自己的公钥、名字等等信息报上去，公证人拿到这些信息后，计算一个Hash值，然后再用公证人的私钥把Hash值进行加密，加密后的结果就是数字签名。
- 公证人把登记的信息和这个数字签名合在一起，封装了一个新的文件发给服务器，登记就完成了，而这个新的文件就是数字证书。然后发给服务器，通信的时候须要将他们的证书发给浏览器验证。
- 浏览器拿到证书后，把证书里面的信息也计算一遍Hash，再用提前记录好的公证人的公钥把证书里的数字签名进行解密，得到公证人计算的Hash，两个一对比，就知道这证书是不是公证人签发的，以及有没有被篡改过了！
-
MTU 是什么
在7层网络协议中，MTU是数据链路层的概念。MTU限制的是数据链路层的payload，也就是上层协议的大小，例如IP，ICMP等。数据链路层接收来自上层数据的大小进行了限制，这个限制就是MTU。
因特网协议允许IP分片，这样就可以将数据报包分成足够小的片段以通过那些最大传输单元小于该数据报原始大小的链路了。这一分片过程发生在 IP 层（OSI模型的第三层，即网络层），它使用的是将分组发送到链路上的网络接口的最大传输单元的值。原始分组的分片都被加上了标记，这样目的主机的 IP 层就能将分组重组成原始的数据报了。
-
[算法] 反转链表后面 n 个节点，如果链表长度不超过 n，直接反转整个链表，最后返回头结点
2023.02.22 18:00-19:00
-
自我介绍+聊项目 20min
-
指针和引用在使用过程中有哪些区别吗
地址vs别名、多级vs一级、可为空vs初始化、改变指向vs不改变、sizeof ptr = 8、参数传递
引用的本质就是指针常量:
int &ref = a;实际为int * const ref = &a; -
智能指针了解吗，手撕实现
-
虚继承了解吗 🔥 参考
- 在普通继承中，如果继承的子类本身有虚函数，就会在从父类继承过来的虚表上进行扩展；而在虚继承中，如果子类本身有虚函数，编译器就会为其单独生成一个虚表指针（vptr）和虚函数表，如果子类本身没有新增虚函数，那么vptr就不会存在，也不会有对应的虚函数表
- 普通继承中，是先按父类的方式构造对象，然后在此基础上进行扩展和覆盖；而在虚继承中，父类对象的虚表是单独保存的，通过新增的虚基类指针和虚基类表，来标明各个父类对象内存空间的偏移值
-
coredump 遇到过吗，是如何处理的
参考 T67. coredump 错误很常见，一般怎样调试？
-
分内核态和用户态的原因是啥，什么情况下进入内核态
设计用户态和内核态的本质意义是进行权限保护
- 系统调用：用户进程通过系统调用申请操作系统提供的服务程序完成工作，调用
int $0x80的汇编指令（软中断） - 异常：当 CPU 在执行运行在用户态的程序时，发现了某些事件不可知的异常，这是会触发由当前运行进程切换到处理此异常的内核相关程序中，也就到了内核态，比如缺页异常（硬中断）
- 外围设备的中断：硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等
- 系统调用：用户进程通过系统调用申请操作系统提供的服务程序完成工作，调用
-
TCP 如何保证可靠性，TCP 断开连接时 TIME_WAIT 为什么
-
算法题：33. 搜索旋转排序数组
2023.03.23—14:00—1h
1、视野预测
后端为啥使用 gunicorn 可以提升 flask 的 QPS 从 20 到 150，实际上是由于 flask 原本是多线程异步的，很多请求过来 CPU 直接拉满，改为 gunicorn 同步高并发之后，启动 4 个 woker，每个 worker 6 个线程，处理高并发，现在 CPU 大概只占一半的核心
2、单组播协同
- 为什么使用 QUIC？相比于 TCP 没有三次握手，相比于单独的 UDP 他有一些差错控制以及拥塞控制机制
- 直接推流到边缘不行吗？不行啊，需要组播，另外直接 TCP 传输也不行，TCP 是点对点的，无法组播
- RTCP 不能重传吗？肯定不行啊，RTCP 一般负责对RTP的通讯和会话进行带外管理（如流量控制、拥塞控制、会话源管理等），RTCP消息含有已发送数据的丢包统计和网络拥塞等信息，服务器可以利用这些信息动态的改变传输速率，甚至改变净荷的类型。RTCP消息也被封装为UDP数据报进行传输
- RTMP 数据封装成 RTP 包的过程
- 设计一个 ring buffer
参考1：https://blog.csdn.net/IoT_Peng/article/details/55656150
参考2：https://zhuanlan.zhihu.com/p/534098236
- sizeof int 在编译期间确定的，不可以用来得到动态分配的存储空间的大小，它是运算符不是函数
2023.04.11 17:00-17:40
- 视野预测中用户观看行为是什么，怎么获取的
- 视野预测中为什么要用 LSTM，不用 RNN
- 单组播系统中为什么需要边缘服务器
- 单组播系统中边缘服务器是怎么使用滑动窗口进行重传的
- 哈希表和一般的 map 有什么区别，哈希表怎么做到 O(1) 时间访问元素
- TCP/IP 协议栈，传输层怎样工作的
- TCP 包的结构你自己如何设计
- 算法题：简单表达式求值 1+2*3/4+5，本质是 后缀表达式求值
好像是做广告推荐的？面试官感觉很匆忙的样子，纯纯 KPI
2023.06.07 16:00-17:00
-
自我介绍 5min，问了一点单组播协同项目，不深入
-
C++ 中 struct 和 class 区别
-
inline 失效场景 参考
-
智能指针
-
g++ 编译过程
-
epoll，mutex，event_loop 了解吗
-
如何防止一个头文件 include 多次
// ① 使用宏定义避免重复引入 #ifndef _NAME_H #define _NAME_H //头文件内容 #endif // ② 使用#pragma once避免重复引入 #pragma once class Student { //...... }; // ③ 使用_Pragma操作符 _Pragma("once");
-
算法：手撕 LRU
2023.09.26—16:30-17:00—服务端开发
-
定时器类为什么要使用红黑树，可以使用跳跃表吗
-
定时任务了解吗，定时任务在单独一个线程中吗，如果任务阻塞这个线程就阻塞了吗
-
寻路算法 Astar 了解吗
经过估值计算之后再进行 Dijkstra 搜索
-
用过 golang ? 那协程了解吗
-
Linux 熟悉吗，如何创建一个守护进程
1、创建子进程，退出父进程
2、将子进程重新创建一个会话
3、设置掩码，更改工作目录
4、关闭、重定向文件描述符，并将标准输入、标准输出和标准错误输出重定向到 /dev/null 文件
-
如何让程序后台运行，又如何让后台的程序来到前台
-
客户端连接不上服务器有哪些可能，如何解决
-
分布式了解过吗，mprpc：zookeeper 会自动请求服务器吗
-
mprpc 如何做负载均衡，nginx 怎么做
-
浮点数怎么存储的
-
内存对齐了解吗，为什么要进行对齐
1、平台原因(移植原因)：不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。
2、性能原因：经过内存对齐后，CPU的内存访问速度大大提升
2023.12.20 — 14:10 - 14:50
-
mutex 和 semaphore 区别，semaphore 为 1 时和 mutex 一样吗
-
分布式了解多少，集群部署如何做到状态同步（写到数据库 redis + mysql
-
nginx 的流量分发在4层和7层的区别
-
单例模式、锁 + 双重检测为何提高效率
2024.01.02 — 19:00-20:00
- STL 好处、使用场景；C++11 新特性
- 多态概念，重载区别，发生时期
- vector 使用时注意场景，哈希表底层
- 红黑树、B 树、B+ 树
- 堆和栈区别
- struct 和 class 区别
- [场景题] 海量文件取 top10 词频元素 参考
- [算法题] 53. 最大子数组和 LCR 006. 两数之和 II - 输入有序数组
2024.01.09 — 19:00-19:30
-
对 transformer 了解多少？（真的服...
-
手写入堆和出堆的操作，基本上就是堆排序