Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Microsoft SWE interview with a graph/union-find problem that sounds straightforward until you're actually coding it under pressure.

Questions Asked (1)

You have an m x n grid that starts as all water. Given a sequence of operations that each flip one cell to land, return the island count after every single operation. Islands are 4-directionally connected. Solve it efficiently.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew union-find was the right call pretty quickly, which felt good.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use Union-Find (Disjoint Set Union) to dynamically maintain connected components as cells are added. For each operation, mark the cell as land, increment the island count, then union it with any adjacent land cells, decrementing the count for each successful union. This yields near O(1) amortized time per operation.

Pro tip: Mention that Union-Find with union by rank and path compression is optimal here, and contrast it with BFS/DFS which would be O(mn) per operation. Also note that if operations are given offline, you could process them in reverse using Union-Find, but online Union-Find is simpler and equally efficient.

1. Clarify the problem and constraints

Confirm that operations are given one by one and we need the island count after each. Ask about grid size and number of operations to gauge if O(mn) per operation is acceptable.

2. Choose the right data structure

Select Union-Find (Disjoint Set Union) with path compression and union by rank/size to efficiently track connected components. Explain why it's better than BFS/DFS for incremental updates.

3. Design the algorithm

Initialize a DSU for all cells, a 2D grid to track land, and a counter for islands. For each operation: if cell already land, skip; else mark land, increment count, and for each of the 4 neighbors that is land, union and decrement count on successful union.

4. Analyze complexity and edge cases

Time: O(k * α(mn)) where k is number of operations and α is inverse Ackermann (nearly constant). Space: O(mn). Handle edge cases: duplicate operations, operations on already land cells, and grid boundaries.

5. Test and validate

Walk through a small example (e.g., 3x3 grid with a few operations) to verify the island count updates correctly. Consider edge cases like all water initially, all land eventually, and isolated cells.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for near O(1) operations.
Incremental approach: start with 0 islands, add land cell, increment count, then union with adjacent land cells and decrement count for each successful union.
Time complexity: O(k * α(mn)) where k is number of operations, α is inverse Ackermann function (practically constant).
Space complexity: O(mn) for DSU parent array and grid state.
Edge cases: duplicate operations, operations on already land cells, and boundary checks for neighbors.
Alternative approaches: BFS/DFS per operation (O(mn) each) is inefficient; offline reverse processing with Union-Find is possible but not necessary.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.