微软上海C+AI 2022年暑期实习一二三面面经
更新：3.5官网的Action Center上的status变为了completed。3.8邮件收到了offer。
------------------------------------------------------------------------
让我简述了一下简历里基于Raft和LSM-Tree的分布式KV存储引擎开发项目经历，遇到了什么问题？怎么解决的？LSM-Tree和B+Tree的区别？如果内存crash了，我有什么机制保证可以做recovery？
算法题1：BST迭代器
算法题2：给定一定的金额和一系列房子，要求尽最大可能买房子，使得房子总价值最大。解法：如果要求买房连续，则是滑动窗口问题，若是不连续，则是0-1背包问题。
2.22二面：
问了一下去年的实习经历。
算法题1：求两相交链表的第一个相交节点。follow up：如果有一个链表成环，或者两个链表都成环，该怎么办？follow up不用具体写码，说出合理解决思路即可。
算法题2：设计一个栈，支持push，pop，和对栈底m个节点加n的操作。follow up：第三个对栈底m个节点加n的操作要求O(1)实现，思路是前缀和的逆运算差分数组。
2.25三面：
问了一下去年的实习经历。
Q：为什么需要token校验？简述一个你能想到的经典的需要token校验的场景
A：我说的是用户注册登录，然后巴拉巴拉说了整个过程。
Q：对密码进行加密的方式是用怎样的方式？
A：我说hash，这样无法还原，从而无法破译。
Q：单模块进行token校验的缺点？
A：1. 单点故障问题；2. 流量瓶颈问题。
Q：解决办法？
A：将单机模块分布式化，利用raft或者paxos协议，并采用一定的优化使其可以水平扩展。
Q：用户拿着token去访问storage资源，那么相关模块怎么确认用户的token是valid的？
A：我说可以采用类似于网络安全里的非对称加密方式，用一个第三方可信机构（类似CA）来给用户当前的token上保证，形成类似于证书的凭证。用户拿着这个可信凭证去访问资源，相关模块就可以认为该凭证是可信的。
第三面没有算法题，纯系统设计。三面面试官都是Azure Storage组，如果有幸能过，应该进的是Storage组。求好运～
#2022春招##实习##面经##微软#
