Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

Will this work?

{
public static double closest(Node node, double k, double k_closest) {
if(node.data == k) {
k_closest = k;
return k;
}
if(node.data > k) {
// handle to adjust k_closest
if((node.data - k) < Math.abs(k_closest - k))
k_closest = node.data;
if(node.left != null)
k_closest = closest(node.left, k, k_closest);
}
if(node.data < k) {
// handle to adjust k_closest
if(Math.abs(node.data - k) < Math.abs(k_closest - k))
k_closest = node.data;
if(node.right != null)
k_closest = closest(node.right, k , k_closest);
}
return(k_closest);
}
}

- anonymous February 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for double, u can't use a==b

- anonymous February 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can use Math.abs for that!!

- Andy2000 September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

y wd u chk node left if n->data<value?

- aaman.singh85 October 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

n: node
d: difference between node to be checked and key targetted
un = ultimate node or solution node

CK(n, d)
	if(abs(d) < min)
		un = n
	if(d == 0)
		return
	if(d <0)
		CK(n->r, n->r - k)
	else
		CK(n->l, n->l - k)

- Prateek Caire February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

neat and correct

- craig February 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

neat and correct

- craig February 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I wonder what value would you use for argument "d" in the initial call for the root. Also I don't think we can assume both children will always be present. Just minor details though.

- Sunny December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

you forgot to update min

- g December 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.

const Node* closest (const Node* node, double value,
                                     const Node* parent = NULL) {
  if (NULL == node) {
    return NULL;
  }
  const Node *left = NULL, *right = NULL, *result = node;
  if ((NULL == parent && value < node->data) ||
      (value < parent->data && value < node->data) {
      left = closest(node->left, value, node);
  }
  if ((NULL == parent && value > node->data) ||
      (value > parent->data && value > node->data) {
      right = closest(node->right, value, node);
  }
  if (NULL != left &&
      std::abs(left->data - value) < std::abs(node->data - value)) {
      result = left;
  }
  if (NULL != right &&
      std::abs(right->data - value) < std::abs(result->data - value)) {
      result = right;
  }
  return result;
}

- sandy2406 February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another one (recursive):

public static BTNode closest(BTNode node, double k) {
        if (node == null) {
            return null;
        }
        BTNode nl = closest(node.left, k);
        BTNode nr = closest(node.right, k);
        if (nl != null) {
            BTNode temp = Math.min(Math.abs(node.data - k), Math.abs(nl.data - k)) == Math.abs(node.data - k) ? node : nl;
            if (nr != null) {
                return Math.min(Math.abs(temp.data - k), Math.abs(nr.data - k)) == Math.abs(temp.data - k) ? temp : nr;
            }
            return temp;
        }
        if (nr != null) {
            return Math.min(Math.abs(node.data - k), Math.abs(nr.data - k)) == Math.abs(node.data - k) ? node : nr;
        }
        return node;
    }

- tracer February 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

n: node
d: difference between node to be checked and key targetted
un = ultimate node or solution node

CK(n, d)
	if(abs(d) < min)
		un = n
	if(d == 0)
		return
	if(d <0)
		CK(n->r, n->r - k)
	else
		CK(n->l, n->l - k)

- Prateek Caire February 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A recursive solution which returns the root if it is closer to the given number, or the closest node in the right/left subtree if that is closer than the root:

Node* closest_node(Node* root, int K)
{
    if((double)K>root->data)
    {
        if(root->right==NULL)
            return root;
        else
        {
            Node* closest_in_subtree = closest_node(root->right,K);
            return abs((double)K-root->data)<abs(double(K)-closest_in_subtree->data) ? root : closest_in_subtree;
        }
    }
    else
    {
        if(root->left==NULL)
            return root;
        else
        {
            Node* closest_in_subtree = closest_node(root->left,K);
            return abs(double(K)-root->data)<abs(double(K)-closest_in_subtree->data) ? root : closest_in_subtree;
        }
    }
}

Running time would be O(log n) if the tree is balanced.

- karthikvenkat February 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}

}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the run time should be bigO( (logn)^2)

- Anonymous September 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic: Find closest value in the left or right child and compare it with current node.

