Google Interview Question for Software Engineer / Developers


Country: Israel
Interview Type: In-Person




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

Do an inorder traversal and stop at k'th element. Use recursion.

- anan January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why use recursion ?. I think it is better to do inorder traversal without recursion.

- abhinav.neela February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the recursive solution:

#include <iostream>

using namespace std;

class FoundInfo {
    public:
    bool found;
    int value;
    
    FoundInfo(bool fnd, int val) {
        this->found = fnd; 
        this->value = val;
    }
};

class Node {
    public:
    int value;
    Node* left;
    Node* right;
    
    Node(int val) {
        this->value = val;
        left = NULL;
        right = NULL;
    }
    
    FoundInfo findKth(int &k) {
        FoundInfo Found(false, 0);    
        if (this->left) {
            Found = this->left->findKth(k);
            if (Found.found) {
                return Found;
            }
        }
        
        --k;
        if ( k == 0 ) {
            Found.value = this->value;
            Found.found = true;
            return Found;
        }
        
        if (this->right) {
            Found = this->right->findKth(k);
        }
        
        return Found;
    }
};

int main() {
    Node* root      = new Node(4);
    Node* child1    = new Node(2);
    Node* child2    = new Node(6);
    Node* gchild11  = new Node(1);
    Node* gchild12  = new Node(3);
    Node* gchild21  = new Node(5);
    Node* gchild22  = new Node(7);
    
    root->left      = child1;
    root->right     = child2;
    child1->left    = gchild11;
    child1->right   = gchild12;
    child2->left    = gchild21;
    child2->right   = gchild22;

    int k=4;
    printf("value(%d)\n", root->findKth(k).value);

   return 0;
}

- pavelkushtia February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is java program-cum-algo that uses pass by reference or pointer

FindKth(Node Root, k)
{
  List<Node> list = new List<Node>();
  Inorder(root, k, list);
  return (list.size>0)? list.get(0) :null;
}

This function will return -1 if we have already reached the kth element.
Once this function returns "list" (which is supposed to be pass by reference) should have the required element.
Inorder(Node N, int k, List<>list)
{
  if(N==null) return 0;
  int l = Inorder(N.Left, k ,list);
  if(l==-1) return -1;
  if(l==k-1) { list.add(N); return -1; } // we found the element
  int r = Inorder(N.Right, k-l-1);
  if(r==-1) return -1;
  return r+l+1;
}

- aditya.eagle059 January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getKthElement(TreeNode root, int k){
        if (k < 0 || root == null){
            return Integer.MIN_VALUE;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        fillStack(stack, root);
        TreeNode current;
        while(!stack.isEmpty()){
            current = stack.pop();
            if (k == 0){
                return current.val;
            }
            k -= 1;
            fillStack(stack, current.rightChild);
        }
        return Integer.MIN_VALUE;
    }

    private static void fillStack(Stack<TreeNode> stack, TreeNode node){
        while (node != null){
            stack.push(node);
            node = node.leftChild;
        }
    }

- GK January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Python in linear O(k):

def find_kth_node(tree, k):
    return _kth_node_recursive(tree.root_node, k)[1]


def _kth_node_recursive(node, k):
    kth_node = None
    if node.left_child:
        k, kth_node = _kth_node_recursive(node.left_child, k)
    if kth_node:
        return k, kth_node
    k -= 1
    if k == 0:
        return k, node
    if node.right_child:
        k, kth_node = _kth_node_recursive(node.right_child, k)
    return k, kth_node

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

InOrder traversal solution without recursion.

public class problem_7{
	public static class Node{
		public Node left;
		public Node right;
		public Integer value;
		public Node(Integer v){
			value = v;
		}
	}
	public static int find(Node head, int k){
		Stack<Node> stack = new Stack<Node>();
		HashMap<Node, Boolean> used = new HashMap<Node, Boolean>();
		stack.push(head);
		int count = 0;
		while(!stack.empty()){
			Node currentNode = stack.pop();
			if(currentNode == null) continue;
			if(currentNode.left == null || used.containsKey(currentNode.left) == true){
				used.put(currentNode, true);
				count++;
				if(count == k)
					return currentNode.value;
				continue;
			}	
			stack.push(currentNode.right);
			stack.push(currentNode);
			stack.push(currentNode.left);
		}
		return -Integer.MAX_VALUE;
	}
	public static void main(String [] args){
		Node head = new Node(4);
		Node l_1 = new Node(5);
		Node r_1 = new Node(0);
		Node l_21 = new Node(3);
		Node l_22 = new Node(7);
		l_1.left = l_21;
		l_1.right = l_22;
		head.left = l_1;
		head.right = r_1;
		System.out.println(problem_7.find(head, 5));
	}
}

- denys.o.p January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This example is not BST.

- biolxj12 February 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The following algorithm calculates the "rank" of each node and stops when the desired rank (i.e. "k" ) is found

int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
   if ( !is_done )
   {
      if ( node_p->m_left )
      {
         rank = FindRank( node_p->m_left, rank, is_done ) + 1;
      }

      if ( rank == k )
      {
         printf("Number : %d, rank: %d\n", node_p->m_number, rank );
         is_done = true;
      }
      else
      {
         if ( node_p->m_right )
         {
            FindRank( node_p->m_right, rank + 1, is_done);
         }
      }
   }
   return rank;
}

