Spatial Indexing for Queries | Dataford Interview Questions

Implement a spatial indexing algorithm, such as a quadtree or R-tree, to efficiently query objects within a bounding box for Neara.

Use a quadtree for point objects. The function receives objects as dictionaries with unique id, x, and y fields, plus an inclusive bounding box [min_x, min_y, max_x, max_y]. Return matching IDs in their original input order. Define the function as def query_objects(objects, bbox):.

Constraints

0 <= len(objects) <= 100000
Each object has a unique string id and numeric x and y coordinates
bbox is [min_x, min_y, max_x, max_y] with min_x <= max_x and min_y <= max_y
Coordinates are finite numbers
A point belongs to the query when both coordinates are within the inclusive bounds
Return IDs in their original input order

Function Signature

def query_objects(objects, bbox):

Your question is Spatial Indexing for Queries. 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

Implement a spatial indexing algorithm, such as a quadtree or R-tree, to efficiently query objects within a bounding box for Neara.

Constraints

0 <= len(objects) <= 100000
Each object has a unique string id and numeric x and y coordinates
bbox is [min_x, min_y, max_x, max_y] with min_x <= max_x and min_y <= max_y
Coordinates are finite numbers
A point belongs to the query when both coordinates are within the inclusive bounds
Return IDs in their original input order

Function Signature

def query_objects(objects, bbox):

Your question is Spatial Indexing for Queries. 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.