Google Interview Question for SDETs


Country: United States




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

Is it possible to store additional data with tree node? If so, we can store "count" field in the node that holds the number of elements in the subtree including this element. Then the algorithm can be:
1. Find the node A where x <= A <= y.
2. Find the biggest node that is less than x in the A->left subtree. Lets call it LBorder.
3. Find the smallest node that is greater than y int the A->right subtree. Lets call it RBorder.
4. The result is: A->count - LBorder->count - RBorder->count.

The complexity is O(log N).
If it is not possible to store additional info I am afraid the complexity cannot be better than O(N), but it's quite easy and not interesting :).

- Ivan April 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Referring to above solution, LBorder value may or may not be the top node of subtree having all the values less than x and similarly RBorder value may or may not be the top most node of subtree holding all values larger than y. Above algorithm will fail in this scenario.

Worst case complexity of this solution is O(n), but it may take much less time depending on tree structure.

public static void parseTree(Node n, int start, int end, int count) {
		if(node == null)
			return;
		if(node.value < start)
			parseTree(n.right, start, end, count);
		else if(node.value > end)
			parseTree(n.left, start, end, count);
		else {
			count++;
			parseTree(n.left, start, end, count);
			parseTree(n.right, start, end, count);
		}
	}

- rit April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rit, could you provide an example where the algorithm fails?

I provide my examples. In a BST bellow each node contains a number and count in braces.

____________8(10)____________
        |                             |
    ____4(6)____                 ____10(3)____
   |            |               |             |
  _2(3)_        6(2)_           9(1)          12(1)
 |      |            |
 1(1)   3(1)         7(1)

Some test cases:
[x, y]: [2, 6]
A: 4(6)
LBound: 1(1)
RBound: 7(1)
Result: 6-1-1=4

[x, y]: [2, 12]
A: 8(10)
LBound: 1(1)
RBound: NULL
Result: 10-1-0=9

- Ivan April 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

____________8(10)____________
        |                             |
    ____4(6)____                 ____10(3)____
   |            |               |             |
 2(3)_        6(2)_           9(1)          12(1)
          |            |
         3(1)         7(1)

I think your approach fails at Test Case:
[x,y] = [3,6]

Your solution considers node 2's count to be excluded from the result, but node 3 should be included.

- atb April 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

____________8(10)____________
        |                             |
    ____4(6)____                 ____10(3)____
   |            |               |             |
 2(3)_        6(2)_           9(1)          12(1)
          |            |
         3(1)         7(1)

I think your approach fails at Test Case:
[x,y] = [3,6]

Your solution considers node 2's count to be excluded from the result, but node 3 should be included.

- atb April 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you are not allowed to add data to the node. head node is given and you have read only access

- solxget May 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

function bfs(G, v, x, y) {
	var Q = [];
	var S = [];
	var count = 0;
	Q.enqueue = Q.unshift
	Q.dequeue = Q.pop;
	
	Q.enqueue(v);
	v.visited = true;
	while (Q.length) {
		v = Q.dequeue();
		if (v.left && !v.left.visited) {
			if (v.value > x) {
				Q.enqueue(v.left);
			}
			v.left.visited = true;
		} 
		if (v.right && !v.right.visited) {
			if (v.value <  y) {
				Q.enqueue(v.right);
			}
			v.right.visited = true;
		}
		S.push(v);
	}

	while (S.length) {
		v = S.pop();
		var left = !v.left;
		if (v.left) {
			left = v.left.value  >  x && v.left.itCounts;
		}
		var right = !v.right;
		if (v.right) {
			right = v.right.value < y && v.right.itCounts;
		}

		v.itCounts = left && right;
		if (!v.left && !v.right) {
			if (v.value <= x || v.value >= y) {
			        v.itCounts = false;
			}
		}
		if (v.itCounts) {
			count++;

		}
	}
	return count;
}

var Node = function (value) {
	this.value = value;
};

var four = new Node(4);
var two = new Node(2);
var seven = new Node(7);
var one = new Node(1);
var three = new Node(3);
var five = new Node(5);
var six = new Node(6);
four.left = three;
two.right = four
two.left = one;
five.left = two;
seven.left = six;
five.right = seven;
console.log(bfs(null, five, 0, 5));

- srterpe May 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

