面经集合 - 2021

推荐搭配 面试相关知识 食用。

2021春 腾讯成都 CSIG 后台开发 暑期实习

这次是腾讯云负责数据库的组。一面的时候没咋看数据库，后面得赶紧了解和复习。

一面

1. 自我介绍
2. 自我介绍的时候我提到了晚上八点的夜宵券，面试官说晚上九点半下班是常态，大概是 995 的作息。emmm 不是 996，而且报销打车费，还能接受。
3. 会 Java 吗，不会（我简历上也没写会啊）
4. 给一个数据流，要求维护 Top n 的数组，每输入一个数就输出前 10 大的数。

本来第一反应是堆 (C++ priority queue) 的，但是堆只能输出前 10 大的。于是就还是用数组来做，对每个新来的数进行冒泡排序就行。时间复杂度 $O(n)$。

有没有更快的？这么说就只有 $O(\log n)$ 了。想到这点以后去寻找 $O(\log n)$ 的方法，不难想到平衡二叉树 (C++ set/map) 就可以搞定。

5. 给定两个数组，要求两个数组相同的元素。

第一反应是两个集合的交集 (C++ set_intersection)，但是建立两个集合可是 $o(m\log m + n\log n)$ 的。所以认真想一下吧。

如果是有序的情况，最简单的就是双指针分别把数组遍历一遍，$O(m + n)$ 简单易懂。
不过，如果 $n >> m$ 时，可以考虑遍历 $m$ 数组，对 $n$ 使用二分，复杂度是 $O(m\log n)$。

如果无序，最简单的就是排序后再按上面的方法，复杂度 $O(m\log m + n\log n)$。
如果 $n >>m$，也可以只排 $m$，然后遍历 $n$，二分 $m$，复杂度 $O(m\log m + n\log m) = O(n\log m)$。

6. CAP 是什么。我甚至没听说过。问了才知道是分布式的概念。不会。
7. 三次握手的过程，老生常谈了。
8. TIME_WAIT 和 CLOSE_WAIT 是什么。这是四次挥手的过程，但是我正好只记了过程，没记这两个是啥。危
9. ACID 是什么。数据库的东西，我还没复习。危
10. RAFT 是什么。依旧是没听过的概念。后来才查到也是分布式的。

总结

挂了。毕竟 Java 和分布式都不会。不过我简历上也没写会这两个，不懂为什么要捞我面试 hhhh。

2021春 阿里成都 研发工程师 C/C++ 暑期实习生

笔试

投完阿里，马上就会去做一个类似于行测的东西，以及参加一场笔试。

今年的行测的形式是：

• 10 道语文文段阅读理解（类似于高考语文的第 1 题）
• 10 道图表数据题（这题有点阴间，全是给五年的数字，让你判断这五年的增长率变大了还是变小了，而且给的时间很短，每题只有 60s，可能都来不及用计算器）
• 10 道找规律（图形的那种，看不出来规律就只能随便选）
• 98 道性格测评（每个题给三个选项，可能有好有坏，让你从三个选一个最符合自己的、一个最不符合自己的）

然后就是笔试，是牛客网测试，需要电脑录屏+摄像头录像+手机监控消息，两个题给一个小时。

第一个题是一个水题，给一个类似下面的迷宫：

@...
.#..
..##
#...

其中 @ 是初始点，# 是墙。然后给四条指令（上北下南左西右东），问最后到达的坐标。如：

EAST
SOUTH
WEST
NORTH

将会走 -> (1, 4) -> (2, 4) -> (2, 3) -> (1, 3)。输出 1 3。

直接模拟就可以了。

---

二题有点意思。后来查了一下发现是原题 LeetCode 1388. 3n 块披萨。

我是按 dp 做的 $O(n^2)$，不过似乎还有贪心+算法能做到 $O(n\log n)$，这种做法不要求掌握。

一面

1. 自我介绍
2. 项目，哪些是自己兴趣 哪些是课程要求
3. C++ Python 区别
4. C++ 面向对象的核心
5. C++ 为什么要封装
6. C++ 为什么要多态
7. C++ 哪些方面有多态
8. C++ 自己的多态
9. new delete malloc free
10. const #define，const 的好处
11. 进程和线程的区别
12. 进程交互方式，有没有写过
13. 多个线程读写同一块数据会有线程
14. 有没有了解死锁
15. 数据库索引，优点及其缺点
16. 使用数据库开发的时候要注意什么点
17. 聊聊事务
18. 聊聊事务的特性
19. 分布式事务有了解吗
20. 聊聊 UDP 和 TCP
21. TCP 流量控制和拥塞控制
22. 描述一个数据结构
23. C++ unoredered_map 扩容过程
24. 随便讲一种排序
25. 从项目背景、目标、方案聊一个项目
26. 有没有逛什么技术社区
27. 反问

考得不完全按照套路出牌，感觉答得不怎么样（和美团一个水平，感觉铁挂），但是居然过了。

二面

