「面试」旷视科技研究院 - Face Recognition 部门

前言

之前在北邮人论坛上看到旷视 Face Recognition 部门招人,虽然没说具体做什么工作,不过还是顺手投了一波。

基本情况

  • 面试岗位:旷视科技研究院——Face Recognition 部门
  • 投递渠道:北邮人论坛邮件投递
  • 面试时间:2019.9.3

一面

上午面完商汤来到旷视这边一中午没睡……两点的时候感觉自己已经快要睡着了。

面试官:先来一道算法题吧,给你一个单链表,实现一下链表排序

然后我就写了个选择排序(我为什么要写选择排序,sb*1)

(PS:旷视的代码是在白板上用笔写

面试官:有没有更快的方法啊

然后我就写了个快排……说实话还是第一次写链表实现的快排,还好顺利写出来了。

面试官:嗯,那再来一个,给定 $N, k$,请你求 $\sqrt{N}$,且误差不超过 $10^{-k}$

这个明显的二分嘛,就写完了

面试官:这个复杂度是多少?

我:$O(\log \sqrt{N})$ 吧(sb*2)

面试官:嗯哼?这里还有个 $k$ 呢

我:啊啊,是 $O(\log(10^{k}\sqrt{N}))$

面试官:嗯,那现在你想一下有没有什么优化的方法能降低一下这个复杂度,哪怕一丁点也ok

我:(深思熟虑一分钟),可以先在整数上进行二分,找到一个 $x$ 满足 $x^2 \leq N\leq (x+1)^2$,然后在这个小范围上进行实数二分,这样复杂度就变成 $O(\log(10^{k} + \sqrt{N}))$ 了。

面试官:不错,还能继续优化吗?比如用点数据结构什么的。你可以认为你有很多内存和 CPU,然后要执行很多次这个操作

这说的我就有点迷糊了,这玩意还能用数据结构优化?感觉没有 get 到面试官的暗示。

面试官:其实可以首先将 $N$ 的小数部分抹掉,然后这个 $N$ 对应的 $x$ 可以用一个数组来存下来,这样就不用每次二分了,复杂度就变成了 $O(\log{10^k})$

我:好吧2333,不过这个复杂度其实基本没变

面试官:所以我说哪怕一丁点也ok啊(笑)

面试官:那接下来再来一个问题,知道聚类问题吗?

我:只知道 kmeans

面试官:kmeans 初始 k 个点的选择对结果的影响是很大的对吧

我:嗯对,如果选的过于集中那可能学出来的分类并不好

面试官:对,所以这个问题怎么解决有思路吗?

我:(想了挺久还是没什么太好的思路,就开始随便口胡了),这个要想不要选的太集中的话肯定要考虑根据坐标选,可以按 x 坐标均匀选 k 个,按 y 坐标均匀选 k 个,然后再从这 2k 个里面随机选 k 个……?(这要是靠谱我自己都不信)

面试官:这个代价有点大啊,而且你这个 k 怎么确定也不好确定。这 k 个点是可以按顺序一个一个选的。

我:那先选 1 个点,然后设一个阈值,下次选必须从离第一个点距离大于阈值的点里随机选?

面试官:没必要设阈值啊,直接选距离最大的不就 OK 了吗?

我:好像也有道理

面试官:那你第三个点怎么选?

我:emm,那就离前两个点距离之和最大的?但是这样每次选的代价都很高啊

面试官:嗯,这样也可以,不过 kmeans 里的 k 一般都不会很大,这部分不会是主要开销,所以这样也是可以的。

我:好吧

面试官:那算法就问到这,问点计算机相关的吧。说下进程和线程的区别。

我:(md我操作系统真的已经忘光了),一个进程可以包含多个线程,然后线程间通信比进程间通信的代价小很多(给自己挖坑)。

面试官:说到这了,那你说下进程间通信都有什么方法吧。

我:共享内存、消息机制、socket、RPC……

面试官:共享内存和消息机制都是怎么实现的?

我:共享内存就是有一段内存区域,两个进程都可以对其进行读写。消息机制就是通过 send 和 receive 进行消息的传递。

面试官:嗯,那你应该知道生产者-消费者模型吧

我:知道

面试官:现在比如我们在爬虫,你要发起 HTTP 请求来获取一个网页的源代码,然后交给 CPU 来解析,这就是一个生产者-消费者模型,你觉得这两部分哪个是主要开销?

我:(这里我真的开始瞎猜了),emm,解析的开销应该比较大吧。

面试官:嗯,其实请求网页源代码算是一个 IO 密集型任务,解析算是一个 CPU 密集型任务。那你觉得这两部分哪个可以用多线程优化,哪个可以用多进程优化?

我:请求网页可以用多线程,解析可以用多进程吧(瞎猜)。我记得 Python 的线程池可以实现并发爬虫。

面试官:你的意思是先爬下所有网页,再进行解析,可不可以边爬边解析?

我:可以吧,用非阻塞的方式,爬下来一个就喂给 CPU 解析(还是瞎猜)。

二面

面试官:来考虑这样一个问题,有一个猎人,一只兔子,还有排成一排的五座山,兔子可能在某一座山上,每天兔子会跳到相邻的某一座山上,猎人会去某座山上打猎。问猎人有没有什么策略一定可以抓到兔子。

这个我当时想了很久也没有想出必胜策略,当时觉得唯一能抓到兔子的情况就兔子在 1/5 然后猎人守在 2/4,但是并没想出策略能把兔子逼到某一头上,主要瓶颈就在于猎人和兔子相邻时,下一时刻可能猎人和兔子发生位置交换,然后可以继续交换下去……

于是就说了自己没思路,面试官也没说到底有没有必胜策略,就这么过去了(gg*1)

面试官:那再考虑这样一个问题,在一个 $1\times n$ 的图像上,做一个 $1\times m$ 的最大池化,这样得到一个 $1\times (n-m+1)$ 的图像,要求在 $O(n)$ 的时间复杂度内求出池化后的图像。

我:其实就是求每个长度为 $m$ 的区间的最大值,这个可以用单调队列来做,维护一个单调递减的队列,处理到 $i$ 时,保证队列中的所有元素都在 $i-m+1 \sim i$ 的范围内,这样队首元素就是这个区间的最大值,扫一遍就 OK 了

面试官:嗯,可以,那下面讲一下线段树的 lazy 策略吧

我:lazy label 其实就是对于一个区间操作,把操作下放到 $O(\log n)$ 个小区间上,而不是下放到每一个元素上。对于每个具有 label 的结点,我们要更新其维护的一些权值,而对其子树内结点的权值不进行更新。当需要操作/查询到子树中的某个结点时,对该结点的 label 进行下放,所谓下放就是取消当前的 label,并把相同的 label 打到子结点上。

面试官:OK,下面问一个概率的问题吧,一个圆周上随机分布 $n$ 个点,让你随机选四个,问这四个点分布在同一个半圆上的概率。

这个我记得我见过一个类似的问题,是在一个圆内随机选 4 个点,问这 4 个点在同一个半圆内的概率。然而这个我当时想了一会儿还是不会做,然后就放弃了,数学太菜了555(gg*2)

面试官:好吧,那问个别的问题吧,矩阵可逆的条件是什么?

我:行列式不为 0,列向量线性无关,满秩

(沉默一分钟)

我:还有别的吗……

面试官:OK,那下一个问题吧,你怎么理解特征值?

我:emm,如果把矩阵 $A$ 看成一个线性变换的话,满足 $Ax = \lambda x$ 的 $\lambda$ 就是特征值,$x$ 就是对应的特征向量。特征向量就是那些经过线性变换后仍然不改变方向的向量,特征值代表的是这些向量经过线性变换后放大的倍数。

面试官:特征向量之间一定正交吗?

我:不一定啊

面试官:那有没有什么情况他们是正交的?

我:(好像是有个结论来着),$A$ 是实对称矩阵的时候吧。

面试官:能解释一下为什么吗?

我:不知道(背结论被发现了,gg*3)

面试官:OK,那问点操作系统的内容吧,能解释一下进程和线程的区别吗?

我:(wdnmd 怎么又是这个,开始复读),一个进程可能包含若干个线程,线程间通信的代价比进程间通信小

面试官:进程间通信的方式有哪些?

我:(继续复读),共享内存、消息机制、socket、RPC……

面试官:共享内存指的是什么?两个进程拥有的内存空间应该是独立的啊,怎么共享?

我:进程操作内存需要进行内存地址转换,把虚拟地址转换成物理地址,不同的虚拟地址可以映射到同一段物理地址。

面试官:内存地址转换是怎么实现的?

我:就是把地址从高到低分成若干段,高若干位可能表示一级段号/页号,然后后若干位表示二级段号/页号,最后一段表示偏移量。

面试官:问一个计网的问题,五层协议模型里,前三层都有哪些协议?

我:第一层是物理层,好像没啥协议……第二层是数据链路层,有停等协议、后退N、选择重传等协议,第三层是网络层,常见的协议比如 IP。

面试官:知道 ARP 吗?

我:就是发送一个广播,根据 IP 地址去找那个什么地址……那个什么地址来着,记不起那个名词了(回到宿舍才想起来叫 MAC 地址,gg*4)

面试官:说下你知道的分类模型

我:SVM……

面试官:讲下 SVM 的原理吧

我:(记不起来大间隔的原理了,gg*5),就是训练一个向量 $w$,用 $wx+b$ 来进行分类

面试官:二分类里的 precision 和 recall 是什么意思?

我:精确率就是我预测为正的样本里有多少为正,召回率就是所有为正的样本中有多少被预测对了

然后问问题的基本就结束了,后面就问了一些实习几天的问题,然后就结束了,感觉凉透了

面试官:知道 PCA 吗

我:可以用来降维

面试官:简单讲一下原理吧

我:忘了……(机器学习的东西好久没看过了,gg*6)

面试官:那这样,在一个 n 维平面上有一个点 a,还有一个 n-1 维的过原点的超平面,给定这个超平面的单位法向量 p,求点到超平面的距离。

我:这个就先是点在法向量上投影的长度,也就是 a 点乘 p 再除以 p 的模长,因为 p 是单位向量,所以答案就是 a 点乘 p。