Microsoft

The interviewer started by asking: "Given an array of integers representing elevations, calculate how much rainwater can be trapped after raining." I first clarified whether the elevation values were strictly non-negative and whether the array edges could hold water, which he confirmed they could not. I pointed out that calculating the trapped water above any index requires knowing the minimum of the highest wall to its left and right minus its own height, which takes O(N^2) naively or O(N) space using two precomputed prefix and suffix max arrays. He pushed me to optimize the memory, so I walked through a Two-Pointer technique maintaining `left_max` and `right_max` from both ends, explaining that we only need to advance the pointer pointing to the shorter boundary since that shorter side acts as the limiting bottleneck. I coded the solution in O(N) time and O(1) space, dry-ran an edge case with monotonically increasing heights where zero water is trapped, and verified the pointer convergence. He then moved on to dynamic programming on strings: "Given two strings text1 and text2, return the length of their longest common subsequence." I asked if the match had to be contiguous, which he clarified was not required, differentiating subsequence from substring. When he asked for the baseline approach, I explained that exploring all possible subsequences takes exponential O(2^N) time, making a 2D dynamic programming grid the right path. I defined `dp[i][j]` as the LCS length for prefixes `text1[0...i-1]` and `text2[0...j-1]`, walking through the recurrence: if characters match, we transition diagonally via `dp[i-1][j-1] + 1`; otherwise, we take `max(dp[i-1][j], dp[i][j-1])`. He challenged me on space optimization, so I demonstrated reducing the auxiliary space from O(M * N) down to O(min(M, N)) using just two 1D rows since each cell only depends on the previous row, and walked through a trace to prove correctness. For the last question, he switched to tree design: "Construct a binary tree from its given preorder and inorder traversal arrays." I started by confirming whether all node values were guaranteed to be unique, which he affirmed, noting that duplicates would make the reconstruction ambiguous. I explained that the first element of preorder always defines the root, and finding that root's location inside the inorder array divides the tree into its exact left and right subtree partitions. To avoid an O(N^2) scan searching for root indices repeatedly, I loaded the inorder array values and their corresponding indices into a Hash Map for O(1) lookup. I wrote a recursive helper tracking boundary indices across both arrays, clearly demonstrated how to calculate subtree sizes to shift preorder window bounds accurately, and showed that the overall time and space complexity were strictly bounded to O(N).