1. 自我介绍
2. 进程的状态，以及转换状态，在什么时候会转换状态
3. 线程和进程的区别
4. 进程的通信方式
5. 线程的同步方式
6. 索引的作用
7. InnoDB 索引结构，其特点是什么
8. 所有查询都可以用到索引吗（必须索引命中）
9. 事务的概念
10. ACID
11. MySQL 如何保证事务（锁机制）
12. redo log 和 undo log
13. 乐观锁 和 悲观锁
14. tcp/ip 每一层，以及其作用
15. 三次握手和四次挥手的过程
16. 链表结构，以及其查找、插入、删除复杂度
17. 快速排序描述，以及其最好、平均、最坏复杂度
18. 项目（为什么要写、怎么选择技术栈、遇到了什么问题）
19. 有没有后来居上的经历，觉得自己能达到目标吗
20. 有没有啃硬骨头的经历
21. 反问

三面

这个三面直接拖了两个月，早拿到腾讯 offer 了，去阿里实习肯定是去不了了，但是据说阿里面试过了不去，秋招也可以直通终面，就还是面一下。

1. 自我介绍
2. 为什么不读研
3. 项目
4. 竞赛经历
5. 哪儿
6. 学生工作的一些经历，难在哪里
7. 有没有和其他人合作、沟通
8. 对未来有什么期待
9. 有投其他大厂吗 挂掉的有自己总结经验吗
10. 反问

阿里的三面更加偏向项目、克服困难、合作、沟通，技术这方面考的不多。

2021春 腾讯深圳 PCG 后台开发 暑期实习

得知 CSIG 挂掉的当天晚上 11 点，腾讯的 HR 打电话问我拒绝面试的原因。哈？

问了一下，原来是另一个部门的 HR 想捞我（猜测可能是我正在 CSIG 的面试流程，于是系统自动拒绝了面试）。简单了解了一下，便约了第二天的面试。

一面

一面一个小时。

1. 自我介绍
2. C++ 智能指针（不会 赶紧说自己最近用 Python）
3. 最近 Python 写了什么项目，以及某一个项目中遇到了什么困难
4. Python 的垃圾回收机制
5. MySQL 的数据引擎（MyISAM, InnoDB）
6. InnoDB 用的是什么数据结构（B+ 树）
7. B+ 树和 B 树有什么区别（不会）
8. 聚簇索引和非聚簇索引有什么区别（不清楚 口胡）
9. 索引的结构是什么（口胡）
10. MySQL 数据库中的事务隔离性如何保证（不会 还被反问一句 基础的都不会吗 呜呜呜别骂了别骂了，还没学结果又考到了）
11. 线程和进程的区别
12. 进程的消息队列是什么（口胡）
13. 进程的同步和互斥是什么
14. 用户级线程和系统级线程是什么
15. 僵尸进程和孤儿进程是什么
16. TCP 四次挥手，以及其中客户端、服务端的状态
17. TCP 拥塞控制
18. （简历上提到 Docker）Docker 的使用程度（能够安装）
19. （简历上提到 Nginx）Nginx 的功能
20. Nginx 的负载均衡算法（只会轮训和加权轮训）
21. （Nginx 提到 HTTPS）HTTPS 加密方式和握手过程（口胡）
22. LeetCode 322. 零钱兑换

---

一面过了，果然不管人多菜，只要面得够多，总有一家会捞你。这一面很多问题都是面试官追问的，所以没答上也影响。当然，复盘的时候了解一下这些知识也挺好。

二面

二面一个半小时（然而算法题写了一个小时）。

1. 自我介绍
2. 上来问我是不是搞过 ACM，我连忙说只是参加了集训后面没去了，然后面试官给了一道硬核算法题（LeetCode 480. 滑动窗口中位数），我写了一个多小时（面试官说要不不写了说下思路，我说再调试最后一次，然后过了）
3. TCP 三次握手，少握手一次可以吗（不可以，反例是第二次握手丢包了，客户端不知道）
4. TCP 拥塞控制（一面问过了hhh）
5. Nginx 为什么这么快（不知道）
6. 有没有了解过 Nginx 的底层（无）
7. Nginx 的 Master 和 Worker 分别做什么（不知道）
8. 数据库事务的性质 (ACID)
9. 数据库的原子性是怎么实现的（记录日志，回滚）
10. 数据库的日志是什么
11. 数据库的持久性是怎么实现的（记录日志，重做）
12. 线程和进程的区别（一面问过了hhh）
13. 进程通信的方法（五个）
14. 进程通信的管道分为有名管道和无名管道，二者的区别
15. OS 的缓存一致性怎么实现（在缓存上标记是否被修改）

三面

三面半个小时，应该是主管面。

1. 自我介绍
2. 问一面不会的东西：僵尸进程和孤儿进程
3. MySQL 事务隔离级别
4. B+ 树的结构
5. Docker 原理
6. Linux top 命令
7. Linux free 命令
8. Linux 查询端口占用命令 (lsof -i:8000)
9. 多路复用 Select
10. C++中将基类对象赋值给派生类指针这个操作是允许的吗？派生类对象赋值给基类指针呢？
11. 调用函数时发生的过程（计算机组成原理？）
12. 调试的方法
13. vector 内存管理
14. 深拷贝和浅拷贝的区别
15. 设计 hashmap
16. 从项目出发：问 Scrapy 底层
17. JS 闭包是什么
18. 决策树是什么

2021春 微软苏州 SDE - STCA Summer Intern

笔试

笔试使用的 Codility 平台还挺不错，答完就能出分，小数据的 Correctness 和大数据的 Performance 是分开计算的。不过只能提交一次，最后搞的一套题也没有拿满分主要还是太菜了。