double find(Node * root, double val){
     double delta = val - root->data;
     double x;
     if(delta > 0 )   // look in right
       x = find(rott->right,val);
     else
      x = find(root->left,val);

    double deltax = abs(x-val);
    if(deltax < abs(delta))
         return x;
    else
        return root->data;

  }

- Anonymous February 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

del_min <- INFINITY
p <- root
p_min <- root

while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p

if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left

if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right

if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash

//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left

if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end

end //end p

- Will it work? (BC not checked) February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

del_min <- INFINITY
p <- root
p_min <- root

while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p

if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left

if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right

if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash

//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left

if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end

end //end p

- Will it work? (BC not checked) February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

del_min <- INFINITY
p <- root
p_min <- root

while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p

if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left

if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right

if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash

//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left

if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end

end //end p

- Does it work? (BC not checked) February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//BC not checked properly

del_min <- INFINITY
p <- root
p_min <- root

while (p)
del_p = (p->val - K)
p_min_dash = p, del_min_dash = del_p

//Tackle left
if (p->left)
del_l = (p->left->val - K)
if (abs(del_l) < abs(del_p))
del_min_dash = abs(del_l)
p_min_dash = p->left

//Tackle right
if (p->right)
del_r = (p->right->val - K)
if (abs(del_r) < abs(del_p))
del_min_dash = abs(del_r)
p_min_dash = p->right

// Tackle root, left, right
if (del_min_dash < del_min)
del_min = del_min_dash
p_min = p_min_dash

