腾讯校招 - 腾讯 - 校招 | Value's Blog = 繁華落盡似水流年 = 寄予厚望还请善待

# 一面（心态爆炸）

一开始问了我的研究方向 ，讲一讲论文提出的方法.
问我 熟悉的语言 是什么？我说 C++
程序的空间分布？ 这里我居然还卡了一下，栈、堆、全局 / 静态存储区、常量存储区、代码区。栈区主要用于存储一些局部变量，空间由操作系统来管理；堆是动态内存空间，由程序员管理内存的申请和释放。全局 / 静态区用于存储全局变量和静态变量；面试官说先到这. (我当时紧张其实忘记了常量区，但是我记得有五个区，所以卡了)
vector你了解吗？你知道它的内存管理吗?``vector 是 STL 内的一个顺序容器，其空间是从堆上申请的， vector 可以通过 size() 来获取其实际存储的变量数目， capacity() 可以用于获取所占空间，当 size()和capacity() 相等时，会进行扩容的操作，这个扩容的系数依赖于不同的操作系统，它会去堆内找一片更大的空间分配给这个 vector ，将之前的内容复制过来，然后释放由来申请的空间. 比较常用的扩容系数是什么? ，我回答 2 或者 1.5.
你说vecotr申请的空间是在堆上，那比如说我想要你去验证它所申请的空间是在堆的，你如何证明？ 这个我没有想到，但是面试官一直引导我，几乎快说出答案了，最后我才反应过来，这里直接说方法。首先在 main 函数内写 int a[10000000000]; 程序会报段错误，其是栈空间溢出了（局部变量存储在栈中）; 然后换成另外一段程序 vector<int> res(10000000000); 程序顺利编译执行，说明 vector 所申请的空间和前面的语句所申请的空间不是同一片，所以应该是在堆上的.
讲一下三次握手的流程？ 首先客户端发送 SYN报文 给服务端，服务端接收到 SYN报文 后，发送 ACK确认 ，同时把 SYN 置为 1，客户端收到响应后，向服务端发送 ACK确认 ，服务端收到确认后，三次握手连接建立成功.
为什么是三次啊. 首先 2 次是一定不可以的. TCP 是一个全双工的协议，而且 TCP 采用了确认机制，所以必须至少 4 次才能建立双向的连接。其次是在第二次握手的同时向客户端发送 ACK确认 可以和服务端建立连接的请求 SYN=1 合并.
那么挥手是几次呢？ 四次. 为什么呢？不可以三次吗？ 四次挥手中间的连接中断和 ACK确认 两个报文不能合并，因为当被动断开方收到断开连接请求的同时，可能还有数据没有发送完。此时不能仓促的将断开连接请求和 ACK确认 请求合并.
TIME_WAIT状态你了解吗？是哪一方的状态，是主动断开连接方还是被动断开连接方. 被动断开连接方
你平时有没有用过一些抓包工具啊. 比如说我想看一些客户端和服务端的一些状态. wireless shark，但是我用的并不多.
那在Linux下呢？有什么命令可以查看网络状态. 我说记不太清楚了，其实我并不知道，后来查了一下。可以用 netstat ，具体还得再去看看
TCP是可靠传输的吗？它是怎么保证可靠传输的. 是可靠传输的，它有很多机制来保证。超时重传、序号和确认、流量控制、拥塞控制。于是他又问 TCP里面是不是有一个字段也可以保证这个可靠传输? 校验和
既然TCP有这么多机制来保证可靠校验，传输层只是网络协议的一层，那么在应用层，为什么还需要做额外的可靠性校验. 这里我回答不上。面试官也引导了我，可惜我不会！后来面试官说先到这里，让我写两道题.
股票买卖,一次交易
链表逆置
最后就结束了！比较令人烦的是腾讯会议搞的这个 面呗 ，不知道是我不会用还是设计的有问题，题目也没办法调试，没有输入输出，我也没办法验证我写的对不对。最后特意写了一个输入输出，还需要写一个链表.
最后简单聊了一些，问我有什么问题需要问他的？我随便问了一些，他说就一个问题吗？当时面的巨烂，瑟瑟发抖，于是乎又问了几个。最后结束的时候问我实验室，发现面试官是一个实验室的学长！那还挺幸运. hh

两个星期了还是没有约二面，感觉过了一面还有一个池子。最近腾讯突然又搞了一个笔试，今天（2023-03-30）去看一下进度，发现流程结束了，还是老老实实被八股，准备项目吧！

# 笔试（2024-03-31）

感觉腾讯这次是笔试比较简单，思维题不多，都是常规题. (52min)

# Q1

小红拿到了一个无向图，其中一些边被染成了红色。
小红定义一个点是 “好点”，当且仅当这个点的所有邻边都是红边。
现在请你求出这个无向图 “好点” 的数量。
注：如果一个节点没有任何邻边，那么它也是好点。

输入描述

第一行输入两个正整数 n,m，代表节点的数量和边的数量。
接下来的 m 行，每行输入两个正整数 u,v 和一个字符 chr，代表节点 u 和节点 v 有一条边连接。如果 chr 为 'R'，代表这条边被染红；'W' 代表未被染色。
$1\leq n,m \leq 10^5$
$1\leq u,v \leq n$