1. 给一个非负整数 n，重新排列 n 中每个数字的顺序，使之组成一个最大的整数（如果结果大于 1e9 就返回 -1）。由于给定的 n 是 int，所以很小，转成 string 排序再转回 int 就可以了。但我应该是没考虑到 n 溢出 int 的情况，导致挂了。

2. 类似于 LeetCode 56. 合并区间，不过不是要求输出区间，而是每个区间代表一个吊车能运送的范围，给定起点和终点，问起点的东西能否通过吊车运送到终点。这个题小数据 Correctness 也没过，可能是两个点重合的情况，应该直接输出 true。

3. 给一个数组，问其中长度大于等于 3 的连续子序列的数量，如 [1, 2, 3, 3, 3, 4, 5, 6] 应当返回 5（注意，长度为 4 的子序列包含两个长度为 3 的子序列）。如果结果大于 1e9 就返回 -1。结果这题是因为忘了判这个情况，导致 Performance 只拿了 60 分。

2021春 中望龙腾 C++研发

之前也没听说这公司，只是看到学校贴了招聘，就随手扫了码投了简历，宣讲会也没去。昨天 HR 晚上十一点联系我今天十一点半面试，我说有课。晚上十二点 HR 又给我打电话，让我下午一点来面，地点在学校附近的酒店。

本来不是很想去线下的，但是人家专门为了我拖到了下午，有点不好有意思，于是还是去了。就当是第一次线下面试的练习。

第二天过去了，发现没啥人来，签到表上只有四个人（也就是说上午只有四个人来面试了），感觉我也是来走个过场。没想到这公司还挺有意思。

一面

关于技术方面只问了 C++，具体不记得了，包括但不限于：

1. 多继承
2. 虚函数实现
3. 动态指针
4. 用过的 STL
5. unordered_map 和 map 的底层实现

然后简单聊了一下项目。

然后就是面试官（似乎是主管）介绍自己公司，本来我来也就图一乐，但是听他说的还真有点心动。

中望是一家民企，不是做互联网的，而是做工业软件的，所以相较于互联网公司的急功急利，中望更加养生，一是 955、加班有加班费，二是越老越吃香。

感觉还有点想去，不过 base 只有北京、深圳和武汉，而且走了这条路以后，很难再转互联网企业，只能一条路走到黑。但是，如果不想走互联网公司的 996 的话，它的优点也能和这些抵消；而且，国内也有同类软件（苏州的浩辰），即使就算倒闭了，也不至于没饭吃。

笔试

是关于 C++ 的，10 个选择和 7 个简答。简答题如下：

1. 看代码读结果，一个小的计算题
2. 如何防止对象被拷贝
3. 如何显示代码所在文件名、函数名、行数
4. 简述快排原理，什么时候达到最坏复杂度，是多少
5. 给定球（球心在 (0,0,0)，半径 R）和射线（(0,0,0) -> (x0, y0, z0)），编程求解球和射线的交点
6. 给定 1970/01/01 是周四，编程求解给定日期是星期几
7. 以字符串形式给一个数，求其重新排序后，最小的合法（即不能 0 开头）的数（如 123320 输出 102233）

二面

1. 聊一个 C++ 项目
2. 用过什么 STL 容器
3. const 作用
4. docker 用到什么程度
5. 是否有虚构造函数
6. C++ 最近看过什么书，看了多少
7. 平时什么写 C++（VS），哪个版本的 VS
8. VS 下断点的快捷键（平时用鼠标，正解是 F9）
9. 确认不准备考研
10. 下来有了解过我们公司吗
11. 描述一个自己性格方面的缺点
12. 老家是哪的
13. 为什么想来外地工作，有没有什么顾虑（没办法，老家这边软件开发搞不起来）
14. 有北上广的 offer 吗
15. 反问

2021春 美团成都 后台开发

笔试

感觉比阿里、MS 的要难一点。

1

#include<bits/stdc++.h>

using namespace std;

/*
小美最近在学习操作系统。

流是操作系统中一个重要的概念。在 Linux 操作系统中，/dev/random 和 /dev/urandom 是两个重要的设备，它们可以提供永不为空的随机字节数据流。

小美自己也实现了一个类似于 /dev/random 的设备 /dev/crandom，但是它只能提供预先设定好但循环不断的某个小写字母排列。例如预先设定的字符串为 abcdefgh...xyz，那么这个设备会提供永不为空的字符串流 abcdefgh...xyzabcdefg...xyzabc...。

小美想利用这个设备生成一段文字，但她想知道恰好生成完这段文字时，浪费了这个流的多少个字符。

样例说明

拿取生成流中字母的情况如下，拿取的字母用下划线表示。

abcde...lmn...def...hij...stu..zab...mno...

在生成好最后一个 n 的时候，浪费了没有标下划线的 59 个字符。



输入描述
第一行一个长为 26 的字符串 s，表示预先设置在设备中的小写英文字母排列。

第二行一个长为 n 的字符串 a，表示小美想要生成的字符串。

1 ≤ n ≤ 105，保证 s 一定是一个小写字母的排列，且 a 中只包含小写英文字母。

输出描述
输出一行一个整数，表示恰好生成完这个字符串时，浪费了这个流的多少个字符。

qwertyuiopasdfghjklzxcvbnm
meituan
59
*/

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<vector<int>> dis(26, vector<int>(26, 26));
    string t, s;
    cin >> t;
    int len = t.length();
    t += t;
    for (int i = 0; i < len; i++)
    {
        int chi = t[i] - 'a';
        dis[chi][chi] = 25;
        for (int d = 1; d < len; d++)
        {
            int chj = t[i + d] - 'a';
            dis[chi][chj] = d - 1;
        }
    }
    cin >> s;
    int ans = s[0] == t[0] ? 0 : dis[t[0] - 'a'][s[0] - 'a'] + 1;
    for (int i = 1; i < s.length(); i++)
        ans += dis[s[i - 1] - 'a'][s[i] - 'a'];
    cout << ans;
}

