求职记 —— 实习篇

Job Hunting for 2018 Summer Intern

Posted by JetMuffin on May 2, 2018 | times

从 2018 年 2 月底开始,到 2018 年 5 月初结束,持续了近三个月的实习告一段落,收到了一些 offer(其实是投的 5 家都拿到了 offer[机智]),总结下整个过程,也为秋招做准备。

投递

由于研究方向偏向于基础架构和底层(集群调度、容器、操作系统内核),因此在简历投递时偏向于大厂,因为一般大厂比较重视基础架构方面的技术。

最先开始内推的是阿里(印象中在过年之前就开放内推途径),由于之前关注过阿里的系统软件部门,方向和我感兴趣方向非常吻合,包括 SigmaPouch,于是找师兄定向内推到阿里的系统软件部门;第二个选择则是百度,做调度方面国内除了阿里之外的大厂,应当是百度的基础架构部门(INF,北京)里负责 Matrix 的团队。刚好本科一个朋友在百度工作,于是在百度 2018 校招开始之前就提前拜托他帮忙内推了;投了 BA 两家,自然想尝试一下 T,但是腾讯的校招岗位侧重于后台开发、游戏开发这些岗位,似乎做核心的容器或者调度的部门很少。于是先在校招官网上投了一个比较近似的运营开发,校招网上对这个岗位的描述是建设运营云平台,同时由于比较热衷于游戏,选择了上海的 IEG 下的运营开发;第四个投递的公司是网易游戏(互娱),网易游戏有专门的基础架构部门,分别负责调度、容器、虚拟化等方面,同时听师兄描述实习体验不错,于是又投了互娱的基础架构部门(广州);最后一个选择是微软,不管是南大还是软件所每年都有比较多的师兄选择微软,我选择投递的是微软上海的 C+E 部门的暑期实习,主要方向是 Azure 相关的云计算业务开发。

这里需要另外提一下的是谷歌,谷歌一般简历筛的比较厉害,有内推才相对较稳。一开始觉得以自己的实力投谷歌基本上是过不了的,就没有找师兄内推谷歌,到四月份慢慢收割了几个 offer 以后自信心开始膨胀,想要试试谷歌,但发现 Summer Intern Project 的简历投递已经结束了,也是比较可惜。

面试

有些面试过程较久,这里就简单记录一些其中比较重点的问题当时的回答

阿里一面

一面主要是简历测评面,首先做了简单的自我介绍,然后围绕之前的项目内容进行了一些讨论。由于在研一到研二做了一些 Mesos 上的超售和混布的项目,面试官比较感兴趣,讨论了其中的几个重要点的解决思路。之后给了一些开放性的题目,印象比较深和比较感兴趣的问题主要有以下几个。

Q: 容器编排之后,设计一个算法使得分配容器到物理机的资源碎片最小。

明确这是一个 NP-Hard 问题,可以用动态规划,背包,贪心(Best-Fit,First-Fit)

Q: 任务在混布时,低优先级将会被 Kill,Kill 任务的策略选择;更进一步,加入任务数量巨大,无法进行排序,如何进行 Kill?

基于特定顺序的:业务优先级(之前读过 Sigma 的一些文章);任务执行时长(任务中带有 checkpoint 或者 progress 信息),任务重要性(任务 DAG 依赖图中的出度入度关系);不依赖于排序:启发式方法,根据任务类别分类(桶),每个类别中每次 Kill 随机挑选;每个桶之间维护权值,根据 Kill 后的效果反馈更新桶权值,再将桶排序进行下次 Kill。(虽然还是要排序,但是是对桶的排序,数量很少,面试当时瞎编的方法)

Q:cpu.share 有什么缺点?

它是个固定值,在进程创建时设定,运行过程中 share 值不变,但是进程运行时的优先级可能会变化。

Q:任务运行的 cpu.share 怎么定?

根据优先级给,高优先级的给比例 1,低优先级给比例 0.01 (参考 Mesos);考虑 cpu.quota,quota 越高从另一个方面说明这个任务较为重要

阿里二面

二面面试官是宏良(孙宏亮,@allencloud),之前 Daocloud 的大佬 DockerDocker SwarmPouch 等多个项目的 contributor 和 maintainer。二面主要围绕调度容器开源三个方面问的。

Q:混布中的主要关键点是什么

隔离(现在利用容器仍然存在冲突)、混布后台任务的数量(评估机器可以混布的程度)、如何探测冲突(QoS 的异常值,从宏观和操作系统围观反映)、如何解决冲突(Kill 哪些后台任务)

