Meta·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Meta ML Engineer coding round, just one problem but the follow-up constraint is where it gets interesting. Pretty clean problem on the surface but the O(1) space requirement forces you to actually think instead of just flood-filling your way out.

Questions Asked (1)

Given an m x n grid of characters where 'X' marks a battleship and '.' marks empty space, count the number of distinct battleships. Battleships are horizontal or vertical and guaranteed not to be adjacent. Follow-up: do it in O(m*n) time, O(1) space, without modifying the board.

Algorithms & Data Structures

Author's notes

The naive approach is easy enough, just DFS or BFS and mark visited cells.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that since battleships are not adjacent, each ship can be identified by its top-left cell (or leftmost/topmost cell). Scan the grid and count a cell as a new ship only if it is 'X' and has no 'X' above or to the left. This gives O(m*n) time and O(1) space without modifying the board.

Pro tip: Explicitly state the non-adjacency guarantee and how it simplifies the problem; interviewers at Meta value candidates who leverage constraints to avoid unnecessary complexity like DFS or union-find.

1. Clarify constraints and edge cases

Confirm that ships are 1xk or kx1, non-adjacent (no touching even diagonally), and that the board cannot be modified. Discuss empty grid, single cell, and all empty cases.

2. Identify the key insight

Because ships are non-adjacent, each ship has exactly one cell that is the topmost and leftmost (i.e., no 'X' above or to the left). Counting these cells counts ships.

3. Design the algorithm

Iterate through each cell. If grid[i][j] == 'X' and (i == 0 or grid[i-1][j] != 'X') and (j == 0 or grid[i][j-1] != 'X'), increment count. This is O(m*n) time and O(1) extra space.

4. Analyze complexity and follow-up

State time O(m*n) and space O(1). Address the follow-up by emphasizing no board modification and constant space. Mention that the solution naturally satisfies the follow-up.

5. Test with examples

Walk through a small example (e.g., 2x2 with one ship) to verify correctness, and consider edge cases like a ship at the border.

Key Points to Mention

Non-adjacency guarantee means no two ships share an edge or corner, so each ship has a unique top-left cell.
Counting top-left cells avoids traversal or marking, achieving O(1) space.
Time complexity is O(m*n) because each cell is visited once.
No board modification: we only read the grid.
Edge cases: ships at row 0 or column 0, empty grid, single-cell ship.
Alternative approaches like DFS/BFS would use extra space and are unnecessary given the constraint.

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