2

#include<bits/stdc++.h>

using namespace std;

/*
题目描述：
学校正在举行喝奶茶比赛。这次比赛准备了 n 杯奶茶（为了比赛公平，奶茶里没有珍珠，椰果等各种小料，也就是纯奶茶），编号为 1 到 n。第 i 杯奶茶有 ai 毫升，这 n 杯奶茶准备的吸管都是一样的，每秒最多能吸上来 C 毫升奶茶，选手只能通过吸管吸奶茶，不能捅破包装把奶茶倒进嘴里，这样对其他选手不公平。

选手按队伍参赛，小团所在的队伍有 m 个人，比赛要求队内的每个人选取编号在一个连续区间的奶茶喝，当然参赛选手也可以不喝任何奶茶。但是选定一杯奶茶喝就一定要喝完，不然的话这杯奶茶就被浪费了。

如果小团所在队打破了校记录，那么她们队的每个人都将获得一年的奶茶畅饮卷，所以她想知道所有奶茶都被喝完的最短用时。



输入描述
第一行三个整数 n, m, C，意义如题目描述。

第二行 n 个整数，第 i 个整数为 ai。

1 ≤ n, m ≤ 105, 1 ≤ C ≤ 50, 1 ≤ ai ≤ 104。

输出描述
输出一行一个整数，表示所有奶茶都被喝完的最短用时，为了保证精度，请输出答案上取整后的结果。


样例输入
5 3 4
5 8 3 10 7
样例输出
4
*/


int n, m, c, ans;
int a[int(1e5+5)];

bool ok(int tc)
{
    int remain = tc, cur_m = 1;
    for (int i = 0; i < n; i++)
    {
        if (remain >= a[i])
            remain -= a[i];
        else
        {
            if (tc < a[i])
                return false;
            remain = tc - a[i];
            cur_m++;
        }
    }
    return cur_m <= m;
}

bool _ok(int tc)
{
    bool ans = ok(tc);
    cout << tc << (ans ? ": true" : ": false") << "\n";
    return ans;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int sum = 0;
    cin >> n >> m >> c;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }

    int low_t = sum / m / c, high_t = sum / c + 1;
    while (low_t < high_t)
    {
        // assert low_t <= ans <= high_t
        int mid_t = (low_t + high_t) / 2;
        if (ok(mid_t * c))
            high_t = mid_t;
        else
            low_t = mid_t + 1;
    }
    cout << low_t;
}

3

#include<bits/stdc++.h>

using namespace std;

/*
时间限制： 1000MS
内存限制： 262144KB
题目描述：
小团现在有两个等大的多重集合（与集合的区别仅是在可以在集合中出现重复元素）A 和 B。她现在想让 A 集合与 B 集合相等。她会先选择一个非负整数 x，然后让 A 集合中的所有数都加上 x 并对 m 取模。也就是说，对于 A 中的全部元素 a，都把 a 变成 (a + x) mod m。

她想知道这个最小的 x 是多少，才能使经过变换后 A = B。并且她保证至少存在一个满足条件的 x。



输入描述
第一行两个正整数 n, m，n 表示 A, B 两集合分别有 n 个元素；

第二行 n 个非负整数 ai，表示 A 多重集。

第三行 n 个非负整数 bi，表示 B 多重集。

1 ≤ n ≤ 2000, 1 ≤ m ≤ 109, 0 ≤ ai , bi < m。

输出描述
输出一个非负整数，表示最小的 x 值。


样例输入
6 8
1 1 4 5 1 4
3 0 4 0 3 0
样例输出
7
*/

typedef pair<int, int> P;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    map<int, int> m1, m2;
    int n, mod;
    cin >> n >> mod;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        m1[temp]++;
    }
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        m2[temp]++;
    }
    vector<P> v1(m1.begin(), m1.end()),
        v2(m2.begin(), m2.end());
    int len = v2.size();
    int ans = mod;
    for (int dis = 0; dis < len; dis++)
    {
        int curans = (v2[dis].first - v1[0].first + mod) % mod;
        for (int i = 0; i < len; i++)
        {
            int j = (i + dis) % len;
            if (v1[i].second != v2[j].second || (v2[j].first-v1[i].first+mod)%mod != curans)
                break;
            if (i == len - 1)
                ans = min(ans, curans);
        }
    }
    cout << ans;
}

4

#include<bits/stdc++.h>

using namespace std;

