/ ALGORITHM

2018 微软预科生面试

4月2日参加在线笔试,4月13日收到了面试邀请,也是非常开心。
面试时间:4月26日
面试地点:中关村微软大厦

插曲:4月26日因为高铁班次原因,HR小姐姐非常好心地帮我把面试时间调整到了下午并让我注意安全别急着赶路,真是大厂风范,非常感激了。

面试流程


准备


  • 等待面试的同学都被安排在一间大屋子里休息,提供饮料、盒饭,还能享受在微软大厦中俯瞰中关村的风光 :)

  • 认识了几个来自天南地北的小伙伴

  • 下午一点开始面试

一面


  • 面试官是一位很年轻很有活力的程序猿,上来先聊了一会 Surface

  • 问了一个问题:说一个你觉得最有趣的数据结构
    • 傻乎乎地说了 Treap
    • 但是自己退役后好久没用了,细节都忘了
  • 第一题:简单地写一下数字转字符串
    • 记得判断负数
  • 第二题:给出两个已排序数组,要求找出它们合并后的中位数
    • 刚开始很蠢地说了一个 $O(n)$ 的做法
    • 面试官提醒还有没有时间复杂度更优的 idea, 于是想到了二分

二面


  • 一面结束后等待了几分钟就见到了二面的面试官,看起来是一位很强的程序媛!

  • 简单自我介绍后就开始做题!

  • 第一题:找出一个字符串里第一个只出现过一次的字符
    • 提示要用常数空间,设定 ASCII 大小的数组遍历两次
  • 第二题:2 SUM问题
    • 先用 stl::map 写了一下
    • 面试官要求时间复杂度更优,于是想了一个从前后同时扫的方法,也没去想证明了,跟着感觉走
  • 第三题:求LCA
    • 直接写了一个预处理深度的方法,然后时间就到了

三面


  • 终面等了一个小时,最后见到了最终的面试官,感觉气场很不一样!

  • 先围绕着简历聊了很久,被问到有没有特别关注的技术网站

  • 要求自己随便选一个 topic, 充当讲述人的角色聊天

  • 做题:要求一种挑选方案,使得从 $n$ 个不同的数字中,挑选出 $k$ 个数字且这 $k$ 个数字被选中的概率都是 $\frac{k}{n}$

    • 没有做出来
    • 正解如下:

Result


4月28日晚收到了HR的邮件,表示我的面试结果很positive, :)

Summary


  • ACMer 可以刷一下 LeetCode 适应面试题的风格难度(避免想太多)
  • 可以准备一下相关的项目内容来和面试官聊