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

- linuxchain August 10, 2016 | Flag Reply
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).

- naraink@andrew.cmu.edu August 05, 2016 | Flag Reply
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

- Shihab Shahriar August 01, 2016 | Flag Reply
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

- Shihab Shahriar August 01, 2016 | Flag Reply
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);
        }
    }
}

- jjongpark August 27, 2016 | Flag Reply
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);

}

- tryingtosolvemystery September 15, 2016 | Flag Reply
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>();
		helperQueue.add(root);
		
		int count =0;
		
		while(!helperQueue.isEmpty()){
			Node temp = helperQueue.remove();
			
			if(temp.data>= min && temp.data<=max){
				count++;
			}
			
			if (temp.left != null) {
				helperQueue.add(temp.left);
			}

			if (temp.right != null) {
				helperQueue.add(temp.right);
			}
		}
		
		return count;
	}

- kvdeshmukh1989 November 06, 2016 | Flag Reply
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)

- sanjogj43 November 17, 2016 | Flag Reply
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.

- sanjogj43 November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.


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