//Traverse
if (p_min_dash == p)
if ((p->left) && ((del_p XOR del_l < 0))
p = p->left

if ((p->right) && ((del_p XOR del_r < 0))
p = p->right
else
if (p_min_dash == p->left)
p = p->left
else
p = p->right
end
end

end //end p

- bose.debasish February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//BC not checked properly

del_min <- INFINITY
p <- root
p_min <- root

while (p)
  del_p = (p->val - K)
  p_min_dash = p, del_min_dash = del_p

  //Tackle left
  if (p->left)
     del_l = (p->left->val - K)
     if (abs(del_l) < abs(del_p))
       del_min_dash = abs(del_l)
       p_min_dash = p->left
  
  //Tackle right
  if (p->right)
    del_r = (p->right->val - K)
    if (abs(del_r) < abs(del_p))
      del_min_dash = abs(del_r)
      p_min_dash = p->right

  // Tackle root, left, right
  if (del_min_dash < del_min)
    del_min = del_min_dash
    p_min = p_min_dash

  //Traverse
  if (p_min_dash == p)
      if ((p->left) && ((del_p XOR del_l < 0))
         p = p->left
      
      if ((p->right) && ((del_p XOR del_r < 0))
        p = p->right 
  else
     if (p_min_dash == p->left)
       p = p->left
     else
       p = p->right
     end
  end

end //end p

- bose.debasish February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Apology for repeated posts. CareerCup was showing internal error, but post got submitted !!

- bose.debasish February 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findNearest(double key) {
		Node previousNode = null;
		Node traverseNode = root;
		int absValue;
		float value;
		while (traverseNode != null) {
			if (key < traverseNode.getValue()) {
				previousNode = traverseNode;
				traverseNode = traverseNode.getLeft();
			} else {
				previousNode = traverseNode;
				traverseNode = traverseNode.getRight();
			}
			if ((traverseNode == null)
					|| (key > previousNode.getValue() && key < traverseNode
							.getValue())) {
				break;
			}
		}
		Double diffParent = Math.abs(previousNode.getValue()- key);
		Double diffNode = Math.abs(traverseNode.getValue()- key);
		if(diffParent <diffNode){
			return previousNode.getValue();
		}else
		{
			return traverseNode.getValue();
		}
	}

- jerry February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
|| (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue()- key);
Double diffNode = Math.abs(traverseNode.getValue()- key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}

- jerry February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.

const Node* closest (const Node* node, double value, const Node* parent = NULL) {
  if (NULL == node) {
    return NULL;
  }
  const Node *left = NULL, *right = NULL, *result = node;
  if ((NULL == parent && value < node->data) || (value < parent->data && value < node->data) {
    left = closest(node->left, value, node);
  }
  if ((NULL == parent && value > node->data) || (value > parent->data && value > node->data) {
    right = closest(node->right, value, node);
  }
  if (NULL != left && std::abs(left->data - value) < std::abs(node->data - value)) {
    result = left;
  }
  if (NULL != right && std::abs(right->data - value) < std::abs(result->data - value)) {
    result = right;
  }
  return result;
}

- sandy February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Usually I wouldn't compare doubles using ==, but I am just too lazy to write a macro to compare against epsilon.

const Node* closest (const Node* node, double value, const Node* parent = NULL) {
  if (NULL == node) {
    return NULL;
  }
  const Node *left = NULL, *right = NULL, *result = node;
  if ((NULL == parent && value < node->data) || (value < parent->data && value < node->data) {
    left = closest(node->left, value, node);
  }
  if ((NULL == parent && value > node->data) || (value > parent->data && value > node->data) {
    right = closest(node->right, value, node);
  }
  if (NULL != left && std::abs(left->data - value) < std::abs(node->data - value)) {
    result = left;
  }
  if (NULL != right && std::abs(right->data - value) < std::abs(result->data - value)) {
    result = right;
  }
  return result;
}

- sandy February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//example call: findClosest(t, 4.1, MAX_DOUBLE);
double findClosest(Node t, double value, double closestSofar)
{
	if(delta(value, t.value) < delta(value, closestSofar))
	{
		closestSofar = t.value;
	}
	if(t.value < value)
	{
		closestSofar = findClosest(t.right, value, closestSofar);
	}
	else
	{
		closestSofar = findClosest(t.left, value, closestSofar);
	}
	return closestSofar;
}


private double delta(double value, double value2) {
	double d = value - value2;
	if(d < 0)
		return -1*d;
	return d;
}

- sandeepgiri February 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use in-order traversal of the tree and whenever a node appears larger than what is required to search, stop the traversal and return the closer node from the two nodes(i.e the last and the second last seen).

- Anonymous March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use in-order traversal of the tree and whenever a node appears larger than what is required to search, stop the traversal and return the closer node from the two nodes(i.e the last and the second last seen).

- Anonymous March 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo:
Find left closest and right closest node of the given node in tree by traversing the tree.
At end return whichever of right and left is closer to the node

public Node find_closest(Node root, Node nodeToFound, Node left, Node right) {
    if(root == NULL){
         if(left != NULL && right != NULL){
                if(abs(nodeToFound, left) < abs(nodeToFound, right)){
                        return left;
                } else {
                        return right;
                }
         }
        if(left == NULL){
			return right;
        }		
		return left;
    }
	
	if(nodeToFound.compare(root) < 0){
	    return find_closest(root->left, nodeToFound, left, root);
	} else {
		return find_closest(root->right, nodeToFound, root, right);
	}
}

- swapsmagic April 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the key here is how to compare two double values. In java, can use BigDecimal but need to convert double to String first. My code is shown as follows:

public static Node closest(Node root, BigDecimal key){
if (root == null)
return null;
BigDecimal value = new BigDecimal(root.value+"");
int compare = key.compareTo(value);
if ( compare == 0){
return root;
}
else if (compare < 0){
if (root.left == null) return root;
else {
BigDecimal leftvalue = new BigDecimal(root.left.value + "");
if (key.compareTo(leftvalue) > 0){
if ((key.subtract(leftvalue)).compareTo(value.subtract(key)) <= 0)
return root.left;
else
return root;
}
else
return closest(root.left, key);
}
}
else if (compare > 0){
if (root.right == null) return root;
else{
BigDecimal rightvalue = new BigDecimal(root.right.value + "");
if (key.compareTo(rightvalue) < 0){
if ((key.subtract(value)).compareTo(rightvalue.subtract(key)) <= 0)
return root;
else
return root.right;
}
else
return closest(root.right, key);
}
}
return null;
}

- eboyGTK April 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node
{
    Node* left;
    Node* right;
    double value;
}

doulbe findClosest (Node * root; double key)
{
    vector<double> path´╝Ť
    while (root!=NULL)
    {
        if(root->value == key)
        {return root-> value;}
        else if(root->value > key)
        {
            path.push_back(root -> value);
            root = root->left;
            continue;
        }
        else
        {
            path.push_back(root->value);
            root = root -> right;
            continue;
        }
    }
    path.push_back(key);
    sort(path.begin(), path.end());
    int len = path.size();
    for (int i = 0; i<len; i++)
    {
        if (path[i] == key)
        {
            if (abs(path[i-1]-path[i]) < abs(path[i+1]-path[i]))
            return path[i-1];
            else
            return path[i+1];
        }
    }

}

- lixulehigh September 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

MinNode(node):
    while (node.left):
        node = node.left
    return node

MaxNode(node):
    while(node.right):
        node = node.right
    return node

Successor(node):
    if (node.right):
        return MinNode(node.right)

    while (node.parent && node == node.parent.right):
        node = node.parent

    return node

Predecessor(node):
    if node.left:
        return MaxNode(node.left)
    
    while (node.parent && node == node.left)
        node = node.parent
    return node

FindClosest (key):
    node = Find(key)
    s = Successor(node)
    p = Predecessor(node)
    if (Abs(s.key - key) < Abs(p.key - key)):
        return s
    else:
        return p

- Ben October 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry, I realized I understood the problem wrongly.

- Ben October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The correct answer should then be:

Traverse along the path that has keys closer and closer to zero, by visit(node.left) if node.key > key and visit(node.right) if node.key < key. Then track back and find the node that gives the minimal key difference.

- Ben October 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

struct Node
{
	Node *left;
	Node *right;
	double val;
	Node():left(NULL), right(NULL){}
};

Node *find(Node *node, double key)
{
	if (node == NULL)
		return NULL;

	double val = node->val;

	if (val == key)
		return node;
	else if (val < key)
	{
		Node *ret = find(node->right, key);
		if (ret == NULL)
			return node;
		else
			return abs(node->val - key) < abs(ret->val - key) ? node : ret;
	}
	else
	{
		Node *ret = find(node->left, key);
		if (ret == NULL)
			return node;
		else
			return abs(node->val - key) < abs(ret->val - key) ? node : ret;
	}
}

int main()
{
	Node node[10];
	for(int i = 0; i < 10; i++)
		node[i].val = i;

	node[4].left = &node[2];
	node[4].right = &node[7];

	node[2].left = &node[1];
	node[2].right = &node[3];

	node[1].left = &node[0];

	node[7].left = &node[6];
	node[7].right = &node[8];

	node[6].left = &node[5];

	node[8].right = &node[9];

	Node *ret = find(&node[4], 4);
	cout << "key:" << 4 << " ret:" << ret->val << endl;

	ret = find(&node[4], 4.4);
	cout << "key:" << 4.4 << " ret:" << ret->val << endl;

	ret = find(&node[4], 10);
	cout << "key:" << 10 << " ret:" << ret->val << endl;

	ret = find(&node[4], 1.1);
	cout << "key:" << 1.1 << " ret:" << ret->val << endl;

	ret = find(&node[4], -1);
	cout << "key:" << -1 << " ret:" << ret->val << endl;

	ret = find(&node[3], 3.3);
	cout << "key:" << 3.3 << " ret:" << ret->val << endl;

}

- remlostime October 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<algorithm>
#include<cfloat>
struct node {
	float value;
	struct node *left;
	struct node* right;
};

typedef struct node NODE;

NODE* constructBST(const std::vector<float>& numbers, int low, int high) {
	if (low > high) {
		return NULL;
	}

	int mid = (low + high) / 2;
	NODE *root = new NODE;
	root->value = numbers[mid];
	root->left = constructBST(numbers, low, mid -1);
	root->right = constructBST(numbers, mid+1, high);

	return root;
}

float findClosest(NODE *root, float k) {
	static float mindiff = FLT_MAX;
	static float closest = 0.0F;
	if (root == NULL) 
		return 0.0F;

	if (fabs(root->value -k) < mindiff) {
		mindiff = fabs(root->value-k);
		closest = root->value;
	}

	findClosest(root->left, k);
	findClosest(root->right, k);

	return closest;	
}

int main() {

	// Read k
	std::cout << "Enter key\n";
	float k;
	std::cin >> k;

	// Read input numbers to a vector
	std::cout << "Enter numbers\n";
	std::vector<float> numbers;
	float input;
	while (std::cin >> input) {
		numbers.push_back(input);
	}

	// Sort the vector
	std::sort(numbers.begin(), numbers.end());

	// Cosntruct a BST
	NODE* root = constructBST(numbers, 0, numbers.size()-1);
	
	// findClosest 
	float closestValue = findClosest(root, k);
	std::cout << "Closest value is " << closestValue << std::endl;	

	return 0;
}

- Anonymous April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<vector>
#include<algorithm>
#include<cfloat>
struct node {
	float value;
	struct node *left;
	struct node* right;
};

typedef struct node NODE;

NODE* constructBST(const std::vector<float>& numbers, int low, int high) {
	if (low > high) {
		return NULL;
	}

	int mid = (low + high) / 2;
	NODE *root = new NODE;
	root->value = numbers[mid];
	root->left = constructBST(numbers, low, mid -1);
	root->right = constructBST(numbers, mid+1, high);

	return root;
}

float findClosest(NODE *root, float k) {
	static float mindiff = FLT_MAX;
	static float closest = 0.0F;
	if (root == NULL) 
		return 0.0F;

	if (fabs(root->value -k) < mindiff) {
		mindiff = fabs(root->value-k);
		closest = root->value;
	}

	findClosest(root->left, k);
	findClosest(root->right, k);

	return closest;	
}

int main() {

	// Read k
	std::cout << "Enter key\n";
	float k;
	std::cin >> k;

	// Read input numbers to a vector
	std::cout << "Enter numbers\n";
	std::vector<float> numbers;
	float input;
	while (std::cin >> input) {
		numbers.push_back(input);
	}

	// Sort the vector
	std::sort(numbers.begin(), numbers.end());

	// Cosntruct a BST
	NODE* root = constructBST(numbers, 0, numbers.size()-1);
	
	// findClosest 
	float closestValue = findClosest(root, k);
	std::cout << "Closest value is " << closestValue << std::endl;	

	return 0;
}

- Anonymous April 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

1. Keep two variables currDiff = Integer.MAX_VALUE and prevDiff = Integer.MAX_VALUE
2. Do BST,
but at each node do currDiff = node.value - key
if(Math.abs(currDiff) < prevDiff)
{
prevDiff = Math.abs(currDiff);
closest = node.value;
}
At the end return closest;

If the value is zero it is going to find that element, if not the closest one.

- Dev February 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the code for the algorithm I discussed:-

private static BTNode closestLookup(BTNode node, double data) 
	{ 
		double currDiff = Integer.MAX_VALUE, prevDiff = Integer.MAX_VALUE;
		BTNode closest = null;
	    while(node != null)
		{
	    	currDiff = node.data - data;
			if(Math.abs(currDiff) < prevDiff)
			{
				prevDiff = Math.abs(currDiff);
				closest = node;
			}
	    	if(node.data == data)
	    	{
	    		break;
	    	}
	    	else
	    	{
	    		if(data < node.data)
	    		{
	    			node = node.left;
	    		}
	    		else
				{
					node = node.right;
				}
	    	}
		}
	    return closest;
	}

- Dev February 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simple optimization on the code given here.
The loop can discontinue when the prevDiff is less than the current Diff. The node.data = data, < data or > data checks are needed only if currDiff < prevDiff

- ramya987 February 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

1) Naive solution is to store every element into an array, then scan whole element to find the closest element. Because Binary Tree can be converted as sorted array, this way is possible. However, it needs O(n) memory space and O(n) time complexity.

2) The better way is to follow tree nodes. The important point is that we should follow nodes until we find the leaf node unless the same value is found. Here is an example tree which I used.

3
2 100
1.9 2.8 3.1

Suppose input is (3.12), the closest value is 3.1. My idea is similar to Dev's idea. Just follow nodes using input value and store the value which has the smallest delta.

** ramya987 mentioned it is possible to optimize using curDiff < prevDiff. For my input 3.12, curDiff is much bigger than prevDiff when curNode is on 100(3-3.12 = -0.12, 100-3.12= 96.88). If we discontinue following nodes, it will return 3 as the closest node, but it is incorrect. 3.1 is the closest node. Thus, please follow nodes until the leaf node.

public double findCloset(TreeNode root, double key)
{
	TreeNode t = root;
	double closest = t.value;
	while (t != null)
	{
		if(t.value == key)
		{
			//If it is exactly equal, comparison doens't need anymore
			closest = t.value;
			break;
		}
		else if (t.value > key)
		{
			t = t.left;
		}
		else
		{
			t = t.right;
		}

		if (t != null && Math.abs(t.value - key) < Math.abs(closest - key))
		{
			closest = t.value;
		}
	}

	return closest;
}

- Ted June 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

bhakk.... 0
( )
/ \-0
( )
< /

- topcoder June 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}
}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Maan your not returning node, just difference?

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

If you already know the node's value is greater than the target value, then you shouldn't need to check the right subtree at all because they all will be farther from the target value than the node. Similarly for the opposite case.

This is true because the question says it's a binary search tree. If it were just a binary tree, then of course you have to check both subtrees as well.

- Sunny December 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}
}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}

}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}

}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi

