Compute optimal locker placement with obstacles

Q: Compute optimal locker placement with obstacles

This question evaluates understanding of computational geometry and algorithmic optimization, focusing on Manhattan-distance minimization and handling forbidden cells (obstacles) on a 2D integer grid.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute optimal locker placement with obstacles

Overview

Comments (0)