/// <solution>
/// For each node , if we know right and left sub tree satisfy the criteria, we increment the count.
/// If self node also satisfy the criteria we retun true to parent node to account that for counting
/// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
/// If the min and max value are in the range [x,y] we increase count by one.
/// If self value is in range of [x,y] return true to parent that we all are in range
///
/// </solution>

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Testyourskills
{
    /// <summary>
    /// Problem:
    /// Given a Binary search tree of integer values, return the count of nodes where
    /// all the nodes under that sub-tree lies between a given range [x, y]. 
    /// Assume there are more than 100,000 nodes
    /// </summary>
    /// 
    /// <solution>
    /// For each node , if we know right and left sub tree satisfy the criteria, we increment the count. 
    /// If self node also satisfy the criteria we retun true to parent node to account that for counting
    /// Algoritham: Traverse each node's left and right child recursively to know the min Left child and max Right child value.
    /// If the min and max value are in the range [x,y] we increase count by one.
    /// If self value is in range of [x,y] return true to parent that we all are in range
    /// 
    /// </solution>
    /// <author>
    /// Pramod Kumar Chandoria
    /// </author>
    public class BSTNodeCountByRange
    {
        public static int CountNodeBySubTreeValueInGivenRange(Node tree, int minRange, int maxRange)
        {
            int count = 0;
            recusiveCountNode(tree, minRange, maxRange, ref count);
            return count;
        }

        private static bool recusiveCountNode(Node tree, int minRange, int maxRange, ref int count)
        {
            if (tree == null)
            {
                return true;
            }
            bool isLeft = recusiveCountNode(tree.left, minRange, maxRange, ref count);
            bool isRight = recusiveCountNode(tree.right, minRange, maxRange, ref count);
            if ( isLeft && isRight)
            {
                if (tree.left != null || tree.right != null) // This check to avoid counting leaf nodes
                {
                    count++;
                }
                if (tree.data >= minRange && tree.data <= maxRange)
                {
                    return true;
                }
            }
            return false;
        }

        public static void Main(string[] args)
        {
            var count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(null, 100, 100);
            Console.WriteLine("Null tree expected count 0, actual count is:" + count);

            Node tree = new Node(5);
            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
            Console.WriteLine("Tree with only 1 node (5) for range [1,3], expected 0, actual count  is:" + count);

            tree = new Node(4);
            tree.left = new Node(2);
            tree.right = new Node(6);
            tree.left.left = new Node(1);
            tree.left.right = new Node(3);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 3);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,3], expected 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 1, 6);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 6, 6);
            Console.WriteLine("Tree (Preorder 4,2,1,3,6) with range [1,6], expected 0, actual count  is:" + count);

            tree = new Node(20);
            tree.left = new Node(10);
            tree.right = new Node(25);
            tree.left.left = new Node(5);
            tree.left.right = new Node(16);
            tree.left.right.left = new Node(14);
            tree.left.right.right = new Node(18);

            tree.right.left = new Node(24);
            tree.right.right = new Node(30);
            tree.right.right.left = new Node(28);
            tree.right.right.right = new Node(40);
            tree.right.right.right.left = new Node(35);
            tree.right.right.right.right = new Node(45);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 24, 45);
            Console.WriteLine("Tree with range [24, 45], expected count is 3, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 35, 45);
            Console.WriteLine("Tree with range [35, 45], expected count is 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 14,18);
            Console.WriteLine("Tree with range [14, 18], expected count is 1, actual count  is:" + count);

            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 5, 18);
            Console.WriteLine("Tree with range [5, 18], expected count is 2, actual count  is:" + count);
            count = BSTNodeCountByRange.CountNodeBySubTreeValueInGivenRange(tree, 4, 46);
            Console.WriteLine("Tree with range [4, 46], expected count is 6, actual count  is:" + count);

 
        }
    }

    public class Node
    {
        public Node(int data)
        {
            this.data = data;
            left = right = null;
        }

        public Node left;
        public Node right;
        public int data;
    }
}

- pc May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

public int countNodesBetweenRange(NodeB root, int l, int r) {
	if (root == null) {
		return 0;
	} else if (root.val >= l && root.val =< r) {
		return 1 + countNodesBetweenRange(root.left, l, r) +
				countNodesBetweenRange(root.right, l, r);
	} else if (root.val < l) {
		return countNodesBetweenRange(root.right, l, r);
	} else if (root.val > r) {
		return countNodesBetweenRange(root.left, l, r);
	}		
	return 0;
}

