Microsoft·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Microsoft SWE coding round, one problem the whole session. It's a grid traversal thing dressed up in satellite imagery flavor, which I thought was a fun skin on a classic problem.

Questions Asked (1)

Given a 2D grid of Heat Radiation Index values from 0 to 9, a cell is considered part of a cloud if its value is 4 or below. Return the total number of distinct clouds, where two cloud cells belong to the same cloud only if they are directly adjacent horizontally or vertically.

Algorithms & Data Structures

Author's notes

It's basically number of islands with a threshold check instead of a '1' vs '0' comparison.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a graph where each cell with value ≤ 4 is a node, and edges connect horizontally or vertically adjacent cloud cells. Then count the number of connected components using either BFS/DFS or Union-Find. Clearly state the time and space complexity, and discuss trade-offs between the two approaches.

Pro tip: Mention that you can mutate the grid in-place to mark visited cells (e.g., set to -1) to save space, but clarify that this modifies the input; if that's not allowed, use a separate visited matrix. Also, proactively discuss edge cases like empty grid or all non-cloud cells.

1. Clarify and define the problem

Confirm that clouds are connected components of cells with value ≤ 4, using 4-directional adjacency. Ask about input constraints (e.g., grid size, whether modification is allowed) to guide algorithm choice.

2. Choose an algorithm

Decide between BFS/DFS (simpler, O(mn) time) and Union-Find (good for dynamic connectivity, but overkill here). Explain your choice based on constraints and clarity.

3. Implement traversal and counting

Iterate through each cell; when you find an unvisited cloud cell, increment the cloud count and perform BFS/DFS to mark all connected cloud cells as visited.

4. Analyze complexity and edge cases

State time complexity O(mn) and space complexity O(mn) for visited matrix (or O(1) if mutating input). Discuss edge cases: empty grid, no cloud cells, all cloud cells, single row/column.

5. Test and verify

Walk through a small example to ensure correctness, and consider potential pitfalls like recursion depth for large grids (prefer iterative BFS or increase recursion limit).

Key Points to Mention

Graph traversal (BFS/DFS) or Union-Find for connected components
4-directional adjacency (up, down, left, right)
In-place marking vs. separate visited matrix
Time complexity O(mn) and space complexity O(mn) or O(1)
Edge cases: empty grid, no cloud cells, all cloud cells, large grid recursion depth
Trade-offs between BFS/DFS and Union-Find

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