Applied intuition·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Applied Intuition coding round, one meaty grid problem that took up basically the whole session. Not a bad experience but the complexity analysis portion at the end felt rushed on my side.

Questions Asked (1)

Given an m x n grid with k marked points, find the cell whose sum of shortest-path distances to all marked points is minimized. If any marked point is unreachable from all cells, return -1. Implement a BFS-based solution, return both the minimum total distance and an optimal cell, then analyze time and space complexity. Also discuss when multi-source BFS or coordinate medians could reduce complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the brute force pretty quickly: run BFS from each marked point, accumulate distances per cell, track the minimum.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then propose a BFS-based solution that computes distances from each marked point to all reachable cells, aggregates the distances, and finds the cell with the minimum sum. After implementing, analyze time and space complexity, and discuss optimizations like multi-source BFS or coordinate medians for special cases.

Pro tip: Mention that if any marked point is unreachable from some cells, those cells are invalid, but if a marked point is unreachable from all cells, return -1. Also, note that multi-source BFS is useful when the number of marked points is large and the grid is small, but it doesn't directly solve the sum minimization; it can help in computing distances efficiently for certain patterns.

1. Clarify requirements and edge cases

Confirm grid dimensions, movement allowed (4-directional), and what 'unreachable' means. Discuss cases like no marked points, marked points unreachable from each other, or grid with obstacles.

2. Design BFS-based algorithm

For each marked point, run BFS to compute shortest distances to all reachable cells. Maintain a 2D array to accumulate distances and a count of reachable marked points per cell.

3. Aggregate and find optimal cell

After all BFS runs, iterate over cells to find the one with the minimum total distance where all marked points are reachable. If no such cell exists, return -1.

4. Analyze complexity and discuss optimizations

State time complexity O(k * m * n) and space O(m * n). Discuss when multi-source BFS (O(m*n) for all sources simultaneously) could be beneficial, and when coordinate medians (for Manhattan distance without obstacles) reduce to O(k log k).

Key Points to Mention

BFS guarantees shortest paths in unweighted grids; run BFS from each marked point.
Accumulate distances in a 2D array and track number of reachable marked points per cell.
Edge case: if any marked point is unreachable from all cells, return -1.
Time complexity: O(k * m * n) for k marked points; space O(m * n) for distance arrays and queue.
Multi-source BFS computes distances from all marked points simultaneously in O(m*n), but doesn't directly give sum of distances to all points; it's useful for other problems like nearest marked point.
Coordinate median (Manhattan distance) gives optimal cell in O(k log k) when no obstacles, but BFS is needed for obstacles or other distance metrics.

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