Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jul 2026

Summary

Amazon coding round, one meaty grid problem that looked deceptively clean on the surface. The median trick is well-known but the tree-obstacle wrinkle is what they actually care about.

Questions Asked (1)

Given a set of house coordinates and a set of blocked tree coordinates on a 2D integer grid, find a location for a locker that minimizes the total Manhattan distance to all houses, with the constraint that the locker cannot be placed on a tree cell. Return the minimum total distance and one valid optimal location.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The median approach clicked pretty fast for me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, explain that the unconstrained Manhattan distance minimizer is the median of x-coordinates and median of y-coordinates. Then, if that point is blocked, search nearby cells (e.g., within a small radius) to find the optimal valid location. Finally, compute the total distance and return the minimum and one optimal location.

Pro tip: Mention that the optimal unconstrained point is the median, and if blocked, the next best is among the 4 neighbors or within a small neighborhood; this shows you understand the problem's structure and can optimize the search.

1. Identify the unconstrained optimal point

Compute the median of all house x-coordinates and the median of all house y-coordinates. This point minimizes the sum of Manhattan distances without any constraints.

2. Check if the optimal point is blocked

If the median point is not a tree cell, it is the answer. If it is blocked, proceed to find the next best valid location.

3. Search for the best valid location

If the median is blocked, evaluate candidate points near the median (e.g., all cells within a small radius, or the four adjacent cells) that are not trees. Compute the total distance for each and pick the minimum.

4. Compute total distance and return result

For the chosen valid location, calculate the sum of Manhattan distances to all houses. Return this minimum total distance and the location.

Key Points to Mention

Manhattan distance is separable: the sum of distances is the sum of x-distances plus y-distances.
The median minimizes the sum of absolute deviations for 1D points.
If the median is blocked, the optimal valid point is among the cells adjacent to the median or within a small neighborhood.
Time complexity: O(n) to find medians and O(n) per candidate to compute total distance, so overall O(n) if checking a constant number of candidates.
Edge cases: multiple medians, all candidate points blocked, or houses on trees (though typically houses and trees are disjoint).
Trade-offs: exhaustive search over all grid cells is O(n * grid_size) but unnecessary; leveraging the median property gives an efficient solution.

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