## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

We can do this simply by augmenting a tree node with the total number of nodes in the sub-tree rooted by the given node.

Pseudo code for doing this is:

``````int Tree::countRange(int start, int end)
{
// step1. find common root node of start and end
Node *nroot = findCommonRoot(start, end);

if(!nroot)
return 0;

// step2. get the number of nodes rooted by nroot
int count = nroot->getNodeCnt();
// step3. subtract the nodes whose value is less than range start
count -= countSmallerNode(nroot, start);
// step4. subtract the nodes whose value is larger than range end
count -= countLargerNode(nroot, end);
return count;
}``````

The auxiliary method implementations are:

``````Node *Tree::findCommonRoot(int start, int end)
{
Node *nroot = dynamic_cast<Node*>(root);
while(nroot){
if(end < nroot->getValue())
nroot = nroot->getLeft();
else if(start > nroot->getValue())
nroot = nroot->getRight();
else
break;
}

return nroot;
}

int Tree::countSmallerNode(Node *nroot, int start)
{
int count = 0;
Node *cur = nroot;

while(cur){
if(start < cur->getValue()){ // take left
cur = cur->getLeft();
}
else {
// all left nodes are smaller
if(cur->getLeft()){
count += cur->getLeft()->getNodeCnt();
}

if(start == cur->getValue())
break;
// cur node is also smaller
count++;
// take right
cur = cur->getRight();
}
}

return count;
}

int Tree::countLargerNode(Node *nroot, int end)
{
int count = 0;
Node *cur = nroot;

while(cur){
if(end > cur->getValue()){ // take right
cur = cur->getRight();
}
else {
// all right nodes are larger
if(cur->getRight()){
count += cur->getRight()->getNodeCnt();
}
if(end == cur->getValue())
break;
// cur node is larger
count++;
// take left
cur = cur->getLeft();
}
}

return count;
}``````

Those are test results

``````[TREE]
8
-12                            14
-13              3             11
-15          -9              7
-10    -4     4
6

nodes in [-11, 5]: 5
nodes in [-16, -4]: 6
nodes in [-8, 1]: 1
nodes in [-9, 0]: 2
nodes in [6, 7]: 2
nodes in [3, 5]: 2
nodes in [-8, 12]: 7
nodes in [-3, 8]: 5
nodes in [-4, 8]: 6
nodes in [4, 2]: 0
nodes in [-15, 9]: 11
nodes in [-18, -6]: 5
nodes in [-2, 9]: 5
nodes in [-9, -5]: 1
nodes in [7, 9]: 2
nodes in [2, 12]: 6
nodes in [6, 13]: 4
nodes in [-9, -12]: 0
nodes in [9, 14]: 2
nodes in [-15, -8]: 5``````

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

At each node in the BST, store the order value at that node ( the 4th smallest node in the tree stores 4, the smallest stores 1, etc.) according to the ordering on the BST. Then, for a interval range (i,j), i <= j, navigate to the smallest element great than i. Let this element's order value be A. Navigate to the largest element less than j and let it's order value be B. Return B - A.

Note: If we use a balanced BST (Treap, AVL Tree) this solution is O(log(n)). Otherwise the solution is O(n).

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

Unlike the previous answer, this approach tries to optimize the search by not travelling to completely redundant sub-trees.For example, when range is 15-25 and our root is 10, searching left sub-tree would be a waste.

``````class Node:
def __init__(self,v):
self.v=v
self.left=None
self.right=None

def nodesInRange(a,b,root):
if root==None: return []

ans=left=right=[]
if a<=root.v<=b: ans=[root]
if root.v>a:
left=nodesInRange(a,min(root.v-1,b),root.left)
if root.v<b:
right=nodesInRange(max(root.v,a),b,root.right)
return ans+left+right``````

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

Unlike the previous answer, this approach tries to optimize the search by not travelling to completely redundant sub-trees. For example, when range is 15-25 and our root is 10, it would be a waste to search left sub-tree.

``````class Node:
def __init__(self,v):
self.v=v
self.left=None
self.right=None
def nodesInRange(a,b,root):
if root==None: return []

ans=left=right=[]
if a<=root.v<=b: ans=[root]
if root.v>a:
left=nodesInRange(a,min(root.v-1,b),root.left)
if root.v<b:
right=nodesInRange(max(root.v,a),b,root.right)
return ans+left+right``````

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

``````abstract class Tree {
int value;
}

class Node extends Tree{
Tree left;
Tree right;
}

class Leaf extends Tree {
}

void printNodesInRange(Tree t, int from /* inclusive */, int to /* inclusive */) {
// if this is a leaf node, then just test if value is within the range
if (t instanceof Leaf) {
if (t.value >= from && t.value <= to) {
println (t.value);
}
}
else {
Node n = (Node)t;
if (n.value < from) {
// search only right subtree
printNodesInRange(n.right, from, to);
}
else if (n.value > to) {
// search only left subtree
printNodesInRange(n.left, from, to);
}
else {
// search both left and right with divided range
printNodesInRange(n.left, from, n.value);
printNodesInRange(n.right, n.value, to);
}
}
}``````

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

O(n) simple in-order traversal with conditions solution

``````public static void CountNodesInRange(TreeNode tree, int low, int high, ref int count)
{
if (tree == null)
return;

if (tree.Value >= low)
CountNodesInRange(tree.Left, low, high, ref count);

if (tree.Value >= low && tree.Value <= high)
count++;

if (tree.Value <= high)
CountNodesInRange(tree.Right, low, high, ref count);``````

}

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

Can be solved using level order traversal in O(n) time.

``````private static int getCountBetweenRange(Node root, int min, int max){

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

Queue<Node> helperQueue = new LinkedList<Node>();

int count =0;

while(!helperQueue.isEmpty()){
Node temp = helperQueue.remove();

if(temp.data>= min && temp.data<=max){
count++;
}

if (temp.left != null) {
}

if (temp.right != null) {
}
}

return count;
}``````

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

1) Use DFS to find the given start element or next largest element (if given start element does not exist)
2) Keep traversing until you find the given last element (or previous smallest element, if the given end element does not exist)

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

Use segment tree to find the elements in the given range in O(log n) complexity.

Comment hidden because of low score. Click to expand.

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.