输出描述

一个整数，代表 “好点” 的数量。

示例 1

输入

4 4
1 2 R
2 3 W
3 4 W
1 4 R

输出

1

说明

只有 1 号节点是好点。

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	using namespace std;
	using ll = long long;
	constexpr int N = 1e5 + 10;
	int cnt1[N], cnt2[N];
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m; cin >> n >> m;
	for(int i = 0; i < m; i ++ ){
	char c;
	int a, b; cin >> a >> b >> c;
	if(c == 'W') cnt1[a] ++, cnt1[b] ++ ;
	else cnt2[a] ++, cnt2[b] ++ ;
	}
	int res = 0;
	for(int i = 1; i <= n; i ++ ){
	res += (cnt1[i] == 0);
	}
	cout << res << endl;
	return 0;
	}

$时间复杂度:O(max(n, m))$ ， $n$ 表示节点数目， $m$ 表示边的数据
$空间复杂度:O(n)$

# Q2

小红拿到了一个链表。她准备将这个链表断裂成两个链表，再拼接到一起，使得链表从头节点到尾部升序。你能帮小红判断能否达成目的吗？
给定的为一个链表数组，你需要对于数组中每个链表进行一次 “是” 或者 “否” 的答案回答，并返回布尔数组。
每个链表的长度不小于 2，且每个链表中不包含两个相等的元素。所有链表的长度之和保证不超过 10^5

示例 1

输入

[{1,2,3},{2,3,1},{3,2,1}]

输出

[true,true,false]

说明

第三个链表无论怎么操作都不满足条件。

	/**
	* struct ListNode {
	* int val;
	* struct ListNode *next;
	* ListNode(int x) : val(x), next(nullptr) {}
	* };
	*/
	class Solution {
	public:
	/**
	* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
	*
	*
	* @param lists ListNode 类 vector
	* @return bool 布尔型 vector
	*/
	bool deal(ListNode* head){
	int f = head->val;
	while(head->next && head->next->val > head->val) head = head->next;
	if(head->next == nullptr) return true;
	head = head->next;
	while(head->next && head->next->val > head->val) head = head->next;
	if(head->next != nullptr) return false;
	return f > head->val;
	}
	vector<bool> canSorted(vector<ListNode*>& lists) {
	int n = lists.size();
	vector<bool> res(n);
	for(int i = 0; i < n; i ++ ){
	ListNode*cur = lists[i];
	res[i] = deal(cur);
	}
	return res;
	}
	};

$时间复杂度:O(nm)$ ， $n$ 表示 lists 的长度， $m$ 表示每个链表的长度
$空间复杂度:O(1)$

# Q3

小红拿到了一个有 n 个节点的无向图，这个图初始并不是连通图。
现在小红想知道，添加恰好一条边使得这个图连通，有多少种不同的加边方案？

输入描述

第一行输入两个正整数 n,m，用空格隔开。
接下来的 m 行，每行输入两个正整数 u,v，代表节点 u 和节点 v 之间有一条边连接。
$1\leq n,m \leq 10^5$
$1\leq u,v \leq n$
保证给出的图是不连通的。

输出描述

一个整数，代表加边的方案数。

示例 1

输入

4 2
1 2
3 4

输出

4

说明

添加边 (1,3) 或者 (1,4) 或者 (2,3) 或者 (2,4) 都是可以的。

示例 2

输入

4 1
1 3

输出

0

说明

无论添加哪条边，都不可能使得该图变成连通图。

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	using namespace std;
	using ll = long long;
	constexpr int N = 1e5 + 10;
	int p[N], cnt[N];
	int find(int x){
	if(p[x] == x) return x;
	return p[x] = find(p[x]);
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m; cin >> n >> m;
	for(int i = 0; i <= n; i ++ ) p[i] = i, cnt[i] = 1;
	for(int i = 0; i < m; i ++ ){
	int a, b; cin >> a >> b;
	int pa = find(a), pb = find(b);
	if(pa == pb) continue;
	cnt[pa] += cnt[pb];
	p[pb] = pa;
	}
	unordered_set<int> S;
	for(int i = 1; i <= n; i ++ ) S.insert(find(i));
	if(S.size() >= 3) cout << 0 << endl;
	else{
	auto it = S.begin();
	int x = *it;
	it ++ ;
	int y = *it;
	cout << (ll)cnt[x] * cnt[y] << endl;
	}
	return 0;
	}

$时间复杂度:O(max(n, m))$ ， $n$ 表示节点数目， $m$ 表示边的数目
$空间复杂度:O(n)$

# Q4

小红拿到了一个数组，她准备将数组分割成 k 段，使得每段内部做按位异或后，再全部求和。小红希望最终这个和尽可能大，你能帮帮她吗？

输入描述

输入包含两行。
第一行两个正整数 n, k , ( $1\leq k \leq n \leq 400$ )，分别表示数组的长度和要分的段数。
第二行 n 个整数 $a_i (0 \leq a_i \leq 10^9)$ ，表示数组 a 的元素。

输出描述

