Uber | SDE 2 Interview | Hard Question
Summary
I interviewed with Uber for an SDE 2 role and encountered a challenging QuadTree compression problem during a virtual onsite round, ultimately receiving a rejection.
Full Experience
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.
Edit: Everyone is using GPT,Bard,etc to solve this problem. Just think of odd size case. Say 6 x 6 -> 3 x 3 -> (?) GPT sucks for such cases.
Follow up: What if given matrix is not square matrix ?
Interview Questions (1)
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 | |
Follow up: What if given matrix is not square matrix ?