/*
小美和小团的班上有 n 个人，分别编号为 1 到 n。其中小美的编号为 1，小团的编号为 2。

班上有个值日表 ai,j。第一天由小美值日，第二天由小团值日。接下来的每一天，如果今天是 i 值日，昨天是 j 值日，那么明天就是 ai,j 值日。值日表是已经规划好的，保证今天值日的同学明天一定不值日。

小美想知道，第 m 天值日的同学的编号。

输入描述
第一行两个整数 n, m，表示班上有 n 个同学和小美想知道的天数。

接下来 n 行，每行 n 个整数，表示值日表 ai,j (0 ≤ ai,j ≤ n)。保证有且仅有对角线上的数字是 0。

1 ≤ n ≤ 500, 1 ≤ m ≤ 1018。

输出描述
输出一行一个整数，表示第 m 天值日的同学的编号。


样例输入
3 7
0 3 2
3 0 3
2 1 0
样例输出
1
*/

#define int long long

typedef pair<int, int> P;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> table(n, vector<int>(n, 0)), last(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> table[j][i];

    if (m <= 2)
    {
        cout << m;
        return 0;
    }
    m -= 2;
    int day[3] = { 1, 2, 0 };
    while (m)
    {
        day[2] = table[day[0]-1][day[1]-1];
        //cout << "m=" << m << " people=" << day[2] << "\n";

        int& _last = last[day[0]-1][day[1]-1];
        if (_last == 0)
        {
            _last = m;
        }
        else
        {
            int diff = _last - m;
            m %= diff;
        }

        day[0] = day[1];
        day[1] = day[2];
        m--;
    }
    cout << day[2];
}

5

#include<bits/stdc++.h>

using namespace std;

/*
小美在做化学实验，这个实验需要配置很多种浓度溶液，因此配溶液之前需要详细计算溶液浓度（用质量分数表示），避免误操作。
实验初始溶液质量和质量分数分别为 m0 , ω0%。小美会进行如下两种操作：
1、A(m, ω) 表示向目前的溶液中加入质量为 m 质量分数为 ω% 的溶液；
2、B 表示撤销上一步 A 操作。
对于每一步操作，小美都想知道当前溶液的质量与质量分数。
质量分数 ω 按如下方式计算：设溶液中溶质质量为 x，溶液总质量为 y，则

输入描述
第一行两个整数 m0 , ω0。
第二行一个整数 n，表示操作数。
接下来 n 行，每行一条操作，格式为：A m ω 或 B，保证 m 和 ω 都是整数。
如果当前操作是撤销，但是没有可撤销的 A 操作，那么忽略这条撤销操作。
1 ≤ n ≤ 5×104, 1 ≤ m0, m ≤ 104, 0 ≤ ω0, ω ≤ 100。
输出描述
n 行，第 i 行表示第 i 次操作以后的溶液质量和质量分数 mi, ωi，其中 mi 为整数，ωi 为浮点数（保留 5 位小数），之间用一个空格隔开。

样例输入
20 50
4
A 30 0
B
B
A 80 14
样例输出
50 20.00000
20 50.00000
20 50.00000
100 21.20000
*/

class Liquid
{
private:
    double m1; // 溶质
    int m0; // 溶质+水
public:
    Liquid(int m0, int omega)
    {
        this->m0 = m0;
        this->m1 = (double)m0 * omega / 100;
    }
    Liquid()
    {
        this->m0 = 0;
        this->m1 = 0;
    }
    int get_m0()
    {
        return m0;
    }
    double get_omega()
    {
        return m1 / m0 * 100;
    }
    void add(int m0, double omega)
    {
        this->m0 += m0;
        this->m1 += m0 * omega / 100;
    }
};

const int max_n = (int)5e4 + 5;
Liquid liquid[max_n];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int m0, omega, n, cur = 0;
    cin >> m0 >> omega;
    liquid[0] = Liquid(m0, omega);
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char operation;
        cin >> operation;
        if (operation == 'A')
        {
            cin >> m0 >> omega;
            liquid[cur + 1] = liquid[cur];
            liquid[cur + 1].add(m0, omega);
            cur++;
        }
        else
        {
            if (operation == 'B')
                if (cur > 0)
                    cur--;
        }
        printf("%d %.5f\n", liquid[cur].get_m0(), liquid[cur].get_omega());
    }

}

一面

1. 聊项目，详细地聊了两个项目
2. 有了解过哪些设计模式
3. 设计模式的原则
4. MySQL 的事务隔离级别
5. MySQL 的两种引擎
6. 介绍 InnoDB 的索引结构（B+ 树）
7. InnoDB 索引分类（聚簇索引 非聚簇索引）
8. 已知表结构 order(id, code, name) 且以 code 建立了索引，编写 SQL 查询按 code 降序、第 10000 页（每页 10 个）的结果：SELECT * FROM order ORDER BY code DESC LIMIT 99991, 10
9. 上述 SQL 在效率方面有什么问题，以及如何优化（MySQL Limit 优化）
10. code 上的索引（即非聚簇索引）记录了什么
11. InnoDB 行锁的分类
12. InnoDB 行锁的实现 (Record Locks, Gap Locks 和 Next-Key Locks)
13. Next-Key Locks 有死锁问题吗
14. 介绍一下悲观锁和乐观锁
15. OSI 的七层
16. HTTP 在哪一层
17. GET 和 POST 的区别
18. TCP 和 UDP 的区别
19. TCP 在哪一层
20. TCP 的可靠性是如何实现的
21. 用户从输入 url 到获取到信息过程中发生了什么
22. 进程和线程的区别
23. 线程的通信方式
24. 进程的通信方式
25. 内存缓冲区溢出会发生什么（不清楚面试官问的是什么，栈溢出/内存不够发生交换）
26. 分段和分页有什么区别
27. 有哪些进程调度策略
28. 链表内指定区间反转，限时 15 分钟
29. 有一个 5 升的桶和一个 3 升的桶，如何得到 4 升的水？
30. 有9个球，体积、外观完全一样，其中有一个球里面有一个珍珠，这个球比其它8个球质量要重一些；现在有一个天平，如何用2次机会将这个球称出来？
31. 反问