- guilhebl April 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why have you added last 2 else if conditions?

- varun April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Imagine you want to search all nodes between range 4 - 6 , you start from Root of tree, it's value is 3, so now you know the only possible nodes between that range must be in the right side, if there are any, so return any counts you can find starting from the right child. The other case is the opposite, it's when the range is lower than the current root's value, so only possible nodes remains in the left side.

- guilhebl April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For the last two else conditions, is it not sufficient to check root.val < l for the first and root.val > r for the second? Since l <= r.

- JW April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@JW You're right no need for the additional (v < l && v < r ) and ( v > l && v > r ) checks since we always will have l < r

- guilhebl April 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I checked for root.val == l and root.val == r as well as 4 other conditions your code would be a bit faster. I like your optimization I think it has a valuable lesson for us all.

- DR A.D.M May 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

the problem indicates that there are more than 100,000 so using recursive call may cause stack overflow , so I am using a stack to do inorder traverse , the time complexity is O(n)

public int getRange (TreeNode root, int x, int y){
		int c = 0 ;
		Stack<TreeNode> stack = new Stack<> ();
		TreeNode cur = root ;
		while (!stack.isEmpty() || cur != null) {
			if (cur != null) {
				stack.push(cur) ;
				cur = cur.left ;
			} else {
				TreeNode tmp = stack.pop() ;
				if (tmp.val >= x && tmp.val <= y) {
					c++;
				}
				cur = tmp.right ;
			}
		}
		return c ;

}

- Scott April 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You're going to end up spending a linear amount of memory in both recursive and stack versions. I believe the memory footprint would be roughly equal.

- Anonymous April 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you can put the additional condition (tmp.val >= x && tmp.val <= y) in while loop itself and let increment the counter at each push operation , this will reduce the unnecessary nodes traversal till the end.

- sonia April 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But stack memory << main memory.

Stack memory can be around 64Kb per thread while main memory can be 4 Gb.

- ac_rocker85 May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ac_rocker85, can you give a reference for stack and main memory explanation?

- Max July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

this will only enter the element that are in range on the stack

stack <TreeNode> s;
TreeNode temp = rootNode;
int sum = 0;
int nodeCount = 0;
while(!s.empty() || temp != null)
{
while(temp != null)
{
if(temp.data >= x && temp.data <= y)
{
nodeCount++;
sum=sum+temp.data;
if(temp.rightNode != null)
{
s.push(temp.rightNode);
}
temp=temp.leftNode;
}
else if(temp.data < x)
{
temp=temp.rightNode;
}
else if (temp.data >y)
{
temp=temp.leftNode;
}
}
if(!s.empty())
{
temp = s.top();
s.pop();
}
}
}

- crazysea13 April 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stack>
using namespace std;

template <class T>
class Node{
	public:
		Node *left, *right;
		T value;
		Node(T v):value(v),left(NULL),right(NULL) {}
};

template <class T>
int countNodesInRange(Node<T> *root, T l, T r)
{
	if(root == NULL)
		return 0;
		
	stack<Node<T>*> s;
	int count = 0;
	
	s.push(root);
	while(!s.empty())
	{
		Node<T>* temp = s.top(); 
		s.pop();
		
		if(temp->value >= l && temp->value <= r)
		{
			count++;
			if(temp->right != NULL)
			{
				s.push(temp->right);
			}
			if(temp->left != NULL)
			{
				s.push(temp->left);
			}
		}
		else if(temp->value < l)
		{	
			if(temp->right != NULL)
			{
				s.push(temp->right);
			}
		}
		else if (temp->value > r)
		{
			if(temp->left != NULL)
			{
				s.push(temp->left);
			}
		}
	}
	
	return count;
}

int main() {

	Node<int> A(5),B(3),C(7);
	A.left = &B;
	A.right = &C;
	
	cout << "[1,9]=" << countNodesInRange(&A,1,9) << endl;
	cout << "[1,6]=" << countNodesInRange(&A,1,6) << endl;
	cout << "[4,9]=" << countNodesInRange(&A,4,9) << endl;
	cout << "[4,6]=" << countNodesInRange(&A,4,6) << endl;
	cout << "[1,4]=" << countNodesInRange(&A,1,4) << endl;
	cout << "[6,9]=" << countNodesInRange(&A,6,9) << endl;
	cout << "[1,2]=" << countNodesInRange(&A,1,2) << endl;
	cout << "[8,9]=" << countNodesInRange(&A,8,9) << endl;
	
	return 0;
}

