Microsoft

The interviewer started with a tree query optimization problem: "Given a tree of n nodes where each node has a value, answer q offline queries asking for the Lowest Common Ancestor (LCA) and the distance between any two arbitrary nodes u and v." I pointed out that walking the tree via standard DFS takes O(N) per query, leading to an O(q * N) bottleneck that times out when q and n are 10^5. I proposed Binary Lifting. The interviewer followed up: "Walk me through how you construct the jump table and how binary lifting resolves LCA in logarithmic time." I explained that we precompute `up[node][i]`, which stores the 2^i-th ancestor of `node`, using dynamic programming: `up[node][i] = up[up[node][i - 1]][i - 1]`. During a query, we first equalize the depths of u and v by lifting the deeper node by powers of 2. If they are not already equal, we lift both nodes together from the highest power of 2 down to 0, ensuring they jump only when their 2^i-th ancestors differ; the immediate parent of either node at the end is the LCA. He had me write the O(N log N) preprocessing and O(log N) query logic, verifying O(N log N) total space. He then shifted to string hashing and pattern identification: "Given a string s, find the longest duplicate substring that appears at least twice in s." I noted that generating and comparing all substrings takes O(N^3) naively, and suffix automata might be overkill if randomized hashing is allowed. I framed it as Binary Search on Substring Length paired with Rabin-Karp Rolling Hash. The interviewer challenged me: "Substring existence isn't strictly monotonic across all strings, so why does binary search work here, and how do you handle hash collisions?" I clarified that the property is monotonic with respect to length: if a duplicate substring of length L exists, any sub-slice of length L - 1 within it also appears at least twice. For a fixed length mid, we slide a window across the string, updating the rolling polynomial hash in O(1) time using `hash = (hash * base + char_in - char_out * base^mid) % MOD`. To eliminate spurious false positives from hash collisions, I implemented double hashing with two distinct large primes (e.g., 10^9 + 7 and 10^9 + 9). He approved the collision defense, confirmed the expected runtime runs in O(N log N), and watched me code the window pass. For the final challenge, he introduced a graph flow and matching scenario: "Given an n x n chessboard with some cells removed, find the maximum number of non-overlapping dominoes (1x2 tiles) that can be placed on the remaining empty squares." I explained that a greedy placement fails because placing one tile can sub-optimally block two adjacent valid slots. I recontextualized the board as a bipartite graph: each cell `(r, c)` is colored like a standard chessboard where `(r + c) % 2 == 0` forms set A (white cells) and `(r + c) % 2 == 1` forms set B (black cells). Because dominoes can only connect adjacent cells of alternating colors, finding the maximum dominoes is mathematically equivalent to finding the Maximum Bipartite Matching. The interviewer cut in: "How would you model and execute this as a network flow problem?" I showed how to add a virtual source `S` connected to all white cells with capacity 1, directed edges of capacity 1 from white cells to their adjacent valid black cells, and directed edges of capacity 1 from all black cells to a virtual sink `T`. I walked through running Dinic's Algorithm or Hopcroft-Karp, proving that on unit networks Dinic finds the max flow in O(E * sqrt(V)) time, and wrapped up by explaining how saturated edges map directly to the matched domino coordinates.