- koosha.nejad January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the complete code so you can run and test it

#include "stdafx.h"

class CNode
{
public:
   CNode( int number )
   {
      m_number = number;
      m_right = NULL;
      m_left = NULL;
   }
   int      m_number;
   CNode *   m_right;
   CNode *   m_left;
};

CNode * root = NULL;

void InsertNumber( CNode * node_p, int number )
{
   if ( number > node_p->m_number )
   {
      if ( node_p->m_right )
      {
         InsertNumber( node_p->m_right, number );
      }
      else
      {
         node_p->m_right = new CNode( number );
      }
   }
   else
   {
      if ( node_p->m_left )
      {
         InsertNumber( node_p->m_left, number );
      }
      else
      {
         node_p->m_left = new CNode( number );
      }
   }
}

void PrintTree( CNode * node_p )
{
   if ( node_p )
   {
      PrintTree( node_p->m_left );
      printf("%d,", node_p->m_number );
      PrintTree( node_p->m_right );
   }
}

int k = 4;
int FindRank( CNode * node_p, int rank, bool &is_done )
{
   if ( !is_done )
   {
      if ( node_p->m_left )
      {
         rank = FindRank( node_p->m_left, rank, is_done ) + 1;
      }

      if ( rank == k )
      {
         printf("Number : %d, rank: %d\n", node_p->m_number, rank );
         is_done = true;
      }
      else
      {
         if ( node_p->m_right )
         {
            FindRank( node_p->m_right, rank + 1, is_done);
         }
      }
   }
   return rank;
}

int _tmain(int argc, _TCHAR* argv[])
{
   int A[8]={4,3,6,9,8,2,1,7};

   int i;

   root = new CNode( A[0] );

   for ( i = 1 ; i < 8 ; i++ )
   {
      InsertNumber( root, A[i] );
   }

   PrintTree( root );
   printf("\n");

   bool is_done = false;
   FindRank( root, 0, is_done );
   printf("\n");
	return 0;
}

- koosha.nejad January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the first question to ask is what the k-th mean?
Does it mean the k-th largest ? or the k-th smallest?
or just mean the k-th node you encounter whether by DFS or BFS ?
to be honest, I don't quite understand this question .

- Ike Feng January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe it's asking for kth element when items are sorted ascending

- koosha.nejad January 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

YOu need to ask, do we know the size ! :D then you can optimize it !

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

Do an inorder traversal and DO NOT USE recursion, use iterative solution. The question is all about it.

- anan February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * Find Kth largest element in given BST 
 * time: average case is O(logN), worst case is O(n) if it's not balanced BST
 * space: O(1)
 * 
 * idea: 
n == num_elements(left subtree of tree), value=root.val;  
n > num_elements(left subtree of T), ignore the left subtree, then find the k - num_elements(left subtree of T) smallest element of the right subtree.
n < num_elements(left subtree of T), find kth smallest element in left subtree.

 */
class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
  public TreeNode(int x) { val = x; }
}

public class findNLargestBST {
	
