← Applied Intuition Interview InsightsSoftware Engineer

Applied Intuition·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Applied Intuition SWE coding round, one problem the whole time. It was a BFS grid question, a twist on a classic LC problem, and the twist is what got me.

Questions Asked (1)

Q1

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. Unlike the standard version, cells already occupied by a building are also valid placement candidates.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew LC 317 well enough and started coding pretty confidently.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the twist: buildings are valid placement candidates, so we must consider all cells, not just empty ones. Then propose a multi-source BFS from each building to compute distances to all reachable cells, aggregating totals and tracking reachability counts to ensure all buildings are reachable. Finally, scan all cells to find the minimum total distance among those reachable from every building, returning -1 if none exist.

Pro tip: Mention that the twist actually simplifies the problem because you no longer need to exclude building cells from the candidate set, but you must still handle obstacles and unreachable buildings. Also, note that if any building is completely isolated by obstacles, the answer is immediately -1.

1. Clarify the problem and edge cases

Confirm that buildings (1) are valid placement candidates and that obstacles (2) cannot be placed on. Discuss edge cases: no buildings, no empty cells, isolated buildings, and multiple buildings.

2. Choose the algorithm: multi-source BFS per building

Run BFS from each building to compute shortest distances to all reachable cells. Aggregate total distances and count how many buildings can reach each cell.

3. Aggregate distances and track reachability

Maintain a distance sum array and a reach count array. For each building's BFS, update sums and counts for visited cells. If any building cannot reach all others, early exit with -1.

4. Find the optimal cell

Iterate over all cells (including buildings) that are reachable from all buildings and have the minimum total distance. Return that minimum or -1 if none.

5. Analyze complexity and trade-offs

Discuss time complexity O(B * m * n) and space O(m * n). Compare with alternative approaches like single BFS from each empty cell (worse) and mention optimizations like early termination.

Key Points to Mention

  • Multi-source BFS from each building to compute distances efficiently.
  • Aggregating distances and reachability counts to ensure all buildings are reachable.
  • Handling the twist: buildings are valid placement candidates, so include them in the final scan.
  • Edge cases: no buildings, isolated buildings, obstacles blocking paths, and grid boundaries.
  • Time and space complexity: O(B * m * n) time, O(m * n) space, where B is number of buildings.
  • Early termination if any building cannot reach all others, returning -1 immediately.

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