I would be happy to get some feedback on this code.

class Finding ClosestNodeInTree {
private static double difference = 0.0;
private static doule key = 0.0;
int main() {
	BinaryTree bt;
	bt.insert(20.43);
	bt.insert(12.78);
	bt.insert(19.89);
	bt.insert(32.69);
	bt.insert(2.54);
	cout << "Please provide the key value" << endl;
	cin >> key;
	const Node &closestNode = closestValue(bt);
	cout << << "Node that has the closest value to " <<  << closestNode.value;
return 1;
}
const Node & closestValue(const BinaryTree &node) {
if(node==null)
	return;
// Some kind of traversal - A Breadth First Search might be useful. 
int val = node.value;
int currDiff = val > key ? val-key:key-val;
difference = currDiff > difference ? currDiff:difference;
if(node.left!=null)
	closestValue(node.left);
if(node.right!=null)
	closestValue(node.right);
return difference;
}

}

I know I am not doing BST. But sometimes the value might be "closer" to either the left side of the value or the right side of the value (thinking on a number line) regardless of whether is lesser or greater than the parent value right ? Or am I missing something ?

Please send in your comments.

Thank You

- Anonymous February 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.util.Arrays;

class TreeNode
{
    public double value;
    public TreeNode left,right;
    public TreeNode(double v)
    {
        value = v;
    } 
}