- Anonymous May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <stack>
using namespace std;

template <class T>
class Node{
	public:
		Node *left, *right;
		T value;
		Node(T v):value(v),left(NULL),right(NULL) {}
};

template <class T>
int countNodesInRange(Node<T> *root, T l, T r)
{
	if(root == NULL)
		return 0;
		
	stack<Node<T>*> s;
	int count = 0;
	
	s.push(root);
	while(!s.empty())
	{
		Node<T>* temp = s.top(); 
		s.pop();
		
		if(temp->value >= l && temp->value <= r)
		{
			count++;
			if(temp->right != NULL)
			{
				s.push(temp->right);
			}
			if(temp->left != NULL)
			{
				s.push(temp->left);
			}
		}
		else if(temp->value < l)
		{	
			if(temp->right != NULL)
			{
				s.push(temp->right);
			}
		}
		else if (temp->value > r)
		{
			if(temp->left != NULL)
			{
				s.push(temp->left);
			}
		}
	}
	
	return count;
}

int main() {

	Node<int> A(5),B(3),C(7);
	A.left = &B;
	A.right = &C;
	
	cout << "[1,9]=" << countNodesInRange(&A,1,9) << endl;
	cout << "[1,6]=" << countNodesInRange(&A,1,6) << endl;
	cout << "[4,9]=" << countNodesInRange(&A,4,9) << endl;
	cout << "[4,6]=" << countNodesInRange(&A,4,6) << endl;
	cout << "[1,4]=" << countNodesInRange(&A,1,4) << endl;
	cout << "[6,9]=" << countNodesInRange(&A,6,9) << endl;
	cout << "[1,2]=" << countNodesInRange(&A,1,2) << endl;
	cout << "[8,9]=" << countNodesInRange(&A,8,9) << endl;
	
	return 0;
}

- Anonymous May 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess we need to read the problem again. All nodes in that subtree should be in range.
Here is my code that returns 3 for this example with range[2,6] (which I believe is the right answer).
____________8_____________
| |
___5____ ______10____
| | | |
_3_ 6_ 9 12
| | |
2 4 7

public class SameInorder {
	static int count;
	static int start;
	static int end;

	private static boolean inRange(Node root) {
		if (root == null)
			return true;
		if ((int) root.data > end) {
			if (root.left == null && root.right == null)
				return false;
			return inRange(root.left);
		}
		if ((int) root.data < start) {
			if (root.left == null && root.right == null)
				return false;
			return inRange(root.right);
		} else {
			boolean r = inRange(root.right);
			boolean l = inRange(root.left);
			if (r && l) {
				count++;
				return true;
			}
			return false;
		}

	}

	public static void main(String[] args) {

		count = 0;
		start = 2;
		end = 6;

		Node tree = new Node(8);
		{
			tree.setLeft(5);
			{
				tree.left.setLeft(3);
				{
					tree.left.left.setLeft(2);
					tree.left.left.setRight(4);
				}
				tree.left.setRight(6);
				{
					tree.left.right.setRight(7);
				}
			}
			tree.setRight(10);
			{
				tree.right.setRight(12);
				tree.right.setLeft(9);
			}
		}
		if (inRange(tree))
			count++;

		System.out.println(count);

	}
}

- Nasim May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we need to read the question again. All nodes in subtree of counting nodes should be in range. Here is my code that returns 3 for this tree with range[2,6] which I believe is the right answer:
____________8____________
| |
__5____ ____10____
| | | |
_ 3_ 6_ 9 12
| | |
2 4 7

Code:

public class SameInorder {
	static int count;
	static int start;
	static int end;

	private static boolean inRange(Node root) {
		if (root == null)
			return true;
		if ((int) root.data > end) {
			if (root.left == null && root.right == null)
				return false;
			return inRange(root.left);
		}
		if ((int) root.data < start) {
			if (root.left == null && root.right == null)
				return false;
			return inRange(root.right);
		} else {
			boolean r = inRange(root.right);
			boolean l = inRange(root.left);
			if (r && l) {
				count++;
				return true;
			}
			return false;
		}

	}

