Intersection of Two Quadtrees | tech::interview
Given a quadtree structure:
1
2
3
4
5
|
struct QuadNode {
QuadNode(int num_ones = 0) : ones(num_ones) {}
int ones{ 0 };
QuadNode* child[4]{ nullptr };
};
|
- Please build a quadtree to represent a 0-1 matrix, assume the matrix is a square and the dimension is power of 2.
- Given two such quadtrees with same depth, please write a function to calculate how many 1s are overlapped.
For example:
1
2
3
4
5
6
7
|
Matrix 0:
0 1
1 1
Matrix 1:
0 0
1 1
|
Your function should return 2.
四叉树多次出现在G家的onsite面经中，构建0-1矩阵和求交集则属于频率比较高也比较简单的考查方式。
注意在计算交集的时候，如果比较的两个节点有一个节点的ones等于0，则该子树可以直接砍掉，这就是四叉树的高效之处。
题目很简单，直接上代码。
Build tree代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
QuadNode* build_tree(const vector<vector<int>>& mat) {
if(mat.empty()) return nullptr;
function<QuadNode*(int,int,int)> build = [&](int size, int row, int col) {
if (size == 1) return new QuadNode(mat[row][col]);
auto root = new QuadNode();
size /= 2;
int sub_coords[4][2] = {{row, col},{row + size, col},
{row, col + size},{row + size, col + size}};
for(int i = 0; i < 4; ++i) {
root->child[i] = build(size, sub_coords[i][0], sub_coords[i][1]);
root->ones += root->child[i]->ones;
}
return root;
};
return build((int)mat.size(), 0, 0);
}
|
Calculate intersection代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
int intersections(QuadNode *t0, QuadNode *t1) {
function<int(QuadNode*,QuadNode*,int)> solve = [&](QuadNode *tree0, QuadNode* tree1, int sum) {
if(!tree0 || !tree1 || !tree0->ones || !tree1->ones)
return 0;
int ret = sum;
if (!tree0->child[0] && !tree1->child[0]) {
ret += tree0->ones && tree1->ones ? 1 : 0;
} else {
for(int i = 0; i < 4; ++i)
ret += solve(tree0->child[i], tree1->child[i], sum);
}
return ret;
};
return solve(t0, t1, 0);
}
|
Read full article from
Intersection of Two Quadtrees | tech::interview
