## Google Interview Question for SDETs

• 0

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 :).

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

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

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

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``````

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

``````____________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.

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

``````____________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.

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

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

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

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;

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

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

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

why have you added last 2 else if conditions?

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

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.

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

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.

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

@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

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

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.

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 ;``````

}

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

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.

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

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.

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

But stack memory << main memory.

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

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

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

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

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

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

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

}
}``````

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

}
}``````

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

The right tree:

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

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

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))).

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

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

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

Doesnt work

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

}``````

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

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

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).

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

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

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.