## Google Interview Question for Site Reliability Engineers

Team: Google Engineering
Country: United States
Interview Type: Phone Interview

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

Similar to OP's but with an optimization.

``````long sumRange(Tree root, int max, int min) {
if (root == null) return 0;

long sum = 0;

if (root.Data >= min && root.Data <= max) sum+= root.Data;

if (root.Data > max)  {
return sum + sumRange(root.Left, min, max);
}

if (root.Data < min) {
return sum + sumRange(root.Right, min, max);
}

return sum+sumRange(root.Left, min, max) + sumRange(root.Right, min, max);
}``````

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

Bug: min and max are swapped when calling for sub-trees.

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

This is important to reduce the complexity to O(lgn) instead of O(n)

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

@Anonymous: No, the worst case is still Omega(n).

What if we had to print all of them? (or even n/2 of them?).

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

sum = print.

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

very good

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

``````// Follow the normal pre-order and decide which branch to take
void print_in_range_bst(struct TNode* node, int min, int max, int& sum=0)
{
if(root) {
if(root->data >= min && root->data<=max) {
cout<<root->data<<endl;
sum += root->data;
print_in_range_bst(root->left, min, max, sum);
print_in_range_bst(root->right, min, max, sum);
} else {

// Go right if root's data is smaller than min since all nodes in the left will be smaller than min too.
if(root->data < min) {
print_in_range_bst(root->right, min, max, sum);
}

// Go left if root's data is greater than max since all nodes in the right will be greater than max too.
if(root->data > max) {
print_in_range_bst(root->left, min, max, sum);
}
}
}
}``````

complexity depends on the range and given nodes in the BST.
But on average would save a lot of unnecessary work since we are preventing those branches.

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

``````public int sumRange(Node root, int min, int max) {
if (root == null) return 0;

a = root.value;
if (min <= a && a <= max) {
return a + sumRange(root.left, min, max) + sumRange(root.right, min, max);
else if (a < min)
return sumRange(root.right, min, max);
else if (a > max)
return sumRange(root.left, min, max);
}

}``````

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

int rangeSum(Node root, int max, int min) {
int sum = 0;
if(root == null) return 0;
if (root.data > min && root.data < max) sum = root.data;
return sum + rangeSum(root.left,max, min) + rangeSum(root.right,max,min);
}

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

Does this work?

- Do recursive Depth First Search on the tree.

- Don't visit the left subtree if node.data < min.

- Don't visit the right subtree if node.data > max.

- if node.data is between min and max add it to sum.

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

``````int rangesum(tree *root, int max, int min)
{
if(!root)
return 0;

if (max < min)
return 0;

if(min == root->data && max == root->data)
return root->data;
if(min<=root->data && root->data <=max)
return (root->data + rangesum(root->left) + rangesum(root->right));
if(min < root->data && max < root->data)
return (rangesum(root->left));
if(min>root->data && max>root->data)
return (rangesum(root->right));

return 0;
}``````

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

``````/* Assuming that the range is inclusive*/
long sumRange(Tree *root, int min, int max)
{
int sum = 0;

/*Error checking*/
if (min > max) {
return 0;
}

/* Base case */
if (root == NULL) {
return 0;
}

if (root->data >=min && root->data <= max) {
sum += root->data;
return (sum + sumRange(root->left, min, max) + sumRange(root->right, min, max));
}
if (root->data > max) {
return sumRange(root->left, min, max);
}
/* Don't really need this if check below - as this is the only condition applicable.
* Left here for clarity.
*/
if (root->data < min) {
return sumRange(root->right, min, max);
}

/* Should not reach here */
return -1;

}``````

}

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

Do inorder traversal ...find the least key......than start adding the values untill the max term of the given range arrive....

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

nice answer.. :)

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

excellent :)

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

``````#include<stdio.h>
#include<stdlib.h>

typedef struct tree
{
int a;
struct tree* left;
struct tree* right;
}TREE;

TREE* addNode(TREE* node, int val)
{
if(node==NULL)
{
node=(TREE*)malloc(sizeof(TREE));
node->a=val;
node->left=NULL;
node->right=NULL;
}
else if(val<=node->a)
node->left=addNode(node->left,val);
else if(val>node->a)
node->right=addNode(node->right,val);

return node;
}

void printInorder(TREE* head)
{
if(head==NULL)
return;

printInorder(head->left);
printf(" %d ",head->a);
printInorder(head->right);

}

int sum;

void printSum(TREE* head,int min,int max)
{
if(head==NULL)
return;

printSum(head->left,min,max);
if(head->a>min&&head->a<max)
sum+=head->a;
printSum(head->right,min,max);

}

int main()
{
int arr[]={2,5,9,7,6,-1,0,10,23,12,15,18,14,3,1};
int i;
TREE* head=NULL;

for(i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
head=addNode(head,arr[i]);

printInorder(head);
printf("\n");

int min=5,max=11;

printSum(head,min,max);
printf("%d\n",sum);

return 0;
}``````

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

inorder traversal will find the sum but here we are not pruning unnecessary paths and not using the BST property.

So for this questions using full inorder traversal is an overkill but ofcourse an approach to tell your interviewer.

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

Thanks for your input

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

``````package One;

public class SumTree{
public static void main(String[] args) {
Tre t=new Tre(5);
t.left=new Tre(3); t.right=new Tre(7);
t.left.left=new Tre(2); t.left.right=new Tre(4); t.right.left=new Tre(6); t.right.right=new Tre(8);
int sum=t.getSumBetween(-1, 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
System.out.println(sum);
}

}

class Tre{

int value;
Tre left;
Tre right;

public Tre(int v)
{
value=v;
}

public int getSumBetween(int givenMin,int givenMax,int Min,int Max)
{
System.out.println(this.value);
int s=0;
int sleft=0;
int sright=0;

if(givenMin>Max || givenMax<Min || this==null)
{
return 0;
}

if(this.value >=givenMin && this.value<=givenMax)
{
s=this.value;
if(this.left!=null)
{
sleft=this.left.getSumBetween(givenMin,givenMax,Min,this.value);
}

if(this.right!=null)
{
sright=this.right.getSumBetween(givenMin, givenMax, this.value, Max);
}

s=s+sleft+sright;
}

return s;
}
}``````

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

Just go through every node to see if its value is between min and max.

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

int findRange(TreeNode *root, int max, int min)
{
if(root==NULL) return 0;

if(root->value>=min && root->value<=max)
return a+findRange(root->left,max,min)+findRange(root->right,max,min);
if(root->value<min)
return findRange(root->right,max,min);
if(root->value>max)
return findRange(root->left,max,min);

}

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