Microsoft

"Given a stream of incoming integers, continuously report the median value in real time after every insertion": The interviewer barred sorting the array on each tick; I solved it using a Two-Heap pattern (a max-heap for the lower half and a min-heap for the upper half), rebalancing heap sizes so that median lookups take O(1) time while each insertion runs in O(log N). "Clone an undirected graph where each node contains an integer label and a list of references to its neighbors": The interviewer asked how to handle self-loops and arbitrary cycles without infinite recursion; I used a Breadth-First Search (BFS) paired with a Hash Map, mapping original node pointers to newly allocated clones to ensure each vertex and edge is copied exactly once in O(V + E) time. "You have an array of daily stock prices, and you want to know how many consecutive days prior to today had a price less than or equal to today's price": A naive nested loop takes O(N^2), so I solved it using a Monotonic Decreasing Stack storing indices, popping smaller past prices to resolve span boundaries in O(1) amortized time per day (O(N) total).