Microsoft

The interviewer opened with a topological dependency problem on trees: "Given a tree of n nodes where you are allowed to delete nodes only if they are leaves, repeatedly peel off leaves layer by layer until you isolate the tree's center; return all minimum height tree (MHT) roots." I pointed out that running a BFS/DFS from every single node to find max depths takes O(N^2) time. I reframed the problem as finding the graph centroid: analogous to peeling an onion, the centroid(s) must be the innermost nodes, and mathematically a tree has at most two centroids. The interviewer followed up: "Walk me through how you transition inward and what your termination condition is." I framed it as a Reverse Kahn's Algorithm / Inward BFS: compute node degrees, push all degree-1 nodes (leaves) into a queue, and strip them layer by layer while decrementing adjacent neighbor degrees. The loop halts when remaining nodes count is <= 2. He had me trace a line graph of 4 nodes, verify that the queue flushes in strict O(N) time and O(N) space, and confirm that roots are returned without lingering cycles. He then transitioned to a bit-level state optimization challenge: "Given an undirected weighted graph with n nodes (where n <= 15), find the minimum cost to visit all nodes starting and ending at node 0." I recognized this immediately as the Traveling Salesperson Problem (TSP) and dismissed standard recursion due to O(N!) exponential blowup. I proposed dynamic programming with Bitmasking. The interviewer challenged me: "Define your DP state representation, and what prevents you from re-visiting intermediate subsets inefficiently?" I defined `dp[mask][u]` as the minimum cost to visit the exact set of nodes marked by the bits in `mask`, ending at current node `u`. A bitwise state of `(1 << n) - 1` indicates all nodes have been visited. For state transitions, from current vertex `u`, we iterate over all unvisited neighbors `v` where `(mask & (1 << v)) == 0`, relaxing the new state: `dp[mask | (1 << v)][v] = min(dp[mask | (1 << v)][v], dp[mask][u] + cost[u][v])`. He asked about memory footprint; I showed that allocating an array of size `(1 << n) * n` takes around 15 * 32,768 integers (negligible memory), proving runtime drops from O(N!) to O(N^2 * 2^N). For the final challenge, he introduced an arithmetic string parsing engine: "Implement a basic calculator to evaluate a math expression string containing non-negative integers, '+', '-', '*', '/', and parenthesis without using built-in eval functions." I explained that operator precedence and nested parentheses make a single left-to-right pass tricky without stack management. The interviewer cut in: "How do you handle unary signs or operator precedence without writing an unwieldy set of nested conditions?" I walked through the Shunting Yard Algorithm / Two-Stack approach: one stack for integer operands and another stack for operator characters. As we parse characters, numbers are pushed onto the operand stack; when encountering an operator, we pop and execute operators from the operator stack onto the operands as long as the stack top has greater or equal precedence (e.g., '*' and '/' over '+' and '-'). An open parenthesis '(' acts as a precedence barrier, pushed directly, and a closing parenthesis ')' triggers pops and evaluations until the matching '(' is cleared. He had me dry-run `"3 + 2 * (4 - 1)"`, watched me resolve the zero-division check, and proved the linear evaluation completes in O(N) time and O(N) stack space.