虹软2023自动驾驶算法岗机试
牛客系统, 一共有三个题型, 总时间两小时
- 不定项选择, 20题, 每题2分, 多选不给分, 少选给1/3分
- 算法题, 3题, 每题10分好像
- 问答题, 5题, 一共90分
考的非常全面, 感觉自己要挂
需要注意的是, 这三个部分, 可以自选顺序开始作答, 但是必须要把当前部分做完提交, 才能选下一部分. 也就是说, 不能在两部分之间切换来回作答, 所以要对时间有个把控.
不定项选择
涉及了线性代数, 神经网络, 概率论, 机器学习相关的知识. 具体来讲, 比如有给一个卷积层, 让你算他的参数规模, 输出维度. 还有SVM如何处理噪声, 核函数的一些问题. 概率论主要考了一个贝叶斯条件概率, 线代的题比较多, 但都比较基础, 比如秩和行列式.
总的来讲这里难点在于概念性的东西特别多, 而且全部都是不定选, 比如常见的低通高通滤波器等, 给的选项中有些没有听说过.
算法题
这部分是整张我感觉最简单的部分, 三题都非常简单.
白色斑点数量
dfs模板题, 给一个矩阵 i m a g e \large image image, 其中 1 1 1表示白色像素, 0 0 0表示黑色像素, 求有多少个白色斑点. 题目没有描述什么是白色斑点, 从样例我猜测是 上 , 下 , 左 , 右 上,下,左,右 上,下,左,右四个方向连续的白色像素, 那就是一个标准的 d f s \large dfs dfs, 3分钟写完, 提交, 轻松AC
跳楼梯
题干
标准 d p dp dp问题, 难点在于不能连续跳多次2级或者3级
我的思路
令 d p [ x ] [ l ] \large dp[x][l] dp[x][l]表示跳到第 x \large x x级台阶, 且最后一跳跳了 l = 1 , 2 , 3 \large l=1,2,3 l=1,2,3级台阶的方法数. 很显然跳到第 n n n级台阶有3种可能:
- 最后一跳跳了1级, 即 d p [ n ] [ 1 ] \large dp[n][1] dp[n][1]
- 最后一跳跳了2级, 即 d p [ n ] [ 2 ] \large dp[n][2] dp[n][2]
- 最后一跳跳了3级, 即 d p [ n ] [ 3 ] \large dp[n][3] dp[n][3]
因此, 有
a n s [ n ] = d p [ n ] [ 1 ] + d p [ n ] [ 2 ] + d p [ n ] [ 3 ] \large ans[n] = dp[n][1]+dp[n][2]+dp[n][3] ans[n]=dp[n][1]+dp[n][2]+dp[n][3]
考虑状态转移, 不妨设当前在 i i i级台阶,
- 当状态 l = 1 \large l=1 l=1时, 说明是从 i − 1 \large i-1 i−1跳了一级跳到 i \large i i的, 而由于是跳了一级, 那么怎么到 i − 1 \large i-1 i−1级依然有三种可能
- 即, d p [ i ] [ 1 ] = d p [ i − 1 ] [ 1 ] + d p [ i − 1 ] [ 2 ] + d p [ i − 1 ] [ 3 ] \large dp[i][1] = dp[i-1][1] + dp[i-1][2]+dp[i-1][3] dp[i][1]=dp[i−1][1]+dp[i−1][2]+dp[i−1][3]
- 当状态 l = 2 \large l=2 l=2时, 说明是从 i − 2 \large i-2 i−2跳了两级到 i \large i i的, 因为跳了两级, 所以到 i − 2 \large i-2 i−2只能是从 i − 3 \large i-3 i−3跳了一级跳过来的, 因为不能连续跳超过一级.
- 即, d p [ i ] [ 2 ] = d p [ i − 2 ] [ 1 ] \large dp[i][2] = dp[i-2][1] dp[i][2]=dp[i−2][1]
- 类似的,
- d p [ i ] [ 3 ] = d p [ i − 3 ] [ 1 ] \large dp[i][3] = dp[i-3][1] dp[i][3]=dp[i−3][1]
整个算法如下:
#define MAXN 10001;
int jump_stairs(int n){
int dp[MAXN];
memset(dp, 0, sizeof(dp));
// 初始状态
dp[0][1] = 1;
dp[1][1] = 1;
dp[2][1] = 1;
dp[2][2] = 1;
for(int i=3; i<=n; i++){
dp[i][1] = dp[i-1][1] + dp[i-1][2]+dp[i-1][3];
dp[i][2] = dp[i-2][1];
dp[i][3] = dp[i-3][1];
}
return dp[n][1]+dp[n][2]+dp[n][3];
}
依然轻松AC
最小素因子集数
具体题干记不清了, 反正是和筛选 [ 1 , n ] \large [1, n] [1,n]范围内的素数有关的, 欧拉筛写的有bug, 所以没有用欧拉筛, 导致时间复杂度高, 导致只过了 82 % \large 82\% 82%的样例, 用欧拉筛的话应该可以AC
问答题
这部分是最恶心的, 感觉自己得分率不高, 一共90分的分值, 占了整张试卷的一大半.
-
第一题是快速幂, 还算简单
-
第二题是图像处理相关, 问你两幅图像特征匹配的问题, 包括SIFT和SURF的区别, 如何解决时间复杂度, 映射两幅图像需要至少多少匹配点, 如何去掉错误的匹配点等
-
第三题是三维刚体变换, 问你三维空间中的旋转有多少种表示方法, (欧拉角, 四元数, 旋转矩阵, 旋转向量), 然后给你一个任意向量 v ∈ R 3 \large v \in \mathbb{R}^3 v∈R3, 一个单位向量 n ∈ R 3 \large n \in \mathbb{R}^3 n∈R3, 让你求 v \large v v关于 n \large n n旋转 θ \large \theta θ角度的向量 v ′ \large v' v′. 就是考你如何将旋转向量转化到旋转矩阵, 也就是罗德里格斯公式, 不过我好像把公式写错了. 答案应该是(这里我假设 v , n \large v, n v,n都是列向量.
v ′ = R v = ( I cos θ + ( 1 − cos θ ) n n T + sin θ n ∗ ) v \large v'=Rv=(I\cos\theta+(1-\cos\theta)nn^T+\sin\theta n^{*})v v′=Rv=(Icosθ+(1−cosθ)nnT+sinθn∗)v
其中 n ∗ \large n^* n∗表示 n \large n n对应的反对称矩阵, 因为^这个符号直接写在右上角markdown识别不了
- 第四题, 存储客户数据的硬盘丢失了100条数据, 如何补回来, 说白了就是如何用时序模型建模
- 第五题, 最变态的, 考你SLAM中的BA, 包括BA的概念, BA常用的求解方法, GN和LM等细节, 并让你写出一个样例的海塞矩阵 H \large H H