Q:Docker 的基本工作原理

namespace / cgroup,volume,image 等相关的一些东西

Q:你觉得 Docker 的缺点有哪些?

讲缺点一时真答不出来(大概是为什么要做 Pouch 项目?),后来查查应该是 Docker 的隔离性、安全性以及在虚拟机环境下跑的一些缺点。

Q:那你觉得 Docker 带来的好处有哪些?

部署应用更轻量级(相比虚拟机);Devops 相关,减少开发运维成本

Q:之前是否在开源社区贡献过代码

提过的一些 issue,contribute 过一些小项目

阿里三面

三面是系统软件部门的大 Boss 面的,开始也讨论了一些超分和混布的一些项目中的问题,之后问了一些基础。

Q:评估任务可用回收量时,任务使用量突然上升,导致机器超负荷,如何解决

评估层面根据历史使用数据,加二次指数平滑做一个趋势的提前量;运行时使用 cpu.share 把后台任务低优先级降低;回收时给一个固定的 margin 做缓冲

Q:之前做的项目中是否有要解决高并发的情况,如何解决的

不想答 c++ 相关的高并发相关内容,于是答了 tornado 的工作原理

Q:Golang 的垃圾回收过程

标记,整理,回收

阿里四面

四面是交叉面,面试官是隔壁中间件部门的大佬,同样讨论了一会儿项目的内容。

Q:cgroup 如何做资源隔离

cpu.(quota/share/period),memory.quota,disk.io;更细粒度需要 cpu.set

Q:怎么限制进程的内存带宽使用?

开源/商业级的应用没有比较好的方法。(Heracles 的论文里提到过);限制进程使用的 cpu 核数来限制 per-core memory bandwidth。(Memguard 的论文的方法)

Q:为什么 cgroup 可以限制磁盘读写 IO,而无法限制内存带宽?

撤了一堆内存总线占用之类的有的没的,但是面试官一直让我从体系结构方面去思考。之后回答disk 属于外设(外存),读写由操作系统的驱动程序控制;而 CPU 读内存的逻辑是写在硬件逻辑中(寻址等),内核只是使用这些逻辑,没法控制

Q:能否通过加一层 hypervisor 来实现限制内存带宽

这个真不知道,然后面试官说他也不知道

阿里 Offer

HR 面完当天阿里的 HR 就加了微信表示面试通过,马上会发 Offer,几天后收到阿里的录用意向书。

百度

百度是最早收到面试通知的一家,效率非常高,一天搞定一面二面和 HR 面,当天就给了 Offer,瞠目结舌。

百度一面

一面面试官小哥约了早上 10 点的面试(大概是他们的上班时间?),然后路上遇到了堵车(吐槽下北京的交通),大概到了 10 点半才开始。面试过程中主要就是对着简历上写的项目,挨个问细节,然后具体讨论一些技术方案(可能是因为方向非常一致的原因)。

Q:为什么要在 HDFS 中合并小文件?

HDFS 适用于高吞吐量场景,例如体积较大的日志文件读写。默认的一个 block 为 64 MB,而小文件(几百 kb 到 几 MB 是远小于这个的块大小的),而 block 的 metadata 是存在 namenode 的内存中的。一旦小文件数量非常多(几万至几十万),namenode 中 metadata 数量剧增,内存压力大,并且查询 block 位置信息时效率也慢。

Q:你是怎们做的 HDFS 合并小文件?

用 Mapfile 或者 Sequencefile,把小文件打包成接近一个块的大小,这样在 namenode 查询 metadata 的时候速率会大大提升,虽然增加了额外的 Mapfile 中寻址的时间,但是总的读取时间会降低。

Q:为什么要写 docker 的 webtty?怎么实现的?

因为之前平台的项目中,如果容器需要调试,经常需要登到机器上 docker exec,而 webtty 直接可以从一个 controller node 进到集群指定容器调试。实现上是用了 docker remote api 获取一个 stream,再通过两个 PIPE 把这个 stream 的 I/O 两端 hiject 到一个 websocket server 上。

这里面试官问了下是否会碰到非 utf-8 字符集的情况,刚好想到之前 project 开源在 github 上有人提到的 vim 上有些问题和中文的一些问题,然后解释了下,对 stream 内容取再 hiject 到 websocket 上时会先用 base64 encode 一下保证排除字符的影响。

