## Problem Design a spatial index that supports storing 2D points and efficiently answering proximity queries. Implement: ```python class SpatialIndex: def insert(self, point_id: str, x: float, y: float) -> None: ... def delete(self, point_id: str) -> None: ... def nearest(self, x: float, y: float, k: int) -> list[str]: ... def range_query(self, x1: float, y1: float, x2: float, y2: float) -> list[str]: ... ``` `nearest` returns the `k` closest point IDs by Euclidean distance. `range_query` returns all points within the given bounding box. ## Example ``` index.insert("A", 1.0, 2.0) index.insert("B", 3.0, 4.0) index.insert("C", 1.5, 2.5) index.nearest(1.0, 2.0, k=2) -> ["A", "C"] # closest two to (1,2) index.range_query(0, 0, 2, 3) -> ["A", "C"] # within bounding box ``` ## Follow-ups 1. Compare a grid-bucket approach vs. a k-d tree for this workload. When does each win? 2. How do you handle points clustered in a small area causing one bucket to dominate? 3. What changes if points are moving (e.g., tracking vehicles in real time)? 4. How would you scale this index to billions of points across multiple machines?

InterviewDB Question

Spatial Index: Implement a 2D Grid Index for Efficient Proximity Queries

Onsite

Question Details

Problem Design a spatial index that supports storing 2D points and efficiently answering proximity queries. Implement: nearest returns the k closest point IDs by Euclidean distance. range_query returns all points within the given bounding box. Example Follow-ups Compare a grid-bucket approach vs. a k-d tree for this workload. When does each win? How do you handle points clustered in a small area causing one bucket to dominate? What changes if points are moving (e.g., tracking vehicles in real ti…

Full Details

🔒

Unlock all Palantir questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a palantir interview during the onsite round.

It covers the following topics: Coding, Onsite, Matrix .

Topics

Coding Onsite Matrix

Spatial Index: Implement a 2D Grid Index for Efficient Proximity Queries

Question Details

Full Details

About This Question

Topics

More Palantir Interview Questions