菜鸡的算法岗日常实习面经总结

2022-01-08

前言

第一次在掘金写面经，其实今年过得不尽人意，好在能找找实习调整一下心态吧，终于有钱换手机了！要说有什么新年愿望，那就希望2022一切好运吧。 虽然是实习面经但是其实也没怎么准备，随缘，放弃了bat的部门，估计对学历和论文有门槛(尝试性投了深圳字节直接挂简历，我永远喜欢bytedance😭)，10月投b站简历挂，旷视面试没过以后就没投了，后面去学车了，结果科目二没过，有点闲看到有朋友也在投，就不抱希望还是投了3家，比较幸运最后拿到了美团和商汤的实习offer，感谢面试官们手下留情🤣。

个人情况：

学校：211 大四
成绩：前5%
项目：3段CV相关项目经历，无论文，两个算法实践工程落地项目，一段kaggle竞赛铜牌，总体上来说都比较水
算法能力：无ACM，比较菜只是比较喜欢刷，leetcode400题(以easy+medium为主，剑指offer+程序员面试经典+每日一题/周赛)

因为感觉自己很菜找不到实习，所以都没找内推，也没有海投，不过好像大多都会给面试机会的，感觉如果能找内推可能会更好一点。没想到最后能去美团当外卖骑手了😁！

旷视

旷视的实习面试是最早的，不过也面试通知也等了好久，hr说有两个面试官mark了我的简历，所以面了两个组，当时是第一次面试，比较紧张，虽然面试问的不难，但是有些地方答的不好，面试问题记不太清了。另一个面试官，我等了半小时结果被他放鸽子了，改天再面的。。。

手写IoU
求三个部分的IoU，根据定义就是求：$\frac{A \cap B \cap C}{A \cup B \cup C} $,只用讲思路，其实就是容斥原理，当时有点紧张，公式最后一项系数写错了一直没看出来，场面一度尴尬。
讲解Focal loss的原理作用
为什么会用到StratifiedKFold，和KFold有什么区别
介绍一下比赛用到的TTA，Cutmix方法（Cutout和mixup的结合，最好三个都讲解一下）
讲讲Resnet（建议读一下论文，从目的，作用，残差结构的形式，反向传播梯度计算，机器学习GBDT思想等角度进行阐述）
目标检测的mAP达到了多少，有没有测过双目测距的精准度，为啥使用wifi和flask推流通信，这样会比较慢（树莓派算力不够，跑着跑着宕机了），小车目标检测的帧数能达到多少fps（emm我们只是做了一个无人清洁车落地的demo，只测了模型目标检测在数据集上的mAP，其他的更多的是我们自己提供一种idea，具体指标没有测试过😥）。
旋转矩阵，不能开空间，其实做过但是面试很容易紧张卡住，有想到思路但是没写对有点bug，不过面试官说我思路是对的，面完就发现原来是下标对错了。。。
团队合作交流是如何分工和解决问题的？
其他人或者老师给你任务安排时，如果与你的想法不合时，你会如何做？

手写IoU

import numpy as np

def IoU(bounding_box,ground_truth):
    """

    :param bounding_box: [[x1,y1,x2,y2,score]]
    :param ground_truth: [x1,y1,x2,y2]
    :return:
    """
    x1 = bounding_box[:,0]
    y1 = bounding_box[:,1]
    x2 = bounding_box[:,2]
    y2 = bounding_box[:,3]
    score = bounding_box[:,4]

    areas = (x2-x1) * (y2-y1)
    gt_area = (ground_truth[2] - ground_truth[0]) * (ground_truth[3] - ground_truth[1])

    xx1 = np.maximum(x1,ground_truth[0])
    yy1 = np.maximum(y1,ground_truth[1])
    xx2 = np.minimum(x2,ground_truth[2])
    yy2 = np.minimum(y2,ground_truth[3])

    h = np.maximum(0,yy2-yy1)
    w = np.maximum(0,xx2-xx1)

    inter = w * h

    ovr = inter / (gt_area + areas - inter) # np.true_divide(inter, (gt_area + areas - inter))

    return ovr

