微软苏州SWE一二三面过经

STCA是一二面平行，过了一个就进lead面。

一面

1.英文自我介绍
2.问了几个JAVA基础问题
3.算法题：设计一个数据结构以O(1)时间复杂度实现4个方法：
void addWordOnce(string word);
void removeWordOnce(string word);
int GetMaxOccurredWord();
int GetMinOccurredWord();
一面题还是比较难的，说了自己的错误思路后，在面试官引导下有了正确（maybe）思路，写了变量定义，第一个方法刚写了两行就断开了白板连接，并且科学上网也连不上。。就口述实现，细节比较繁琐，不写成代码比较容易漏掉情况。一面挂，一是题确实难，二是连不上只能口述也太难受了。。

二面

1.斐波那契数列分析时空间复杂度，问我系统栈压栈顺序，这块我说不太确定，面试官人很好说我下去可以了解一下。
2.拓扑排序：题目类似LC课程表，想好之后把思路说了下，面试官说思路对的，开始写的不是最优，问怎么优化，然后想了一会说出了优化思路，感觉MS比较重视follow up，而不是一上来写最优解。
3.最长递增子序列
都是原题，天不绝我。。

三面

lead面
1.中文自我介绍
2.实习项目问了比较久，比较细，问有没有可以优化的地方
3.JVM垃圾回收一些问题
4.Linux命令 shell语法的一些问题（项目有用到）
5.算法：最大子序和（子数组）
easy题，但是比较经典。
这个我刚开始比较紧张，想着区间dp，说了一下，然后复杂度是O（n2）,后面我说我想下效率更高的解法，他说不用返回子数组，只要最大和，我就想到了一维dp，就写了，写完我看可以压缩到O（1），就边说边改。白板写代码corner cases一定要注意，最后还让我写几个test cases。写完面试官很满意。

总结

感觉微软是比较看重你思考优化的过程，思路一定先说出来，面试官认可了再写代码，写完也可以自己写一下test cases。
二三面手撕代码都是原题，只能说我欧气太足了哈哈哈，三面中午面完，下午五点前就出结果了，MS效率还是很高的，HR说三面过了后面就offer审批了。

PS: MS面试属实玄学，我每次看到大佬们的面经都看的怀疑人生，只能说多刷题多总结，不要期望每次都碰到原题，提高自己的算法思维能力才是王道。
PPS: Luck Game