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

目录：

---

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

1.17 一面

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

1.18 二面

• 中文自我介绍
  • 概括成了 4 句话左右，精炼了很多
• 在实验室做的 OS 中负责什么内容
• 算法题：原地倒转链表
  • 三指针，last、curr、next
• 顺着第一个算法题问了些 OS 知识
  • 代码是怎么编译出可执行文件的
    • 编译到目标文件，再链接为可执行文件
  • 可执行文件是怎么运行的
    • 我回答的是 OS 或 ld.so 加载 ELF 的过程
    • 实际想问的也可能是 fork + exec
• 算法题：求一个 0-1 矩阵中最大的相邻 1 的面积
  • 假设所有相邻的 1 之间有边，用 DFS 或 BFS 找到最大连通子图即可
  • DFS 的遍历条件一开始写漏了，面试官提醒 2 次有问题让仔细检查一下，分别检查出了一些错，最后完成
• 顺着第二个算法题问了些 OS 知识
  • vector<vector<int>> M 参数如果换成 int *M 和 int **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 号收到了录用意向书。