How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Quadtree for 2D Geospatial Points | Uber Coding Question

Quick Overview

This question evaluates the ability to design a spatial data structure, specifically a point quadtree, for storing and querying two-dimensional coordinates. It tests practical implementation skills around node subdivision, capacity thresholds, and handling edge cases like duplicate coordinates and boundary points. Such questions are common in coding interviews to assess data structure design and geospatial indexing knowledge.

Quadtree for 2D Geospatial Points

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Interview Round: Onsite

# Quadtree for 2D Geospatial Points Design and implement a **point quadtree** that stores geographic locations on a 2D plane and supports efficient axis-aligned rectangular range queries. Each stored location is a point `(x, y)` (for example, `x` = longitude, `y` = latitude) with an associated `data` payload. The tree is created over a fixed bounding box (the region that contains all valid points). Each internal node represents a rectangular region and is split into four quadrants — **NW, NE, SW, SE** — when it exceeds a capacity threshold. Implement the following operations: ### 1. `insert(x, y, data)` Insert a point at coordinates `(x, y)` carrying `data`. - A leaf node holds up to `CAPACITY` points (a constructor parameter). When inserting a point would make a leaf exceed `CAPACITY`, the leaf subdivides into its four quadrant children and its existing points are redistributed into the children before the new point is placed. - Inserting a point that lies outside the tree's bounding box returns `false` (not inserted); a successful insert returns `true`. - You must correctly handle **duplicate / overlapping points** (multiple points with identical `(x, y)`). Subdividing alone will never separate identical coordinates, so a leaf must be able to hold more than `CAPACITY` points when they are all coincident (i.e., do not recurse infinitely when points cannot be separated by further subdivision). ### 2. `query(rect) -> list` Given an axis-aligned query rectangle `rect` (specified by its min/max x and y, boundaries inclusive), return all stored `(x, y, data)` entries whose coordinates fall inside `rect`. - The search must **prune** entire subtrees whose region does not intersect `rect`, so that the cost is proportional to the number of nodes overlapping the query plus the number of points reported — not the total number of points in the tree. ### Required boundary semantics - A point lies inside a rectangle if `rect.minX <= x <= rect.maxX` and `rect.minY <= y <= rect.maxY`. - Define a single, consistent rule for assigning a point that lands exactly on a quadrant dividing line to one quadrant, and apply it in both `insert` and `query` so no point is lost or double-counted. ### Constraints & Notes - Coordinates are real numbers within the tree's bounding box. - Optimize for many inserts followed by many range queries. - Be prepared to discuss the tree's worst-case shape (e.g., heavily clustered or coincident points), how subdivision depth is bounded, and the time complexity of `insert` and `query` in the average versus worst case. ### Example ``` Tree bounds: [0, 0] to [10, 10], CAPACITY = 2 insert(1, 1, "a") -> true insert(2, 2, "b") -> true insert(8, 8, "c") -> true # leaf subdivides here insert(9, 9, "d") -> true insert(1, 1, "a2") -> true # duplicate coordinate of "a" insert(20, 5, "x") -> false # outside bounds query(rect = [0,0]..[3,3]) -> {(1,1,"a"), (2,2,"b"), (1,1,"a2")} query(rect = [7,7]..[10,10]) -> {(8,8,"c"), (9,9,"d")} ``` (Ordering of the returned points does not matter.)

Quick Answer: This question evaluates the ability to design a spatial data structure, specifically a point quadtree, for storing and querying two-dimensional coordinates. It tests practical implementation skills around node subdivision, capacity thresholds, and handling edge cases like duplicate coordinates and boundary points. Such questions are common in coding interviews to assess data structure design and geospatial indexing knowledge.

Design and implement a **point quadtree** over a fixed bounding box that stores 2D geographic points `(x, y)` with an associated `data` payload and answers axis-aligned rectangular range queries efficiently. Because the online judge drives your structure through a list of operations, implement a single function `solution(bounds, capacity, operations)`: - `bounds = [minX, minY, maxX, maxY]` is the region that contains all valid points. - `capacity` is the maximum number of points a leaf holds before it subdivides into its four quadrants **NW, NE, SW, SE**. - `operations` is a list where each op is one of: - `["insert", x, y, data]` -> return `True` if the point was inserted, `False` if `(x, y)` lies outside `bounds`. - `["query", minX, minY, maxX, maxY]` -> return every stored `[x, y, data]` whose coordinates fall inside the inclusive rectangle. Return a list with one result per operation (a `bool` for each insert, a list of `[x, y, data]` for each query; query result order does not matter). ### Requirements - **Subdivision:** when inserting a point would make a leaf exceed `capacity`, subdivide the leaf into NW/NE/SW/SE, redistribute its existing points into the children, then place the new point. - **Coincident points:** multiple points may share identical `(x, y)`. Subdividing can never separate them, so a leaf must be allowed to hold more than `capacity` coincident points — do **not** recurse infinitely. - **Boundary rule:** a point is inside a rectangle when `minX <= x <= maxX` and `minY <= y <= maxY`. Pick one consistent rule for points that fall exactly on a quadrant dividing line (e.g. `x >= midX` is East, `y >= midY` is North) and apply it in both insert and query so no point is lost or double-counted. - **Pruning:** a query must skip any subtree whose region does not intersect the query rectangle, so cost is proportional to overlapping nodes plus reported points — not the total point count. ### Example (bounds `[0,0]..[10,10]`, capacity `2`) ``` insert(1,1,"a") -> True insert(2,2,"b") -> True insert(8,8,"c") -> True # leaf subdivides here insert(9,9,"d") -> True insert(1,1,"a2") -> True # duplicate of "a" insert(20,5,"x") -> False # outside bounds query([0,0]..[3,3]) -> (1,1,"a"), (2,2,"b"), (1,1,"a2") query([7,7]..[10,10]) -> (8,8,"c"), (9,9,"d") ```

