Design Manhattan-distance meeting point finder
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Quick Answer: 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.
Return one median meeting cell and the minimal total Manhattan distance for all homes in a grid.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,0,0],[0,0,1],[0,1,0]],)
Expected Output: [[1, 1], 4]
Explanation: Median row and column minimize Manhattan distance.
Input: ([[0,0]],)
Expected Output: [None, 0]
Explanation: No homes returns None and zero distance.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.