旋转矩阵

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i=0;i<n/2;i++)
        {
            for(int j=0;j<(n+1)/2;j++)
            {
                // (i,j) (j,n-i-1)  (n-j-1,i) (n-i-1,n-j-1)
                swap(matrix[i][j],matrix[n-i-1][n-j-1]);
                swap(matrix[i][j],matrix[n-j-1][i]);
                swap(matrix[j][n-i-1],matrix[n-i-1][n-j-1]);
            }
        }
    }
};

小米

小米面试其实是当时最好的选择，因为就在武汉本地，也不用外出，但是当时面试确实不太好，面试官对我其中一个项目比较感兴趣，被疯狂怼着追问细节。

描述项目中用到的SIFT匹配和直方图相似度比对基本原理。
one-stage和two-stage的区别。
双目摄像头视觉下应该可以得到整个三维空间下的信息，没考虑方向角度的问题，对测距的处理有些草率（没有很懂，之后再去了解了解，只用到了物理上小孔成像的原理😰
为什么不直接在树莓派上推理，采用推流和主机服务器去进行计算，速度和精度如何
继续追问项目细节。
手写SIFT匹配过程，直接人傻了😭（被面试官怼对传统图像处理了解不深，只会玩玩深度学习搭积木）

美团-智能视觉 offer

美团面试官面试体验比较好，没有过分针对，对待我这种本科生可能相对更看重对我的motivation和potential吧感觉，评价也比较好。

一面

聊项目，做项目的目的和缘由，你觉得有什么亮点。
讲讲one-stage和two-stage的区别。
anchor-free的方式比如FCOS有了解吗
看你有用过ViT，能不能讲讲transformer的架构，再讲讲vit是怎么做的，BERT有了解吗，跟vit有什么区别
看你项目经常用到kaiming的东西，kaiming最近新出的MAE有了解吗（虽然面试官看着年龄有点大，不过还挺紧跟潮流的，kaiming yyds！
讲讲SIFT匹配到双目测距的过程和原理
为什么要用树莓派采集图像借助flask推流，再由主机进行模型推理
对GNN和GCN有了解吗
讲讲人脸检测MTCNN是怎么做的
聊美团这边的业务，问我有没有这方面技术的了解
自己出的算法题，以条形码识别为背景，有点像是去除干扰字符的匹配，用双指针解决即可。

二面

聊项目缘由，团队协作。
讲讲transformer，讲讲position encoding的方法，作者用这种三角函数的方式有什么特点，在vit里面是如何做位置编码的。
介绍self-attention，transfomer的encode和decode有什么区别，你对这两部分有什么理解，以及相对于CNN的一些特点。
项目用的数据集有多大。
项目目标检测用的什么指标，达到了什么效果。
聊美团业务，问我有没有兴趣。
出了个hard题扰乱字符串，不会，简单讲了一下dfs暴力的思路但还是没理清楚写不出😭，后面换了个简单点的题不过要求让我用python写

商汤-基础视觉 offer

一面

一面比较简单，面试官也比较和蔼。

