Microsoft

The interviewer asked me to design a system to find the running median of numbers streamed across distributed machines without a single bottleneck; I began with the two-heap approach for a single node, and when they pushed for distributed scale, we pivoted to an approximate quantile tracking strategy using a T-Digest data structure to bound error while processing millions of events per second. I was presented with a grid representing an integrated circuit layout where metal pins must be connected using orthogonal wire segments, and the interviewer asked me to find the minimum wire cost to connect all pins without overlapping obstacles; I modeled this as finding a Rectilinear Steiner Minimum Tree and walked through an $A^*$ pathfinding heuristic with Manhattan distance to handle obstacle routing sequentially. The interviewer framed a problem around an in-memory database index where write queries update key-value pairs concurrently while read queries request historical snapshots at timestamp t; I walked through implementing a persistent balanced search tree (Treap) using path-copying to achieve $O(\log N)$ updates while preserving full historical immutability across past versions.