Google Interview Question
Software EngineersCountry: Poland
Interview Type: In-Person
In the above solution there is minor mistake. Suppose you have a tree with the root as 75, the left child as 72 and right child as 78. The value of X is 73. The above solution would return 75 instead of 72. The comparison should be to the absolute value (Math.Abs(x - valReturn) > Math.Abs(x -rootval);
Iterative one
private static Node GetClosestNodeToX(Node root, int x)
{
Node result = null;
int min = Int32.MaxValue;
while (root != null)
{
int currMin = Math.Abs(root.data - x);
if (currMin == 0)
return root;
if (min > currMin)
{
result = root;
min = currMin;
}
if (x < root.data)
root = root.left;
else if (x > root.data)
root = root.right;
}
return result;
}
private static class Tree {
public Tree left;
public double value;
public Tree right;
public Tree(Tree left, double value, Tree right) {
this.left = left;
this.value = value;
this.right = right;
}
}
public static double closest(Tree root, double value) {
double delta = Math.abs(root.value - value);
if (value < root.value && root.left != null) {
double left = closest(root.left, value);
if (Math.abs(left - value) < delta) {
return left;
}
}
if (root.value < value && root.right != null) {
double right = closest(root.right, value);
if (Math.abs(right - value) < delta) {
return right;
}
}
return root.value;
}
Perform birary search for the given number X in the given BST. There are 2 possbile cases
1) Number X is present in the given BST.
2) Number X is not in the given BST.
In case of 1st scenario, return X as answer.
In case of 2nd scenario, Binary search process will reach to leaf node without finding x, in this case maintain Closest node (which has minumum value(node)-x ) in the path from the root to leaf.
Complexity O(log n)
Code:
Node closest(Node root, int value){
Node ans = root;
int diff;
if(!root) return ans;
diff = abs( ans->value - value);
while(root){
if(root->value == value){
ans = root;
break;
}
if(diff > abs(root->value - value)){
diff = abs(root->value - value);
ans = root;
}
if(value < root->value){
root = root->left;
}else{
root = root->right;
}
}
return ans;
}
public class Node
{
private int value;
private Node left;
private Node right;
}
public class BSTService
{
public Node findClosestValue(Node n,int x)
{
if(n.value==x)
{
return n;
}
Node result=findClosestValue(n.left,x);
if(result==null)
{
result=findClosestValue(n.right,x);
}
if(result.left==null && result.right==null)//If target node is a leaf, closet value will be its parent
{
return n;
}
//if target node is not a leaf, either its left child or right child will have the closest value.
if(result.left!=null && result.right==null)
{
return result.left;
}
if(result.right==null && result.left!=null)
{
return result.right;
}
result=Math.abs(result.value-result.left.value)<Math.abs(result.value-result.right.value)?result.left:result.right;
return result;
}
}
int closest(TreeNode root, int v){
int pred = Integer.MAX_INTEGER;
int succ = Integer.MIN_INTEGER;
while (root!=null) {
if (root.value > v) {
if (root.value < succ) {
succ = root.value;
}
root = root.left;
}
else if (root.value < v) {
if (root.value > pred) {
pred = root.value;
}
root = root.right;
} else {
return root.value;
}
}
if (v - pred < succ - v) {
return pred;
}
return succ;
}
I don't think you can do this by iterating through the tree, consider the following example:
search for 4
10
1 6
4
How do you know to iterate left when the it seems the right value is closer? I would instead do an in-order traversal of the tree into an array list, and then do a binary search on that list for the number your searching for. I think this is the simplest solution.
public class ClosestInBST {
public static void main(String[] args) {
Tree<Integer> tree =new Tree<>();
tree.root = new Node<>(15);
tree.root.lChild = new Node<>(9);
tree.root.rChild = new Node<>(22);
tree.root.lChild.lChild = new Node<>(6);
tree.root.lChild.rChild = new Node<>(12);
System.out.println(getClosestVal(10, tree.root));
}
public static int getClosestVal(int key, Node<Integer> root){
if(root.data==key){
return root.data;
}
int diff = Math.abs(root.data-key);
if(key<root.data){
return getClosestVal(key, root.lChild, diff, root);
} else{
return getClosestVal(key, root.rChild, diff, root);
}
}
private static int getClosestVal(int key, Node<Integer> node, int diff, Node<Integer> closestNode){
if(node==null){
return closestNode.data;
}
if(node.data==key){
return node.data;
}
if(Math.abs(node.data-key)<diff){
diff = Math.abs(node.data-key);
closestNode =node;
}
if(key<node.data){
return getClosestVal(key, node.lChild, diff, closestNode);
} else{
return getClosestVal(key, node.rChild, diff, closestNode);
}
}
}
1480 int MOD(int x, int y) {
1481 return (x-y)>0?(x-y):(0-(x-y));
1482 }
1483 TREE* closest(TREE* node, int n, int *close) {
1484
1485 TREE* temp;
1486
1487 if(!node)
1488 return NULL;
1489
1490
1491 if(node->value > n)
1492 temp = closest(node->left, n, close);
1493 else if(node->value <= n)
1494 temp = closest(node->right, n, close);
1495
1496 // if the difference between the node value and passed val is less than previously stored value, then update it
1497 if(MOD(node->value, n) < *close) {
1498 *close = MOD(node->value, n);
1499 temp = node;
1500 }
1501 return temp;
1502
}
The idea is :
1. start with root
2. if the number is less than root value , go left otherwise go right
3. recursively continue step 2 till you reach the leaf node,
4. Now as the recursion stack pops, at each node check if the abs(difference between the node value and the number is minumum value) is less than the previous value.
5. If you find the abs value calculated in step 4 to be less , then return the node pointer.
Below is the simple code :
1480 int MOD(int x, int y) {
1481 return (x-y)>0?(x-y):(0-(x-y));
1482 }
1483 TREE* closest(TREE* node, int n, int *close) {
1484
1485 TREE* temp;
1486
1487 if(!node)
1488 return NULL;
1489
1490
1491 if(node->value > n)
1492 temp = closest(node->left, n, close);
1493 else if(node->value <= n)
1494 temp = closest(node->right, n, close);
1495
1496 // if the difference between the node value and passed val is less than previously stored value, then update it
1497 if(MOD(node->value, n) < *close) {
1498 *close = MOD(node->value, n);
1499 temp = node;
1500 }
1501 return temp;
1502
}
int closesetValue(Node * root , int value) {
int aboveCandidate = -1;
int belowCandidate = -1;
Node * currentNode = root;
if (root == NULL)
return NULL;
while (currentNode != NULL) {
if (currentNode->data < value)
{
belowCandidate = currentNode->data;
currentNode = currentNode->left;
}
else if (currentNode->data > value)
{
aboveCandidate = currentNode->data;
currentNode = currentNode->right;
}
else
return value;
}
return( value - belowCandidate < aboveCandidate - value ) || aboveCandidate == -1 ? belowCandidate : aboveCandidate;
}
struct Node {
Node(int v) : val(v) {}
int val;
Node *left, *right;
};
int findClosestValue(Node *root, int x) {
assert(root != nullptr);
int ans;
int diff = MAXI;
while (root != nullptr) {
if (root->val == x) {
return x;
}
else if (root->val > x) {
if (root->val -x < diff) {
ans = root->val;
diff = ans - x;
root = root->left;
}
}
else {
if (x - root->val < diff) {
ans = root->val;
diff = x - ans;
root = root->right;
}
}
}
return ans;
}
- smarthbehl July 14, 2015