微软 SDE Intern 面经｜Microsoft SDE 两轮面经｜微软实习

面试结构

两轮，每轮 45 分钟，中间休息 15 分钟。结构大致是：

• 前 15 分钟：行为问题
• 中间 20 分钟：做题
• 最后 5 分钟：自由提问

和 Amazon 不同，微软的流程没那么死板，面试官之间差别很大：有的直接跳过行为问题进入代码题，有的喜欢在代码题里加很多 follow-up。

行为问题不会像 Amazon 那样「拷打」，主要了解你在团队协作、解决问题方面的经验，准备几段 STAR 框架的故事就够了，也不会做技术深挖。

第一轮：Key-Value Store（Azure 存储背景）

题目

实现一个简化的 Key-Value Store，支持：

• put(key, value)
• get(key)
• getWithPrefix(prefix)：返回所有以 prefix 开头的 key-value

思路演进

1. HashMap：put / get 都是 O(1)，最直观；但 getWithPrefix 要遍历所有 key，O(n)，大规模下不够高效。
2. Trie 或有序结构（TreeMap）：按前缀组织 key，前缀查询只需要访问相关的 key。

class TrieNode:
    __slots__ = ("children", "has_value", "value")

    def __init__(self):
        self.children = {}
        self.has_value = False
        self.value = None

class KVStore:
    def __init__(self):
        self.root = TrieNode()

    def put(self, key, value):
        node = self.root
        for ch in key:
            node = node.children.setdefault(ch, TrieNode())
        node.has_value, node.value = True, value

    def get(self, key):
        node = self._find(key)
        return node.value if node and node.has_value else None

    def get_with_prefix(self, prefix):
        """返回 {key: value}，复杂度 O(前缀长度 + 匹配到的 key 的总长度)"""
        node, out = self._find(prefix), {}
        stack = [(node, prefix)] if node else []
        while stack:
            cur, path = stack.pop()
            if cur.has_value:
                out[path] = cur.value
            for ch, child in cur.children.items():
                stack.append((child, path + ch))
        return out

    def _find(self, key):
        node = self.root
        for ch in key:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

用 has_value 标记而不是检查 value is None，这样值本身可以是 None。

扩展性讨论

面试官比较在意能否从基础实现逐步扩展到可扩展的设计，接着讨论了：

• 数据量非常大时，分布式环境下如何存储、如何分片（比如按 key 的 hash 分片；要支持前缀查询的话，按 key 范围分片更合适）
• 一致性怎么处理
• 高频访问场景下的缓存优化

代码写到基础版本就停下了，没有真正跑测试，直接进入设计和扩展性的问答。

第二轮：Rate Limiter（Bing / Teams 背景）

题目

实现一个简化的 Rate Limiter，接口是 allowRequest(userId, timestamp)：如果用户在某个时间窗口内的请求数超过阈值，返回 false 拒绝；否则返回 true。

思路演进

1. 时间戳列表：为每个用户维护请求时间戳列表，新请求来时先清理过期时间戳，再看剩余数量是否超过阈值。简单，但列表很大时清理开销是 O(n)。
2. 滑动窗口队列：用双端队列按时间顺序存时间戳，过期的只会出现在队头，每个时间戳最多入队、出队各一次，均摊 O(1)。
3. 令牌桶：每个用户只存「令牌数 + 上次补充时间」，严格 O(1)、内存 O(1)，还允许一定的突发流量。

from collections import defaultdict, deque

class SlidingWindowLimiter:
    """任意 window 秒内最多 limit 个请求（滑动窗口日志）"""
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.logs = defaultdict(deque)

    def allow_request(self, user_id, ts):
        q = self.logs[user_id]
        while q and q[0] <= ts - self.window:   # 清理窗口外的请求
            q.popleft()
        if len(q) >= self.limit:
            return False
        q.append(ts)
        return True

class TokenBucketLimiter:
    """容量 capacity，每秒补充 rate 个令牌；每个请求消耗 1 个令牌"""
    def __init__(self, capacity, rate):
        self.capacity, self.rate = capacity, rate
        self.state = {}                          # user -> (tokens, last_ts)

    def allow_request(self, user_id, ts):
        tokens, last = self.state.get(user_id, (self.capacity, ts))
        tokens = min(self.capacity, tokens + (ts - last) * self.rate)
        if tokens >= 1:
            self.state[user_id] = (tokens - 1, ts)
            return True
        self.state[user_id] = (tokens, ts)
        return False

不同算法的优缺点（面试官重点追问）

算法	优点	缺点
固定窗口计数	实现最简单，内存小	窗口边界处可能放过两倍流量
滑动窗口日志	精确	要存每个请求的时间戳，内存随请求数增长
令牌桶	O(1) 时间和内存，允许合理突发	突发量要通过容量参数控制，计数不如日志精确

最后 QA 聊了很多，超时五分钟才结束。

小总结

• 两轮都结合了微软的业务背景（Azure 存储、Bing / Teams），但本质还是常规的数据结构和算法题。
• 题目比较开放，可以通过和面试官的互动逐步明确范围。
• 微软更看重你能否在有限时间里先写出清晰的基础解法，再通过讨论展示对扩展性和复杂度优化的思考。