Google Interview Question for Software Engineers


Country: Poland
Interview Type: In-Person




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

int findValueClosestToX(TreeNode root, int x)
{
	if(root==null) return null;
	if(x==root) return root.val;
	if(x-root>0)
	{
		if(root.right!=null)
		{
			int valReturn = findClosestToX(root.right,x);
			return (Math.Abs(x-valReturn) > x-root.val ? root.val :valReturn );
		}
		else{
			return root.val;
		}
	}
	else{
		if(root.left!=null){
			int valReturn = findClosestToX(root.left,x);
			return (Math.Abs(x-valReturn) > x-root.val ? root.val :valReturn );
		}
		else{
			return root.val;
		}
	}
}

- smarthbehl July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vs August 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codealtecdown October 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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

- tested.candidate July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

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

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

- divm01986 July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- anna.tovkun July 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Trevor July 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

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

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

}

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

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

}

- vivekh August 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the above program , close is set to INT_MAX when the function is called

- vivekh August 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

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

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

- malinbupt October 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Keep the parent node for checking the closest one.

- sonesh July 14, 2015 | 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