微软校招实习提前批面试经验

部门选的是 C+AI,工作地点选的是上海。

1.17 一面

  • 中文自我介绍
    • 说得太长了,感觉面试官根本没听
  • 算法题:求一个未排序的数组的逆序对数量
    • 想了 40 分钟,期间让面试官提示了 3、4 次,愣是没想起来
    • 对归并排序、快排这类基础算法掌握不牢,也没复习到
    • 最后完全没做出来,没写出代码,也没想出思路
  • 表现稀烂,草草收场

1.18 二面

  • 中文自我介绍
    • 概括成了 4 句话左右,精炼了很多
  • 在实验室做的 OS 中负责什么内容
  • 算法题:原地倒转链表
    • 三指针,lastcurrnext
  • 顺着第一个算法题问了些 OS 知识
    • 代码是怎么编译出可执行文件的
      • 编译到目标文件,再链接为可执行文件
    • 可执行文件是怎么运行的
      • 我回答的是 OS 或 ld.so 加载 ELF 的过程
      • 实际想问的也可能是 fork + exec
  • 算法题:求一个 0-1 矩阵中最大的相邻 1 的面积
    • 假设所有相邻的 1 之间有边,用 DFS 或 BFS 找到最大连通子图即可
    • DFS 的遍历条件一开始写漏了,面试官提醒 2 次有问题让仔细检查一下,分别检查出了一些错,最后完成
  • 顺着第二个算法题问了些 OS 知识
    • vector<vector<int>> M 参数如果换成 int *Mint **M,访问元素是还是 M[i][j]
      • 这里主要是考察对一个指针进行 [] 实际会发生什么
    • 如果矩阵很大,DFS 这样的递归算法还能工作吗
      • 栈溢出
    • 什么因素影响递归的深度
      • OS 为线程分配的栈大小、以及是否会动态增加栈大小
      • 每层函数调用的栈帧大小,具体包括局部变量、caller/callee saved 寄存器、函数返回地址
    • 估算上面写的 DFS 函数每层调用消耗的栈空间
      • 我一开始忘记了 caller saved 寄存器(在 call 之前需要保存当前层的参数寄存器才能再设置下一层的参数),最后面试官说不太对准备结束了,我强行问他,然后才终于想起来

1.21 三面(Lead 面)

  • 中文介绍自己的教育背景和项目经历
  • 在实验室做的 OS 中负责什么内容
    • 问了微内核和 Linux 这种宏内核有什么区别
    • 问了我们的 OS 如何实现信号量
    • 还问了一些忘记了
  • 擅长什么编程语言
    • 答了 C++ 和 Python
    • 接着问 Python 的内存管理和 C++ 有什么区别
      • 想考察的是关于 GC 的知识,我一开始没反应过来,因为之前刚在说操作系统的内存管理
      • 后来我说 Python 的对象内存管理是通过 reference counting
      • 然后又说了 GC 的 mark-and-sweep 算法
      • 感觉这块答得非常混乱,太紧张了
  • 算法题:如何求一个数的平方根
    • 我说可以用牛顿迭代,但我有点忘了来牛顿迭代是怎么做的
    • 他说那想想别的方法
    • 最后用了二分法,要写出代码(就几行)
  • 算法题:给一个未排序的数组,如何找到数组排序后中间那个数(也就是第 n/2 大的数)
    • 只要求说思路
    • 实际上就是 top k 问题,用快排的思路,在 partition 的过程中根据 pivot 最后所在的位置和 n/2 比较,来决定继续处理左半边或右半边,直到 pivot 的位置就在 n/2
  • 算法题:扩展上一题,如果数组的数字是一个一个输入的,如何在输入每个数字之后输出当前第 n/2 大的数
    • 同样只要说思路
    • 一开始说不能把数字存下来,没想出解法(真的可能不把数字存下来吗😂)
    • 然后放宽要求,可以存下来,边想边跟面试官讨论,经历了以下思路
      • 维护一个平衡二叉树,让两个子树节点数相差不超过 1,后来我发现不可行
      • 然后赶紧提出最简单的思路,维护当前第 n/2 数和左右两边的链表,像插入排序那样,每来一个数就插入到对应的位置,当两边数量差超过 1 时,取出左边最大的或右边最小的,更新第 n/2 数
      • 接着面试官提醒左右两个链表是否要维护全序关系,我于是想到可以左右两边分别维护一个大顶堆和小顶堆即可
  • 上面每个算法题每个思路都问了复杂度
  • 最后问我有没有什么想问的,然后结束

1.29 录用意向书

最后在 1 月 29 号收到了录用意向书。

评论