之后又和面试官讨论了下如何用一条 shell 去判断该用 /bin/sh 还是 bin/bash(如果容器中没有 /bin/bash 进程),刚好项目里也考虑了这个问题,大概写了下 shell。

最后是会话进程可能不会因为 socket 关闭而关闭的问题,也和面试官讨论了下。

百度二面

百度二面同样是 INF 部门,应该是调度部门的 Boss 级别人物,内容还是讨论项目,依然是两个话题,超分和混布,围绕之前的超分和混布的项目的一些细节讨论了比较多,和阿里的面试比较类似,这里不再赘述。

Q:用一句话概括下什么是 DRF 算法

DRF(Dominant Resource Fairness)主要是用主导资源这个概念来表示一个应用可能的瓶颈资源,并用这个一维指标进行 max-min 的公平调度算法。

二面面完面试官挺满意的,并且表示他们做的内容和我的研究方向非常一致,希望我能去他们那儿实习,并介绍了下他们最近的工作,同时强调了下百度在业内做调度系统方面是领先的。

百度 Offer

当天下午就收到了 HR 电话,简单聊了下基本情况,表示面试都已经通过,可以下发 Offer 了。但是由于当时百度的校招还没开始(大概是3月初),太早发 Offer 怕之后拿了其他公司 Offer 就不去百度而站着 headcount,于是让我在百度校招开始之后电话联系她,她在给我发 Offer。

腾讯

腾讯内推是找了论坛上的一个内部员工,并没有定向投,第一次被 QQ 音乐(估计这个员工是 QQ 音乐的)捞过去了。一面完全像是在考试,面试官感觉是拿着一张面试题表挨个问你,你给答案他打分。由于准备不充分,回答的不太好,并且被问到用 C 还是 C++ 多一点的时候脑子一热回答都不多,直接被面试官拉闸 gg,面试体验极差。

挂了以后大概经过一周,简历又被游戏部门的运营开发团队捞了起来,这次面试准备充分多了。

腾讯一面

腾讯一面问的内容跨度非常大,从前端到后端到安全到机器学习再到智商题都有涉及,这里就挑选一些比较有趣的题目(CS 几大课程的基础题就不写了)。

Q:如果让你设计一个论坛防灌水机器,你要如何去写它的逻辑

第一次拿到设计题,感觉面试官想用一个设计题考察知识的广度。

首先按现有的一些论坛的方法给出了方案,先是回帖最短时间间隔设定,然后是回帖需要输入验证码,再是论坛发帖必须满足一定条件(例如邮箱验证,手机验证,注册满一小时等),利用这些机制先过滤掉大部分的灌水机器人。面试官对回帖最短时间间隔设定的具体实现又考察了下,并具体讨论了下高并发下多事务可能出现不一致性以及加锁的实现。

然后我又瞎掰了一个基于语料库的方法,根据人工标记的一些典型灌水类型内容,提取特征,训练一个语料库,再之后的发言过程中根据训练的模型去验证该回答是灌水发言的置信度。

Q:一个微信群发红包,分 5 元,10 元,20 元,50 元,100 元这 5 档,每个档个数相同,每个红包分到概率相同,每个人只能看到自己分到的钱,现在你分到了 10 元钱,可以允许你向别人申请交换红包(双方都只能看到自己的钱),且每个人都从个人利益最大化角度考虑,那么你会选择换还是不换,为什么

这是一个很有意思的智商题。理科生拿到这个题目首先的想法是去算概率,最 naive 的想法就是我有 3/5 的概率拿到更高的钱,1/5 的概率拿到更低的钱,从概率上讲,选择换是收益更大的。

但是仔细一想,面试官强调了每个人都从个人利益最大化角度思考。那么拿到 100 元的人,他选择换,必然是会亏损的,所以他必然不会换;拿到 5 元的人,不管和谁换都不亏,肯定选择换;拿到 50 元的人,如果站在 100 元的人的立场思考过,那么他如果换,肯定不会碰到 100 元的人,只会碰到低档,所以也是亏的,也选择不换;以此类推,那么我拿 10 元钱,如果选择换,只能碰到 5 元的人了,也是必亏的,所以不换才是正确的。

腾讯二面

腾讯二面的面试官是个声音很好听的小姐姐(应该是大部门的总监,虽然可能是个阿姨级别的 Boss)。由于可以看到前一个面试官的评论,讨论了好久为什么之前面试会挂,并且挨个问了之前面试没有回答出来的内容。

Q:用两个栈实现队列

