Case 1
虚拟内存相关详细讲一下
讲讲左值和右值
什么时候使用右值
完美转发
假如 a 是 T 的左值引用,T 是 int&& 类型的,那么 a 实际上是什么
讲一下智能指针
shared_ptr 和 unique_ptr 区别,以及性能对比
weak_ptr 及其作用
shared_ptr 是线程安全的吗
lambda 表达式有哪些捕获类型
讲讲多态及实现机制
虚基类
多继承的时候,虚函数表指针怎么存
using std::cin 和 在using namespace std 后使用cin有什么区别
元编程
一个有环链表,两个速度不一样的指针移动,起始位置也不一定一样,它们一定相遇吗
详细介绍自己所做项目
编程题:
数据中最小的k个数
class Solution {
private:
int randInRange(int l, int r) {
srand(time(0));
return rand() % (r - l + 1) + l;
}
int partition(vector<int> &input, int l, int r) {
if (l >= r) return l;
int idx = randInRange(l, r);
swap(input[idx], input[r]);
int large = l - 1;
for (int i = l; i < r; ++ i) {
if (input[i] < input[r])
swap(input[++ large], input[i]);
}
swap(input[++ large], input[r]);
return large;
}
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
int n = input.size();
int l = 0, r = n - 1;
vector<int> res;
while (l <= r) {
int idx = partition(input, l, r);
if (idx + 1 == k) {
res.assign(input.begin(), input.begin() + k);
return res;
} else if (idx + 1 < k)
l = idx + 1;
else
r = idx - 1;
}
return res;
}
};
首先介绍了自动驾驶系统涉及的研发方向,问我对哪个感兴趣
自我介绍
发现性能瓶颈使用过什么方法
如何发现死锁
在开发时制定什么样的规则可以避免死锁
如何调试内存泄露
如何调试 core dump
虚拟内存介绍
每个进程的虚拟内存有多大
如果物理内存大于 4G,可以不使用虚拟内存吗(安全性)
线程切换要进入内核态吗
一个很大的二维数组存在内存中,是按行读取快还是按列读取快(CPU cache,局部性原理)
map 和 unordered_map区别
unordered_map 使用什么方法解决 hash 冲突
编程题:
LRU,要求自己实现双向链表
#include <bits/stdc++.h>
using namespace std;
struct Node {
int key;
int value;
Node *left;
Node *right;
Node(int k, int v): key(k), value(v) {
left = nullptr;
right = nullptr;
}
Node(int k, int v, Node *l, Node *r): key(k), value(v), left(l), right(r) {}
};
struct BiList {
Node *head;
Node *tail;
BiList() {
head = new Node(0, 0);
tail = head;
}
void insert_front(Node *node) {
auto first = head->right;
node->right = first;
head->right = node;
node->left = head;
if (first) {
first->left = node;
}
if (tail == head)
tail = head->right;
}
pair<int, int> erase_end() {
if (tail == head)
return {-1, -1};
Node *tmp = tail;
tmp->left->right = nullptr;
tail = tmp->left;
int key = tmp->key, val = tmp->value;
delete tmp;
return {key, val};
}
void erase(Node *node) {
if (node == tail)
tail = node->left;
auto left = node->left;
auto right = node->right;
left->right = right;
if (right)
right->left = left;
delete node;
}
Node *first() {
return head->right;
}
~BiList() {
Node *ptr = head;
while (ptr) {
Node *tmp = ptr->right;
delete ptr;
ptr = tmp;
}
}
};
class LRUcache {
private:
int cap;
BiList *lst;
unordered_map<int, Node*> mp;
public:
LRUcache(int k): cap(k) {
lst = new BiList();
}
void set(int key, int value) {
if (mp.find(key) == mp.end()) {
if (mp.size() == cap) { //evict
auto p = lst->erase_end();
int rm_key = p.first;
mp.erase(rm_key);
}
} else {
auto node = mp[key];
lst->erase(node);
}
lst->insert_front(new Node(key, value));
mp[key] = lst->first();
}
int get(int key) {
if (mp.find(key) == mp.end())
return -1;
auto node = mp[key];
int value = node->value;
lst->erase(node);
lst->insert_front(new Node(key, value));
mp[key] = lst->first();
return value;
}
~LRUcache() {
delete lst;
}
};
int main() {
int n, k;
cin >> n >> k;
LRUcache cache(k);
vector<int> res;
for (int i = 0; i < n; ++ i) {
int opt;
cin >> opt;
if (opt == 1) {
int x, y;
cin >> x >> y;
cache.set(x, y);
} else {
int x;
cin >> x;
res.push_back(cache.get(x));
}
}
for (int num : res)
cout << num << " ";
return 0;
}
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<char>>& 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 <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>> &g, int i, int j, int &cnt, vector<vector<int>> &vec, vector<vector<bool>> &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<int>> g = {{1, 1, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 0, 0, 0, 1},
{1, 1, 0, 1, 1}};
vector<vector<bool>> visited(4, vector<bool>(5, false));
int res = 0;
for (int i = 0; i < 4; ++ i) {
for (int j = 0; j < 5; ++ j) {
vector<vector<int>> 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<int> 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 <iostream>
#include <vector>
using namespace std;
int main() {
// vector<int> v = {4,5,6,7,0,1,2};
vector<int> 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 不同
设计一个域名转换服务器,提供两个接口,一个是将长链接转换为短链接,一个是将短连接转换为长链接。用户在浏览器输入短链接会自动转为长链接。
Case 3
自我介绍
讲讲之前工作做的性能优化的工作
如何想到要做这方面的优化的
对 linux 和编译了解多吗
讲讲工作中接触到的、自己了解比较深的linux知识
它在哪些底层系统会经常使用
在 XX 做了哪些工作
cv 和工程都有经历,以后倾向于哪个方向
编程题:
一行中有 N 张多米诺骨牌,一开始每张多米诺骨牌处于直立、向左、向右三种状态中的一种。每过一秒:倒向左边的多米诺骨牌会使其左边相邻的多米诺骨牌(若为直立状态)变为倒向左边;倒向右边的多米诺骨牌会使其右边相邻的多米诺骨牌(若为直立状态)变为倒向右边;如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边,该骨牌仍然保持不变。已经变为非直立状态的多米诺骨牌的状态不会再次改变。给定表示初始状态的字符串s,返回表示最终状态的字符串。
Sample Input
|\|/|||\/||\||
Sample Output
\\|//|\\//\\||
string solve(string &s) {
int n = s.size();
string res = "";
vector<int> l2r(n, -1);
vector<int> r2l(n, -1);
for (int i = 0; i < n; ++ i) {
if (s[i] == '/')
l2r[i] = 0;
else if (s[i] == '|' && i > 0 && l2r[i - 1] != -1)
l2r[i] = l2r[i - 1] + 1;
}
for (int i = n - 1; i >= 0; -- i) {
if (s[i] == '\')
r2l[i] = 0;
else if (s[i] == '|' && i < n - 1 && r2l[i + 1] != -1)
r2l[i] = r2l[i + 1] + 1;
}
for (int i = 0; i < n; ++ i) {
if (l2r[i] == -1 && r2l[i] == -1)
res += s[i];
else if (l2r[i] == -1)
res += '\';
else if (r2l[i] == -1)
res += '/';
else {
if (l2r[i] == r2l[i])
res += '|';
else if (l2r[i] < r2l[i])
res += '/';
else
res += '\';
}
}
return res;
}
自我介绍
看你做了一些性能优化工作,一般考虑从哪些方面进行性能优化
会用什么方法来发现性能瓶颈
造成磁盘顺序 IO 和随机 IO 性能差异的原因
什么是协程
Golang 的协程好在哪里
除了用引用,如何在函数传参时避免拷贝
一个对象调用 move 转移资源所有权后,再调用这个对象会发生什么情况
stack 底层实现
vector 的 push_back 复杂度
vector 扩容,为什么是倍数增加,而不是定量增加
编程题:
数轴上从左到右依次放着n个宽度都为1的矩形,给出数组H,H[i]表示第i个矩形的高度。问能找到一个面积最大多大的矩形R,使得这个矩形R能放在这n个矩形构成的图形中。
Sample Input
H = [1, 2, 3, 2]
Sample Output
6
int findRec(vector<int> h) {
h.push_back(0);
int n = h.size(), res = 0;
stack<int> st;
st.push(-1);
for (int i = 0; i < n; ++ i) {
while (st.size() >= 2 && h[i] < h[st.top()]) {
int idx = st.top();
st.pop();
res = max(res, (i - st.top() - 1) * h[idx]);
}
st.push(i);
}
return res;
}
详细讲 XX 实习项目
分区表好在哪里
是多机分布式的分区表吗
如果是多机分区表,有全局二级索引吗
实习过程中遇到的最大的问题
编程题
车载系统上,一个模块会产生 output message,并发送给后续的模块,要求设计一个日志系统(磁盘上),记录这些message。类给定如下:
class ModuleBase {
public:
virtual void WaitUntilRun() = 0;
virtual OnboardMessage RunOneIteration(vector<OnboardMessage>) = 0;
std::vector<OnboardMessage> GetInput();
void SendMessageToModule(OnboardMessage, std::string);
void Run() {
while (1) {
WaitUntilRun();
std::vector<OnboardMessage> inputs = GetInput();
OnboardMessage output = RunOneIteration(inputs);
for (const std::string& module: downstream_modules_) {
SendMessageToModule(output, module);
}
}
}
};
想做自动驾驶系统哪一方面
为什么选择做车载系统
介绍XX 实习项目
如何发现可以优化性能的点
全局二级索引并行扫描给线上用户带来了多大提升
遇到最大的挑战是什么
code review 要多久
认为同事们给的代码修改意见更合适吗
为什么自己没有想出最优的解决方案
Case 4
多态、虚函数、虚函数表
类函数在内存的存储形式
结构体字节对齐
了解编译原理吗
内存池如何设计,如何处理碎片问题
堆和栈的区别
堆和栈哪个分配快
智能指针知道哪些,各有什么特点
weak_ptr 用来干啥的
malloc 和 new 区别,malloc 可以给复杂类分配空间吗
怎样让 new 失败时不抛出异常
lambda 函数
进程和线程区别
进程有哪些同步方式
进程间共享内存怎么实现的
线程有哪些同步方式
自旋锁什么情况下好
poll、epoll 区别
什么时候用 ET 模式
epoll_wait 函数参数中类型
static 关键字
const 关键字
为什么是三次握手,为什么是四次挥手
了解 RPC 底层吗
protobuf 了解吗
编程题:
判断链表是否有环
计算进入环前的链表长度
一个数组,相邻位上大小差不超过1,给定一个 target,输出其在数组中的所有位置,要求复杂度低于 O(n)
一个位置值为 n,则其 target-n-1 相邻位内不会有 target,跳过这些位置
介绍 XX 实习工作
EVM 是什么
介绍XX工作
对开源的 RPC 框架有了解吗
介绍天池数据库比赛
AEP 是什么,有什么特性
介绍 XX
Raft 相关问题
出现网络分区后可能出现什么情况
网络恢复后会发生什么情况
编程题:
LRU
编程题:
如何判断两个链表是否有交点
如何找到交点
如何以最低复杂度查找无序数据中位数(有限大的数组)
概率题:
已经生了一个女儿,求再生一个还是女儿的概率
Case 5
详细介绍 XX 的实习工作
介绍天池数据库比赛
如何利用 AEP 的特性
故障恢复怎么做的
存储空间分配机制怎么设计的,有参考一些已有的空间分配机制吗,比如malloc
为什么使用 spinlock 性能会更好
索引用什么设计的,为什么用哈希表,有考虑过别的索引结构吗
为什么使用LRU作为缓存效果不好
对RPC框架原理
epoll 和 reactor
看过哪些开源代码和技术书
专业之外喜欢看什么书
编程题:
实现LRU
旋转数组二分查找
XX 项目
Raft 协议什么作用
详细介绍 Raft 流程
follower 会响应 client 的读写操作吗
超过半数的决策机制如何保证 leader 日志的完整性
为什么使用 log,不直接写
如何解决 split vote 的问题
了解 paxos 吗
天池比赛详细介绍
STL内存池
挑一段实习经历讲
分区表是做什么的
全局二级索引回表相关有遇到过什么技术难点吗
B+Tree 是如何存储的
B+Tree 插入时如何扩张
讲讲 buffer pool 的实现原理
如何分配新的 page
B+Tree 如何支持并行扫描
什么情况下会创建临时表
了解 PolarDB 的分布式原理吗
PolarDB 是如何支持事务的
ACID特性的保证:redo log、undo log、MVCC等
为什么要使用binlog而不直接使用redo log
如何设计一个 webserver
如何实现无锁队列
浏览器输入 url 的过程中,做哪些优化可以提升响应速度
cookie 和 session
浏览器如何访问本地缓存
使用浏览器缓存可能会有什么问题
详细介绍XX实习
介绍天池比赛
和前面的队伍相比不足之处在哪里
spinlock 怎么实现的
Raft
Raft 通过什么机制保证节点间 log 一致性
主要讨论了旧 leader 挂掉后产生新 leader,如何保证它们对于 log commit 有一样的认知
Case 6
内存池实现原理
编译过程 各个阶段的文件名
动态库怎么调用
信号量与锁的原理
大端小端
模板会让程序变快吗
C语言有哪些厉害的点
移动构造哪里用到了
C语言类型转换 int* -> char* 有哪些问题
虚函数表里存的是二级指针吗
手写滤波器
cuda编程
无锁编程知道吗
list怎么找中间节点
C++11关键字
怎么检测内存泄漏
free为设备么不用指定大小
hpp文件是什么
图像处理相关
波兰表达式
机器学习,深度学习,概率论
Case 7
fpn
mobileNet
卡尔曼滤波
xgboost和svm
二叉树,红黑树性质
C/C++程序编译过程
C/C++内存分布
汇编后形成的机器指令里面是什么东西
C++多态
进程调度
进程和线程
虚拟地址
c实现重载
指针和引用的区别
友元
一个.c文件如何访问另外一个.c文件中的static类型变量
c++中的const
虚拟内存是如何映射的
xgboost怎么做车道线检测
行人测距怎么实现
Case 8
IIC协议和SPI协议的区别,如何选择用什么协议
volatile关键字的作用,什么时候会用到
多态的实现原理
多重继承时,多态如何实现
右值引用的作用
智能指针的作用
如何不用中间变量,直接交换两个变量的值
什么时候用多态,什么时候用模板
const比define应该尽量用哪个
移植linux系统时的步骤
linux系统驱动分哪几种?网卡驱动属于哪一种
做过哪些驱动的移植?他们之间有什么不同
linux开发板从上电到启动系统的步骤
在从SD卡往内存搬移系统时,谁初始化了内存?这个发生在什么阶段
编程题:有n盏灯,编号为1~n。第1个人把所有灯打开,第2个人按下所有编号为2的倍数的开关(这些灯将被关掉),第3个人按下所有编号为3的倍数的开关(其中关掉的灯将被打开,开着的灯将被关闭),依此类推。一共有k个人,问最后有哪些灯开着?输入n和k,输出开着的灯的编号。k≤n≤1000。
Case 9
const常量指针与指针常量
c与c++区别
简述多态
class和struct区别
this指针是什么
函数重载是怎样的
结构体赋初值
使用指针时候遇到过哪些问题
const修饰函数解释
static关键字解释
什么情况下需要进行对现场的保存和恢复
编程题:
八个球有一个比较重,问称几次可以把较重的球拎出来
给定一个字符串,将里面的大写字母变为小写
给定排序数组nums1(大小为m+n,其中放了m个排序数字,后面n个用0填充),nums2(大小为n),将nums2和nums1合并变成新的排序数组放在nums1中。
给定一个string,按照出现频率输出新的string(如“aAabcdd”,输出“aaddAbc”(不一定要严格按照顺序,也可以是''ddaaABc'等))
为什么做这个项目
什么是线程池
线程池是如何抢占资源的
会不会有线程抢不到资源
poll和epoll的区别
怎么测试高并发
线程和进程的区别
线程和进程切换的具体过程
介绍对stl的了解
往期面经干货:
1、NLP算法 面经 1
2、计算机视觉 面经1
3、自动驾驶 感知算法面经 1
4、自动驾驶/机器人 SLAM算法 面经1
5、自动驾驶 决策规划算法 面经1
6、嵌入式开发面经 1