← Google Interview Insights

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

SeniorPrefer not to say
May 2026

Summary

Google SWE coding round with a grid/graph problem that looked straightforward until it wasn't. The Union-Find angle wasn't where my head went first and I spent a while fumbling before things clicked.

Questions Asked (1)

Q1

Given a binary matrix of land and water cells, and a query point guaranteed to be on land, count the number of lakes within the island containing that point. A lake is a connected water region (4-directional) that is fully enclosed by the island and has no connection to the border of the matrix.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was BFS from the query cell to find the island, then BFS again on each adjacent water region and check if any of them touch the border.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, identify the island containing the query point using BFS/DFS on land cells. Then, find all water cells connected to the matrix border (not part of any lake) via BFS/DFS from border water cells. Finally, count the connected components of water cells that are not border-connected and are adjacent to the island; each such component is a lake.

Pro tip: Clarify whether the island can have holes (lakes) that contain other islands, and whether lakes can contain islands. This shows attention to edge cases and can lead to a more robust solution.

1. Clarify definitions and edge cases

Confirm that a lake is a water region fully enclosed by the island (no connection to matrix border) and that the query point is on land. Discuss handling of nested islands/lakes.

2. Identify the island

Use BFS/DFS from the query point to mark all connected land cells (4-directionally) as part of the island.

3. Mark border-connected water

Perform BFS/DFS from all water cells on the matrix border to mark all water cells connected to the border (these are not lakes).

4. Count lakes

Iterate over unvisited water cells that are adjacent to the island and not marked as border-connected. For each, BFS/DFS to mark the entire lake and increment the count.

5. Analyze complexity and trade-offs

Discuss time and space complexity (O(m*n) time, O(m*n) space) and possible optimizations or alternative approaches (e.g., union-find, flood fill variations).

Key Points to Mention

  • Use BFS/DFS for connected component traversal on both land and water.
  • Distinguish between water connected to the border (ocean) and enclosed water (lakes).
  • Ensure the island is correctly identified from the query point before counting lakes.
  • Handle edge cases: no lakes, multiple lakes, lakes with islands inside, query point on border of island.
  • Time and space complexity: O(m*n) for an m x n matrix.
  • Potential optimizations: early termination if no water cells, using union-find for connectivity.

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