Google Interview Question
Software EngineersCountry: United States
The logic of the problem is a mere extension of the diameter of the tree. We will apply the same dp state as that of diameter with additional check of if the current node has same color as that children.
{{
int finalAns = 0;
pair<int, int> foobar(int[][] tree, int[] col, int root, int parent) {
vector<int> childDiameters;
for(int node : tree[root]) {
if(node != parent) {
continue;
}
pair<int, int> colorDiameter = foobar(tree, col, node, root);
int color = colorDiameter.first;
int diameter = colorDiameter.second;
if(color == col[root]) {
childDiameters.push_back(diameter);
}
}
sort(childDiameters.rbegin(). childDiameters.rend());
int ans = 0;
for(i = 0; i < min(2, childDiameters.size()); ++i) {
ans += childDiameters[i];
}
finalAns = max(finalAns, ans + 1);
return {col[root], childDiameters.size() == 0 ? 0 : childDiameters[0]};
}
}}
The logic of the problem is a mere extension of the diameter of the tree. We will apply the same dp state as that of diameter with an additional check of if the current node has the same color as that children.
int finalAns = 0;
pair<int, int> foobar(int[][] tree, int[] col, int root, int parent) {
vector<int> childDiameters;
for(int node : tree[root]) {
if(node != parent) {
continue;
}
pair<int, int> colorDiameter = foobar(tree, col, node, root);
int color = colorDiameter.first;
int diameter = colorDiameter.second;
if(color == col[root]) {
childDiameters.push_back(diameter);
}
}
sort(childDiameters.rbegin(). childDiameters.rend());
int ans = 0;
for(i = 0; i < min(2, childDiameters.size()); ++i) {
ans += childDiameters[i];
}
finalAns = max(finalAns, ans + 1);
return {col[root], childDiameters.size() == 0 ? 0 : childDiameters[0]};
}
since its a tree if we disconnect a tree by removing a node we will still get a tree so if connect only node with same lable we will get a collection of tree for each such tree we have to find its diameter
- bfmrck July 04, 2019