Microsoft

The interviewer opened with a dynamic range maintenance problem: "Given an array of n elements, process a stream of two types of operations: update a range [L, R] by adding a value x, and query the sum of elements in a range [L, R]." I pointed out that a simple array takes O(N) per update, while a standard Segment Tree without lazy mechanics takes O(N log N) for range updates because every leaf must be modified. I proposed a Segment Tree with Lazy Propagation. The interviewer followed up: "Walk me through how a lazy tag is pushed down, and what happens when an update partially overlaps an existing unpropagated tag?" I explained that each tree node maintains both `tree_sum` and a `lazy` accumulator; when a range update completely covers a node's segment, we immediately update that node's sum by `lazy_val * segment_length`, append `lazy_val` to its lazy tag, and return without descending further. If an operation later partially hits that node, we first 'push down' the pending tag to its two children, clear the current node's tag, and then recursively recurse into both halves. He had me code the `push_down` and `update_range` helpers, verifying that both range updates and sum queries run in strict O(log N) time and O(N) space. He next shifted to an offline array query challenge: "Given an integer array of size n and q offline queries asking for the number of distinct elements in subarray [L, R], answer all queries efficiently." I noted that answering each query naively using a hash set takes O(q * N), which TLEs when n and q reach 10^5. I proposed Mo's Algorithm (Square Root Decomposition). The interviewer cut in: "How does sorting queries by blocks reduce total pointer movement, and what is your comparator function?" I explained that we partition the array into blocks of size B = sqrt(N) and sort queries primarily by `L / B` (block index) and secondarily by `R`. By using Hilbert curve ordering or alternating the sort direction of `R` (ascending on even blocks, descending on odd blocks), the right pointer moves monotonically across each block while the left pointer shifts at most O(sqrt(N)) between consecutive queries. I demonstrated maintaining a global frequency array and a `distinct_count` scalar, adding or removing elements in O(1) as the window boundaries shift. He had me trace the pointer convergence, proving an optimal total runtime of O((N + q) * sqrt(N)) with O(N + q) auxiliary storage. For the final problem, he introduced a graph bridge-detection problem: "Given a connected undirected network of servers, identify all critical connections (bridges) whose failure would disconnect the network." I ruled out the brute-force approach of removing each edge one by one and running BFS/DFS (which takes O(E * (V + E))). I proposed Tarjan's Bridge-Finding Algorithm using Depth-First Search. The interviewer challenged me: "Define discovery time and low-link values, and state the exact invariant that flags an edge as a bridge." I explained that during DFS, `disc[u]` records the timestamp when node u is first reached, and `low[u]` records the earliest discovery time reachable from u via its subtree and at most one back-edge. When exploring an edge (u, v): if v is already visited and not the immediate parent, we update `low[u] = min(low[u], disc[v])` (a back-edge). If v is unvisited, we recursively visit v, update `low[u] = min(low[u], low[v])`, and check the bridge invariant: if `low[v] > disc[u]`, it means the subtree rooted at v has no back-edge reaching u or any of u's ancestors. Therefore, edge (u, v) is a critical bridge. He watched me implement the DFS traversal, verified the parent-skipping logic, and proved the algorithm runs in strict linear O(V + E) time and O(V) stack space.