Microsoft

The interviewer opened with a sliding window challenge: "Given a string s and a string t of lengths m and n, return the minimum window substring of s such that every character in t (including duplicates) is included in the window." I began by clarifying if characters were restricted to ASCII and what to return if no valid substring exists, confirming an empty string output. I pointed out that checking every substring takes O(M^2 * N) time, so I proposed a variable-sized Sliding Window using two hash tables and two pointers, `left` and `right`. I maintained a `formed` counter tracking how many unique characters met their required frequency thresholds, expanding `right` to satisfy the condition and contracting `left` to minimize the window length once satisfied. He asked how to optimize frequent hash map lookups, so I replaced dynamic hash tables with fixed 128-element frequency arrays, coded the pass in O(M + N) time and O(1) space, and dry-ran an edge case where no window matches. He next transitioned to back-tracking and search optimization: "Given a 9x9 Sudoku board with empty cells marked as '.', write a program to solve the puzzle by filling the empty cells." I confirmed that each input board had exactly one unique solution and verified that standard row, column, and 3x3 box rules applied. I explained that a naive brute-force testing of digits 1 through 9 at every cell incurs exponential O(9^81) worst-case time, so backtracking with state caching was critical. I walked through representing constraints using three bitmasks—`rows[9]`, `cols[9]`, and `boxes[9]`—where the d-th bit set indicates digit d is present, turning valid-placement checks into O(1) bitwise operations. He had me code the recursive solver, asked how to speed up search depth, and I explained how always picking the empty cell with the fewest available candidate digits (minimum remaining values heuristic) prunes suboptimal branches early. For the final problem, he introduced a distributed streaming scenario: "You are given an array of k linked lists, where each linked list is already sorted in ascending order; merge all k sorted lists into one sorted linked list." I immediately clarified the scale of k versus total elements N and confirmed whether modifying node pointers in-place was permitted. I pointed out that merging lists sequentially takes O(k * N) time, which chokes when k is large. I then proposed using a Min-Heap (Priority Queue) initialized with the head node of each of the k lists, extracting the minimum node and inserting its `next` pointer back into the heap at each step. He challenged me on whether we could achieve the same O(N log k) time without paying the O(k) auxiliary heap space, so I walked through a Divide and Conquer pairwise merge strategy resembling bottom-up Merge Sort, coded the in-place pointer rewiring, and proved it runs in O(N log k) time with O(1) extra space.