Microsoft SWE New Grad面试题和答案
New Grad Interview Questions & Answers
微软SWE New Grad面试经验，刚出炉的！
说实话，准备微软的面试真的是一场持久战。从海投到最后拿到Offer，中间的每一步都踩过不少坑。今天就来复盘一下，给还在路上的小伙伴们一些参考，希望能帮大家少走点弯路。
我的背景是美硕CS，刷了大概300道LC题，主攻Array, String, Tree和DP。微软的面试流程相对固定，对于New Grad来说，基本就是OA -> Virtual Onsite。
【OA阶段】
微软的OA通常是在Codility或者HackerRank上进行，时长大概60-90分钟，2-3道Coding题。难度基本在LC Easy到Medium之间，偶尔会有一道比较tricky的。我当时遇到的两道题，感觉就是考察基本功。
第一道题：判断字符串是否是半交替的
给一个只包含'a'和'b'的字符串，如果一个字符串中没有三个连续相同的字符，就称之为半交替字符串。比如"aabab"就是，但"aaab"就不是。写一个function判断给定的字符串S是不是半交 替字符串。
解题思路： 这道题不难，直接遍历一遍String，检查S[i], S[i-1], S[i-2]是不是都相等就行。Time Complexity是O(n)，Space Complexity是O(1)。属于送分题，但要注意边界条件，比如字符串长度小于3的情况。
第二道题：给一个Array，找出和为0的最长子数组的长度
这题稍微有点绕，我当时卡了大概10分钟。题目是给一个只包含-1和1的Array，让你找到一个和为0的连续子数组，返回这个子数组的最大长度。
解题思路： 这题可以用HashMap来做。思路是计算从头开始的累积和，用一个HashMap来存每个累积和第一次出现的位置。如果当前的累积和在HashMap里已经存在了，说明从那个位置到当前位置的子数组和为0。我们就算一下这个长度，然后和当前的最大长度比较更新一下。血泪教训，一定要把初始情况（累积和为0在-1位置）放进HashMap里，不然会漏掉从头开始就是和为0的子数组。
第三道题：设计一个LRU Cache
这道题算是LC Medium里的经典了，也是面试高频题。要求实现一个LRU (Least Recently Used) Cache，支持get和put两个操作。当Cache满了之后，要先淘汰最久没被用过的数据。
解题思路： 标准的解法是结合用一个Doubly Linked List和一个HashMap。HashMap存key和Node的映射，这样可以O(1)时间找到Node。Doubly Linked List用来维护Node的顺序，最近用过的放头部，最久没用的放尾部。每次get或者put一个已有的key，都要把它移到链表头部。put一个新的key时，如果满了，就删掉尾部节点，然后把新节点加到头部。这个数据结构操作起来有点繁琐，写的时候一定要思路清晰，不然很容易出错。
【Virtual Onsite】
如果OA顺利通过，恭喜你进入下一轮，也是最关键的一轮：Virtual Onsite。通常是连续的3-4轮面试，每轮45-60分钟，中间会有短暂休息。面试官都是组里的Engineer或者Manager。
Coding Round： Onsite的Coding难度会比OA高一些，通常是LC Medium到Hard。题目类型也更广，Tree和Graph的题出现概率很高。我当时被问到了一道关于Binary Tree的题，要求找到两个节点的Lowest Common Ancestor。除了写出代码，面试官还会追问Time Complexity和Space Complexity，以及各种edge Case的处理。沟通非常重要，一定要边想边说，让面试官知道你的思路。
System Design Round： New Grad的System Design通常不会太难，更偏向于概念性的讨论。比如我被问到如何设计一个TinyURL服务。这种问题没有标准答案，关键是展现你的思考过程。可以从API设计开始，然后讨论如何生成短URL，如何存储映射关系，如何处理高并发的读写请求等等。能提到用什么Database，要不要用Cache，怎么做Load Balancing这些点，就很加分了。
Behavioral Question Round：
千万别小看BQ！微软非常看重culture fit。准备BQ的最好方法就是STAR原则（Situation, Task, Action, Result）。提前准备几个你做过的项目或者实习经历的例子，把它们套进STAR框架里。常见的BQ问题有：
- Tell me about a time you had a conflict with a teammate.
- Tell me about a challenging Project you worked on.
- Why Microsoft?
说实话，BQ环节的回答要真诚，不要背稿子。可以适当展示你的热情和对技术的热爱。我当时就聊到了自己对微软Azure云服务的兴趣，以及做过的一些相关小项目，感觉面试官还挺满意的。
总的来说，微软的面试体验还是不错的，面试官都很nice。准备过程虽然辛苦，但也是一个快速提升自己的过程。希望我的这点经验能帮到大家。有什么问题可以留言问我，看到都会回。
#微软 #Microsoft #面试经验 #求职 #北美求职 #CS #SoftwareEngineer #NewGrad #面经 #OA