Leetcode 经典题,出队的时候需要把其中一个栈里的东西全部压到另一个栈里。

Q:为什么用 go,用 go 的优势

语言级别支持并发(goroutine 相关),channel,mutex 等特性便于并发中多协程通信,编译时只依赖于 glibc 等。

Q:golang 垃圾回收

怎么哪儿面试都要问垃圾回收。

腾讯 Offer

由于挂了一次腾讯,第二次腾讯面试通过的时间就比较晚了,接近提前批的末尾。腾讯的 HR 非常负责任,在清明前的一个周六打来表示希望能够在提前批结束前把流程走完,这样我就不用重新进行面试流程,然后进行了简单的 HR 面,涉及的内容也就是对个人性格的一些描述。面试通过以后大概两三天录用 offer 就发到邮箱了。

网易游戏

网易游戏总共就面试了一轮,但是这一轮面试内容非常多,从电话中可以听出大概有 3 个面试官同时在出题,一面一共面了一个小时半。首先介绍了下之前做的项目,并讨论了项目细节。面试内容很贴切容器、调度这几个方面,问的内容非常细节,具体问题记得不太清楚,这里主要记录其中的几个。

网易游戏一面

Q:你知道 websocket 底层是怎么实现的吗?用到操作系统中的什么内容?

瞎答,卒

Q:cgroup 有哪些子系统?

blkio,cpu,cpuacct 等

Q:namspace 有哪些种类?

面试当时就只记得起 PID,其他都忘了,卒

Q:docker 如何获取实际容器的 cpu 使用量?

读取 cpu.acct 中有 cpu 使用时间总量,根据两次采样点的时间差 delta,以及总的 cpu 时间总量做除法得到

Q:go 是如何实现并发的

讲了下 goroutine 和 go runtime scheduler,被面试官指出细节上有比较多的出入

Q:go 垃圾回收

又一个问垃圾回收的

网易游戏 Offer

面完网易游戏感觉人的虚了,感叹下网易游戏基础架构水平确实挺高的。虽然面试时感觉面试答的一塌糊涂,但是面试官表示可能是他们考察的内容比较多,实际实习会分到一个比较细的部门(例如调度)去做,一两周后竟然收到了网易游戏的 Offer。

微软一面

微软的面试很常规,先大概介绍 10-15 分钟的项目,然后开始白板写题,题目面试官口述,然后用 Skype 自带的白板或者一个白板做题的网站上直接编码。由于之前没怎么刷过 leetcode,做题全部靠本科打 ACM 的底子。

Q:反转链表

常规的 leetcode 题,写了一个基本的调指针指向的方法,边界情况写的很谨慎。面试官检查完以后安利了一种更好理解的方法,直接拿一个新的指针作为链表尾,边遍历边往指针头部加元素。

Q:实现一个 LRU cache

也是常规的 leetcode 题,用双向链表加上一个 hashmap 来实现。先和面试官讲了大概思路,提了两种更新操作需要 O(n) 的方法,又讲了下正解。之后开始编码,编码的快差不多时,面试时间到了,面试官觉得写的也差不多,直接让准备第二轮面试了。

微软二面

Q:无向图中最长路径

给定一个无向图,无环无重边,求这个无向图上的最长路径。

首先明确了一点,无向图,无环无重边,那就是一棵树,也就是要求树上最长的路,也就是树的直径。一开始拿到题目,还是先想暴力方法,对于任意一个点 v,都可以 bfs 或者 dfs 找出以这个节点为根的最长路径,然后遍历所有节点,总复杂度是 O(V^2)。然后其实最长路径肯定是以叶子节点为首,以叶子节点为尾的路径,因此可以继续加上剪枝,但是复杂度仍然还是 O(V^2)

之后和面试官讨论了下用 DP 或者记忆化搜索的可能性,发现都不太行,最后没给出更进一步的方法。面试完查了下资料,发现是个结论题。

st 分别为该图的最长路径的两个端点,则从任意一点 u 出发搜到的最远的点一定是 st 中的一点,那么只要从这个最远点开始再做一次搜索,就可以搜到另一个最长路的端点,即用两遍搜索就可以找出树的最长路。题目类似 POJ#2631,证明过程摘自题解:

