Google·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Google ML engineer coding round, basically a graph traversal problem dressed up as an island counter. Not the most exotic thing I've seen but still had to think carefully about the BFS vs DFS tradeoff under pressure.

Questions Asked (1)

Given a 2D binary grid where 1s represent land and 0s represent water, count the number of islands, where an island is a group of land cells connected horizontally or vertically.

Algorithms & Data Structures

Author's notes

Went with DFS, marked visited cells in-place by flipping 1s to 0s.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a graph traversal algorithm like BFS or DFS to explore each unvisited land cell and mark all connected land cells as visited, incrementing the island count for each traversal. Alternatively, use Union-Find to group connected land cells and count distinct sets. Discuss time and space complexity, and consider edge cases.

Pro tip: Mention that you can optimize space by modifying the grid in-place (e.g., changing '1' to '0') if allowed, but clarify with the interviewer first. Also, be prepared to discuss trade-offs between BFS, DFS, and Union-Find in terms of performance and code complexity.

1. Clarify the problem

Confirm the definition of an island, connectivity (4-directional), and input constraints (grid size, mutability). Ask if the grid can be modified.

2. Choose an algorithm

Select a traversal method (BFS/DFS) or Union-Find. Explain why it's suitable and outline the approach.

3. Implement the solution

Write clean code with helper functions. For BFS/DFS, iterate through each cell; if it's land and unvisited, increment count and traverse to mark all connected land.

4. Analyze complexity

State time complexity O(M*N) and space complexity O(M*N) for BFS/DFS (worst-case queue/stack) or O(M*N) for Union-Find. Mention in-place modification reduces space to O(1) extra if allowed.

5. Test with examples

Walk through a small example, including edge cases like empty grid, all water, all land, and single row/column.

Key Points to Mention

Graph traversal (BFS/DFS) or Union-Find as core algorithms
Time and space complexity analysis
Handling edge cases (empty grid, no islands, all land)
In-place modification to save space (if allowed)
Avoiding revisiting cells (visited set or marking)
Trade-offs between different approaches (e.g., BFS vs DFS vs Union-Find)

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