2019-03-26 微软第二次面试

面了微软的 Cloud + AI 组。

一面

1. 二叉树上每一个节点具有 value，求一条路径，使得总收益最大。

一开始想到了动态规划的解法，但是一直陷在了单次遍历的问题中。经面试官提示之后，完善了解法：

• 先递归求出途经每个节点无分叉的单边最大收益

• 再根据单边最大收益求出每个节点的最大总收益

二面

1. 给出一个 m * n 的矩阵 M，矩阵元素满足同行递增、同列递增，如

M: [0, 3, 5, 9]
[1, 6, 8, 10]
[4, 11, 15, 20]
[7, 13, 22, 99]
给出一个目标值，返回它在矩阵中的位置，如果未找到，返回（-1， -1）。

解法：
边界情况判定后，沿着对角线找，如果找到直接返回，否则找到对角线上第一个比目标元素大的值，将矩阵划分成 四个象限，在左下和右上子矩阵中递归查找。

其实就是二分查找的二维情况。

三面 Word Count 问题：

1. 给出一个文本文件，求出其中词频最大的十个词。
   解法： 用 Map 保存词频，维护一个大小为 10 的数组，遍历 Map

2. 问题升级，求出词频前 10% 的词语。
   解法：Map 保存词频，利用快拍的策略，得出词频前 10% 的词语（并不是完全有序）

3. 问题升级，有一千个文件，求出其中词频前 100 的词语。内存限制不能用一个 Map 保存总的词频结果。
   这个问题我就完全没有头绪了，经面试官提醒，了解了解法：
   将 a 开头的词语放在磁盘一上，b 开头的放在磁盘二上，以此类推。
   分别找出每个磁盘中词频最大的前 100 个词语，再进行比较。