2021春 滴滴 后端研发工程师（C++/Go）

笔试

选择题

就是面试的一堆常考题，但有不少 Java 题，还有 Java 看代码写结果（？可我是面 C++/Go 啊）

1

#include<bits/stdc++.h>

using namespace std;

/*
时间限制： 1000MS
内存限制： 65536KB
题目描述：
给一个字符串s，你可以至多选择两个不同位置的字符进行交换（可以选择不交换，保留原串），问所有可能中字典序最小的串。

有关字典序：对于长度相同的串a和串b，串a的字典序小于串b当且仅当存在一个位置i使得串a和串b的前i-1个字符完全相同且串a的第i个字符小于串b的第i个字符。即a1=b1,a2=b2,...ai-1=bi-1且ai<bi。

输入描述
一行一个字符串s，保证串中都为小写字母('a'~'z')。字符串长度<=200000

输出描述
输出一个串t，表示所有可能中字典序最小的串。


样例输入
aaazbcdeadcd
样例输出
aaaabcdezdcd
*/

int main()
{
    string t;
    cin >> t;
    int front = 0, end;
    for (char cur = 'a'; cur <= 'z'; cur++)
    {
        // front 为第一个不等于 cur 的字母
        // front 从上一次地方开始
        for (; front < t.length() && t[front] == cur; front++);
        // end 为第一个等于 cur 的字母
        for (end = t.length() - 1; end >= front && t[end] != cur; end--);
        
        if (end > front)
        {
            swap(t[end], t[front]);
            break;
        }
    }
    cout << t;
    return 0;
}

2

应该是个假题。

#include<bits/stdc++.h>

using namespace std;

/*
时间限制： 1000MS
内存限制： 65536KB
题目描述：
X星是宇宙中一个非常敬畏生命和热爱生命的星球。在X星上建有一个规模很大而且设备很先进的救援站。

为了方便救援工作的开展，X星规定：任意两点之间的一条边（即两个点之间的一条道路）出现问题，都不会将救援站和居民点之间的联系完全切断。也是说救援站到其他顶点都有两条或者两条以上的路线，这样在救援过程中，即使某一条路线出现问题，还可以通过其他路线到达目的地。

已知救援站和部分居民点之间，以及某些居民点之间有直接的边相连（所有的边均为无向边）。

现在请你编写一个程序，根据给出的救援站和居民点之间，以及某些居民点之间的连接信息，判断每一组输入数据是否满足X星的规定。如果满足规则请输出“Yes”，否则输出“No”。



输入描述
多组输入，第1行输入一个正整数T表示输入数据的组数。

对于每一组输入数据：

第1行输入两个正整数N和M，其中N表示救援点和居民点的数量，对应N个顶点。其中编号为1的顶点表示救援点，编号为2到N表示(N-1)个居民点。M表示救援站和居民点之间，以及某些居民点之间边的数量。（N<=1000，M<=100000）

接下来M行每行包含两个正整数，分别为相邻的两个顶点（救援点或居民点）的编号，两个正整数之间用空格隔开。

输出描述
针对每一组输入数据，如果输入数据满足X星的规定，任意一条边的断开都不会影响到救援站到居民点之间的连通性，输出“Yes”，否则输出“No”。


样例输入
2
4 4
1 2
2 3
3 4
4 1
4 4
1 2
2 3
3 4
1 3
样例输出
Yes
No
*/

struct UnionFindSet
{
    int n;
    vector<int> father;
    UnionFindSet(int n)
    {
        this->n = n;
        father = { 0 };
        for (int i = 1; i <= n; i++)
            father.push_back(i);
    }
    int getFather(int n)
    {
        return father[n] == n ? n : (father[n] = getFather(father[n]));
    }
    void merge(int i, int j)
    {
        father[i] = getFather(j);
    }
    int haveSameFather(int i, int j)
    {
        return getFather(i) == getFather(j);
    }
};

bool solve()
{
    int m, n;
    cin >> n >> m;
    vector<vector<int>> neighbors(n + 1);
    vector<pair<int, int>> p;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        p.push_back({ a, b });
        neighbors[a].push_back(b);
        neighbors[b].push_back(a);
    }
    for (int i = 1; i <= n; i++)
    {
        if (neighbors[i].size() < 2)
            return false;
    }

    UnionFindSet ufs(n);
    for (auto i : p)
    {
        ufs.merge(i.first, i.second);
    }
    for (int i = 2; i <= n; i++)
    {
        if (!ufs.haveSameFather(i, 1))
            return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    for (int t = 0; t < T; t++)
        cout << (solve() ? "Yes" : "No") << "\n";
}

一面

