微软暑期实习面经分享

#微软-STCA-北京
## 3.1 投简历
内推，简历没过筛，没有获得免笔试资格
## 3.25 笔试
三道题，第一题过了，第二题过了4个case，一共10个，第三个没看。具体题目在牛客上可以找到。
## 4.1 hr收集面试时间，约定4.8和4.9两天集中面试
## 4.8 一面
自我介绍大概5分钟，简单聊了项目
给了个链接，白板写代码
算法题：
1. 字符串反转：字符串中用空格分隔每个单词，空格数量至少一个，输出反转后的字符串，要求反转后单词之间的数量与之前不变。
（先交流思路，然后写代码，没问题后问测试用例怎么写，有几类。测试用例没怎么了解过，面试官提示说要考考虑非法输入和合法输入，保证非法输入下程序不会崩溃才可以）
2. 机器人走棋盘：一个m*n的棋盘，机器人从左上出发，目的地是右下，每次只能向右或者向下，格子中为0表示机器人可以通过，为1表示障碍，机器人不能通过。问机器人是否可以成功从左上出发到达右下。
（交流思路，写代码，没问题后面试官又拓展，让求机器人从左上到右下的路径条数，在上题代码上修改。改完后问除了递归解法，还有没有其他方法，说了dp，面试结束）

## 4.10 二面
（本来是4.9二面，hr临时通知面试官有事，约明天或者之后重新发面试链接）
算法：求无序数组中前K个最大值。
用最小堆求了前K个，面试官要求不用优先级队列，自己写一个最小堆，不会
转而用冒泡写了另一种解法，面试官要求优化时间复杂度，一次遍历，又回到了最小堆
面试官拓展说，求海量数据中前K大元素，内存空间不足。回答了桶排序，面试官要写出代码，因为思路本身就不清晰，代码没写出来时间就到了，估计没戏了。
## 4.16 三面
自我介绍，讲项目（大概半小时），然后做题。
算法：（1）输入excel中一个列号的字符串（e.g. “AX”），输出是第几列。
（2）输入一个字符串，输出去掉所有空格后的字符串，要求不使用额外空间。
（感觉整体比较简单，本来以为微软面试就结束了，结果hr小姐姐来电话约下周面试时间，下周还有一次，希望好运呀）
## 4.21 四面
自我介绍，聊项目，做题
算法：（1）逆时针反转矩阵：先垂直折叠翻转，再对角线翻转，两次交换
（2）二叉树中序遍历下一个节点：这个刚开始没理清思路（虽然之前做过），跟面试官说了两遍错误的思路，第三次才说清楚，然后写代码。
还有时间，面试官提出第一题能不能一次交换完成反转，没思路，面试官给了提示，类似于剑指offer上逆时针遍历矩阵的思想，从外围向里依次旋转，写代码。代码写出了外层循环，中间具体交换没写，时间到了，结束了。
#微软北京实习面经##微软##实习##软件研发工程师##面经#