R-Tree Geospatial Partitioning | Dataford Interview Questions

Implement a rudimentary geospatial partitioning scheme using R-trees. Build a bulk-loaded R-tree over axis-aligned rectangles, then answer each axis-aligned rectangle query by returning the intersecting rectangle IDs in their original input order. Use inclusive intersection, so rectangles or boundaries that touch count as intersecting.

Input and Output

Implement spatial_queries(rectangles, queries). Each rectangle is [id, x1, y1, x2, y2], each query is [x1, y1, x2, y2], and coordinates satisfy x1 <= x2 and y1 <= y2. Return one list of IDs per query. An empty rectangle collection is valid.

Constraints

0 <= rectangles.length <= 5000
0 <= queries.length <= 5000
Each rectangle has the form [id, x1, y1, x2, y2]
Each query has the form [x1, y1, x2, y2]
Rectangle IDs are unique integers
Coordinates are integers in [-10^9, 10^9]
For every rectangle and query, x1 <= x2 and y1 <= y2
Intersection is inclusive at boundaries

Function Signature

def spatial_queries(rectangles, queries):

Your question is R-Tree Geospatial Partitioning. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Input and Output

Constraints

0 <= rectangles.length <= 5000
0 <= queries.length <= 5000
Each rectangle has the form [id, x1, y1, x2, y2]
Each query has the form [x1, y1, x2, y2]
Rectangle IDs are unique integers
Coordinates are integers in [-10^9, 10^9]
For every rectangle and query, x1 <= x2 and y1 <= y2
Intersection is inclusive at boundaries

Function Signature

def spatial_queries(rectangles, queries):

Your question is R-Tree Geospatial Partitioning. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.