Microsoft

The interviewer opened with an advanced randomized search structure: "Design an in-memory ordered set that supports insert, delete, search, and lower-bound queries in O(log N) expected time without the rebalancing rotations and color bookkeeping of Red-Black or AVL trees." I proposed implementing a Skip List. The interviewer followed up: "Explain how height levels are assigned to nodes, and walk through how the search pointer descends through forward pointers." I explained that a Skip List layers forward-linked lists where level 0 contains every element and each subsequent level acts as an express lane. When inserting an element, its level is chosen via a geometric distribution by simulating coin flips (each level elevated with probability p = 0.5), capping max height at O(log N). During searches, we start at the top-left sentinel node, traverse rightward as long as the next value is strictly less than target, and drop down one level when the next value equals or exceeds target. Once at level 0, the next node directly yields the lower bound. I walked him through maintaining an `update[]` predecessor array during insertions to splice pointers across levels in O(log N) time, verifying O(log N) average query time and O(N) expected memory. He then shifted to string algorithms and periodicity analysis: "Given a string s of length n, find the longest substring that is also both a proper prefix and a proper suffix, and compute its exact number of occurrences across the entire string." I noted that KMP's Longest Prefix Suffix (LPS) array identifies candidate prefix-suffix matches, but evaluating total occurrences for each candidate naively takes O(N^2) time. I pitched Z-Algorithm paired with a prefix-frequency DP. The interviewer cut in: "Explain the Z-box invariant [L, R], and how you compute full-string occurrences of prefix-suffixes in linear time." I explained that `Z[i]` records the length of the longest substring starting at `s[i]` that matches a prefix of `s`. We maintain a bounding interval `[L, R]` representing the rightmost matched prefix substring found so far, allowing `Z[i]` within the box to be initialized from `Z[i - L]` in O(1) before expanding the right boundary linearly. A candidate prefix-suffix of length k is valid if `Z[n - k] == k`. To count occurrences, every index with `Z[i] >= k` implies a match of length k; we compute a prefix sum of frequencies over an array of Z-values in O(N) time, immediately answering the count for each valid prefix-suffix. He approved the linear-time guarantee, confirming O(N) total runtime and O(N) space. For the final challenge, he introduced a computational geometry and spatial query task: "Given n stationary points on a 2D plane, answer q range queries returning the count of points strictly inside an arbitrary axis-aligned rectangular bounding box [x1, x2] x [y1, y2] in sub-linear time per query." I pointed out that scanning all points takes O(q * N), while a 2D matrix prefix-sum grid fails when coordinates are large or floating-point values. I proposed a 2D Range Tree (a Segment Tree over x-coordinates where each internal node contains an auxiliary balanced structure or sorted array over y-coordinates) or a 2D K-d Tree. The interviewer challenged me: "Let's focus on the 2D Segment Tree with sorted arrays. Standard fractional cascading optimizes lookup, but how does the structure execute queries without it, and what are the exact space and query bounds?" I broke it down: the primary Segment Tree splits points by x-coordinates; each node covers an x-range and stores a sorted vector of all y-coordinates falling in that range. To query `[x1, x2] x [y1, y2]`, the primary tree decomposes `[x1, x2]` into at most O(log N) canonical nodes. Inside each canonical node, we run two binary searches (`std::lower_bound` and `std::upper_bound`) over its pre-sorted y-array to count points in `[y1, y2]` in O(log N) time. This results in O(log^2 N) query time. Because each point appears in exactly one node per level of the primary tree (depth log N), the total memory footprint is strictly bounded to O(N log N).