Google Interview Question for Software Engineers


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 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

- bfmrck July 04, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Make

- Kanika Singhal November 27, 2019 | Flag Reply
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]};
}

}}

- Rajat.nitp June 30, 2020 | Flag Reply
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]};
}

- Rajat.nitp June 30, 2020 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More