面经集合 - 2021 | 小灰灰灰灰的博客

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

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

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

# 一面

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

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

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

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

第一反应是两个集合的交集 (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)$ 。

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

# 总结

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

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

# 笔试

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

今年的行测的形式是：

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

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

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

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

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

EAST
SOUTH
WEST
NORTH

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

直接模拟就可以了。

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

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

# 一面

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

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

# 二面

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

# 三面

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

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

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

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

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

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

# 一面

一面一个小时。

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

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

# 二面

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

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

# 三面

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

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

# 2021春微软苏州 SDE - STCA Summer Intern

# 笔试

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

给一个非负整数 n，重新排列 n 中每个数字的顺序，使之组成一个最大的整数（如果结果大于 1e9 就返回 -1）。由于给定的 n 是 int，所以很小，转成 string 排序再转回 int 就可以了。但我应该是没考虑到 n 溢出 int 的情况，导致挂了。
类似于 LeetCode 56. 合并区间 (opens new window)，不过不是要求输出区间，而是每个区间代表一个吊车能运送的范围，给定起点和终点，问起点的东西能否通过吊车运送到终点。这个题小数据 Correctness 也没过，可能是两个点重合的情况，应该直接输出 true。
给一个数组，问其中长度大于等于 3 的连续子序列的数量，如 [1, 2, 3, 3, 3, 4, 5, 6] 应当返回 5（注意，长度为 4 的子序列包含两个长度为 3 的子序列）。如果结果大于 1e9 就返回 -1。结果这题是因为忘了判这个情况，导致 Performance 只拿了 60 分。

# 2021春中望龙腾 C++研发

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

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

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

# 一面

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

多继承
虚函数实现
动态指针
用过的 STL
unordered_map 和 map 的底层实现

然后简单聊了一下项目。

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

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

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

# 笔试

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

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

# 二面

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

# 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());
    }

}

# 一面

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

# 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";
}

# 一面

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

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

# 二面

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

# 三面

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

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

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

面试没写出来，面试尝试找了一下原题，没找到，只找到一个有一点类似的题 (opens new window)。后来突然发现，可以仿照这个题，把这个数组排序后切成两半，然后双指针贪心，在左边从大到小找 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点以后报销打车腾讯八月会有集体转正，建议在七月之前工作

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

# 2021春腾讯成都 CSIG 后台开发

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

# 一面

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

算法题两数之和 (opens new window)，口胡就行
反问（问了一下工作时间是 10-9.5-5）
加一下面试官微信

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

# 二面

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

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

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

# HR 面

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

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

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

# 一面

# 总结

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

# 笔试

# 一面

# 二面

# 三面

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

# 一面

# 二面

# 三面

# 2021春 微软苏州 SDE - STCA Summer Intern

# 笔试

# 2021春 中望龙腾 C++研发

# 一面

# 笔试

# 二面

# 2021春 美团成都 后台开发

# 笔试

# 1

# 2

# 3

# 4

# 5

# 一面

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

# 笔试

# 选择题

# 1

# 2

# 一面

# 二面

# 三面

# 2021春 腾讯深圳 IEG 后台开发

# 一面

# 2021春 腾讯成都 CSIG 后台开发

# 一面

# 二面

# HR 面

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

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

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

# 2021春微软苏州 SDE - STCA Summer Intern

# 2021春中望龙腾 C++研发

# 2021春美团成都后台开发

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

# 2021春腾讯深圳 IEG 后台开发

# 2021春腾讯成都 CSIG 后台开发