Google Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

after calling this function, "minDiff" will hold the minimum difference. O(n) time.

static void findBSTMinimumValueDifference(Node root) {
		 if (root != null) {
			 findBSTMinimumValueDifference(root.left);
			 if (previous != null && minDiff > root.value - previous.value) {
				 minDiff = root.value - previous.value;
			 }
			 previous = root;
			 findBSTMinimumValueDifference(root.right);
		 }
	 }
	 
static int minDiff = Integer.MAX_VALUE;
static Node previous;

- ikoryf February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

do inorder traversal, compare current node to the previously visited one.
While traversing maintain "minDiff" variable.
If current (node - previous) is greater than "minDiff" then update "minDiff".
Return "minDiff" in the end.

- zr.roman February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

I am going to do inorder traversal of BST tree and in the meanwhile will check the mininum difference between each two successive elements (they are in ascending order) and take the minimum value. O(n) complexity

- EPavlova February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

O(n), For every node get max from left branch and get min from right branch and check which one gives min diff compare to the node. Do recursively for each node in a tree and keep latest min result in variable. Both getting min/max from sub trees and recursion can be done in same tree recursion.

class Node:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right 

min_pair = None
min_diff = None

def find_min_pair(node, return_max):
    global min_diff
    global min_pair
    if node is not None:
        left_max = find_min_pair(node.left, True)
        right_min = find_min_pair(node.right, False)
                
        if left_max is not None:
            diff = abs(node.value - left_max)
            if min_diff is None or diff < min_diff:
                min_diff = diff
                min_pair = (left_max, node.value)
        if right_min is not None:
            diff = abs(node.value - right_min)
            if min_diff is None or diff < min_diff:
                min_diff = diff
                min_pair = (right_min, node.value)
        
        if return_max is None:
            return None
        elif return_max == True:
            if right_min is not None:
                return right_min
            else:
                return node.value
        else:
            if left_max is not None:
                return left_max
            else:
                return node.value
    else:
        return None


min_pair = None
min_diff = None
bst = Node(10, Node(5, None, None), Node(16, Node(12, None, None), Node(20, None, None)))
find_min_pair(bst, None)
print(min_pair)                

min_pair = None
min_diff = None
bst = None
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, None, None)
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, Node(100, None, None), None)
find_min_pair(bst, None)
print(min_pair)

min_pair = None
min_diff = None
bst = Node(10, None, Node(100, None, None))
find_min_pair(bst, None)
print(min_pair)

- rizTaak February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I realized the example is not added correctly. I add it here again:

Given an input BST, find the minimum value difference between any two nodes in the tree.

...10
.../....\
5.....16
......./.....\
....12.....20

- a.asudeh February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import sys

class Node:

      def __init__(self, v):
          self.v = v
          self.left = None
          self.right = None


class BST:

    def __init__(self, node):

        self.root = node
        self.distanceD = sys.maxsize
        self.tested = set()

    def addNodes(self, nList):
        

        for n in nList:
           current = self.root
           #print('n:: ', n, ' and current:: ', current.v)
 
           while True:
              if  n < current.v:
                 if current.left:
                    current = current.left  
                 else:
                    newNode = Node(n)
                    current.left = newNode
                    break
              elif n > current.v:
                if current.right:
                   current = current.right
                else:
                   newNode = Node(n)
                   current.right = newNode
                   break    
              else:
                break  

    def updateDistance(self, lList):

         for i in range(0, len(lList)-1):
            for j in range(i+1, len(lList)):
               if (lList[j], lList[i]) not in self.tested:
                 d = lList[j] - lList[i]
                 self.tested.add((lList[j], lList[i]))
                 if d < self.distanceD :
                      self.distanceD = d
 
    def traverseInorder(self, current): 

        l = [] 
        r = []
        c = []
        if current.left:
           l = self.traverseInorder(current.left) 
  
        c = list([current.v])      
        #print(c)
  
        if current.right:
            
           r = self.traverseInorder(current.right) 
        z = l + c + r
        #print(z)
        self.updateDistance(z)
        return z


aList = [34, 23, 78, 12, 19, 77, 21, 101, 52]
#aList = [16,5, 12, 20]
r = Node(10)
myBST = BST(r)
myBST.addNodes(aList)
bList = myBST.traverseInorder(myBST.root)
#print(bList)
#print(myBST.tested)
print(myBST.distanceD)
#print('total subcases: ', len(myBST.tested))

Sample Output:

[10, 12, 19, 21, 23, 34, 52, 77, 78, 101]
1

- fahmida.hamid February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int GetMinDiff(TreeNode root)
{
    if (root == null)
        return 0;

    Queue<TreeNode> queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int minValue = int.MaxValue;

    // Using Breath Search/Traversal
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        if (node.Left != null)
        {
            queue.Enqueue(node.Left);
            int value = GetMaxValue(node.Left);
            minValue = Math.Min(minValue, node.Value - value);
        }
        if (node.Right != null)
        {
            queue.Enqueue(node.Right);
            int value = GetMinValue(node.Right);
            minValue = Math.Min(minValue, value - node.Value);
        }
    }

    return minValue;
}

