Design Manhattan-distance meeting point finder

Q: Design Manhattan-distance meeting point finder

This question evaluates algorithmic problem-solving and data-structure design skills for geometric aggregation problems, focusing on properties of Manhattan distance, handling dynamic updates, and analyzing time/space complexity within the Coding & Algorithms domain.

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 an m×n grid with cells marked 1 for homes and 0 otherwise, choose a single meeting cell that minimizes the sum of Manhattan distances from all homes to that cell. Return both the minimal total distance and one optimal cell. Then extend the design to a dynamic setting that supports operations addHome(i, j), removeHome(i, j), and query() -> (cell, distance). What data structures would you use for the static and dynamic cases, and what are the time and space complexities? Discuss why your approach prefers medians over averages and how you would handle large sparse grids.

Design Manhattan-distance meeting point finder

Overview

Comments (0)