Microsoft

"The interviewer opened with: 'Suppose you have a sorted array that was rotated at an unknown pivot, find a target value in sub-linear time.' I started by asking if duplicates were present; once he confirmed distinct elements, I discarded the initial instinct of finding the pivot first. I explained how one half of the array is always strictly sorted at every midpoint, walked him through adjusting the binary search bounds based on whether the target fell within that sorted segment, coded it up in O(log N) time, and wrapped up by dry-running an edge case where the pivot lands at the very ends." "He shared a doc and said: 'Imagine you have an array of daily temperatures, return an array where each day tells you how many days you must wait for a warmer temperature.' I acknowledged that a nested O(N^2) loop was obvious, but pointed out how future elements depend on past unresolved values. I proposed a Monotonic Decreasing Stack storing indices, traced on the whiteboard how incoming warmer days resolve indices off the stack in amortized O(1) time per element, and finished the round by writing the clean O(N) pass while explaining why the stack space bounds at O(N)." "The round kicked off with: 'Given a 2D grid of 0s and 1s, how would you find the shortest path from the top-left to the bottom-right corner where cells can only move 4-directionally?' I immediately ruled out DFS because it cannot guarantee the shortest path without an exhaustive search, and pitched Breadth-First Search (BFS) using a FIFO queue. He pressed me on how to prevent infinite loops, so I updated the grid in-place to track visited states, traced the step-by-step queue transitions level by level, and proved the time and space complexity were strictly bounded to O(R * C)."