Microsoft

The interviewer opened with an advanced palindrome and string-structure challenge: "Given a string s of length n, dynamically compute the number of distinct palindromic substrings and report the maximum length of a palindrome ending at each position in O(n) total time." I noted that running Manacher's Algorithm isolates maximal palindromic radii centered at each character, but counting distinct palindromic substrings requires deduplicating identical palindromes across different centers, which naively incurs an O(n^2) hash-map bottleneck. I proposed building an Eertree (Palindromic Tree). The interviewer followed up: "Walk me through the auxiliary roots of the tree, how failure/suffix links are formed, and why the total number of states is strictly bounded by n." I explained that the structure maintains two roots: an imaginary root with length -1 and an empty-string root with length 0. Every other node represents a unique palindromic substring formed by wrapping its parent's palindrome with a matching character `c` on both flanks (`c + parent + c`). Suffix links point to the longest proper palindromic suffix of the node's string. When appending a character to the text stream, we traverse suffix links starting from the previous character's longest palindromic suffix until finding an ancestor whose preceding character matches the current one. Because adding a single character can introduce at most one brand-new distinct palindrome, the tree allocates at most n nodes. He had me code the transition state updates and verified strict O(n) time and O(n * alphabet) memory. He then shifted to a probabilistic stream-processing scenario: "You are monitoring an infinite, high-volume stream of integer events; design a fixed-size memory data structure that can estimate the frequency of any incoming query key in O(1) time while guaranteeing that estimates never underestimate the true count." I explained that an exact hash table grows linearly with unique keys and exhausts memory, whereas Bloom filters only support set membership without tracking counts. I pitched the Count-Min Sketch. The interviewer cut in: "How do you select hash functions to guarantee error bounds, and what mathematical theorem proves the maximum error limit?" I explained that we allocate a 2D array of counters with depth d and width w, using d independent pairwise-independent hash functions. For every key insertion, we hash the key with all d functions and increment the corresponding counter in each row by 1. For a point query, we return the minimum value among the d hashed positions (`min_i table[i][hash_i(key)]`), since hash collisions can only artificially inflate counts (ensuring zero false negatives or underestimates). By setting width $w = \lceil e / \epsilon \rceil$ and depth $d = \lceil \ln(1 / \delta) \rceil$, Markov's and Chebyshev's inequalities guarantee that the estimated frequency exceeds the true frequency by at most $\epsilon N$ with probability at least $1 - \delta$, using tiny constant space. He verified the collision analysis and approved the fixed-memory sketch. For the final challenge, he introduced a graph match-and-order optimization problem: "Given an undirected bipartite graph where each edge has a positive integer weight, find a maximum-weight perfect matching in polynomial time without using an exponential backtracking search." I pointed out that unweighted bipartite matching uses Hopcroft-Karp in O(E * sqrt(V)), but edge weights require dual LP optimization to avoid brute-forcing the combinatorial permutation space. I proposed the Hungarian Algorithm (Kuhn-Munkres Algorithm). The interviewer challenged me: "Define dual vertex potentials (feasible labeling), explain the concept of the equality subgraph, and show how potential adjustments force augmenting paths to emerge." I explained that we assign potentials $u[i]$ to left vertices and $v[j]$ to right vertices such that $u[i] + v[j] \ge \text{weight}(i, j)$ across all edges. The equality subgraph retains only tight edges where $u[i] + v[j] == \text{weight}(i, j)$, and any perfect matching in this equality subgraph is guaranteed by the duality theorem to achieve maximum total weight. If an augmenting path cannot be found via alternating trees, we compute the minimum slack $\Delta = \min(u[i] + v[j] - \text{weight}(i, j))$ among all edges crossing from visited left nodes to unvisited right nodes, subtract $\Delta$ from visited left potentials, and add $\Delta$ to visited right potentials. This invariant strictly introduces at least one new tight edge without violating feasibility. He watched me trace an alternating path on a 3x3 cost matrix, confirming that using slack arrays optimizes the runtime to strict $O(V^3)$ time and $O(V^2)$ space.