## 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) {
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) {
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);
}
}

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

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

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

We can use Math.abs for that!!

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

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

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

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

neat and correct

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

neat and correct

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

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.

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

you forgot to update min

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

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

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

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.

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

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 ?

Thank You

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

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

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;

}``````

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

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

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

Sorry, I realized I understood the problem wrongly.

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

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.

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;

}``````

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() {

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

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() {

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

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.

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

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

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

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

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

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

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

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

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 ?

Thank You

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

Maan your not returning node, just difference?

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

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.

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 ?

Thank You

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 ?

Thank You

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 ?

Thank You

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 ?

Thank You

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

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

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

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

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.