private int GetMinValue(TreeNode root)
{
    var node = root;
    while (node.Left != null)
        node = node.Left;

    return node.Value;
}

private int GetMaxValue(TreeNode root)
{
    var node = root;
    while (node.Right != null)
        node = node.Right;

    return node.Value;
}

- hnatsu February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

using namespace std;

struct node
{
	int key;
	struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
	struct node *temp = (struct node *)malloc(sizeof(struct node));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
	if (root != NULL)
	{
		inorder(root->left);
		printf("%d \n", root->key);
		inorder(root->right);
	}
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
	/* If the tree is empty, return a new node */
	if (node == NULL) return newNode(key);

	/* Otherwise, recur down the tree */
	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);

	/* return the (unchanged) node pointer */
	return node;
}


int *InorderTraversalOfBST(node *binarySearchTreeRoot)
{
	int i = 0, arr_size = 7;
	int *tempArr = new int[arr_size];

	for (int j = 0; j < arr_size; j++)
		tempArr[j] = 0;

	while (binarySearchTreeRoot != NULL)
	{
		InorderTraversalOfBST(binarySearchTreeRoot -> left);
		printf("%d", binarySearchTreeRoot -> key);
		if (i < arr_size)
		{
			tempArr[i++] = binarySearchTreeRoot -> key;
		}
		InorderTraversalOfBST(binarySearchTreeRoot -> right);
	}
	return 	tempArr;
}

/* The function assumes that there are at least two elements in array. The function returns a negative value if the array is sorted in decreasing order. Returns 0 if elements are equal  */

int minDiff(int arr[], int size)
{
	int min_diff = arr[1] - arr[0];
	int min_element = arr[0];
	int i;
	for (i = 1; i < size; i++)
	{
		if (arr[i] - min_element < min_diff)
			min_diff = arr[i] - min_element;
		if (arr[i] < min_element)
			min_element = arr[i];
	}
	return min_diff;
}

/* Driver program to test above function */
int main()
{
	struct node *root = NULL;
	root = insert(root, 50);
	insert(root, 30);
	insert(root, 20);
	insert(root, 40);
	insert(root, 70);
	insert(root, 60);
	insert(root, 80);

	int *arr = InorderTraversalOfBST(root);
	int size = sizeof(arr) / sizeof(arr[0]);
	printf("Minimum difference is %d", minDiff(arr, size));
	getchar();
	return 0;
}

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

#include<iostream>

using namespace std;

struct node
{
int key;
struct node *left, *right;
};

