Applied intuition·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026Remote

Summary

Applied Intuition SWE coding round, one problem the whole time. It was a BFS grid question that looked familiar until it wasn't.

Questions Asked (1)

Given an m x n grid where 0 is empty land, 1 is a building, and 2 is an obstacle, find the cell to place a new house such that the total BFS distance to all buildings is minimized. Return that minimum total distance or -1 if no valid placement exists. Twist: building cells themselves are also valid placement candidates, unlike the standard version of this problem.

Algorithms & Data Structures

Author's notes

I knew the base problem so I started coding pretty confidently, which was a mistake.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Run BFS from each building to compute the total distance to all buildings for every reachable empty cell, tracking the number of buildings that can reach each cell. Then, iterate over all cells (including building cells) that are reachable from all buildings and find the minimum total distance. If no such cell exists, return -1.

Pro tip: Clarify the twist early: building cells are valid candidates, so you must consider them in the final scan. Also, mention that you can optimize by only considering cells that are reachable from all buildings, and use a visited matrix per BFS to avoid revisiting cells.

1. Understand the problem and constraints

Restate the problem: find a cell (0, 1, or 2? Actually 2 is obstacle, so only 0 and 1) to place a house minimizing sum of BFS distances to all buildings. Note the twist: building cells (1) are also valid placement candidates. Clarify that obstacles (2) cannot be placed on.

2. Plan the BFS approach

For each building, perform BFS to compute distances to all reachable cells. Maintain a total distance array and a reach count array. Only cells reachable from all buildings are valid candidates.

3. Handle the twist: include building cells

When scanning for the minimum total distance, include cells that are originally buildings (value 1) as well as empty lands (0). Ensure that building cells are not treated as obstacles during BFS from other buildings.

4. Compute and return the result

After all BFS runs, iterate over all cells (0 and 1) that have reach count equal to the number of buildings. Track the minimum total distance. If none found, return -1.

5. Analyze complexity and edge cases

Discuss time complexity: O(B * m * n) where B is number of buildings. Space complexity: O(m * n). Mention edge cases: no buildings, no empty cells, disconnected components.

Key Points to Mention

BFS from each building to compute distances to all cells.
Maintain total distance and reach count arrays.
Only cells reachable from all buildings are valid candidates.
Include building cells as valid placement candidates (the twist).
Time complexity: O(B * m * n), space complexity: O(m * n).
Edge cases: no buildings, no valid placement, obstacles blocking all paths.

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