	public static void main(String[] args) {

		count = 0;
		start = 2;
		end = 6;

		Node tree = new Node(8);
		{
			tree.setLeft(5);
			{
				tree.left.setLeft(3);
				{
					tree.left.left.setLeft(2);
					tree.left.left.setRight(4);
				}
				tree.left.setRight(6);
				{
					tree.left.right.setRight(7);
				}
			}
			tree.setRight(10);
			{
				tree.right.setRight(12);
				tree.right.setLeft(9);
			}
		}
		if (inRange(tree))
			count++;

		System.out.println(count);

	}
}

- nasim May 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The right tree:

____________8____________
        |                             |
    __5____            ____10____
   |            |               |             |
_ 3_        6_           9          12
|        |          |
2       4         7

- nasim May 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose, we are allowed to precompute & strore some info in the tree data struct.
Once done, we can handle many queries with O(logN) time.
We precompute the # of inorder successors for each node. This could be done
with postorder traversal:

struct node {
    int val;        // BST value
    int sum;        // # of inorder successors
    node *left;     // children
    node *right;
};

// returns # nodes in a subtree
//! for each node compute the number of inorder successors in the tree
int inorder_sum(node *x, int right_sum) {

    if(x == 0)
        return 0;
    int tmp = inorder_sum(x->right, right_sum);
    x->sum = tmp + 1 + right_sum;

    tmp += inorder_sum(x->left, x->sum);
    return tmp + 1;
}

inorder_sum(root, 0);

Then, for each "range query" we just need to find 2
nodes 'xleft' and 'xright' that mark the boundaries of the given interval [vmin; vmax]:

node *xleft = 0, *xright = 0;

void find_subtree(node *x, int vmin, int vmax) {

    if(x == 0)
        return;
    
    if(vmin <= x->val && x->val <= vmax) {
        // we know that this node lies within the interval =>
        // could improve the bounds if needed
        if(xleft == 0 || xleft->val > x->val)
            xleft = x;
            
        if(xright == 0 || xright->val < x->val)
            xright = x;
        
        find_subtree(x->left, vmin, x->val);
        find_subtree(x->right, x->val, vmax);
        
    } else if(x->val > vmax) { // no need to explore right subtree
        
        find_subtree(x->left, vmin, vmax);
    
    } else { // x->val < vmin => no need to expolore left subtree
        find_subtree(x->right, vmin, vmax);
    }
}

find_subtree(root, vmin, vmax);

if(xleft != 0 && xright != 0) {
     printf("# of nodes: %d\n",  
            xleft->sum - xright->sum + 1);
}

- 111 May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simplest approach is, find node (lt) having data just immediate >= X (O(log(n))), similarly, find node (rt) with data just immediate <= Y (O(log(n))). Now, simply do in order traversal from lt to rt and count if node is in between[X, Y]. Total worst case complexity would be (O(n + 2log(n))).

- Suren May 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what about the leaf nodes, I assume they will not be counted but want to make sure

- pc May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function countNodes(root, lb, rb) {
  if (root === null) {
    return 0;
  }

  if (root.val < lb) {
    return countNodes(root.right, lb, rb);
  }

  if (root.val > rb) {
    return countNodes(root.left, lb, rb);
  }

  return 1 + countNodes(root.left, lb, rb) + countNodes(root.right, lb, rb);
}

- NI May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesnt work

- B May 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

small tweak needed in inorder code..

public static int inorder(Node root, int lbound, int ubound){
    Int count=new Int();
    // short-circuit to get new root
    while(root.data<lbound){
        root=root.rightChild;
    }
    inorder(root, count, lbound, ubound);
    return count.val;
       
   }

   public static void inorder(Node root, Int count, int lbound, int ubound){
	
	if(root==null){
		return;
	}
	// Left
	inorder(root.leftChild, count, lbound, ubound);
	// Data with short-circuit
	if(root.data>= lbound){
		if(root.data > ubound){
			return;
		}
		else{
			count.val++;
		}
	}
	// Right
	inorder(root.rightChild, count, lbound, ubound);
}

private static class Int{
	int val;
	Int(){this(0);}
	Int(int val){
		this.val=val;
	}
	
}