// A utility function to create a new BST node
struct node *newNode(int item)
{
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST
void inorder(struct node *root)
{
if (root != NULL)
{
inorder(root->left);
printf("%d \n", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in BST */
struct node* insert(struct node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);

/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */
return node;
}


int *InorderTraversalOfBST(node *binarySearchTreeRoot)
{
int i = 0, arr_size = 7;
int *tempArr = new int[arr_size];

for (int j = 0; j < arr_size; j++)
tempArr[j] = 0;

while (binarySearchTreeRoot != NULL)
{
InorderTraversalOfBST(binarySearchTreeRoot -> left);
printf("%d", binarySearchTreeRoot -> key);
if (i < arr_size)
{
tempArr[i++] = binarySearchTreeRoot -> key;
}
InorderTraversalOfBST(binarySearchTreeRoot -> right);
}
return tempArr;
}

/* The function assumes that there are at least two elements in array. The function returns a negative value if the array is sorted in decreasing order. Returns 0 if elements are equal */

int minDiff(int arr[], int size)
{
int min_diff = arr[1] - arr[0];
int min_element = arr[0];
int i;
for (i = 1; i < size; i++)
{
if (arr[i] - min_element < min_diff)
min_diff = arr[i] - min_element;
if (arr[i] < min_element)
min_element = arr[i];
}
return min_diff;
}

/* Driver program to test above function */
int main()
{
struct node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);

int *arr = InorderTraversalOfBST(root);
int size = sizeof(arr) / sizeof(arr[0]);
printf("Minimum difference is %d", minDiff(arr, size));
getchar();
return 0;
}

- Basu February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can do it just using in-order traversal

public int minDiff() {
			return minDiff(new TreeNode(null), root, -1);
		}
		
		private int minDiff(TreeNode prev, TreeNode cur, int min) {
			if(cur.left != null) {
				min = minDiff(prev, cur.left, min);
			}
			if(prev.data != null) {
				int diff = Math.abs(prev.data - cur.data);
				min = min == -1 ? diff : Math.min(diff, min);
			}
			
			prev.data = cur.data;
			
			if(cur.right != null) {
				min = minDiff(prev, cur.right, min);
			}
			return min;
		}

- Antonio February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for a none leaf node of BST, elements in its left sub tree are smaller than it, and elements in its right sub tree are bigger than it. So, min difference can only happen between a none leaf node and its direct children nodes. So, the min difference of a BST is the min difference of each none leaf node and their direct children node. We can use dynamic programming to compute difference between a none leaf node and its children nodes, and propagate the difference up to it parent.

let MD(n) is the min difference than can be gotten from the sub tree that are rooted at node n. Then:
MD(n) = min(value(n)-value(child of n), MD(child of n))

The time complexity is in linear to the size of the tree.

- runwithfullspeed February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if this is the most efficient solution, but it is working:

import java.io.*;
import java.util.*;


class Solution {
  private static final int NOT_FOUND = -1;
  
  public static Tree buildTree() {
    Node node5 = new Node(5);
    Node node10 = new Node(10);
    Node node16 = new Node(16);
    Node node12 = new Node(12);
    Node node20 = new Node(20);
    
    node10.setLeft(node5);
    node10.setRight(node16);
    node16.setLeft(node12);
    node16.setRight(node20);
    
    return new Tree(node10);
  }
  
  public static int findMinimalDiffRec(Node node, int num) {
    int diffFromValue = Math.abs(node.getValue() - num);
    
    if (node.getLeft() != null) {
      int leftMinFromNum = findMinimalDiffRec(node.getLeft(), num);
      int leftMinFromValue = findMinimalDiffRec(node.getLeft(), node.getValue());
      int minLeftTemp = Math.min(leftMinFromNum, leftMinFromValue);
      int minLeftResult = Math.min(minLeftTemp, diffFromValue);  
      
      if (node.getRight() != null) {
        int rightMinFromNum = findMinimalDiffRec(node.getRight(), num);
        int rightMinFromValue = findMinimalDiffRec(node.getRight(), node.getValue());
        int minRightTemp = Math.min(rightMinFromNum, rightMinFromValue);
        int minRightResult = Math.min(minRightTemp, diffFromValue);
        
        return Math.min(minLeftResult, minRightResult);
      }
      
      return minLeftResult;
    }
    
    if (node.getRight() != null) {
      int rightMinFromNum = findMinimalDiffRec(node.getRight(), num);
      int rightMinFromValue = findMinimalDiffRec(node.getRight(), node.getValue());
      int minRightTemp = Math.min(rightMinFromNum, rightMinFromValue);
      return Math.min(minRightTemp, diffFromValue);      
    }
      
      return diffFromValue;
    }
  
  public static int findMinimalDiff(Node node) {
    if (node == null) {
      return NOT_FOUND;      
    }
    
    if (node.getLeft() == null && node.getRight() == null) {
      return node.getValue();
    }
    
    if (node.getLeft() == null) {
      return findMinimalDiffRec(node.getRight(), node.getValue());
    }
    
    if (node.getRight() == null) {
      return findMinimalDiffRec(node.getLeft(), node.getValue());
    }
    
    int leftMin = findMinimalDiffRec(node.getLeft(), node.getValue());
    int rightMin = findMinimalDiffRec(node.getRight(), node.getValue());
    
    return Math.min(leftMin, rightMin);
  }
  
  public static void main(String[] args) {
    Tree tree = buildTree();
    System.out.println(findMinimalDiff(tree.getRoot()));
  }
}

class Node {
  private int value;
  private Node left;
  private Node right;
  
  public Node(int value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
  
  public void setRight (Node right) {
    this.right = right;
  }
  
  public void setLeft (Node left) {
    this.left = left;
  }
  
  public Node getLeft() {
    return left;
  }
  
  public Node getRight() {
    return right;
  }
  
  public int getValue() {
    return value;
  }
}

class Tree {
  private Node root;
  
  public Tree(Node root) {
    this.root = root;
    
  }
  
  public Node getRoot() {
    return root;
  }
}

- Nir February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

class Node {
    int val;
    Node left,right;

    Node(int x) {
        val = x;
    }
}

class minDiffTree {
    public static void main(String args[]) {
        Node x = new Node(10);
        x.left = new Node(5);
        x.right = new Node(16);
        x.right.left = new Node(12);
        x.right.right = new Node(20);
        System.out.println(inorder(x));
    }

    public static int inorder(Node x) {
        Stack<Node> s = new Stack();
        int min = Integer.MAX_VALUE;
        Node current = x;
        Node prev = null;
        while(true) {
            if(current!=null) {
                s.push(current);
                current = current.left;
            }
            else if(!s.isEmpty()) {
                current = s.pop();
                if(prev!=null) {
                    int temp = Math.abs(current.val-prev.val);
                    if(temp<min) {
                        min = temp;
                    }
                }
                prev = current;
                current = current.right;
            }
            else {
                break;
            }
        }
        return min;
    }
}

- dklol March 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

template<class T>
T Tree<T>::MinDiffInBST()
{
	return m_root ? MinDiffInBST(m_root, nullptr) : -1;
}
template<class T>
T Tree<T>::MinDiffInBST(Node<T>* current, Node<T>* previous)
{
	T min = LONG_MAX;
	// Use In-Order traversal to find min diff between any 2 nodes
	if (current) {
		min = MinDiffInBST(current->Left(), current);
		if (previous)
			min = MIN(min, abs(current->Item() - previous->Item()));
		min = MIN(min, MinDiffInBST(current->Right(), current));
	}
	return min;
}

- funcoolgeek March 05, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
      def __init__(self, val, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right

def min_two_node_diff(tree):
	if tree == None:
		return float("inf")
	compare_with_left, compare_with_right = float("inf"), float("inf")
	if tree.left:
		compare_with_left = tree.val - right_most_val(tree.left)
	if tree.right:
		compare_with_right = left_most_val(tree.right) - tree.val
	return min(compare_with_left, \
			   compare_with_right, \
			   min_two_node_diff(tree.left), \
			   min_two_node_diff(tree.right))

def right_most_val(tree):
	if (tree.right == None):
		return tree.val
	return right_most_val(tree.right)

def left_most_val(tree):
	if (tree.left == None):
		return tree.val
	return left_most_val(tree.left)

bst = Node(10, Node(5), Node(16, Node(12), Node(20)))
print(min_two_node_diff(bst))

- Johnny March 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is O(n) solution. For every node, get min value for left sub tree and max value from right subtree. Check difference between node and min from left subtree. Calculate difference between node and max from right subtree.

static int min_diff = Integer.MAX_VALUE;
    
static int minDiff(Node root)
{
    findMinMax(root);
    return min_diff;
}

static int[] findMinMax(Node root) {
    int[] val = new int[2];
    int min = - 1, max = -1;
    if (root.left != null) {
	   min = findMinMax(root.left)[0];
	   val[0] = min;
    } else {
        val[0] = root.val;
    }
    if (root.right != null) {
	   max = findMinMax(root.right)[1];
	   val[1] = max;
    } else {
	   val[1] = root.val;
    }
    if (max > 0 && max - root.val < min_diff) min_diff = (max - root.val);
    if (min > 0 && root.val - min < min_diff) min_diff = (root.val - min);
    return val;
}

- Kalpesh Balar March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hello

- Kalpesh Balar March 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stack>
#include <limits>
#include <algorithm>

struct Node {
    Node() : left( NULL ), right( NULL ) {}

    size_t val;
    Node* left;
    Node* right;
};

size_t minDiff( Node root ) {
    std::stack<Node*> stack;
    Node* n = &root;
    Node* prev = NULL;
    size_t min = std::numeric_limits<size_t>::max();

    while ( !stack.empty() || n != NULL ) {
        if ( n ) {
            stack.push( n );
            n = n->left;
        }
        else {
            n = stack.top();
            stack.pop();

            if ( prev ) {
                min = std::min( min, n->val - prev->val );
            }
            prev = n;

            n = n->right;
        }
    }
    return min;
}

- vinser52 May 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If we had a (sorted) list of integers, then the minimum difference between any two numbers in the list would necessarily be the smallest difference between two adjacent nodes.

In this case we don't have a list, however we can still visit a BST in sorted order through an in-order visit. This reduces the problem to keeping track of the minimum difference between every step of an in-order visit.

static Node prev;
int findMin(Node bst, int currentMin) {
   if (bst == null) {
     return currentMin;
   }

  currentMin = findMin(bst.left, currentMin);
  if (prev != null) {
    int diff = Math.abs(bst.value - prev.value);
    if (diff < currentMin) {
      currentMin = diff;
    }
    prev = node;
  }
  currentMin = findMin(bst.right, currentMin);

  return currentMin;
}

int min = findMin(root, Integer.MAX_VALUE, null);

- Pasquino May 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import numpy as np

class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.data = val
def insert(root, node):
    if root is None:
        root = node
    else:
        if (root.data > node.data):
            if(root.left is None):
                root.left = node
            else:
                insert(root.left, node)
        else:
            if(root.right is None):
                root.right = node
            else:
                insert(root.right, node)

def postorder(root, nodes=[]):
    if not root: return []
    
    postorder(root.left)
    nodes.append(root.data)
    postorder(root.right)
    
    return nodes

def solution(root):
    nodes = postorder(root)
    minim = np.inf
    for i in range(len(nodes)-1):
        tmp = nodes[i+1] - nodes[i]
        if (tmp < minim):
            minim = tmp
    return minim

- silvio.s December 15, 2018 | 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