Uber·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Uber coding round for a software engineer role, one question the whole time: build a quadtree from a 2D binary grid. Seemed straightforward at first but the recursion logic took a while to get right.

Questions Asked (1)

Design a Quadtree data structure and implement a function that builds one from a 2D binary array. Leaf nodes should be created when all values in a quadrant are identical; otherwise, split the region into four sub-quadrants recursively.

Algorithms & Data StructuresSystem Design

Author's notes

I got the node structure down pretty fast but then spent way too long second-guessing the base case.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and defining the Quadtree node structure. Then, describe a recursive divide-and-conquer algorithm that checks if a region is uniform; if not, split it into four quadrants and recurse. Finally, analyze the time and space complexity and discuss potential optimizations.

Pro tip: Mention that the time complexity is O(n^2) in the worst case but can be much better for uniform grids, and that the space complexity is proportional to the number of nodes. Also, note that the recursion depth is O(log n) for an n x n grid, which is important for stack safety.

1. Clarify requirements and constraints

Ask about the input size, whether the grid is square, and if the binary array can be modified. Confirm the definition of a leaf node and the expected output format.

2. Define the Quadtree node structure

Design a class or struct with fields: val (boolean for leaf), isLeaf (boolean), and children (array of four Quadtree nodes). For internal nodes, val can be arbitrary.

3. Design the recursive build function

Implement a function that takes the grid, and the top-left coordinates (row, col) and size of the current region. Check if all values in the region are the same; if so, create a leaf node. Otherwise, create an internal node and recursively build its four children.

4. Analyze complexity and discuss optimizations

Explain that the time complexity is O(n^2) in the worst case (e.g., checkerboard pattern) because each cell is visited once per level, and there are O(log n) levels. Space complexity is O(number of nodes). Mention that early termination when a region is uniform can reduce time.

5. Test with edge cases

Walk through examples: all zeros, all ones, a single cell, and a checkerboard pattern. Verify that the tree structure is correct and that leaf nodes are created appropriately.

Key Points to Mention

Recursive divide-and-conquer approach: split region into four quadrants when not uniform.
Node structure: isLeaf, val, and four children (topLeft, topRight, bottomLeft, bottomRight).
Time complexity: O(n^2) worst-case, but often better for uniform grids; space complexity O(number of nodes).
Use of a helper function to check uniformity of a region efficiently, possibly with prefix sums for optimization.
Handling of non-square grids or non-power-of-two sizes if applicable.
Potential follow-up: serialization/deserialization of the Quadtree or use in image compression.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.