自己出的题，二维矩阵找最长的严格单调上升的一个连续序列（可以跨行转弯，对角线不算），节点可上下左右移动。先用dfs暴力，然后再用记忆化优化了一下。虽然不难但是写的有点慢。
聊项目。
讲讲Batch Normalization（建议从目的，由来，公式解析，理解操作过程，作用以及使用场景等方面来讲解附博客，看完发现自己面试讲的好烂）
介绍小批量梯度下降
讲讲分布不均衡的数据如何处理（讲了讲数据增强，过采样比如SMOTE，欠采样，调整样本对分类的权重，如FocalLoss，这个我感觉回答的不是很好，希望评论区有更好的理解）
有没有搭建或者使用过单机多卡和多机多卡，是否了解多卡时神经网络的梯度反向传播是如何计算的（没钱没资源🤣，瞎猜了一波可能和计算图的节点资源分配有关）
二面
二面其实感觉面试有点糟糕，连问了十几个八股文，做题也出了一些问题，自闭，答也能答出来一些但是整体感觉不好。。。。不过最后比较幸运还是让我过了。
简单介绍自己的项目和自己觉得有亮点的地方
讲讲one-stage和two-stage的区别和特点
什么是RPN，作用是什么
什么是FPN，有什么特点，这种多尺度是怎么实现和进行预测的
讲述yolov3预测目标的过程（比较关键的几个要点我觉得是损失函数，模型输出，非极大抑制，多种变种的IoU，SPP空间金字塔，以及论文中有提到yolov3的anchor是kmeans聚类出来的，可能会让你手写kmeans）
为什么two-stage要比one-stage的精度要高，你觉得本质是什么
yolov3的三个特征图大尺寸的用来预测大的图还是小的图
anchor-free的方式有了解吗，和anchor-based的差异在哪，本质和原理是什么
介绍一下CenterNet和FCOS，中心度的公式和理论，预测过程
什么是梯度消失和梯度爆炸，如何解决（提到某些要点或者答错了会继续追问，没有答的很全）
进程和线程的区别，python的多线程如何实现
maxpool是如何进行反向传播的（建议看看cs231n，首先要明确的是pool层中是没有参数的，然后再来将maxpool，其实我当时也忘了，我记得好像跟maxout的反向传播差不多）
讲讲Batch Normalization，以及在训练和预测过程的计算方式
讲讲dropout，以及在训练和预测过程的计算方式（建议看看cs231n），你觉得和机器学习当中哪种集成方式比较像(这个我不是很清楚希望各位大佬回答一下，当时瞎说了一个boosting🤣)
剑指 Offer 31. 栈的压入、弹出序列思路大致是对的但是没想得特别清楚，比较紧张，写了很久
剑指 Offer 39. 数组中出现次数超过一半的数字 第二题直接限制时间复杂度$O(n)$，空间复杂度$O(1)$，我只会哈希方法，然后和面试官说了一下最优解方法我只记得叫摩尔投票，然后具体忘了。

栈的压入、弹出序列

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
            stack<int> stk;
            int n = popped.size();
            int m = pushed.size();
            int j = 0;
            for(int i=0;i<m;i++)
            {
                stk.push(pushed[i]);
                while(stk.size()&&stk.top()==popped[j])
                {
                    j++;
                    stk.pop();
                }
            }
            return stk.empty();
    }
};

其他

还有一些感觉比较重要，但是没有被问道的东西，包括各种评价指标的含义等等，包括数学基础等等。
经典教程推荐：cs231n，吴恩达，李宏毅，动手学深度学习，《统计学习方法》
关于八股文方面这里推荐一个DeepLearning-500-questions

手写非极大抑制

使用非极大抑制的前提是，我们已经得到了一组候选框和对应label的置信分数，以及groud truth的信息，通过设定阈值来删除重合度较高的候选框。
算法流程如下：

根据置信度得分进行排序
选择置信度最高的比边界框添加到最终输出列表中，将其从边界框列表中删除
计算所有边界框的面积
计算置信度最高的边界框与其它候选框的IoU。
删除IoU大于阈值的边界框
重复上述过程，直至边界框列表为空。

import numpy as np

def nms(dets, threshod, mode="Union"):
    """
    greedily select boxes with high confidence
    keep boxes overlap <= thresh
    rule out overlap > thresh
    :param dets: [[x1, y1, x2, y2 score]]
    :param threshod: retain overlap <= thresh
    :return: indexes to keep
    """
    x1 = dets[:, 0]
    y1 = dets[:, 1]
    x2 = dets[:, 2]
    y2 = dets[:, 3]

    scores = dets[:, 4]

    areas = (x2 - x1 + 1) * (y2 - y1 + 1)
    order = scores.argsort()[::-1]  # reverse

    keep = []

    while order.size() > 0:
        i = order[0]
        keep.append(i)
        # A & B left top position 
        xx1 = np.maximun(x1[i], x1[order[1, :]])
        yy1 = np.maximun(y1[i], y1[order[1, :]])
        # A & B right down position
        xx2 = np.minimum(x2[i], x2[order[1, :]])
        yy2 = np.minimum(y2[i], y2[order[1:]])

        w = np.maximum(0.0, xx2 - xx1 + 1)
        h = np.maximum(0.0, yy2 - yy1 + 1)

        inter = w * h

        # cacaulate the IOU between box which have largest score with other boxes
        if mode == "Union":
            # area[i]: the area of largest score
            ovr = inter / (areas[i] + areas[order[1:]] - inter)
        elif mode == "Minimum":
            ovr = inter / np.minimum(areas[i], areas[order[1:]])
        # delete the IoU that higher than threshod 
        inds = np.where(ovr <= threshod)[0]
        order = order[inds + 1]  # +1: eliminates the first element in order

    return keep

