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 difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

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

Build a QuadTree From a Grid | Uber Coding Question

Build a QuadTree From a Grid

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a compressed QuadTree for a square grid. You are given an `n x n` grid of values, where `n` is a power of two. The values are not limited to binary values; they may be any comparable type such as integers or strings. Define a QuadTree node with: - `value`: the value stored for a leaf region. For non-leaf nodes, this may be any placeholder value. - `isLeaf`: whether this node represents a uniform region. - `topLeft`, `topRight`, `bottomLeft`, `bottomRight`: child pointers, all `null` for a leaf node. Build and return the root of a compressed QuadTree using the following rules: 1. A region is represented by a leaf node if every cell in that region has the same value. 2. Otherwise, split the region into four equal quadrants and recursively build child nodes for each quadrant. 3. The root represents the entire grid. Example: Input: ```text [ [1, 1, 2, 2], [1, 1, 2, 2], [3, 3, 4, 4], [3, 3, 4, 4] ] ``` Output: an internal root node with four leaf children, whose values are `1`, `2`, `3`, and `4` for the top-left, top-right, bottom-left, and bottom-right quadrants respectively. Implement the data structure and the `buildQuadTree(grid)` function.

Quick Answer: This question evaluates understanding of spatial data structures and recursive divide-and-conquer techniques by compressing uniform regions into a QuadTree representation.

Given a non-empty `n x n` grid, where `n` is a power of two, build a compressed QuadTree for the whole grid. A region should be represented by a leaf node if every cell in that region has the same value. Otherwise, split the region into four equal quadrants and recursively build child nodes in this order: top-left, top-right, bottom-left, bottom-right. For deterministic judging, return the tree as a nested Python dictionary with exactly these keys: `value`, `isLeaf`, `topLeft`, `topRight`, `bottomLeft`, `bottomRight`. Rules for the returned structure: - Leaf node: `isLeaf` is `True`, `value` is the region's value, and all four child fields are `None`. - Internal node: `isLeaf` is `False`, `value` must be `None`, and all four child fields contain child nodes. You may implement a custom `Node` class internally if you want, but the final return value from `solution(grid)` must follow the nested dictionary format above.

Constraints

1 <= n <= 64
n is a power of two
Each row of `grid` has length `n`
Values support equality comparison

Examples

Input: ([[1, 1, 2, 2], [1, 1, 2, 2], [3, 3, 4, 4], [3, 3, 4, 4]],)

Explanation: Each 2 x 2 quadrant is uniform, so the root is an internal node with four leaf children holding values 1, 2, 3, and 4.

Input: ([[7, 7], [7, 7]],)

Expected Output: {'value': 7, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}

Explanation: The entire grid has the same value, so it compresses into a single leaf node.

Input: ([[-5]],)

Expected Output: {'value': -5, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}

Explanation: A single cell is always a uniform region, so the result is one leaf node.

Input: ([[1, 1, 2, 3], [1, 1, 2, 3], [4, 4, 5, 5], [4, 4, 5, 6]],)

Expected Output: {'value': None, 'isLeaf': False, 'topLeft': {'value': 1, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'topRight': {'value': None, 'isLeaf': False, 'topLeft': {'value': 2, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'topRight': {'value': 3, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'bottomLeft': {'value': 2, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'bottomRight': {'value': 3, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}}, 'bottomLeft': {'value': 4, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'bottomRight': {'value': None, 'isLeaf': False, 'topLeft': {'value': 5, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'topRight': {'value': 5, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'bottomLeft': {'value': 5, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}, 'bottomRight': {'value': 6, 'isLeaf': True, 'topLeft': None, 'topRight': None, 'bottomLeft': None, 'bottomRight': None}}}

Explanation: The top-left and bottom-left quadrants are uniform, but the top-right and bottom-right quadrants each require one more level of splitting.

Hints

Use divide-and-conquer recursion on square sub-regions of the grid.
Before splitting a region, scan it to check whether all cells are equal; as soon as you find a different value, you can stop and split.

Quick Overview

This question evaluates understanding of spatial data structures and recursive divide-and-conquer techniques by compressing uniform regions into a QuadTree representation.