「面试」Momenta - 视觉算法实习生

前言

之前在知乎看到 Momenta 的评价还不错(不过也有可能是水军),就投递了一波简历,大概三天就给了回复并安排了面试。

Momenta 的位置还不错,就在宇宙中心五道口,公交车 375 或者骑车都 OK,我骑着小电驴从北邮出发大概二十多分钟就到了。

13:45 的时候上楼,敲门没人理,投过磨砂玻璃看到大厅一个人没有,等了好久一个保洁大妈给打开了门。

进来之后整个大厅还是就我一个人,前台也不知道去哪了,隐约能听到远处传来的键盘声。

等到快 14:00 了还没有消息,无奈给 HR 打了电话,过了几分钟面试官终于来了。

一面

面试官:CV 方面了解多少?

我:了解一些比较基本的算法,比如目标检测什么的

面试官:知道边缘检测怎么做吗

我:YOLO 算法

面试官:简单讲一下 YOLO 算法吧

我:大概就是把图像分成一个 $n\times n$ 的网格,然后每个物体中心所在的网格负责检测该物体

面试官:YOLO 算法的输出是什么?

我:输出一个向量,首先是 bx、by、bh、bw,描述了这个检测框的位置和长宽,然后后面紧跟一个 softmax 输出,表示目标分别属于哪一类的概率

面试官:还有什么其他的输出吗?

我:(纳尼,不就输出这一个向量么,还有什么别的),好像没有了吧

面试官:OK