1.设 u 为 s-t 路径上的一点,结论显然成立,否则设搜到的最远点为 T 则 dis(u,T) > dis(u,s) 且 dis(u,T) > dis(u,t) 则最长路不是 s-t 了,与假设矛盾; 2.设 u 不为 s-t 路径上的点,那么: 1) u 走到了 s-t 路径中的某点,假设为 X,那么最后走到的重点必然是 s 或 t(情况 1 的子问题) 2) u 走到最远点的路径 u-T 与 s-t 无交点,则 dis(u,T) > dis(u,X) + dis(X,t) 首先明确,假如u走到了s-t路径上的一点,那么接下来的路径肯定都在s-t上了,而且终点为s或t,在1中已经证明过了 所以现在又有两种情况了: 1):u走到了s-t路径上的某点,假设为X,最后肯定走到某个端点,假设是t ,则路径总长度为dis(u,X)+dis(X,t) 2):u走到最远点的路径u-T与s-t无交点,则 dis(u,T) > dis(u,t);不妨在 s-t 上取 x1,u-T 上取 x2,那么可以得到 dis(u-x2) + dis(x2-T) > dis(u-x2) + dis(x2-x1) + dis(x1-t),也就是 dis(x2-T) > dis(x2-x1) + dis(x1-t)。再构造 dis(x2-T) + dis(x2-x1) + dis(x1-s) > 2dis(x2-x1) + dis(x1-t) + dis(x1-s),即 dis(s-T) > 2dis(x2-x1) + dis(s-t) > dis(s-t),与 s-t 为最长路径矛盾。

微软三面

Q:统计单词个数

给定一篇文章,统计其中的单词个数(单词只能为大小写字母),要求空间复杂度 O(1),时间复杂度 O(n)

思路比较好想到,就是判断空格的出现。但是边界情况会有很多,于是用一个标识位来表示当前空格的状态,以及一个游标扫当前输入的字符。

Q:加强版:单词允许出现单引号

单词中允许出现单引号,并且只能出现一次单引号,事实上的约束比这个口述标准更复杂。面试官首先和我明确了下题目是否弄明白,于是让我写各种测试用例,然后他告诉我标程得出的结果。整个过程类似他在心中默念一个正则表达式,我给他输入,他告诉我输出,然后让我实现这个正则表达式(这个过程有点类似编程之美的形式)。

大概花了 15 分钟测试了各种各样奇葩的测试用例,测完以后事实上对这个正则表达式还是一头雾水,然后就按照自己的理解写了。编码时间也是 15 分钟,噼里啪啦敲了一番(事实上就是在原来的状态之上再加一个状态,并且注意各个状态的转换),面试官表示除了一处一个小问题其他都不错。

微软 Offer

其实三面面完感觉微软的 Offer 就稳了,面试官的评价挺好的,并介绍了下他们部门做的 Azure 上的混合云以及云存储相关的工作。大概一周之后收到 Congrats Email,再过了几天就收到了正式的 Offer。

总结

经过春招找实习的过程,总结了以下几点经验:

  1. 一定要早准备,早投递

    可能有些同学认为晚点投递可以准备充分一些,但是从春招的情况上看,因为我投递的早,hc 充足,给的面试机会很多。另外,投递的早,即使出现失误(例如面腾讯挂了一次),也有机会再次被捞起来。

  2. 尽量投递方向对口的岗位

    春招过程中基本上都是投的基础架构部门(调度、OS、容器相关),这样面试官对你之前做的项目和研究会很感兴趣,大多时间会讨论你的项目内容,得到认可的概率也高。如果投递的部门方向差别较大,那么面试官只能考察基础,个人比较反感这种纯考察基础(操作系统、计算机网络、编译原理等本科几大课程)的面试。

  3. 面试时不会的题,可以从自己会的方面去获取分数

    在这几次面试过程中,经常有面试官问到知识盲区的地方,相比于直接答不会,我一般答一些比较相近,自己非常有把握的内容,如果面试官人好的话,可以拿到一些补偿分。

  4. 提升自己的算法能力和 bugfree 编码能力

    春招期间除了微软以外其他全部走的内推,笔试比较少。算法还是每个公司考察的基础,非常重要。同时像 Microsoft,Google,Hulu 这类外企还是比较看重算法能力,都需要白板做题,所以还是很需要提示自己的算法能力。

选择

最后拿到的这 5 个 Offer 中,根据城市、部门、获得转正机会概率、工资等方面,以及自己的情况,做了下简单的排序,个人的选择是:

阿里 > 微软 > 网易游戏 > 腾讯 > 百度

最后也是在阿里和微软之间纠结了很久,还是选择了阿里。至于微软以及其他的外企,还是等到秋招再去努力努力!