Microsoft SDE Intern Interview | Two-Round Microsoft SDE Recap | Microsoft Internship

Structure

Two rounds, 45 minutes each, with a 15-minute break. Roughly:

• First 15 minutes: behavioral
• Middle 20 minutes: coding
• Last 5 minutes: open Q&A

Unlike Amazon, Microsoft's process is less rigid and interviewers vary a lot: some skip behavioral and go straight to coding, others like adding lots of follow-ups to the coding question.

Behavioral questions aren't a grilling like at Amazon. They mainly want to know about your teamwork and problem-solving experience — a few STAR stories are enough, and there's no technical deep dive.

Round 1: Key-value store (Azure storage context)

Problem

Implement a simplified key-value store supporting:

• put(key, value)
• get(key)
• getWithPrefix(prefix): return every key-value pair whose key starts with the prefix

How the solution evolved

1. HashMap: put / get are O(1) and the most intuitive, but getWithPrefix scans every key — O(n), not efficient enough at scale.
2. Trie or an ordered structure (TreeMap): organize keys by prefix so a prefix query only touches the relevant keys.

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):
        """Returns {key: value}; O(prefix length + total length of matched keys)"""
        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

Using a has_value flag instead of checking value is None lets the value itself be None.

Scalability discussion

The interviewer cared about evolving from a basic implementation to a scalable design. We discussed:

• How to store and shard a very large dataset in a distributed setup (e.g. shard by key hash; to support prefix queries, range-based sharding by key works better)
• How to handle consistency
• Caching for high-frequency access

We stopped at a basic implementation without running tests and moved on to design and scalability Q&A.

Round 2: Rate limiter (Bing / Teams context)

Problem

Implement a simplified rate limiter with the interface allowRequest(userId, timestamp): if a user exceeds the threshold within a time window, return false to reject; otherwise return true.

How the solution evolved

1. Timestamp list: keep each user's request timestamps; on a new request, drop expired ones and check whether the remaining count exceeds the threshold. Simple, but cleanup is O(n) when the list is large.
2. Sliding-window queue: store timestamps in time order in a deque; expired ones only appear at the front, and each timestamp is pushed and popped at most once — amortized O(1).
3. Token bucket: each user stores only "tokens + last refill time" — strict O(1) time and O(1) memory — and allows some burst traffic.

from collections import defaultdict, deque

class SlidingWindowLimiter:
    """At most `limit` requests in any `window` seconds (sliding-window log)"""
    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:   # drop requests outside the window
            q.popleft()
        if len(q) >= self.limit:
            return False
        q.append(ts)
        return True

class TokenBucketLimiter:
    """Bucket of size `capacity`, refilled at `rate` tokens per second; each request costs 1 token"""
    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

Trade-offs between algorithms (the interviewer's main follow-up)

Algorithm	Pros	Cons
Fixed-window counter	Simplest to implement, little memory	Can let through up to twice the limit around window boundaries
Sliding-window log	Exact	Stores a timestamp per request; memory grows with request volume
Token bucket	O(1) time and memory, allows reasonable bursts	Burst size is controlled by the capacity parameter; less exact than a log

The final Q&A went long and ran five minutes over.

Takeaways

• Both rounds were framed around Microsoft products (Azure storage, Bing / Teams), but at heart they were standard data structure and algorithm questions.
• The questions were open-ended; the scope became clear through interaction with the interviewer.
• Microsoft cares about whether you can write a clear basic solution first in limited time, then show your thinking on scalability and complexity optimization through discussion.