	// assume it is balanced BST
	public static int depth (TreeNode root) {
		int depth =0;
		if (root == null) return depth;
		TreeNode tmp = root;
		while (tmp !=null) {
			tmp=tmp.left;
			depth++;
		}
		return depth;
	}
	
	public static int NthElement (TreeNode root, int depth, int n) {
		int count = (int) (Math.pow((double)2, depth) -1);
		int e =0;
		int index = count/2+1;
		if (n == index) return e=root.val;
		else if ( n< index) e = NthElement(root.left, depth-1, n);
		else e= NthElement (root.right, depth-1, n-index);
		
		return e;
	}
	public static int NthLargest (TreeNode root, int n) {
		int depth = depth (root);
		int count = (int) (Math.pow((double)2, depth) -1);
		int e =0;
		if (n > count) {
			System.out.println("none");
			e =0;
		} else {
			e = NthElement (root, depth, count-n+1);
		}
		return e;
	}
	public static void main (String[] args) {
		
		/* find second largest: 
		 *        20 
		 *     10    30
		 *              40
		 * 
		 */
		
		TreeNode n1 = new TreeNode(20);
		TreeNode n2 = new TreeNode(10);
		TreeNode n3 = new TreeNode(30);
		TreeNode n4 = new TreeNode(40);
		
		n1.left =n2; n2.right = n3;
		n3.right = n4;
		
		int n=2; 
		System.out.println(NthLargest(n1,n));
		
	}
}

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

convert the tree to a Stack by going from right to left and then pop k elements.

public TreeNode findK(TreeNode node, int k) {

	Stack<TreeNode> stk = new Stack<TreeNode>();
	fillStack(mode, stk);

	TreeNode ret = null;
	for(int index=0; index<k; index++)
		ret = stack.pop();

	return ret;
}

private void fillStack(TreeNode node, Stack<TreeNode> stk) {

	if(null == node)
		return;

	fillStack(node.right, stk);
	stk.push(node);
	fillStack(node.left, stk);	
}

- YD February 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is as follows:

public int getKthElem(TreeNode root, int k) {
      if (root == null)
         return -1;
      int lc = getCount(root.left);
      if (lc == k-1)
         return root.value;
      if (lc >= k)
         return getKthElem(root.left, k);
      else
         return getKthElem(root.right, k-1-lc);
   }
   
   public int getCount(TreeNode root) {
      if (root == null)
         return 0;
      return getCount(root.left)+getCount(root.right)+1;
   }

-1 indicates if not found, you should check with interviewers.
The time efficiency is O(n);

- ningxiner May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static TreeNode kth(TreeNode n, int k) {
int i=0;
Stack<TreeNode> s = new Stack<TreeNode>();
while(true) {
while(n!=null){
s.push(n);
n = n.left;
}
if(s.empty())
break;
n=s.pop();
i++;
if(i == k) {
System.out.println(n.value);
return n;
}
n = n.right;
}
return null;
}

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

public static TreeNode kth(TreeNode n, int k) {
	int i=0;
	Stack<TreeNode> s = new Stack<TreeNode>();
	while(true) {
		while(n!=null){
			s.push(n);
			n = n.left;
		}
		if(s.empty())
			break;
		n=s.pop();
		i++;
		if(i == k) {
			System.out.println(n.value);
			return n;
		}
		n = n.right;
	}
	return null;
}

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

public static Node find(Node root, int k) {

    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);

    while (!queue.isEmpty()) {
      Node temp = queue.remove();
      k--;
      if (k == 0) return temp;

      if (temp.left != null) {
        queue.add(temp.left);
      }
      if (temp.right != null) {
        queue.add(temp.right);
      }
    }
    return root;
  }

- manuelescrig December 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Time O(n), Space O(1)
class Solution {
    int counter;
    TreeNode node;
    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return node.val;
    }

    void inorder(TreeNode root, int k) {
        if (root != null) {
            inorder(root.left, k);
            counter++;
            if (counter == k) {
                node=root;
            }
            inorder(root.right, k);

        }
    }
}

- Ven4Coding September 08, 2020 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

EDIT: Perform in order traversal of the tree via DFS and stop at k-th node.

- autoboli January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is preorder traversal, hence wrong.

- anan January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You were absolutely right, my mistake. Code was removed.

- autoboli January 27, 2015 | Flag


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