Uber | SDE 2 Interview | Hard Question

I recently got a chance to interview with Uber for SDE 2 role. I faced a interesting and challenging question in Virtual Onsite round 1.

[QuadTree Compression of a Matrix]

Problem Statement

A QuadTree is a tree data structure in which each internal node is either a leaf node or has exactly four children. QuadTrees are often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.

Given an n x n matrix of integers, compress it using a QuadTree. A region can be compressed into a single value if all elements in that region are the same.

Example

Input:

|2 | 2 |3 |3| |2 | 2 |3 |3| |4 | 2 |5 |5| |2 | 3 |5 |5|

output:

| | | | 2 | 3 | | | | | 4 | 2 | 5 | | 2 | 3 | |

I gave recursive approach, using quadTree data structure, but interviewer doesnt seemed impressed. I got a rejection mail after a day.

Please feel free to post your solution in comments.