Microsoft

The interviewer opened with a bipartite graph matching problem: "Given an integer n representing nodes labeled 0 to n - 1 and an array of undirected edges, determine whether the graph can be partitioned into two independent sets such that every edge connects a node in set A to a node in set B." I started by asking whether the graph was guaranteed to be fully connected or could contain disconnected components, which he confirmed could be disconnected. I explained that an exhaustive search takes exponential time, but mathematically a graph is bipartite if and only if it contains no odd-length cycles. I proposed a Breadth-First Search (BFS) coloring algorithm using an array initialized to -1 (unvisited), iterating through all nodes to handle disjoint components. For each component root, I colored it 0, pushed it to a queue, and iterated through its neighbors—assigning opposite colors or flagging a conflict if an adjacent neighbor already held the same color. I coded the solution, proved it runs in O(V + E) time and O(V) space, and dry-ran an odd-cycle triangle graph to show immediate failure detection. He next transitioned to an array partitioning task: "Given an integer array nums and an integer k, return the k most frequent elements in the array." I confirmed whether the answer was guaranteed to be unique and clarified if the output order mattered, which he noted did not. I pointed out that computing frequencies takes O(N) using a Hash Map, but sorting the entries by frequency incurs an O(N log N) bottleneck. I then presented two optimizations: an O(N log k) approach using a Min-Heap of size k, and an optimal O(N) approach using Bucket Sort. I walked through the Bucket Sort design, creating an array of lists where index i stores all numbers that appear exactly i times (bounded by array length N). After populating the buckets in a single pass over the frequency map, I traversed the buckets in reverse order from N down to 0, gathering numbers until k elements were collected. He had me code the bucket approach, asked how it behaves when all elements have the same frequency, and I proved it guarantees strict O(N) time and O(N) auxiliary space. For the final challenge, he introduced a cycle-detection problem on values: "Given an array of n + 1 integers where each integer is between 1 and n inclusive, prove that at least one duplicate exists and find the duplicate number using O(1) extra space without modifying the original array." I clarified whether multiple duplicates could exist or if one number repeats multiple times, which he confirmed could be either. I pointed out that sorting modifies the array (prohibited) and using a hash set uses O(N) memory (prohibited). I then recontextualized the problem as finding a cycle in a linked list: because each value is in the range [1, n], we can treat each index as a node pointing to `nums[index]` as its next pointer, guaranteeing a cycle due to the pigeonhole principle. I implemented Floyd's Cycle Detection (Tortoise and Hare), initializing slow and fast pointers at index 0, advancing slow by one step (`slow = nums[slow]`) and fast by two steps (`fast = nums[nums[fast]]`) until they intersected. Then, I reset slow to 0 and moved both pointers one step at a time until they met at the cycle entrance, which corresponds directly to the duplicate value, proving strict O(N) time and O(1) space.