Katkat
Back

Compute optimal locker placement with obstacles

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.