输出一个正整数，表示最终的最大和。

示例 1

输入

6 2
1 1 1 2 3 4

输出

10

说明

小红将数组分为了：
[1, 4] 和 [5, 6] 这两个区间，得分分别为： $1 \oplus 1 \oplus 1 \oplus 2 = 3 和 3 \oplus 4 = 7$ 。总得分为 3+7=10。
可以证明不存在比 10 更优的分割方案。
注： $\oplus$ 符号表示异或操作。

示例 2

输入

5 3
1 0 1 1 0

输出

3

示例 3

输入

3 3
1 1 2

输出

4

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	using namespace std;
	using ll = long long;
	constexpr int N = 410;
	ll a[N];
	ll dp[N][N];
	int s[N][32];
	ll tp[N][N];
	ll get(int l, int r){
	ll res = 0;
	for(int i = 0; i < 32; i ++ ){
	int cnt = s[r][i] - s[l - 1][i];
	if(cnt % 2 == 1) res += (1 << i);
	}
	return res;
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, k; cin >> n >> k;
	for(int i = 1; i <= n; i ++ ) cin >> a[i];
	for(int i = 0; i < 32; i ++ ) s[0][i] = 0;
	for(int i = 1; i <= n; i ++ ){
	for(int j = 0; j < 32; j ++ ) s[i][j] = s[i - 1][j] + ((a[i] >> j) & 1);
	}
	for(int i = 1; i <= n; i ++ ){
	for(int j = i; j <= n; j ++ ) tp[i][j] = get(i, j);
	}
	memset(dp, -0x3f, sizeof dp);
	dp[0][0] = 0;
	for(int i = 1; i <= n; i ++ ){
	for(int j = 1; j <= min(i, k); j ++ ){
	int k = 0;
	ll maxv = -0x3f3f3f3f3f3f3f3f;
	while(k < i){
	ll cur = dp[k][j - 1] + tp[k + 1][i];
	maxv = max(maxv, cur);
	k ++ ;
	}
	dp[i][j] = maxv;
	}
	}
	cout << dp[n][k] << endl;
	return 0;
	}

$时间复杂度:O(n^2k)$ ， $n$ 表示数组的长度， $k$ 表示分段的数目
$空间复杂度:O(n^2)$

# Q5

小红拿到了一个字符矩阵，她可以从任意一个地方出发，希望走 6 步后恰好形成 "tencent" 字符串。小红想知道，共有多少种不同的行走方案？
注：每一步可以选择上、下、左、右中任意一个方向进行行走。不可行走到矩阵外部。

输入描述

第一行输入两个正整数 n,m，代表矩阵的行数和列数。
接下来的 n 行，每行输入一个长度为 m 的、仅由小写字母组成的字符串，代表小红拿到的矩阵。
$1\leq n,m \leq 1000$

输出描述

一个整数，代表最终合法的方案数。

示例 1

输入

3 3
ten
nec
ten

输出

4

说明

第一个方案，从左上角出发，右右下左左上。
第二个方案，从左上角出发，右右下左左下。
第三个方案，从左下角出发，右右上左左下。
第四个方案，从左上角出发，右右上左左上。

	#include <iostream>
	#include <cstring>
	#include <cstdio>
	#include <algorithm>
	#include <vector>
	#include <map>
	#include <set>
	#include <queue>
	#include <cmath>
	#include <numeric>
	#include <unordered_map>
	#include <unordered_set>
	#define rint register int
	#define ull unsigned long long
	using namespace std;
	using ll = long long;
	constexpr int N = 1010;
	char g[N][N];
	int dp[N][N][8];
	string tx = "tencent";
	int dx[4] = {0, 1, 0, -1};
	int dy[4] = {1, 0, -1, 0};
	int n, m;
	int dfs(int x, int y, int index){
	if(dp[x][y][index] != -1) return dp[x][y][index];
	if(g[x][y] != tx[index]) return dp[x][y][index] = 0;
	if(index == 6) return dp[x][y][index] = 1;
	int res = 0;
	for(int i = 0; i < 4; i ++ ){
	int xx = x + dx[i];
	int yy = y + dy[i];
	if(xx < 0 \|\| yy < 0 \|\| xx >= n \|\| yy >= m) continue;
	res += dfs(xx, yy, index + 1);
	}
	return dp[x][y][index] = res;
	}
	int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 0; i < n; i ++ ){
	string s; cin >> s;
	for(int j = 0; j < m; j ++ ) g[i][j] = s[j];
	}
	memset(dp, -1, sizeof dp);
	ll res = 0;
	for(int i = 0; i < n; i ++ ){
	for(int j = 0; j < m; j ++ ){
	if(g[i][j] == 't') res = res + dfs(i, j, 0);
	}
	}
	cout << res << endl;
	return 0;
	}

$时间复杂度:O(nm)$ ， $n$ 表示矩阵的长， $m$ 表示矩阵的宽
$空间复杂度:O(nm)$

校招

# 一面（心态爆炸）

# 笔试（2024-03-31）

# Q1

# Q2

# Q3

# Q4

# Q5

多线程编程(C API)

蚂蚁集团校招