Groupon Interview Question for SDE1s

Country: India

Comment hidden because of low score. Click to expand.
2
of 6 vote

It can be easily done using recursion.

``````void countInsideRange(node *root, int min, int max, int* count)
{
if (root == NULL)
return;

countInsideRange(root->left, min, max, count);
countInsideRange(root->right, min, max, count);

if((root->key > min) && (root->key < max))
*count = *count + 1;

return;
}``````

The answer will be in integer count value.

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

return the integer value of that node which is ancestor to both

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I agree with your answer, but you are traversing whole tree. Why not skip a part of tree if it is either less than a OR greater than b ?

``````void countInsideRange(node *root, int min, int max, int* count)
{
if (root == NULL)
return;

if( (root->key < min) || (root->key > max) )
return;

if((root->key > min) && (root->key < max))
*count = *count + 1;

countInsideRange(root->left, min, max, count);
countInsideRange(root->right, min, max, count);

}``````

Comment hidden because of low score. Click to expand.
2

``````void countInsideRange(node *root, int min, int max, int* count)
{
if (root == NULL)
return;

if( root->key < min ) {
countInsideRange(root->right, min, max, count);
}else if( root->key > max ) {
countInsideRange(root->left, min, max, count);
}else if( (root->key >= min) && (root->key <= max) ) {
*count = *count + 1;
countInsideRange(root->left, min, max, count);
countInsideRange(root->right, min, max, count);
}else {
return;
}
}``````

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

I don't agree to the above idea of returning from a node after find that node outside range.

Consider a tree
10
| |
8 15
| | | |
7 9 13 16

and range (9,14).
With your algorithm, we will return from 8 without including 9 and similarly from 15 without including 13. :(

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

Following is one of the many ways to do this.

``````Take the inorder traversal. Since it is sorted you easily check the number of nodes having values between a and b.
O(n) where n is total number of nodes.``````

You can optimize the above if you count the node during traversal itself and reject the left child of nodes having values less than a and right child of nodes having values greater than b.

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

First find LCA of the Nodes.
return(LCA to Node1 distance + LCA to Node2 distance -1 )

Comment hidden because of low score. Click to expand.
-1
of 1 vote

What if the tree is not balanced?

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

Have a visitor which returns an int. If the current value is smaller than 'a', return the result of going right; if it's larger than 'b', return the result of going left.
If it's between the two, then go both ways and return the result of both added up plus one.

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

``````/**
* count the no of nodes in the  subtree rooted at root and containing n1 and n2.
*
*/
int countNodes(struct node* root)
{
int count=0;
if(!root)
return count;
else
{
count=countNode(root->left);
count=countNode(root->right);
count++;
}

return count;
}

int LCA(struct node* root, int n1, int n2)
{
if(root == NULL || root->data == n1 || root->data == n2)
return -1;

if((root->right != NULL) &&
(root->right->data == n1 || root->right->data == n2))
return root->data;
if((root->left != NULL) &&
(root->left->data == n1 || root->left->data == n2))
return root->data;

if(root->data > n1 && root->data < n2)
return countNodes(root->data);
if(root->data > n1 && root->data > n2)
return LCA(root->left, n1, n2);
if(root->data < n1 && root->data < n2)
return LCA(root->right, n1, n2);``````

}

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

void GetCount(struct Node *node,int a,int b,int &count)
{
if(!node || node->data<a || node->data>b)
return;
GetCount(node->left,a,b,count);
if(node->data>a && node->data<b)
count++;
GetCount(node->right,a,b,count);
}

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

Why not first find the lesser one of a and b, and then traverse in-order traversal and stop when greater one is found?

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

int count(int a, int b, BST t)
{
if (!t) { return 0; }
else if (t->key < i) {
return count (i, j, t->right);
}

else if (t->key > j) {
return count(i, j, t->left);
}

else {
return (1 + count(i, j, t->left) + count(i, j, t->right));
}
}

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

``````public static int countNodesInRange(Integer a, Integer b, TreeNode<Integer> root) {

if(root == null) {
return 0;
}

if(root.value > a && root.value < b) {
return 1 + countNodesInRange(a, b, root.left) + countNodesInRange(a, b, root.right);
} else if(root.value >= b) {
return countNodesInRange(a, b, root.left);
} else if(root.value <= a) {
return countNodesInRange(a, b, root.right);
} else {
return 0;
}
}``````

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

``````public static int countNodesInRange(Integer a, Integer b, TreeNode<Integer> root) {

if(root == null) {
return 0;
}

if(root.value > a && root.value < b) {
return 1 + countNodesInRange(a, b, root.left) + countNodesInRange(a, b, root.right);
} else if(root.value >= b) {
return countNodesInRange(a, b, root.left);
} else if(root.value <= a) {
return countNodesInRange(a, b, root.right);
} else {
return 0;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is to find least Common ancestor(LCA problem).

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

Could you please explain what has to be done after finding LCA

Comment hidden because of low score. Click to expand.
-1
of 1 vote

LCA

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.