c++面经

公**** ： 内 ****君*** ，聚焦 自动驾驶、汽车、机器人、芯片、互联网 等高科技行业， 实习、校招 、社招 ，技术发展，行业动态。服务 ：简历修改、升学就业咨询、offer选择导读

Case 2

一面

C++ 常使用哪些 STL 容器 map 和 unordered_map 区别和底层实现是什么 map 除了查询复杂度高还有什么缺点 vector 增删改查复杂度分别是什么 vector 支持越界检查吗 讲讲 vector 扩容 push_back 的复杂度一定是 O(1) 吗 push_back 和 emplace_back 区别 emplace_back 可以传对象吗 移动构造函数和拷贝构造函数区别 智能指针用过哪些，讲讲特点 shared_ptr，引用计数何时增加和减少 如何用普通指针初始化 shared_ptr 用普通指针初始化 shared_ptr 这种用法有什么坏处 static 变量可以用在哪些地方，分别有什么特点 static 修饰的普通变量初始化在 main 函数执行前还是后 类的 static 方法可以访问非 static 对象吗 设计模式知道哪些

编程题 1 /* 有一片海域，中间有一些小岛，找出一共有多少个「实心矩形小岛」。 海域以二维数组给出，数组中包含 0 和 1 两种元素，0 代表海，1 代表地面。被一片海包围的地面成为小岛，小岛通过水平和竖直方向与相邻的陆地连接而成。可以假设数组边缘之外都是海。 「实心矩形小岛」的定义为: 四条边与二维数组边界平行、内部均为 1 的小岛

int numRectangleIslands(vector<vector>& grid){ // Your code here... }

def numRectangleIslands(self, grid): # Your code here... pass

Input: {{1, 1, 0, 0, 0}, {1, 1, 0, 0, 0}, {0, 0, 0, 1, 1}, {0, 0, 0, 1, 1}}

Output: 2

Input: {{1, 1, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {1, 1, 0, 1, 1}}

Output: 2 */ #include #include using namespace std;

void dfs(vector<vector> &g, int i, int j, int &cnt, vector<vector> &vec, vector<vector> &visited) { if (visited[i][j]) return; visited[i][j] = true; if (g[i][j] == 0) return; ++ cnt; vec[0][0] = min(vec[0][0], i); vec[0][1] = min(vec[0][1], j); vec[1][0] = min(vec[1][0], i); vec[1][1] = max(vec[1][1], j); vec[2][0] = max(vec[2][0], i); vec[2][1] = min(vec[2][1], j); vec[3][0] = max(vec[3][0], i); vec[3][1] = max(vec[3][1], j); for (int h = -1; h <= 1; ++ h) { for (int v = -1; v <= 1; ++ v) { if (h == 0 && v == 0 || h != 0 && v != 0) continue; int x = i + h, y = j +v; if (x < 0 || x >= 4 || y < 0 || y >= 5) continue; dfs(g, x, y, cnt, vec, visited); } } }

int main() { vector<vector> g = {{1, 1, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {1, 1, 0, 1, 1}}; vector<vector> visited(4, vector(5, false)); int res = 0; for (int i = 0; i < 4; ++ i) { for (int j = 0; j < 5; ++ j) { vector<vector> v = {{4, 5}, {4, 0}, {0, 5}, {0, 0}}; int cnt = 0; dfs(g, i, j, cnt, v, visited); if (v[0][0] == v[1][0] &&v[0][1] == v[2][1] && v[3][0] == v[2][0] &&v[3][1] == v[1][1] && cnt ==(v[3][0] - v[0][0] + 1) * (v[3][1] - v[0][1] + 1)) ++ res; } } cout << res; return 0; } DFS过程中维护左上、左下、右上、右下四个点，并维护访问到的位置数 一次 DFS 结束后根据四个顶点判断是否为矩形 并计算四个顶点组成的矩形的面积，和本次访问到的位置数作对比，若不相等，则该矩阵不为实心

编程题2 /* 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。

请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

int findInRotatedArray(vector arr, int target) { // Your code here... }

def findInRotatedArray(arr, target): # Your code here... pass

示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4

示例 2： 输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

示例 3： 输入：nums = [1], target = 0 输出：-1 */ #include #include using namespace std; int main() { // vector v = {4,5,6,7,0,1,2}; vector v = {1}; int target = 0; int l = 0, r = v.size() - 1; bool found = false; while (l <= r) { int m = (r - l) / 2 + l; if (target == v[m]) { cout << m; found = true; break; } else if (v[m] >= v[l]) { if (target < v[m] && target >= v[l]) r = m - 1; else l = m + 1; } else { if (target > v[m] && target <= v[r]) l = m + 1; else r = m - 1; } } if (!found) cout << -1; return 0; }

二面

详细介绍XX实习 什么是分区表，有什么作用 什么是全局二级索引，有什么作用 介绍 B+Tree B+Tree page 如何在内存和磁盘上转移 B+Tree 相比于其他索引结构的优点在哪 测试数据量有多大，有多少行 实际业务数据量有多大 知道 MySQL 和 Postgres 的性能差异吗 OLTP 和 OLAP 各适用于什么场景 OLTP 和 OLAP 实现上有何区别 了解多表 join 吗 知道哪些 join 方法，分别介绍一下 详细介绍天池比赛 简单介绍别的实习项目 三面

详细讲 XX实习项目 为什么选择优化区块执行时间 MPT 原理，节点怎么存的 系统吞吐率测试实验如何设置的 pprof 如何使用的 详细讲XX项目 RPC 框架的原理和底层实现 RPC 和 Restful API 对比，各自适合在什么场景下使用 双 buffer 缓存系统的原理 假如动态地对帖子热度排序，怎么设计 数据量大，内存放不下，怎么排序 读数据库中的帖子热度值时，别的线程会写入吗 详细讲XX实习项目 车道线检测算法 车道线的 NMS 怎么设计的 对 Django 和 Vue 的了解 对 JavaScript 了解吗，执行上与 C++ 的区别 详细讲XX 出现网络分区，多数派分区重新选出 leader，此时 client 发送请求给旧 leader，后续会怎么样 网络恢复后会发生什么情况

智能指针 shared_ptr 如何实现 如何让多个 shared_ptr 对象共享引用计数 让 shared_ptr 线程安全该怎么设计 shared_ptr 的使用可能造成内存泄露吗 weak_ptr 作用 unique_ptr 与 shared_ptr 不同

设计一个域名转换服务器，提供两个接口，一个是将长链接转换为短链接，一个是将短连接转换为长链接。用户在浏览器输入短链接会自动转为长链接。