Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

Jun 2026

Summary

Google SWE coding round, one problem the whole session. Grid-based flood fill with a twist I didn't fully see coming until I was already mid-solution.

Questions Asked (1)

Given a binary grid where 1s are land and 0s are water, and a starting cell (r, c), count the number of lakes enclosed within the island that contains that cell. A lake is a connected water region fully surrounded by the island's land cells and not touching the grid boundary.

Algorithms & Data Structures

Author's notes

My first instinct was just BFS from the given cell to find the island, then BFS again on water cells to count enclosed regions.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the island containing the starting cell using BFS/DFS on land cells. Then, find all water regions within the grid and check if they are enclosed by the island (i.e., not touching the boundary and surrounded by the island's land). Count the number of such enclosed water regions that are adjacent to the island.

Pro tip: Clarify the definition of 'enclosed' and handle edge cases like the starting cell being water or the island having no lakes. Also, consider using a visited matrix to avoid reprocessing cells.

1. Identify the island

Perform BFS/DFS from the starting cell to mark all connected land cells as part of the island.

2. Find water regions

Scan the grid for water cells not yet visited, and for each, perform BFS/DFS to find the entire connected water region.

3. Check enclosure

For each water region, determine if it touches the grid boundary. If it does, it's not a lake. Also, check if all adjacent land cells belong to the island.

4. Count lakes

If a water region is enclosed and adjacent only to the island's land, increment the lake count.

5. Return result

After processing all water regions, return the total count of lakes.

Key Points to Mention

Use BFS/DFS for connected components on both land and water.
Maintain a visited matrix to avoid infinite loops and redundant work.
Check boundary conditions to determine if a water region is a lake.
Ensure that the water region is surrounded by the specific island, not just any land.
Consider time and space complexity: O(m*n) time and space.
Handle edge cases: starting cell is water, no lakes, island touches boundary.

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