1. 平时用什么语言开发（C++ 和 Python）
2. 指针和引用的区别
3. 智能指针，以及几种智能智能的区别
4. memcpy memmove strcpy 的区别
5. 多态的实现
6. VTABLE 在什么时候生成
7. B 类继承于 A 类，B 类有三个对象，问 A 类虚函数的 VTABLE 有几项
8. const 作用于成员函数有什么用（分为放在前面和放在后面）
9. new 的内存可以 free 吗（未定义行为，且 free 不会调用析构函数）
10. 用过哪些 stl
11. vector 的底层
12. map 的底层及其优点
13. unordered_map 和 map 的区别
14. vector 迭代器什么时候会失效（原来 push_back、erase、insert 都可能会失效，这也太拉了吧）
15. 析构函数应该什么时候都定义为虚函数吗（我回答是，面试官提示在不允许被继承时就不用定义了）
16. Python pass 的作用
17. Python xrange 和 range 的区别（这可是 Python2 的东西，Python3 range == Python2 xrange 已经没有内存占用的问题了，面试官不会真的就是打开题库 -> 念完题目吧）
18. Python GIL
19. 多线程编程
20. TCP 四次挥手
21. 为什么四次挥手是四次而不是三次
22. 为什么有 TIME_WAIT 状态
23. 有了解过 epoll 吗（没有）
24. 有无阻塞编程的经历吗
25. 有用过 MySQL 和 Redis 的经历吗
26. MySQL 的引擎，默认是哪个
27. InnoDB 的数据结构
28. Linux 查看某进程的 CPU 占用使用什么命令，使用 top 命令怎么按 CPU 降序排序（我用支持鼠标操作的 htop，面试官觉得可）
29. Linux 实时输出文件内容（tail -f）
30. 聊项目
31. Nginx 的结构（一 Master 多 Worker）
32. 了解 I/O 多路复用吗
33. 口胡快排算法
34. 口胡一个在一个旋转排序数组查找某数。我的思路是寻找旋转排序数组中的最小值，找到最小值以后即可标准二分查找

刚开始坐着信号不好，后来站着面完了，面试官看情况没有让我写题，只用口胡，很 nice~

二面

1. 聊项目，四个项目一个一个聊
2. Docker 原理
3. 口胡算法：合并两个有序数组，以及如何在合并的时候去重
4. 平时用 Nginx 吗（平时用 Caddy，夸了一波 Caady 自动申请 TLS，再反过来吹 Nginx 高并发强）
5. Nginx 负载均衡算法
6. 自己未来的规划

三面

1. 聊项目
2. 多态（一面聊过了吧）
3. 内存分配算法（算是冷门知识点了，还好学了 OS 写了博客，有点印象）
4. 有过网络编程（socket 编程）经验吗
5. tcp 三次握手
6. 用过哪些 STL 库
7. set unordered_set 区别
8. vector 插入的复杂度
9. 两个数如果满足 a * 2 < b，我们称 (a, b) 为一个数对。给定数组，求数组中有多少个数对（每个数只能被用一遍）。

这个题排序后无脑贪心会有问题：考虑 1 3 5 7，a 选 1 时不能选最合适的 3 作为 b，正解是 (1 ,5) (3, 7) 两对。

不过有一个性质，如果一开始找到了 (1, 3) 而后面又需要这个 3，可以在数对中把 3 换成更大的数（或把 1 换成更小的数），并没有破坏之前的数对。

面试没写出来，面试尝试找了一下原题，没找到，只找到一个有一点类似的题。后来突然发现，可以仿照这个题，把这个数组排序后切成两半，然后双指针贪心，在左边从大到小找 a，在右边从大到小找 b。

贪心算法的正确性需要证明，如果按此法找到某 b 对应的某 a，而最优解中 b 对应的是 a 左边的数（或 a 右边的数），这两个解是等价的。

int solve(vector<int> arr)
{
    sort(arr.begin(), arr.end());
    int n = (int)arr.size();
    int i = n / 2 - 1, j = n - 1, ans = 0;
    while (i >= 0 && j >= n / 2)
    {
        if (arr[i] * 2 < arr[j])
        {
            i--;
            j--;
            ans++;
        }
        else
        {
            i--;
        }
    }
    return ans;
}

我还为该函数编写了一些测试，可见代码。

2021春 腾讯深圳 IEG 后台开发

一面

地点：深圳
上班时间：995 22点以后报销打车
腾讯八月会有集体转正，建议在七月之前工作

