## Google Interview Question for Software Engineers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Make

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]};
}

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]};
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.