微软 STCA SWE 面经

一面（3.9）：
这一面是中文面试，面试官让我先英文自我介绍，然后问了些简单的口语问题，包括简历里的项目。

.--然后直接做算法题：

• 实现 atoi() 字符串转数字
• 动态规划“高楼扔鸡蛋”问题
  

第一题要注意这几个测试用例：

• 包含非法字符，返回 error 或者 0
• 要考虑正负号
• 要考虑溢出的情况。直接按照字典序，比较输入字符串和 TMin、TMax 的字符串就可以了，不需要在转换过程中判断是否溢出
  

第二道题直接搜索 labuladong 的同名文章。说实话我感觉这道题目很难，没见过就想不出来。

二面（3.13）：
上来直接做题：

• 两棵二叉树，判断树 A 是否包含树 B（值相同，不是指针相同）
• 如何实现一个 Google 搜索的自动建议系统？
  

第二题其实就是前缀树，但是面试官会让你考虑实际场景有哪些问题，然后要求你不断优化。我首先实现了简单的前缀树：

• 前缀树的每个节点保存 26 个子节点，表示下一个字符可能是 a-z
• 搜索过程：找到最长匹配前缀的树节点，然后遍历该节点的子树，找到所有单词
  

然后面试官问我还可以怎么优化。这里主要是自己想+和面试官沟通的过程，向面试官要提示：

• 用户输入的字符不单是 26 个英文字符，可以是任意字符，因此前缀树的每个节点里应当保存 map<char,node> 而不是 node[26]
• 某个前缀可能频繁地被检索，如何优化？（在每个节点里缓存当前节点下面的所有单词）
• 进一步优化：上一步可以缓存成指向节点的指针，而不是单词，能够节省空间
  

然后面试官又问，实际场景中可能遇到哪些问题？我想的是可以对建议结果进行加权排序，排序依据有匹配度、点击率、用户反馈（赞、踩）等。后来查了一下，这里还有很多可以优化的点，比如：

• 剔除一些结果：性别歧视、恶心的、危险的、垃圾
• 更新前缀树：先离线更新前缀树，然后加载到内存里，直接替换指针
• 前缀树可能十分大，内存中加载不下，此时需要将其拆分到多台机器上
  

根据以往面经来看，微软的算法题难度算是 LeetCode 中等偏上。不过我的这些题目可能比较特殊，一面的题目算是 Hard 了，二面的题目比较综合。算是个人运气好吧，做出来了。

请问楼主是面的北京微软吗

楼主一般面完多久出结果？我这面完一周了，hr不回信

User777 发表于 2020-6-15 13:52
请问楼主是面的北京微软吗

是的，STCA

hjy 发表于 2020-9-2 11:17
楼主一般面完多久出结果？我这面完一周了，hr不回信

我是实习生，一个月后才通知的。你是秋招吗？秋招的话分组，现在实习生转生的结果也还没出，所以秋招的应该会月底或者国庆后了吧

这也太难了。。。