1. 问项目
2. C++ map 和 set 的区别
3. 有没有比 map 效率更高的，查询时间复杂度是多少
4. C++ 如何调试
5. 深拷贝和浅拷贝是什么（不考虑语言）
6. 内存零拷贝是什么（不知道）
7. 字节对齐是什么
8. C++ 智能指针
9. 快排复杂度
10. 描述快排算法。给定样例 3 5 1 2，选择 3 为基准值，简单描述如何快排
11. 快排是稳定排序吗（是）
12. 给定 10 亿个数，求前 10 大（小根堆）
13. 向堆插入一个数的复杂度和最坏复杂度（都是 $O(\log n)$）
14. 堆排序是稳定排序吗（是）
15. 建立一个堆的复杂度 （$`O(n)$）
16. 进程通信方式
17. 了解进程通信的概念吗（下面五连问警告）
18. 匿名管道是什么（不知道）
19. 常用信号（没了解过）
20. 共享内存（也不知道）
21. socket（想了一下，发现也不知道）
22. socker server 流程（放弃了）
23. 32 位 OS 的内存寻址空间多大，怎么算的（2^32B=4GB）
24. 确认单位是字节吗（对，因为内存按字节编址）
25. 缺页中断是什么
26. 缺页替换有哪些算法（FIFO、LRU、时钟）
27. MySQL 有哪两种引擎（MyISAM、InnoDB）
28. 两种都有外键吗（MyISAM 还真不支持）
29. 两种引擎锁的粒度（MyISAM 只支持表级，InnoDB 支持表级和行级）
30. 索引的底层架构及其好处（B+）
31. 慢查询是什么 有什么优化方法吗
32. 有用过、听说过其他的数据库吗
33. 有使用过 Go 吗
34. Linux 查询进程 pid：ps aux | grep
35. pid 有什么用（进程唯一标识符）
36. 查看进程信息：top
37. 查看每个 CPU 核的利用率：在 top 中按 1，或使用 htop
38. 查看磁盘空间适用情况：df -h
39. 查看端口占用：lsof -i:8000
40. 有编写过多线程、多进程程序吗
41. 有编写过 C++ 多线程、多进程吗
42. 为什么要使用线程池（线程创建慢，线程池可以复用）
43. 创建线程为什么慢（需要系统中断、创建线程控制块等）

2021春 腾讯成都 CSIG 后台开发

之前都是 HR 来捞我，这次是一面面试官来捞我，还主动让我加微信。（可能是真缺人）

一面

1. 自我介绍
2. 确认工作地点、不读研、毕业以后想在成都发展，还确认了一下我是哪里人（应该是真缺长期工作的人）
3. 介绍你的项目
4. 想做前端还是后端
5. 介绍一下 REST API
6. 输入域名到显示页面的过程（梅开 n 度）
7. 介绍一下 HTTPS 加密的原理和过程
8. HTTPS 是对称还是非对称（都有吧）
9. MySQL 的引擎是什么（InnoDB）
10. InnoDB 的数据结构（B+ 树），以及它的好处
11. InnoDB 叶子结点存的是什么
12. 为什么 InnoDB 推荐主键使用 auto_increment
13. ACID 是什么
14. Linux 命令行如何查看进程（top 或 ps）
15. 进程状态的 S R Z 是什么
16. Linux 命令行如何监控流量大小（nload）
17. 简述 Docker 原理
18. 平时用什么语言开发
19. 简述 C++ 虚函数表
20. 算法题，本地开 IDE 写，应该有手就行

求二维数组（元素为int类型）内横向的所有平衡线，平衡线的意思是该线上面的所有数之和和下面的所有数之和相等

比如数组int a[][] = {{1,1,0},{1,2,1},{1,1,3},{3,2,1}};
1,1,0
1,2,1
1,1,3 ---> 这就是一个平衡线
3,2,1

其中第3行就是一个平衡线，只需要打印出3（或者2，index从0开始）
注意需要找到所有的平衡线，语言不限，假设二维数组是a[m][n], 需要写出完整的代码
20分钟内完成

21. 算法题 两数之和，口胡就行
22. 反问（问了一下工作时间是 10-9.5-5）
23. 加一下面试官微信

---

加了微信以后面试官还帮我推进进度，还发了关于实习生报销打车费的政策，人非常 nice~

二面

我以为推进进度就是尽快（实际也没有快多少）的意思，结果 10:40 面完不到一个小时就约二面了，约在当天 17 点。后来才知道这还是主管面。第一次感受到腾讯的效率 2333

1. 自我介绍
2. 聊项目，聊遇到了什么问题（主管面，聊得比较深入，可以多聊一点）
3. 聊一个开发调试过程比较困难的经历
4. 有没有接触过 HTTP 底层的东西（我说没有，这里就没往下聊了）
5. 知道 TCP 四次挥手的 TIME_WAIT 吧，HTTP 短连接会导致 TIME_WAIT 过多，如何解决这个问题（即 TIME_WAIT 的快速回收和重用，不会）
6. 优化一个特定场景（主管说这个场景没有正解，应该是他们实际业务的场景）的快排中选择 pivot 的算法，使得快排的时间复杂度更稳定。十分钟的问题我大概有五分钟都在纠结这个场景到底是什么，大概是从别的服务查到了一批数据，是以一个数据包的形式发送过来，可以读第一个，可以读最后一个，但是不能随机定位到中间读一个（所以也没法直接用三者取中法）。最后我也没想到什么办法（毕竟没怎么了解过排序方面的优化），提了一句追求复杂度稳定的话，我更喜欢归并排序。

最后三个问题我都没咋答上来，觉得自己铁挂了。面完官网以后看了一眼，过了，真是有惊无险，也可能是我的项目经历聊得比较深入。

HR 面

1. 毕业不打算考研吗，为什么
2. 个人更注重什么（短期利益、职场关系、个人成就等等）
3. 什么时候能实习
4. 能接受加班吗
5. 哪儿人
6. 在腾讯有直系亲属吗
7. 身体健康吗
8. 有投其他大厂吗，走到哪一步流程了
9. 你是一个什么样的人
10. 周围的人如何评价你
11. 你的缺点
12. 反问

最后也是拿到了这个实习 Offer~