Microsoft

The interviewer opened by pasting a bitwise math prompt: "Given an integer array nums where exactly two elements appear only once and all other elements appear exactly twice, find the two unique elements in O(N) time and O(1) extra space." I immediately pointed out that XORing the entire array cancels out the pairs, leaving a combined value `xor_sum = a ^ b`. The interviewer followed up: "Since a and b are distinct, how do you pull them apart from that single XOR accumulator without extra storage?" I explained that because `a != b`, `xor_sum` must contain at least one set bit (value 1), meaning `a` and `b` differ at that exact bit position. I showed how to isolate the lowest set bit using two's complement bitwise arithmetic (`diff_bit = xor_sum & (-xor_sum)`), then performed a second linear pass partitioning all numbers into two distinct groups based on whether that specific bit is set or clear. XORing each group independently collapsed the duplicate pairs, isolating `a` and `b`. He had me code the branchless pass and verified it ran in strict O(N) time and O(1) auxiliary space. He then shifted the discussion to dynamic programming with game theory: "You are given an integer array of coin values where two players take turns picking either the first or last coin from the line; determine if player 1 can guarantee a win assuming both players play optimally." I clarified if coin values were strictly positive and confirmed the array length. I explained that a greedy choice of taking the largest visible coin fails because it can expose a much larger coin to the opponent. He followed up: "How do you model the opponent's optimal decisions in your state transitions?" I framed it as minimax interval DP, defining `dp[i][j]` as the maximum relative score lead the current player can achieve over the remaining subarray `nums[i...j]`. The recurrence evaluated picking either boundary: `dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])`, where subtracting the opponent's subsequent optimal score naturally enforces zero-sum minimax transitions. He asked if we could avoid an O(N^2) space grid; I demonstrated collapsing the DP table into a single 1D array of length N updated in-place from bottom-up, completing the pass in O(N^2) time and O(N) space. For the final challenge, he introduced a monotonic stack geometry problem: "Given an array of integers representing histogram bar heights where each bar has a width of 1, find the area of the largest rectangle that can be formed within the histogram." I ruled out the O(N^2) brute-force of checking all left-right pairs and proposed using an explicit Monotonic Increasing Stack of indices. The interviewer cut in: "What is the trigger to pop an element off the stack, and how do you calculate the popped bar's width?" I explained that whenever an incoming bar is shorter than the bar at the top of the stack, the taller bar can no longer extend rightward, triggering a pop. The popped bar acts as the height of the candidate rectangle; its right boundary is the current loop index `i`, and its left boundary is the new top of the stack (the nearest smaller element to its left), yielding width `w = (stack.empty() ? i : i - stack.top() - 1)`. He then asked how I ensure all remaining bars inside the stack are cleared after the loop ends. I demonstrated appending a sentinel 0-height bar to the end of the array, which automatically forces a complete stack flush down to empty. I coded the solution, proved every index is pushed and popped at most once for O(N) time and O(N) space, and wrapped up the round.