「面试」计蒜客 - 信息学竞赛讲师

前言

上周末杨老师在群里发了一条消息,大概是计蒜客暑假集训招 OI 方面的讲师,薪资 200~500 每小时。当时觉得暑假留校的话大概率也不会太忙,每周抽点时间讲讲课赚点零花钱也可以,就随手扔过去一份简历。

然后计蒜客的 HR 回复还是挺快的,然后电话问我啥时候有空去面个试。内心 OS:这种骗钱的活也要面试?后来想了想毕竟不是去学校或者个人讲课,计蒜客也算是个有点规模的公司了,就算是暑期实习也是要走面试这一步的。正好这周事情也不多,就当去计蒜客逛一圈,也算一次面试的经历,于是就约了周四的面试。

面试

12 点出校门,KFC 解决午餐,地铁坐到五道口转公交到了中关村,下公交后看了一眼地址:中关村大街科贸中心写字楼 B 座 935。这时候我才后知后觉反应过来,哪有什么计蒜客公司,不过就是个办公室而已(摔),合着我这三十多度的天坐地铁跑来参观办公室了。进去之后第一感觉这个写字楼环境还算不错,这儿似乎叫中关村互联网教育创新中心?不少搞在线教育的公司在这边有办公室。然后上去七拐八拐上了九楼终于到了,一眼看进去就是一堆码农各忙各的样子。然后给 HR 打了个电话出来接我,就进小黑屋准备面试了。

面试 I

先是和 HR 聊了一会儿,先是自我介绍,然后 HR 问我未来发展、期望薪资等问题,薪资我说的期望是 350~400,意思就是起码得给我平均数偏上。之后这个 HR 好像技术方面也不太懂 233,就塞给我一瓶冰红茶然后溜了。

面试 II

之后我在小屋里被鸽了十几分钟,就无聊的玩起了手机。玩着玩着两个面试官抱着电脑进来了,然后就默默的放起手机开始面试。

面试官 A 叫杨天,北林毕业的区域赛金牌,给人的第一感觉不错。自我介绍过后,主要是给出了几个教学场景,让我来模拟一下讲课。

场景 1:现在有一个刚刚开始学算法的学生,在他已经理解了递归的基础上,讲解一下深度优先搜索。

然后我就从图的遍历的角度讲了一下,手动模拟了一下 DFS,展示了一下递归和回溯的过程。

场景 2:现在有一个刚学习完变量的学生,讲解一下数组的概念。

考虑到这种问题八成是给小学生讲,就用盒子和球类比了一下,盒子代表变量,球代表数据。然后变量到数组其实就是一个盒子扩展到一排编号连续的盒子。

场景 3:现在有一个学习完了变量、数组、字符串等基本数据类型的学生,讲解一下结构体的概念。

又是语言的问题,那八成还是给小学生讲,就举了一个学生(姓名、班级、学号、年龄)的例子,大概就是说我几个不同的数据类型封装起来会有新的意义,对这个封装好的结构体可以进行更高层面上的操作。

场景 4:现在有一个开始学 DP 的学生,但是搞不懂 DP 和搜索的区别,无法理解 DP 的思想,解释一下。

当时思考了 10 秒钟想举一个例子,最后就举了一个 DAG 求最长路(固定起点、终点)的例子。如果搜索的话那在遍历过程中会做很多无用功,复杂度应该是阶乘级别?而如果我们考虑到最优解一定具有最优子结构的性质,就可以用动态规划来简化这一过程。也就是 $f_i$ 表示从点 $i$ 到终点的最长路,然后可以在 $O(n)$ 的时间内解决这个问题。

这几个问题个人感觉回答的还算可以吧,然后面试官 A 又跟我聊一些工作上的问题,第一是说除了讲课还要有答疑,这个当然可以理解;第二是问我大三有没有可能长期来上课,每周能抽几天,我回答的是每周最多一天,毕竟对我来说最重要的还是学业,这些只能说是赚点零花,也没指望通过实习转正什么的;第三是说可能暑假没事的时候要来办公室这边坐坐班,讨论下课程设计、安排等等的问题,听到这我就有点犹豫了,因为课程设计什么的可以说算另一项工作了,坐班更是没太大必要,不过当时就嗯了一下没说太多。

之后面试官 A 就走了,然后换面试官 B 来考察我的个人水平。

第一个是纸上写代码,让我写二叉树的层次遍历,显然就是写个 BFS,一分钟写完。

把纸递过去,他给我看了电脑上的一道题,大概题意如下:

给定 $n$ 个长度为 $m$ 的二进制串,可以无限次使用以下两种操作:

  • 将某个数字的 $m$ 位全部反转。
  • 选定 $k(1\leq k\leq m)$,将 $n$ 个数字的第 $k$ 位全部反转。

问最后可以得到的 $n$ 个数字之和的最大值和最小值分别是多少。$n,m\leq 3000$

其实做法还是比较显然的,比如要求最大值的话,就先用第一种操作,把最高位全变成 $1$,然后之后这种操作就不能用了,否则某个数字的最高位变成 $0$ 答案一定不会更优。之后就是从高到低扫每一位,如果这一位当前 $1$ 的个数比 $0$ 多就保持不变,否则用第二种操作反转一下。

讲完看面试官 B 的意思应该和标解的做法一样,不过还有一个细节需要考虑,就是把最高位统一之前实际上可以对最高位先进行一次第二种操作,最后答案是这两种情况取最优。

然后又问了一个比较简单的问题,题意如下:

给定一个 $n\times m$ 的迷宫,迷宫是四联通的,然后有一个 $S$ 一个 $T$ 还有一堆 $P$,问从 $S$ 走到 $T$ 且至少经过一个 $P$ 的最短路径是多少。

比较显然的 BFS 吧,我当时给出的做法是从 $S$ 和 $T$ 出发各 BFS 一遍,然后枚举每个 $P$ 将两个距离之和加起来最后取最优。面试官 B 的做法是从 $S$ 出发 BFS 然后加一个标志位 $0/1$ 表示有没有经过 $P$,个人觉得两种做法没有孰优孰劣之分。

然后面试就这么结束了吧,个人感觉还是挺顺利的?基本没有被卡住或者出现什么错误。离开的时候发现一些计蒜客女员工在做面部保健?当时觉得还有点厉害 233。

然后天气实在太热,没什么心情在城里乱逛,就索性回学校了。

回学校后倒头就睡,然后晚上看了看球刷了刷知乎,十点起床去打了会球,一晚上就过去了,咸鱼生活真快乐。

结果

结果就是计蒜客给了 200/h 的 offer,然后我拒掉了。