Microsoft

The interviewer opened by pasting a classic string prompt: "Given a string s, return the longest palindromic substring." I started by asking if the string only contains alphanumeric characters and confirmed the length constraints to gauge whether an O(N^2) solution was acceptable or if he expected O(N) linear time. I explained that while checking all substrings takes O(N^3) and dynamic programming takes O(N^2) time with O(N^2) memory, we could achieve the same time bound in O(1) space using the Expand-Around-Center approach. He asked how I would handle odd versus even palindromes, so I demonstrated running two expansion passes per index—one centered on a single character and one between adjacent pairs. I wrote out the helper expansion function, dry-ran an example with edge cases like single-character strings, and concluded by discussing how Manacher’s Algorithm could drop the time complexity to strict O(N) if scale demanded it. He then shifted the discussion to dynamic programming with: "You are given an integer array of coin denominations and an integer amount, compute the fewest number of coins needed to make up that amount." I immediately clarified whether coin supplies were infinite and what to return if the target cannot be formed. He prompted me on why a greedy approach like picking the largest coin fails, to which I walked through a counterexample like denominations [1, 3, 4] aiming for 6. I proposed bottom-up 1D dynamic programming, defining dp[i] as the minimum coins needed for value i, initialized to infinity with a base case of dp[0] = 0. I wrote the nested loop iterating over every sub-amount and coin, explained why the inner state transition dp[i] = min(dp[i], dp[i - coin] + 1) correctly avoids duplicate sub-problems, and proved the O(amount * N) runtime and O(amount) memory footprint. For the final problem, he set up an interval scenario: "Given an array of intervals where intervals[i] = [start, end], merge all overlapping intervals and return the non-overlapping array." I asked whether the input intervals were pre-sorted, which he confirmed was not guaranteed. I pointed out that sorting was the essential bottleneck: without it, comparing every pair takes O(N^2), but sorting by start time brings structure to the timeline. I walked him through sorting the array in O(N log N) time, then maintaining a running result list where an incoming interval either extends the current interval's end boundary if its start is less than or equal to the current end, or begins a brand-new non-overlapping interval. He had me code the clean linear pass, asked how to handle edge cases where one interval completely swallows another, and I wrapped up by proving the overall complexity was O(N log N) due to sorting and O(N) space for the merged output.