Microsoft

"Given an array of integers representing house values along a street, find the maximum money you can rob without alerting police by hitting two adjacent houses": The interviewer asked for an optimal non-recursive solution; I solved it using 1D Dynamic Programming with state reduction, maintaining only two variables (`prev1` and `prev2`) to compute `dp[i] = max(dp[i-1], dp[i-2] + val)` in O(N) time and O(1) space. "You are given a list of tasks with cooldown intervals between identical tasks; find the minimum CPU cycles required to finish them all": Rather than simulating every clock tick, I solved it using a Greedy frequency-bucket strategy, calculating the idle slots dictated solely by the most frequent task's count: `(max_freq - 1) * (cooldown + 1) + num_max_freq_tasks`, resolving the answer in O(N) time. "You have an m x n 2D grid where '1' represents land and '0' represents water; count the total number of distinct islands": The panel asked to minimize recursion call-stack overhead; I implemented a Breadth-First Search (BFS) with an in-place visited marker, scanning the grid and triggering an iterative queue traversal to flip connected '1's to '0's, achieving O(M * N) time and O(min(M, N)) auxiliary space.