北京微软STCA开发一二面记录

两面连续的，微软这边应该是平行面，感觉可能结果不太好。希望能有奇迹吧。

4月29日第一面：

自我介绍。
因为没什么项目就简单问了几句。
接下来是编程，分享屏幕之后我在记事本里面写的。
第一题是非递归中序遍历二叉树，最开始手滑写成队列了，写了一阵全删了改成栈，没有测试，写完面试官直接把代码拷走了，面试结束之后我手动测了一下，这题是Bug Free。
第二题是LeetCode 26，三数之和，写完之后也是直接拷走代码，面试结束之后调了一下有三个Bug。

4月30日第二面：

自我介绍。问了一些个人情况有关的内容。
这次的编程题是给了一个类似LeetCode Playground的平台，可以在线运行。

第一题是给定一个数组，求数组当中的峰值，所谓峰值就是这个数比他左右两边的数都大。
确定了边界条件和要求之后，最开始打算写一个O(N)的算法，写了不到半分钟面试官说写尽可能快，我就换了一个分治的方法。
面试官问我时间复杂度，然后说不考虑相等的情况下能不能更快，我说可以写一个确定性的对数级别算法。
写完之后自己出样例调试，这题是Bug Free

第二题是给定一组用户和每个用户的好友列表，输出每个用户之间的共同好友的关系。比如A与B有3个共同好友，就输出A,B: 3
我问有多少数据量，面试官说可以认为数据量极大，一次性读不进来，可以用中间文件存储结果。
最开始没想到好方法，经过面试官提示说每行读一遍就行，我立刻想出了解决方法，这题面试官没让我写代码。

第三题是给定一组数字，然后把数字分为三组，其中两组总和相等，要求第三组的总和尽可能小。
面试官一开始就提示是动态规划，我说了一个最朴素的暴力解，面试官让我想想更快的解法，想了好几分钟没想到，面试官让我先写暴力解，没测试，说代码应该没问题，然后面试官告诉我了一个更快的方法。

最后问我有什么问题，随便问了几句面试就结束了，让我等后续通知。