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

Question

## 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?

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

Question Details

Full Details

Topics

More from Palantir