Constraints

Coordinates are real numbers lying within the tree's bounding box.
capacity >= 1.
A point exactly on a quadrant dividing line follows one consistent rule (here: x >= midX => East, y >= midY => North), applied in both insert and query.
Rectangle membership is inclusive on all four edges: minX <= x <= maxX and minY <= y <= maxY.
Duplicate/coincident points are permitted and must all be retained.
Optimize for many inserts followed by many range queries.

Examples

Input: ([0, 0, 10, 10], 2, [["insert", 1, 1, "a"], ["insert", 2, 2, "b"], ["insert", 8, 8, "c"], ["insert", 9, 9, "d"], ["insert", 1, 1, "a2"], ["insert", 20, 5, "x"], ["query", 0, 0, 3, 3], ["query", 7, 7, 10, 10]])

Expected Output: [True, True, True, True, True, False, [[1, 1, "a"], [1, 1, "a2"], [2, 2, "b"]], [[8, 8, "c"], [9, 9, "d"]]]

Explanation: The worked example. Leaf splits when the 3rd point (8,8) exceeds CAPACITY=2; the duplicate (1,1,"a2") is kept alongside (1,1,"a"); (20,5) is outside [0,0]..[10,10] so it returns False. Each query returns exactly the points inside its inclusive rectangle (order does not matter).

Input: ([0, 0, 4, 4], 1, [["insert", 2, 2, "p1"], ["insert", 2, 2, "p2"], ["insert", 2, 2, "p3"], ["query", 0, 0, 4, 4]])

Expected Output: [True, True, True, [[2, 2, "p1"], [2, 2, "p2"], [2, 2, "p3"]]]

Explanation: Three identical coordinates with CAPACITY=1. Subdividing can never separate coincident points, so the leaf is allowed to hold all three (no infinite recursion). The query over the whole box returns all three.

Input: ([0, 0, 10, 10], 2, [["insert", -1, 5, "o"], ["query", 0, 0, 10, 10], ["insert", 5, 5, "m"], ["query", 6, 6, 7, 7], ["query", 0, 0, 5, 5]])

Expected Output: [False, [], True, [], [[5, 5, "m"]]]

Explanation: x=-1 is outside the bounding box so the insert returns False. A query on an empty tree returns []. After inserting (5,5,"m"), a query over [6,6]..[7,7] misses it, while [0,0]..[5,5] includes it on the inclusive boundary.

Input: ([0, 0, 8, 8], 2, [["insert", 4, 4, "center"], ["insert", 1, 1, "a"], ["insert", 4, 1, "b"], ["query", 4, 0, 8, 4]])

Expected Output: [True, True, True, [[4, 1, "b"], [4, 4, "center"]]]

Explanation: Points land exactly on the dividing lines (x=4 / y=4). The rule 'x>=midX is East, y>=midY is North' sends (4,4) to NE and (4,1) to SE, and the same inclusive rule in query makes both appear for the rectangle [4,0]..[8,4] while (1,1,"a") is excluded.

Hints

Model each node by its rectangular region [minX, minY, maxX, maxY]; only leaves store points, and an internal node's points are pushed down to its children when it subdivides.
Compute the split point as midX = (minX+maxX)/2, midY = (minY+maxY)/2. Route a point with 'x >= midX => East' and 'y >= midY => North' into exactly one of NW/NE/SW/SE, and reuse the exact same rule when deciding which children a query rectangle overlaps.
To avoid infinite recursion on duplicates: before subdividing a full leaf, check whether every point in it (and the new one) share the same coordinate — if so, just keep them all in that leaf.
For query, first test whether the node's region intersects the query rectangle; if it doesn't, return immediately (prune) instead of descending.

Last updated: Jul 1, 2026

Loading coding console...