Microsoft

The interviewer opened with a custom cache design: "Design and implement a Least Recently Used (LRU) cache with get and put operations operating in strict O(1) time complexity." I started by clarifying capacity constraints and whether evicted keys needed callback handling. I explained that an array or standard hash map alone cannot satisfy both constant-time updates and eviction ordering simultaneously because finding or shifting elements takes O(N). I proposed pairing a Doubly Linked List with a Hash Map: the map stores key pointers directly to list nodes for O(1) lookups, while the doubly linked list maintains recency order with dummy head and tail sentinels to avoid edge-case null checks. He asked me to trace the eviction step when capacity saturates, so I walked through unlinking the tail's previous node, erasing its key from the hash map, inserting the new node right after the head, and proved that both get and put strictly run in O(1) time and O(capacity) space. He then shifted to binary tree validation: "Given the root of a binary tree, determine if it is a valid binary search tree (BST)." I confirmed whether duplicate node values were allowed (they were not) and clarified 32-bit integer boundary limits. I cautioned against the common trap of only checking if a node's left child is smaller and right child is larger, illustrating a counterexample where a right-subtree leaf is smaller than the global root. I walked through a DFS validation approach propagating valid value ranges (-infinity, +infinity) down the recursive stack, where each step constrains the allowed interval: (min_val, node.val) for the left branch and (node.val, max_val) for the right. He challenged me to do it iteratively without range bounds, so I demonstrated an iterative in-order traversal using an explicit stack, verifying that visited values strictly increase monotonically, running in O(N) time and O(H) stack space. For the final challenge, he introduced an array partition problem: "Given an array of non-negative integers representing jump lengths at each index, find the minimum number of jumps to reach the last index from index 0." I confirmed that a valid path to the end was guaranteed and asked about array length bounds. I noted that while 1D dynamic programming solves this in O(N^2) by checking all reachable backward indices, a Greedy BFS-layering approach drops it to linear time. I walked through maintaining two pointers defining the current jump horizon (`current_end`) and the furthest reachable index (`farthest`). As we scan the array, we continuously update `farthest = max(farthest, i + nums[i])`; when the loop index reaches `current_end`, we trigger an unavoidable jump, increment the jump count, and update `current_end = farthest`. He had me code the single pass, dry-run an edge case where the array has length 1 requiring 0 jumps, and verified the O(N) time and O(1) space guarantee.