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

- Loler September 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous September 25, 2012 | Flag
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)

- Anonymous September 27, 2012 | Flag
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?).

- Loler. September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sum = print.

- Anonymous September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

very good

- shashi shankar bharti September 27, 2012 | Flag
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.

- mr September 28, 2012 | Flag
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);
}
    

}

- Tim September 26, 2012 | Flag Reply
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);
}

- bicepjai September 25, 2012 | Flag Reply
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.

- amir September 25, 2012 | Flag Reply
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;
}

- code_monkey September 26, 2012 | Flag Reply
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;

}

}

- c_p_i_o September 26, 2012 | Flag Reply
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....

- Anonymous September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice answer.. :)

- Anonymous September 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent :)

- apr April 02, 2014 | Flag
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;
}

- okaysh September 27, 2012 | Flag Reply
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.

- mr September 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for your input

- okaysh September 28, 2012 | Flag
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;
	}
}

- Deepak Gupta October 13, 2012 | Flag Reply
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.

- Another Humble Programmer October 29, 2012 | Flag Reply
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);


}

- this is not tough January 24, 2014 | 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