尧图网站设计 尧图网站设计YAOTU DESIGN
ARTICLE DETAIL

资讯详情

深耕网站设计与一线实操的经验洞察。

网易2023校招CV算法笔试复盘:从KMP到卡尔曼滤波的工程实战

网易2023校招CV算法笔试复盘:从KMP到卡尔曼滤波的工程实战 1. 笔试整体情况与考察框架1.1 笔试形式与时间分配我是去年秋天参加的网易2023校招计算机视觉算法工程师笔试当时报的是正式第二批。先说结论这场笔试整体风格偏工程落地不考那种偏门到天际的数学证明但也不是背背八股就能过的。整体题量大、范围广编程题占大头而且题目设计明显在考察你能不能把算法用在真实业务场景里。笔试时间总共是120分钟分为选择题、编程题和简答题三块。我个人的体感是选择题30道左右、编程题3道、简答题2道难度梯度拉得比较开。选择题大概40分钟做完剩下80分钟做编程题和简答题时间比较紧张尤其是编程题如果卡住一道后面简答题就容易被挤掉。这里我多说一句网易的笔试系统是自带IDE的支持C、Java、Python、Go这些主流语言但不支持本地代码调试也就是你写的代码是在网页编辑器里跑用例的。所以平时练习时建议尽量习惯写完就提交的方式别指望断点调试。我身边有同学平时用IDE习惯了笔试时一直在心里纠结格式问题浪费了不少时间。1.2 题型分布与考察范围从第二批正式批的题目来看考察范围基本可以分成四块计算机视觉基础、深度学习与机器学习、数据结构与经典算法、数学基础。我按记忆整理了一张表格方便大家对照自查考察模块主要题型占比体感涉及知识点计算机视觉基础选择题、简答题25%左右图像滤波、特征提取、目标检测、图像分割深度学习与机器学习选择题、简答题25%左右CNN、损失函数、优化器、过拟合与正则化数据结构与算法选择题、编程题35%左右排序、字符串匹配、动态规划、二叉树、图论数学基础选择题、简答题15%左右线性代数、概率论、最优化、卡尔曼滤波这个分布其实很有代表性网易的CV岗位向来不是纯算法研究而是要求你有工程落地能力。所以编程题的分量给得很足而且考的不是LeetCode那种纯模板题而是会嵌套一些业务场景比如给你一批图像标注数据让你设计一个算法筛选出重复样本这类后面我会展开讲。1.3 岗位能力模型分析站在过来人的角度回头看这场笔试实际上是在筛选三种能力基础扎实度、工程编码能力、理论结合实践的能力。基础扎实度看的是你对CV核心知识的理解深度。比如选择题里会问SIFT特征为什么具有尺度不变性、卷积感受野怎么计算、BatchNorm在训练和推理阶段的差异这些知识点不是刷一遍题库就能覆盖的需要真正理解原理。工程编码能力看的是你写代码的熟练度和健壮性。3道编程题涉及字符串处理、动态规划、数组操作中等难度偏上有一两道需要优化到O(n log n)甚至O(n)才能过全部用例。我印象很深的一道题是用KMP思想做字符串匹配变种如果你只会暴力解法小数据能过但大数据量会超时。这里建议准备的时候把经典算法的手写版过一遍特别是KMP、快排、堆排序、二分这些高频考点。理论结合实践的能力则藏在简答题里。比如有一道题是讲图像锐化中的拉普拉斯算子问你为什么拉普拉斯算子的响应可能是负值以及如何处理边界像素。这种题目靠背概念是答不好的必须真正做过图像处理实验知道算子卷积的完整流程才能答到点子上。核心考点深度拆解2.1 计算机视觉基础从图像滤波到特征提取CV基础这部分的笔试内容说难不难说简单也不简单。它的特点是很喜欢把两个相近的概念放在一起考你让你辨析。选择题里有一道我印象很深索贝尔算子Sobel和拉普拉斯算子Laplacian有什么区别它们的应用场景分别是什么这道题看似基础但有很多细节值得展开。Sobel是一阶微分算子通过计算图像在x和y方向的梯度幅值来检测边缘对噪声有一定的平滑抑制作用因为它本质上还是做了局部加权平均。而Laplacian是二阶微分算子对噪声更敏感但能同时检测各个方向的边缘不需要分别计算x和y方向的梯度。实际工程中如果直接用Laplacian做边缘检测经常需要先做高斯模糊去噪这也是LoGLaplacian of Gaussian算子的思路来源。另外还有一个常考点是图像锐化。有一道简答题问到拉普拉斯算子做图像锐化时为什么要用原图减去拉普拉斯响应这背后的原理是拉普拉斯算子响应为零时表示平坦区域响应为非零时表示灰度变化剧烈的区域。把拉普拉斯响应从原图中减去相当于在边缘处拉大对比度从而使图像看起来更清晰。注意这里容易答反我记得是加上或减去取决于算子定义中的符号约定但考场上要按题目给出的算子形式来判断。在特征提取这块网易比较喜欢考SIFT和ORB的对比。SIFT特征是尺度不变、旋转不变的计算量大ORB是二进制特征计算速度快适合实时场景但不具备完全的尺度不变性。选择题可能会给一个场景比如移动端实时AR需要做特征匹配你会选择哪种特征来考察你在精度和速度之间做权衡的能力。这类题没有绝对答案关键是讲清楚取舍。2.2 深度学习与CNN不仅会调库还要懂原理深度学习部分是重头戏。网易这场笔试的难度在于它不会直接问你什么是卷积而是会给你一个具体网络结构让你计算参数量、感受野或者推导反向传播的梯度。比如选择题里有一道输入特征图是H×W×C卷积核大小为k×k输出通道数为C_out卷积步长为spadding为p问输出特征图的尺寸。这个公式相信大家都背过输出尺寸(H2p-k)/s1。但题目不会这么直白它可能会加入空洞卷积dilated convolution问你在dilationd的情况下感受野扩大了多少。这里要记住空洞卷积引入了一个额外参数d实际卷积核覆盖范围变成了k(k-1)×(d-1)。还有一个高频考点是感受野的计算。我当时抽到的是一道计算VGG网络某个卷积层感受野的选择题需要从输入层往前推。这里有个实用技巧从后往前推比从前往后推更容易公式是RF_{l-1} (RF_l - 1) × stride_l kernel_size_l从最后一层往前逐层推。我记得当时这道题我用了不到一分钟就算出来了因为我把公式写在草稿纸上了。反向传播的推导也是简答题的常客。网易比较喜欢考的是一个包含BatchNorm的卷积网络在训练阶段和推理阶段BatchNorm的行为有什么不同训练阶段用的是当前batch的均值和方差还要维护全局的running_mean和running_var推理阶段则直接用训练好的running_mean和running_var。还有一个容易被忽视的细节推理阶段通常会把BN层和前面的卷积层融合减少计算量。如果你在简历里写过模型部署相关的项目这道题几乎是送分题。2.3 机器学习基础损失函数与优化器机器学习基础题目在网易笔试中出现得也不少但整体难度不大重点考察你对概念的理解深度和边界条件的掌握。选择题里比较典型的一道是对于类别不平衡的二分类问题以下哪种损失函数更适合A. 交叉熵损失 B. 加权交叉熵 C. 均方误差 D. Hinge Loss。正确答案是B加权交叉熵。这个知识点本身不难但题目会进一步问你如果正负样本比例是1:99权重应该怎么设置很多人会答1:99实际上更稳妥的做法是给少数类赋予更大的权重但权重也不一定完全按反比来需要结合验证集调参。另外网易还挺爱考优化器的。SGD、Momentum、RMSProp、Adam这四者的对比几乎是必考。我记得有一道选择题问在鞍点处哪个优化器更容易逃离这题的坑在于很多人以为SGD带Momentum就好实际上Momentum确实能用累积动量冲出鞍点而Adam因为自适应学习率在梯度很小时步长会变大也具备一定逃离能力。关键在于题目如果限定只选一个最好选Momentum因为Adam在梯度噪声较大的情况下可能会震荡逃离效率反而不稳定。还有一个我私心觉得会被很多人忽略的点机器学习里的过拟合与正则化。网易的题很少直接问L1和L2的区别而是喜欢给一个训练曲线让你判断是否过拟合以及怎么解决。这时候你要答出数据增强、Dropout、Early Stopping、正则化、降低模型复杂度这几个方向同时还要结合CV场景说明哪些方案在图像任务里更常用。2.4 数据结构与经典算法编程题的核心弹药库根据我的观察网易笔试的编程题重点集中在字符串、动态规划、数组操作、二叉树和图论这几类难度介于LeetCode中等偏难。先说排序算法。选择题里会考排序算法的稳定性快排不稳定、堆排不稳定、归并稳定、插入稳定。还有一道题问在一个几乎有序的数组中以下哪种排序算法性能最好答案是插入排序因为当数组接近有序时复杂度接近O(n)。网易不直接考你冒泡排序C代码怎么写而是考你同一个算法在什么场景下最优这是典型的工程思维考察方式。字符串匹配是网易笔试的高频考点。热搜词里有KMP我笔试时也遇到了KMP相关的变种题。经典KMP的next数组怎么求这个必须会手写。我先给一个C版本供参考vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }其实笔试里不会直接让你默写KMP而是给一个场景比如在长字符串中查找所有与模式串相似的子串允许k个字符不匹配这种变种题用KMP的next思想来优化暴力匹配才能保证时间复杂度达标。所以不要只会背模板要理解next数组的本质是当匹配失败时模式串可以向右滑动多远。动态规划也是必考。我抽到的是一道类似最长公共子序列的变种但背景换成了图像特征点匹配。题目给你两个特征点序列让你求最长连续匹配的子序列长度。本质上还是LCS的思路但边界条件需要根据题目调整。这里我建议把DP的经典题型都练熟最长递增子序列、0-1背包、编辑距离、最长公共子串/子序列这几个基本够用。典型真题解析与解题思路3.1 编程题实战用KMP变种解决字符串匹配笔试的3道编程题里有一道让我印象很深。题目的描述大概是给定两个字符串S和P要求在S中找到所有P的近似匹配起始位置允许最多k个字符不同。看到这个题目第一反应可能是暴力枚举S中每个长度为|P|的子串逐个比较复杂度是O(n×m)在数据量大时肯定超时。第二个反应是用KMP或Z算法扩展但KMP针对的是精确匹配对允许k个不同字符的支持需要额外设计。我当时用的是类似KMP的滑动思路先用KMP的next数组预处理模式串P然后在匹配过程中维护一个失配计数如果失配计数超过k就回溯到上一次可能的位置。这里我给出一个可运行的参考实现#include bits/stdc.h using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } return next; } vectorint approximateKMP(const string s, const string p, int k) { vectorint res; int n s.size(), m p.size(); vectorint next buildNext(p); int j 0, mismatch 0; for (int i 0; i n; i) { while (j 0 s[i] ! p[j]) { if (mismatch k) { mismatch; break; } j next[j - 1]; mismatch 0; } if (s[i] p[j]) { j; } else { mismatch; } if (j m) { if (mismatch k) { res.push_back(i - m 1); } j next[j - 1]; mismatch 0; } } return res; }这个实现并不完美边界条件需要根据题目要求微调但整体思路是对的在传统KMP基础上引入一个失配计数器当失配超过阈值时回退到next所指的位置而不是直接从头开始。踩过的坑是网上很多KMP模板用的是next[i]表示前i个字符的最长相同前后缀长度有的用-1作哨兵笔试时如果记忆混淆很容易写错。我建议平时练习时固定一种写法不要频繁切换考试时肌肉记忆比临场推导更可靠。3.2 CV理论题实战目标检测中的NMS与IoU计算简答题里有一道目标检测相关的题要求解释NMS非极大值抑制的完整流程并说明IoU的计算方式。这道题说难不难但完全答好也不容易。NMS的完整流程应该是对某一类别的所有检测框按置信度从高到低排序。取置信度最高的框A将其加入最终保留列表。计算A与其余所有框的IoU。删除与A的IoU超过阈值通常0.5的框。对剩余框重复步骤2-4。这道题的深层考点在于很多同学会把NMS当成一个死记硬背的流程但没有意识到它的核心目的是解决同一个物体被多个检测框重复框住的问题。如果你能补充说明NMS在边缘情况下的处理比如当两个不同物体的框重叠度较高时NMS会误删就能体现出你对算法局限性的理解。IoU的计算公式是交并比交集面积/并集面积。实际上代码实现时有几个细节交集区域的宽min(x1_max, x2_max)-max(x1_min, x2_min)高同理如果任何一边为负则交集面积为0。这个细节很容易被忽略但笔试可能会让你写伪代码所以要记牢。我整理一个简短的实现参考struct Box { float x1, y1, x2, y2; float score; int label; }; float iou(const Box a, const Box b) { float inter_w min(a.x2, b.x2) - max(a.x1, b.x1); float inter_h min(a.y2, b.y2) - max(a.y1, b.y1); if (inter_w 0 || inter_h 0) return 0.0f; float inter_area inter_w * inter_h; float union_area (a.x2 - a.x1) * (a.y2 - a.y1) (b.x2 - b.x1) * (b.y2 - b.y1) - inter_area; return inter_area / union_area; } vectorBox nms(vectorBox boxes, float iou_threshold) { sort(boxes.begin(), boxes.end(), [](const Box a, const Box b) { return a.score b.score; }); vectorBox result; while (!boxes.empty()) { Box cur boxes[0]; result.push_back(cur); boxes.erase(boxes.begin()); vectorBox remaining; for (auto b : boxes) { if (iou(cur, b) iou_threshold) { remaining.push_back(b); } } boxes remaining; } return result; }这种题在笔试里属于必须拿分的送分题。备考时建议把常见CV流程的伪代码都过一遍包括特征匹配的RANSAC、图像金字塔、Haar特征等。3.3 数学基础实战卡尔曼滤波与贝叶斯更新热搜词里有卡尔曼滤波算法这个出现在网易CV算法笔试里并不意外因为卡尔曼滤波在目标跟踪、SLAM、自动驾驶感知中都是核心算法。网易的考题不是让你推导完整的卡尔曼滤波公式而是考思想。我记得有一道选择题在卡尔曼滤波中预测步骤和更新步骤分别由哪些公式描述选项里混入了粒子滤波的公式来迷惑你。这就考察你能不能分清两个概念。卡尔曼滤波的核心是两大步骤预测Predict和更新Update。预测阶段利用状态转移方程预测当前时刻的状态和协方差更新阶段利用观测值对预测结果进行修正。修正的程度由卡尔曼增益K决定K越大越相信观测值K越小越相信模型预测值。有一个类比很形象你在追踪一个移动目标模型告诉你目标应该在这里传感器观测到目标在那里。卡尔曼滤波就是给这两个来源的信任度分别加权最后得到最优估计。这个加权过程就是贝叶斯更新的线性版本。简答题里可能还会问你卡尔曼滤波的假设条件系统是线性的、噪声是高斯分布的。如果系统是非线性的需要扩展卡尔曼滤波EKF或无迹卡尔曼滤波UKF。这里要注意网易可能会把EKF和UKF的区别作为加分项来考你可以从一阶线性化和采样逼近的角度回答。常见问题与排查技巧实录4.1 时间分配编程题卡壳是最大的坑我考完最大的感受是时间分配直接决定最终成绩。身边至少有三个同学跟我说编程题第一道卡了快40分钟导致后面两道编程题和简答题匆匆扫一眼就交卷了结果自然不理想。这里我给一个我验证过的时间分配方案供大家参考发卷后的前5分钟快速浏览全卷标记出编程题的大致难度。先做选择题控制在35-40分钟以内。选择题里如果遇到卡壳超过2分钟的题先标记跳过不要恋战。编程题按先易后难的顺序做每道题分配15-20分钟。如果一道题超过25分钟还没有AC果断放弃写暴力解或部分分。简答题留15-20分钟。简答题是按点给分的先写核心公式和结论再补充细节保证能拿到大部分分数。我个人的经验是网易笔试的选择题很多都是看起来简单但有一两个陷阱比如计算感受野时忘记算padding、BatchNorm训练和推理阶段的统计量差异等。所以选择题不能做得太快至少要留出检查时间。4.2 易错点与细节陷阱清单我把这次笔试判断题里容易踩的坑整理成了一个清单考前过一遍可以帮你避免很多低级失误易错点正确理解错误理解Softmax输出和为1多分类概率归一化使用二分类也能直接用ReLU在负数区间梯度为0导致Dead ReLU问题梯度恒为0但参数不更新Dropout在训练/推理阶段差异训练时随机失活推理时保留全部并缩放权重推理时也随机失活BN在训练/推理阶段差异训练用batch统计量推理用全局统计量两者一样交并比IoU取值范围0到1之间可以大于1KMP的next数组定义表示最长相等前后缀长度表示失配后跳转的索引这些细节单独看很简单但在限时笔试的高压环境下很容易出错。我建议考前专门整理一份自己的易错本每次模拟考试前翻一遍比刷十道新题更有效。4.3 考后复盘与面试衔接经验笔试结束后不管感觉好坏我建议你马上把还记得的题目记下来。网易的笔试题库很大但同一批次的题目风格和考点是相近的。我当时考完就在手机备忘录里记录了十几道题的关键词后面复盘时发现很有用。尤其要注意的是笔试中答得不好的题目往往会是面试环节的重点考察方向。比如我当时笔试里有一道关于图像锐化的拉普拉斯算子简答题没答好结果面试时面试官就问到了图像增强的知识点好在我笔试后专门补了这块才没有在面试中再次翻车。所以我的建议是笔试后的48小时内趁记忆还热乎把不会的题目对应的知识块补齐。这不只是为了笔试更是为后面的面试做铺垫。网易的面试官明显会参考你的笔试成绩在面试中针对你的薄弱点进行深度追问。5. 备考资源与实战建议5.1 经典书籍与公开课关于备考资源我给不了大家看这个就行的万能答案但可以分享一些我自己实际用下来觉得有帮助的资料。计算机视觉方面我推荐复习的时候以教材为主不用太深究太前沿的论文。重点吃透图像滤波、边缘检测、特征提取、传统机器学习、CNN基础结构这几块。有一本英文专业书内容比较全适合按章节查漏补缺但不需要从头到尾啃。深度学习方面建议先把核心概念过一遍卷积计算、池化、激活函数、损失函数、优化器、BN、Dropout、经典网络结构VGG、ResNet、MobileNet。还有一个容易忽略的知识点是感受野的计算我笔试时至少遇到了两道跟感受野相关的题。编程算法方面我强烈建议把LeetCode的热题100题刷透特别是字符串、动态规划、二叉树的题。网易笔试的编程题风格偏向经典题业务包装比如字符串匹配变种本质上还是KMP或滑动窗口。如果你能把这些题型练到条件反射程度笔试编程题大概率能AC两道以上。5.2 刷题策略不是越多越好很多同学备考时喜欢一天刷十道题但效果往往不好。我的经验是刷题的质量比数量重要得多。对于校招笔试我建议按以下顺序准备先把数据结构和算法的基础打牢数组、链表、栈、队列、哈希表、二叉树、图论基础。再把经典算法逐个攻克排序快排、归并、堆排、二分、KMP、动态规划经典题、DFS/BFS、最短路径。然后做场景化训练比如把一道普通的字符串题套在CV或推荐场景里重新描述锻炼自己把业务问题抽象成算法模型的能力。最后做限时模拟每次模拟要严格按照考试时间和环境来。我当时刷题时有一个习惯每道题AC之后会尝试用至少两种方法解。比如一道最长递增子序列的题可以用O(n^2)的DP也可以用O(n log n)的贪心二分。笔试时如果一种方法超时立刻切换另一种这种灵活应变的能力在限时环境下非常重要。5.3 考前一周的冲刺建议考前一周不建议再大量刷新题了。我当时做的是三件事回顾错题、整理公式、模拟考试。回顾错题不是只看答案而是把每道题的解题思路重新在草稿纸上推演一遍确保自己真正理解了而不是背住了解题步骤。整理公式是指把CNN感受野公式、输出尺寸公式、IoU计算公式、KMP next数组模板等高频公式抄在一张A4纸上考前反复看。模拟考试是最重要的。找一套往年的真题或高质量的模拟题严格按照120分钟来做中间不暂停、不翻资料。模拟结束后重点分析哪些题是本来会但没时间做以及哪些题是浪费时间太多导致没做完针对性调整时间分配策略。我考前做了三次限时模拟每次都能发现一个时间分配上的问题到真正笔试时已经形成了比较稳定的节奏。写在最后回头看看这场笔试我最大的体会是网易的题目其实难度不算顶级但它考察得非常全面而且很看重理论工程结合的能力。算法题本身就是很多CV算法工程师的痛点因为平时做实验写脚本习惯了手写KMP、手写DP的状态不好。但这恰恰是校招笔试和日常工作的分水岭想在笔试里拿到好成绩必须刻意练习手写代码的能力。另外再多说一句笔试只是校招的第一关但它往往会影响后续面试的走向。网易的面试官能看到你的笔试答卷如果你的编程题答得很好面试时会更侧重考察你的项目深度如果笔试表现一般面试官可能会花更多时间考察基础题。所以笔试的优先级真的不低值得投入足够的时间去准备。希望这篇复盘对正在准备大厂CV算法岗校招的同学有帮助。如果后面有需要我可以再单独写一篇面试环节的复盘把我在网易面试中被追问到的那些技术细节整理出来。祝大家笔试顺利offer到手。
返回列表