- infinity May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem states that all the nodes in the sub-tree should be within the specified range. So we can't just do a simple traversal and count every node within the range.
We count the nodes that are within range for the left tree and then the right tree.
The catch is that if we find any invalid nodes within the tree, then the results returned by the function will be zero.
We can use the BST property (left <= current < right) to help save some time.
I am maintaining the results outside the function which is bad but it can be fixed by having a private Result class.

int maxcount = 0;
	Node rootedat = null;
	
	public int countRange(Node node, int x, int y, int min, int max) {
		if( x > max || y < min || node == null ) return 0;
		int lCount = countRange( node.lChild, x, y, min, node.data);
		int rCount = countRange( node.rChild, x, y, node.data+1, max);
		// if the left or right subtree are not null, they should return a non-zero number of 
		//  nodes if all the nodes match the criteria. If return is zero, something is out of range. 
		if( node.lChild != null && lCount == 0 || node.rChild != null && rCount == 0 ) return 0;
		int count = 0;
		if( x <= node.data && node.data <= y) {
			count = lCount + rCount + 1;
			if( count > maxcount ) {
				maxcount = count;
				rootedat = node;
			}
		}
		return count;
	}

- scyle June 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To solve this , we need an augmented data structure. where at each node(r) of BST, we maintain the number of nodes in the subtree rooted at r.(refer
page 340 CLRS). Now given a range first we try to reach to a node(n) such that x<=n<y. ie node lies between the given range. this can be done recursively.

Total nodes lying in the range = nodes > x on the left subtree rooted at n + nodes < y on the right subtree rooted at y + 1 ( the root node, n)
(part 1) (part2)

to calculate part1:
1. start from node n
2. if x < n, go left other wise go right
3. while travering the BST if you find a node greater than x the keep a running count of node->right->size +1
4. continue this procedure till the search terminates.

to calculate part2:
everything remains same, except step 3
3. while travering the BST if you find a node less than x the keep a running count of node->left->size +1

Finally total = part1 + part2 + 1


Comments/Issues ?

- vivekh September 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we can modify each node in BST, it is easy; but I am not sure about this since the size of BST is huge (more than 0.1 million).

Step 1. For each node, we add (min:minimum of subtree where root is this node, max:maximum of subtree where root is this node, count:# of all nodes in the subtree)

Step 2. Do breadth-first search from root to find a node (i.e., sub-tree) where x <= min and max <= y, and return this node's count.

For step 1, the data structure looks like this
E.g., Node (min, max, count)
2 (1, 3, 2)
1 (1, 1, 1) 3 (3,3,1)

and recursively update min, max, count by in-order traverse

For step 2, BFS will work for finding the largest subtree that satisfies the condition (i.e., all sub nodes should be between x and y).

- bruceyhkim February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int rangeCount(T lo, T hi){
		if(lo==null || hi==null || this.root==null){
			return 0;
		}
		return rangeCount(this.root, lo, hi);
	}
	private int rangeCount(Node n, T lo, T hi){
		if(n==null)
			return 0;
		int temp=0,leftCount=0,rightCount=0;
		if(min(n).data.compareTo(lo)>=0 && max(n).data.compareTo(hi)<=0){
			return n.count;
		}
		if(n.data.compareTo(lo)>=0 && n.data.compareTo(hi)<=0)
			temp++;
		if(n.data.compareTo(lo)>=0)		
			leftCount = rangeCount(n.left, lo, hi);
		if(n.data.compareTo(hi)<=0)
			rightCount=rangeCount(n.right, lo, hi);
		return temp+leftCount+rightCount;
	}

- ChandreshV December 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int rangeCount(T lo, T hi){
		if(lo==null || hi==null || this.root==null){
			return 0;
		}
		return rangeCount(this.root, lo, hi);
	}
	private int rangeCount(Node n, T lo, T hi){
		if(n==null)
			return 0;
		int temp=0,leftCount=0,rightCount=0;
		if(min(n).data.compareTo(lo)>=0 && max(n).data.compareTo(hi)<=0){
			return n.count;
		}
		if(n.data.compareTo(lo)>=0 && n.data.compareTo(hi)<=0)
			temp++;
		if(n.data.compareTo(lo)>=0)		
			leftCount = rangeCount(n.left, lo, hi);
		if(n.data.compareTo(hi)<=0)
			rightCount=rangeCount(n.right, lo, hi);
		return temp+leftCount+rightCount;
	}

- mail2chandreshv December 06, 2016 | 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