手写Kmeans方法

参考链接：https://www.cnblogs.com/lunge-blog/p/11657415.html

这个版本不是最佳写法，某些处理有点暴力，可以用矩阵和numpy相关的操作会更简洁，但是退出迭代的条件写的很全的，有达到迭代次数，中心点集不变，中心点变化范围小于$\delta$

import numpy as np
import matplotlib.pyplot as plt

n = 100
a = np.random.randn(0,50,n)
b = np.random.rand(0,50,n)
x = np.random.randint(0,50,n)
y = np.random.randint(0,50,n)
points = np.array(list(zip(x,y)))

def distance(x,y):
    return np.sqrt(np.sum((x-y)**2))

def k_means(points,k=5,epochs=500,delta=1e-3):
    # 初始化聚类中心
    center_ids = np.random.randint(0,n,k)
    centers = points[center_ids]

    # 聚类集合初始化
    results = []
    for i in range(k):
        results.append([])
    step = 1
    flag = True

    # 计算各点到中心的距离
    while flag and step < epochs:
        # 重新迭代
        for i in range(k):
            results[i] = []
        # 计算每个点到距离中心的距离
        for i in range(len(points)):
            point = points[i]
            min_dis = np.inf
            min_id = 0

            for idx, center in enumerate(centers):
                dis = distance(center,point)
                if min_dis > dis:
                    min_dis = dis
                    min_id = idx
            results[min_id].append(point)

        # 更新聚类中心
        for idx, old_center in enumerate(centers):
            new_center = np.array(results[idx]).mean(axis=0)
            if distance(center, new_center) > delta:
                centers[idx] = new_center
                flag = False

        # flag=True说明聚类中心已经不变了则可以退出了
        if flag:
            break
        else:
            flag = True
        step += 1

    return results,centers



plt.plot(x,y,'ro')
results,centers=k_means(points,k=5)
color=['ko','go','bo','yo','co']
for i in range(len(results)):
    result=results[i]
    plt.plot([res[0] for res in result],[res[1] for res in result],color[i])
plt.plot([res[0] for res in centers],[res[1] for res in centers],'ro')
plt.show()

总结

本人能力有限，如果上述回答有任何错误，还请各位大佬及时指出

不同面试官的面试风格不一样，项目相关的知识积累问的会比较多（项目水没关系但相关技术还是要搞懂），项有的会考察广度和思维潜力，有的会考察基础（八股），算法题感觉并没有那种重要，把剑指offer刷了应该差不多。
关于八股文的看法，其实更多的还是要多理解，一些相关原理和数学还是多看看相关论文和经典课程，到时候也不用刻意记也能按自己的想法说出一点（瞎吹），感觉面试官想要的答案并不一定是你能完整的说出来，而是有自己理解的正确描述（这个可能需要在代码实践和理论知识之间多反复几次体会会比较好）。
代码实践还是要多一些，其实很多东西我了解的并不深入，只是大致理解过原理和思路，这样还是不太好，开始害怕顶不住实习压力了。
不用害怕，尽量多交流，避免场面陷入尴尬。
反问环节我一般问的是来这边的工作内容，学习的建议和评价，培养和安排之类的。

「掘金链接：菜鸡的算法岗日常实习面经总结」