Microsoft

The interviewer started with a tree path problem: "Given the root of a binary tree, find the maximum path sum along any non-empty path connecting any two nodes." I first clarified that node values could be negative, meaning paths might be degraded by extending into certain branches. I proposed a post-order DFS where each recursive call returns the maximum single-branch sum extending upward to its parent (`node.val + max(0, left_gain, right_gain)`), while locally maintaining a global maximum that accounts for the path split spanning across the current node (`node.val + max(0, left) + max(0, right)`). He paused me on my return statement and followed up: "What happens if all node values in the tree are negative?" I pointed out that initializing the global maximum to 0 would yield an incorrect answer; therefore, it must be initialized to `-infinity` so that a single least-negative node can be selected if all paths yield negative gains. He nodded, had me code it up, and verified the O(N) time and O(H) stack frame footprint. He then shifted gears to string algorithms: "Implement strStr()—find the first index of needle in haystack." I noted that the brute-force nested comparison takes O(N * M) time in the worst case (e.g., matching "aaaaab" against "aaab"). He followed up: "Can you guarantee linear time without dynamic allocations?" I pitched the Knuth-Morris-Pratt (KMP) algorithm, walking through building the Longest Prefix Suffix (LPS) array in O(M) time, where `lps[i]` records the length of the longest proper prefix that matches a suffix for `needle[0...i]`. As I walked through the matching loop, he interjected: "When a mismatch occurs at needle index j, why don't we roll back the haystack pointer i?" I explained that the LPS array mathematically proves the characters in `haystack[i - j ... i - 1]` already align with `needle[0 ... j - 1]`, so setting `j = lps[j - 1]` preserves the matched prefix without reprocessing the text stream. Satisfied, he had me implement both the preprocessing and matching phases, confirming O(N + M) time and O(M) auxiliary space. For the final challenge, he introduced a graph optimization problem: "You are given n network nodes labeled 1 to n and a list of directed edges with positive traversal times; find the time it takes for a signal sent from node k to reach all nodes, or return -1 if impossible." I recognized this as the Single-Source Shortest Path problem with non-negative edge weights and proposed Dijkstra’s Algorithm using a Min-Heap. He immediately challenged me: "Standard Dijkstra pushes duplicate node entries into the priority queue on relaxation; how do you prevent stale states from inflating your runtime?" I explained that when popping a pair `(dist, u)` from the heap, we compare `dist` against our recorded shortest distance array `dist_to[u]`; if `dist > dist_to[u]`, the entry is an obsolete stale path and we immediately execute a `continue` to prune it. He then asked what happens if an edge weight is 0 or negative; I explained that zero weights are handled correctly by Dijkstra, but negative weights break the greedy invariant, requiring Bellman-Ford or SPFA. I wrote the clean C++ implementation, proved the O(E log V) time and O(V + E) space bounds, and wrapped up the round.