Microsoft

The interviewer opened with a dynamic graph connectivity scenario: "You have an empty network of n computers; process an incoming stream of connections between pairs and queries asking if two computers are in the same network, where some connections can be redundant." I immediately ruled out running BFS/DFS per query (which blows up to O(Q * (V + E))) and proposed Disjoint Set Union (DSU). The interviewer followed up: "What specific optimizations prevent the tree from degrading into a linear linked list, and what is the resulting time complexity?" I explained the two essential mechanics: path compression (flattening the tree during `find` operations so child nodes point directly to the representative root) and union by rank/size (attaching the shallower tree under the deeper tree to minimize tree height). Combined, these ensure that any sequence of m operations across n elements runs in near-linear O(m * alpha(n)) time, where alpha is the extremely slow-growing inverse Ackermann function (effectively <= 4 for all realistic inputs). He had me code the class and dry-ran an edge case with self-loops. He then shifted to a divide-and-conquer binary search challenge: "Given an integer array nums and an integer m, split the array into m non-empty contiguous subarrays such that the largest sum among these subarrays is minimized." I pointed out that evaluating all combination splits using recursion/DP takes O(m * N^2) time, which chokes on large constraints. I recontextualized the problem as Binary Search on Answer. The interviewer cut in: "What defines your search space boundaries, and what is your monotonic validation predicate?" I explained that the search space is bounded by `low = max(nums)` (a single element cannot be split further) and `high = sum(nums)` (a single partition containing the entire array). For a candidate maximum sum `mid`, we run a greedy O(N) pass accumulating elements sequentially; whenever adding a number exceeds `mid`, we trigger a new partition. If the total partitions needed are <= m, `mid` is achievable and we pull `high = mid`; otherwise, `mid` is too small and we push `low = mid + 1`. I coded the loop, proved the O(N * log(sum - max)) time bound, and verified pointer convergence without infinite loops. For the final challenge, he introduced a coordinate compression and interval geometry problem: "Given an array of rectangles on a 2D plane aligned with the axes, compute the total area covered by all rectangles, ensuring overlapping regions are counted only once." I explained that discrete matrix grid mapping runs out of memory when coordinates reach 10^9. I proposed the Line Sweep Algorithm paired with a Segment Tree. The interviewer followed up: "Walk me through how vertical edges are ingested and how the active vertical length is maintained without re-scanning." I broke it down: we decompose each rectangle into two vertical boundary events—an entry event at `x1` with weight +1 and an exit event at `x2` with weight -1, spanning vertical interval `[y1, y2]`. We sort all x-events chronologically. As the vertical sweep-line advances from `x_prev` to `x_curr`, the incremental added area is `(x_curr - x_prev) * total_active_y_length`. To maintain the active y-length dynamically in O(log N) rather than an O(N) linear sweep, we map the unique y-coordinates into a Segment Tree where nodes maintain the total length covered with coverage count `cnt > 0`. He approved the architecture, had me trace two overlapping rectangles, and verified the O(N log N) runtime and O(N) space guarantee.