class BST
{
    TreeNode root = null;
    public void insert(double x)
    {
    	if( root == null )
    	{
    		root = new TreeNode(x);
    		return;
    	}
    	TreeNode current = root;
    	TreeNode parent = root;
    	while(current!=null)
    	{
    		parent = current;
    		if( current.value > x )
    		{
    			current = current.left;
    		}else
    		{
    			current = current.right;
    		}
    	}
    	if( parent.value > x )
    	{
    		parent.left = new TreeNode(x);
    	}else
    	{
    		parent.right = new TreeNode(x);
    	}
    }
    public double findCloset(double [] array, int key)
    {
    	for(double x : array)
    	{
    		insert(x);
    	}
    	//tree built
    	TreeNode t = root;
    	while(t!=null)
    	{
    		double x = t.value;
    		if( x > key )
    		{
    			if(t.left != null && Math.abs(t.left.value - key) < Math.abs(x - key))
    			{
    				t = t.left;
    			}else
    			{
    				return t.value;
    			}
    		}else
    		{
    			if(t.right != null && Math.abs(t.right.value - key) < Math.abs(x - key))
    			{
    				t = t.right;
    			}else
    			{
    				return t.value;
    			}
    		}
    	}
    	
    	return 0;
    	
    }
    
}

public class findArray
{
	public static void main(String[] arg)
    {
    	BST b = new BST();
    	double []v = {1.2,3.4,5.6,1,4.5,6.7,3.2,2.9,3.1};
    	System.out.println(b.findCloset(v, 3));
    }
}

- Ragnarok March 09, 2012 | 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