(后来我反应过来他想问的可能是这个向量还包含什么其他维?我当时忘记说 Pc 了,就是一个布尔变量表示是否检测到物体

面试官:概率论 90 多分是吧,来做个概率论的题,独立同分布的随机变量 $A,B\sim U(0,1)$,求 $\mathrm{Var}(\max(A,B))$。

拿到这个题我还是有点懵,上上学期学的概率论已经忘得差不多了。想了下肯定要先求概率密度,令 $Z = \max(A,B)$,那 $f(z)=\int_0^zf(a)\mathrm{d}a + \int_0^zf(b)\mathrm{d}b=2z$ 吧,然后 $\mathrm{Var}(Z)=E(Z^2)-[E(Z)]^2$,期望就是积分一下,结果我第一遍积错了算出来一个 $\frac{1}{3}$,跟面试官说了答案。

面试官:这个不太对吧,你这个概率密度对吗?你确定是 $f(z)=2z$?

我:(wtf,概率密度都求错了?但是怎么看都感觉没问题啊),这个求法不对么,我感觉没问题啊

面试官:你这样直接加不对吧,我给你提示一下,你可以从分段函数的角度去考虑

分段函数?分什么段……感觉药丸,并不知道他在说啥。于是我又回忆了一下课本上的解法,应该是先求的分布函数?也就是 $F(Z)=P\lbrace z<Z\rbrace =P\lbrace \max(A,B)<Z\rbrace =P\lbrace A<Z\rbrace P\lbrace B<Z\rbrace =z^2$,这tm求下导不还是 $f(z)=2z$ 么?这个做法应该百分百没问题啊。

我:我觉得概率密度函数没问题啊,这样做求出来也是 $f(z)=2z$。

面试官:你再想想,你这个 $P\lbrace \max(A,B)<Z\rbrace=P\lbrace A<Z\rbrace P\lbrace B<Z\rbrace$ 成立吗?

我:独立同分布,为啥不成立?

面试官:我觉得这两个不等价吧,你再想想

这你🐴的怎么会不等价,难道是我结果算错了,重新算了下积分发现果然算错了(捂脸),跟面试官说了一下新结果 $\frac{1}{18}$。

面试官:这个答案是对的,emm,我再看看你这个做法。

(空气寂静了半分钟

面试官:哦,你这个是对的,我擅长的那种做法和你不太一样,刚才你结果算错了我就以为你方法错了。

我:(假装微笑)

面试官:那下面来一个算法题吧,这个比较贴近实际场景,就是你一个 $w\times h$ 的图像上有 $n$ 个小方框,你可以认为这是检测到的 $n$ 个目标。现在你要从图像中截取一个 $sw\times sh$ 的部分,使得该部分内包含的完整的小方框的数量最大。

这个问题还是挺有意思的,感觉不是什么太常规的算法题,我首先想了个 $O(n^3)$ 的算法。

我:考虑到必定存在一种最优方案,满足截取框的下边界和左边界上都有一个小方框。那我们可以先枚举两个小方框,就可以根据这两个框确定截取框的左下角坐标,又由于长宽已知,就可以确定截取框的四个顶点坐标了。这样在枚举一遍所有小方框计算答案就 OK 了。

面试官:OK,这个可以优化吗,你前面枚举的那部分一定要 $O(n^2)$ 吗?

我:emm,如果要枚举两个小方框的话,的确有很多不合法状态可以剪掉,不过如果分布的比较密集或者截取框比较大的话,复杂度可能还是降不下来

面试官:那你再想一想,我提示一下,可以用动规试一下?

想了半天没想出怎么动规,不过又想到了一个 $O(n^2)$ 的做法。

我:没想出怎么动规,不过想了一种其他做法,就是我们可以首先把所有小方框按照纵坐标排序。然后与之前类似,必定存在一种最优方案,满足截取框的左边界上有一个小方框,我们就枚举这个小方框,然后按照纵坐标升序遍历所有的小方框,遍历的时候首先将横坐标不合法的排除掉,纵坐标我们扫描的时候用一个队列来维护,要保证队首和队尾小方框的纵坐标之差在截取框的高度范围内,这样复杂度是 $O(n^2)$ 的,而且实际中第二步可以先二分一下纵坐标的上下界,缩小枚举的范围,复杂度会更低。

面试官:OK,不错,那就这样吧。

(所以动规怎么做你倒是告诉我啊

二面

二面是电话面试,等了面试官 20 分钟没消息,正当准备放弃的时候打电话来了。

面试官:红黑树有什么特性?在 C++ 里有哪些应用?

我:emm,我不太了解红黑树,不过 C++ 里的 set、map 都是用红黑树实现的

面试官:简单讲下红黑树在 map 里的应用吧

我:红黑树其实就是平衡树,map 里实际上就是存储了一些 key-value 对,将 key 用平衡树来组织,这样就可以在 $O(\log n)$ 的时间内实现插入、查询、删除的操作。

面试官:嗯好,那红黑树有什么特性?

我:(???我不是说过我不知道了吗),emm,不好意思这个我的确不太了解

面试官:那换个问题,讲一下多态的概念吧

我:多态实际上就是我同一个函数接口可能对应多个不同的实现,比如子类继承了父类,并且重写了父类的一个函数,那这个函数就存在多态

面试官:那比如你一个父类类型的指针,指向一个子类的对象,通过这个指针调用这个多态的函数,实际调用的是父类的实现还是子类的实现?

我:子类

面试官:虚函数和纯虚函数有什么区别?

我:(md我这个真的有点忘了,bb了一堆没用的废话,也没说出什么区别)

面试官:那为什么要区分虚函数和纯虚函数?

我:(突然想起来一些),emm,虚函数是可以有实现的,纯虚函数存在于抽象类中,只是一个接口,不提供内部实现

面试官:考虑一个算法题吧,有 $n$ 套不同大小的螺母和螺钉,大小相同的螺母和螺钉可以配对,现在将螺母和螺钉分别打乱,你可以查询一个螺母和一个螺钉之间的大小关系(<、>、=),但不能查询螺母之间或螺钉之间的大小关系,请你找一种方法将螺钉和螺母两两配对

这个问题当时差点没想出来……最后时刻还是想出来了,思路就是先拿一个螺钉 A 和所有螺母比较,找出匹配的螺母 B,不匹配的螺母可以分成两部分,分别是小于 B 的和大于 B 的。然后拿 B 和所有螺钉比较,将螺钉分成小于 A 的和大于 A 的。这样就划分成两个子问题,递归就可以了。

面试官:OK,那就这样吧,你有什么问题吗

我:如果去实习的话能够做一些什么工作呢?

面试官:C++ 开发方面吧

????????我投的不是算法岗么,我说今天怎么问我的都是 C++ 的东西

我:好吧,那我没问题了

后续

被 Momenta 拒了,从头到尾体验极差,再也不见。