Hive.ai·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Interviewed for a software engineering role at Hive.ai and got a grid-based BFS problem that looked deceptively straightforward. The algorithmic constraint made it more interesting than a typical graph traversal warmup.

Questions Asked (1)

Given an n×n grid of land and water cells, find the water cell that is farthest from any land cell and return its Manhattan distance. If the grid has no land or no water at all, return -1. You need to solve it in O(n²) time.

Algorithms & Data Structures

Author's notes

My first instinct was BFS from each water cell individually, which would've been way too slow.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a multi-source BFS starting from all land cells simultaneously to compute the shortest distance to the nearest land for every water cell. Then, scan the distance grid to find the maximum distance among water cells. This approach runs in O(n²) time and handles edge cases (no land or no water) by returning -1.

Pro tip: Clarify that the multi-source BFS is essentially a dynamic programming approach that propagates distances level by level, and mention that you can optimize space by using a 2D array of distances or by modifying the grid in-place if allowed.

1. Check edge cases

First, verify if the grid contains both land and water. If either is missing, return -1 immediately.

2. Initialize BFS queue

Add all land cells to a queue and set their distance to 0. For water cells, initialize distance to infinity (or a large number).

3. Multi-source BFS

Perform BFS from all land cells simultaneously, updating the distance of each water cell to the minimum distance from any land cell.

4. Find maximum distance

After BFS, scan the distance grid to find the maximum distance among all water cells. Return that maximum.

Key Points to Mention

Multi-source BFS ensures O(n²) time by visiting each cell once.
Distance is measured in Manhattan distance (4-directional moves).
Edge cases: no land or no water returns -1.
Space complexity is O(n²) for the queue and distance array, but can be optimized.
The BFS propagates distances level by level, so the first time a water cell is reached gives its minimum distance to land.
If all cells are land, there is no water, so return -1.

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