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.

Compute optimal locker placement with obstacles

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.

Hints

  1. 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.
  2. 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)).
  3. 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.

Loading coding console...