微软苏州STCA暑期实习一面+终面凉经【已感谢信】

3.15 一面（50min）

自我介绍+概念题

英文介绍（对着稿子说着说着发现截图掉了最后两段，草草收尾，逐渐紧张。。。）

介绍一下你的一个项目吧

面试官：我更希望听你从设计模式方面来讲你的项目，但你更多的是讲的算法相关的是吧，不过没关系

设计模式还有了解？

介绍一下死锁吧

C++的虚函数了解吗？virtual？多态了解吗？

【此时心想，咋这么多概念题，，我以为上来微软就算法呢。。】

那问道数学题吧，小学时候我们学过，能被三整除的数字有一个性质，就是各位的和加起来能被三整除，为什么？能证明一下吗？（讲得比较好吧，面试官说很好，然后就发链接写代码了）

算法题（给了一个在线编辑的网页链接写代码）

1. 给一个字符串，仅由空格和单词组成，只要不是空格就是单词的一部分，把单词的顺序全部反转，并保留原来的两个单词之间的空格长度。比如：" Nice to meet you! \0" -> " you! meet to Nice \0"

（题很简单，肯定是O(n)解决。但是面试官考察的更多是在问能不能优化性能（常数级别），比如要求传入的是一个char *，直接在原串的空间上把答案存进去。）（然而我为了写的顺手用了一堆string）

（还好第一题手速比较快，面试官又给了道题，不然写代码部分就惨了）

2. 给两个数组表示rank的分数，比如[6, 3, 5], [8, 4, 6]这两个，每一个代表给每个下标的page的一个打分，但是最终结果不关心打分的分数，只关心这一组page里的排名大小是否相同。写一个函数判断这两个数组代表的排名是否相同。

（问了一下要求O(n)吗？面试官说那至少有一个排序的复杂度吧。直接不想神仙离散化操作，直接开数组sort。。两个数组分别存一下val和idx后sort，然后判断两个数组的idx是否相同）

（思路没问题，问能否优化？答只sort一个数组根据idx判断另一个序列的val是否递增的，面试官说对的）

感想

写完第二道题，面试官说后面也没有别的场次面试了，和我多聊一聊吧，然后就问了些情况之类的。
当时面完觉得算法题太简单了，没展示出什么优势，然后八股答得又比较一般，结果聊到最后还蛮愉快的，感觉面试官人很随和，顺利通过一面。

3.19 二面（45min）

介绍

用英文介绍一个你做的项目吧（当时现说的，有些磕磕绊绊）
CCF-CSP是什么？CCPC是什么？

算法题（共享屏幕写代码）

题面：给一个字符串，找到其中最长的回文子串（teams里发的文字描述，还有几点别的要求，能想到的最优复杂度，测试尽量完备的测试数据等）

当时看到就有点慌（平时字符串做得比较少），，说，我知道最优解是 $O(N)$ 的manacher，但是我可能忘记了几个关键点，现场可能手写不出来。面试官说没事，他面试几百人可能现场能写的也没几个，你写你能想到的最好算法就行了。

我当时纠结了一会儿，没什么思路，感觉除了马拉车肯定都是 $n^2$ 的，面试官说，你可以写dp啊。

我又想了很久，觉得dp的复杂度似乎都没有暴力扫一遍优秀啊，如果有二维那肯定是 $n^2$ 起步，状态看着也有点小儿科。于是说我可能还是打算写暴力吧。

然后就开始写，我直接想到的暴力就是插入分隔符后扫一遍中心扩展，一边写一边在说我的思路。【面试官直接打断说，你确定你有认真读题吗？请发挥出最好水平，写出你能想到的最优复杂度的解法。】我那会儿就很慌了，说我可能dp想不到很好的定义状态的方法，没有马拉车那步关键的优化复杂度肯定是 $n^2$ 的。

于是我还是接着写中心扩展，一边写一边试图解释我的思路，【面试官再次打断，说你安静写你的好了，时间也不多了。】

写完之后，我说应该没问题了，我多出几组测试样例再试试。面试官突然说时间差不多了，你那边代码写的怎么样了？我说差不多了，我的暴力写好了。然后面试官直接说，那你还有什么问题想问我的吗？（当时心情挺复杂的，我写代码的时候看不到teams的摄像头，看他说问问题的时候似乎也在看电脑屏幕别的地方，好像完全没读我的代码之类的……）问了问题他也没回答，直接嗯嗯了两句说，你现在大三是吧？以后机会还多，拜拜。

感想

终面的体验真的很糟糕，感觉面试官后半段都不愿意理我，也不看我的代码也不听我说话，有种拳头打在棉花上的感觉，可能这就是Lead面吧（苦笑）重温了一下manacher发现当时距离正解就差一个maxRight的点拨。当时百思不得其解，难道有O(n)的dp解法我不知道吗。。

后来和同学复盘，发现LC上题解的dp就是 $n^2$ ，且空间也是 $n^2$ ，那么复杂度其实是劣于中心扩展法的，而我把中心扩展称为“暴力”，可能面试官当时以为我说的是 $n^3$ 的暴力，就完全不想听我的思路了。。思考了一下，感觉这次最主要是吃亏在了自己知道自己的算法不够优秀，就说了是暴力，下次得先说，“我有一个 $n^2$ 的算法”了。。