How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Compute optimal locker placement with obstacles

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute optimal locker placement with obstacles states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given house coordinates H = {(xi, yi)} and tree coordinates T = {(xj, yj)} on a 2D integer grid, choose a locker location L = (x, y) such that L ∉ T and the sum of Manhattan distances from L to all houses is minimized. Return the minimal total distance and one optimal location. Discuss an efficient algorithm that leverages medians and how to handle cases where the unconstrained median lies on a tree cell.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Compute optimal locker placement with obstacles states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a list of `houses`, where `houses[i] = [xi, yi]` are the integer grid coordinates of the i-th house, and a list of `trees`, where `trees[j] = [xj, yj]` are the coordinates of tree cells. Tree cells are blocked: a locker cannot be placed on them. Choose a locker location `L = (x, y)` on the integer grid such that `L` is NOT a tree cell, and the sum of Manhattan distances from `L` to every house is minimized. The Manhattan distance between `(x, y)` and `(xi, yi)` is `|x - xi| + |y - yi|`. Return the minimal achievable total Manhattan distance. If `houses` is empty, return `0`. Key idea: because Manhattan cost separates into independent x- and y-terms, the unconstrained optimum is `(median(xs), median(ys))`. The cost surface is convex and separable, so when that median cell (or any candidate) is blocked by a tree, an optimal valid cell lies in the small band around the median/house/tree coordinates — checking that finite candidate set yields the true minimum.

Constraints

0 <= len(houses) <= 10^4
0 <= len(trees) <= 10^4
-10^6 <= xi, yi, xj, yj <= 10^6
A house and a tree may share the same cell; the locker still may not be placed on a tree cell.
If houses is empty, the answer is 0.

Examples

Input: ([[0,0],[0,4],[2,2]], [])

Expected Output: 6

Explanation: Median is (0, 2). No trees block it. Cost at (0,2) = (0+2) + (0+2) + (2+0) = 6.

Input: ([[0,0],[0,4],[2,2]], [[0,2]])

Expected Output: 7

Explanation: The unconstrained optimum (0,2) is now a tree. The cheapest non-tree cell (e.g. (1,2) or (0,1) or (0,3)) costs 7.

Input: ([[1,1],[1,1],[1,1]], [[1,1]])

Expected Output: 3

Explanation: All houses sit on (1,1), which is a tree, so the locker must move one step away. Any adjacent cell is distance 1 from each of the 3 houses: total 3.

Input: ([[5,5]], [])

Expected Output: 0

Explanation: A single house with no obstacle: place the locker on the house for distance 0.

Input: ([[0,0],[10,0],[0,10],[10,10]], [[5,5]])

Expected Output: 40

Explanation: Four symmetric corners. Any cell inside the bounding box gives total 40; the central tree at (5,5) doesn't increase the minimum since neighbors are equally optimal.

Input: ([[-3,-3],[3,3]], [[0,0]])

Expected Output: 12

Explanation: Negative coordinates. The whole box between the two points is optimal at cost 12; the tree at (0,0) is avoidable (e.g. (1,1) also costs 12).

Input: ([], [[1,1]])

Expected Output: 0

Explanation: No houses, so the total distance is 0 regardless of trees.

Hints

Manhattan distance is separable: the total cost = (sum over houses of |x - xi|) + (sum over houses of |y - yi|). Optimize the x-coordinate and y-coordinate independently.
Each one-dimensional sum |x - xi| is minimized when x is a median of the house x-coordinates (likewise for y). That gives the unconstrained optimum (median(xs), median(ys)).
The constraint is that the chosen cell can't be a tree. Because the cost grows monotonically as you move away from the median along each axis, an optimal valid cell is close to the median — check the median, the house coordinates, and the cells one step around them (and around trees) and take the cheapest non-tree cell.

Quick Overview