Google Interview Question for Software Engineer / Developers


Country: United States




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

for inorder traversal:
=> if k-left == 1: n is curr node
=> else if k > left+1 : n = n.right, k = k-left-1
=> else : n = n.left

- Adi November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't understand what does n mean? Can you explain more about the question and answer?

- fenghanlu November 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Adi's solution seems to be correct with a few examples I tried.
'n' is the current node, the logic should start with n as the root node.

- andy November 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Did you mean a BinaryTree with n number of nodes and find k'th node while traversing in-order?
Or 
You are given a node "n" and find k'th element under that subtree.

I am sure it's not this trivial as your question sounds.

- pk November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Java Version without recursion
		Node currentNode = rootNode;
		int k = 1;
		int currentK = k;
		while (currentNode != null) {
			int currentNodeRank = currentNode.count;
			if (currentNode.left != null) {
				currentNodeRank = currentNode.left.count + 1;
			}

			else if (currentNode.right != null) {
				currentNodeRank = 1;
			}
			//System.out.format("nodeRank %s for node %s with current K %d\n",currentNodeRank,currentNode.value,currentK );
			if (currentK == currentNodeRank) {
				System.out.println("found this " + currentNode.value);
				System.exit(1);
			}
			if(currentK < currentNodeRank) {
				currentNode = currentNode.left;
				continue;
			}
			else {
				currentK = currentK - currentNodeRank;
				currentNode = currentNode.right;
			}
		}

- naren November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node findKthNode(Node root, int number) {
     if (root == null) {
         return null; //or throw an exception
     }
     int leftRange = 0;
     int rightRange = root.totalElements;
     
     if (number > rightRange) {
         return null; //or throw an exception
     }
     Node current = root;
     while (current != null) {
         int currentTotal = current.totalElements;
         Node left = current.left;
         int leftTotal = left == null ? 0 : left.totalElements;
         
         int currentPosition = leftRange + leftTotal + 1;
         if (currentPosition == number) { //found it
             return current;
         } else if (currentPosition < number) { //go right
             leftRange = currentPosition;
             current = current.right;
         } else if (currentPosition > number) { //go left
             rightRange = currentPosition;
             current = current.left;
         }
     }      
     
     return null; //not possible unless nodes' totalElements corrupt
}

- Anonymous November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node findInOrder(Node n, int k){
		if(n.childno-1 == k)
			return n;
		if(n.childLeft != null && n.childLeft.childno >= k-1)
			return findInOrder(n.childLeft, k);
		else 
			return findInOrder(n.childRight, k);
	}

- Monica November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int inorder(struct node *tree1)
{


if(tree1!=NULL)
{
inorder(tree1->left);
if(count==5) where count is a global variable
return(tree1->no);
else
{
count++;
printf("%d ",tree1->no);
}
inorder(tree1->right);
}
}

- mithilesh kumar (tict kolkata) November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

class InOrderTraversalFindK
    {
        public class Node
        {
            public Node Left;
            public Node Right;
            public int Count;
        }

        public static Node findK(Node root, int k)
        {
            if (k > root.Count) return null;
            if (k == root.Count) return root;
            if (k <= root.Left.Count)
            {
                return findK(root.Left, k);
            }
            else
            {
                return findK(root.Right, k - root.Left.Count);
            }
        }

        public static Node findKNonRecursive(Node root, int k)
        {
            if (k > root.Count) return null;

            Node curNode = root;
            while (curNode!=null)
            {
                if (k == curNode.Count) return curNode;
                if (k <= curNode.Left.Count)
                {
                    curNode = curNode.Left;
                }
                else
                {
                    k -= curNode.Left.Count;
                    curNode = curNode.Right;
                }    
            }
            return null;
        }
    }

- C# solution November 10, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think findk is right. Consider a node with one left and one right. root.count == 3. Your code will return root in this case, but you want it to return root.right, since its in order traversal.

- No Name Smith November 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node kthRecurse(Node root, int k) {
    int lSize = (root.left == null) ? 0 : root.left.getCount();
    if (k <= lSize) return kthRecursive(root.left, k);
    if (k == 1) return root;
    return kthRecursive(root.right, k - 1 - lSize);
}

public Node kthIterative(Node root, int k) {
    Node cur = root;
    int i = k;
    while (true) {
        int lSize = (cur.left == null) ? 0 : cur.left.getCount();
        if (k <= lSize) {
            cur = cur.left;
            continue;
        }
        if (k == 1) break;
        cur = cur.right;
        i = i - ls - 1;
    }
    return cur;
}

Something like this could probably work.

- No Name Smith November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can just maintain a current node and compare the number of its left child and k, then move the current node. Here is my implementation and test cases.

#include <iostream>
using namespace std;

struct TreeNode{
    int num, no;//the amount of nodes and the id
    TreeNode *left, *right;
    TreeNode(int _num, int _no):num(_num), no(_no), left(NULL), right(NULL){}
};

TreeNode* solve(TreeNode *root, int k){
    if(root == NULL || root->num<k || k<=0)   return NULL;
    TreeNode *cur = root;
    while(k > 0){
        int lnum = cur->left?cur->left->num:0;
        int rnum = cur->num-lnum-1;
        if(k == lnum+1) return cur;
        else if(k<=lnum){
            cur = cur->left;
        }else{
            cur = cur->right;
            k -= lnum+1;
        }
    }
    return NULL;
}

int main(){
    TreeNode *t1 = new TreeNode(10, 1);
    TreeNode *t2 = new TreeNode(4, 2);
    TreeNode *t3 = new TreeNode(5, 3);
    TreeNode *t4 = new TreeNode(3, 4);
    TreeNode *t5 = new TreeNode(2, 5);
    TreeNode *t6 = new TreeNode(2, 6);
    TreeNode *t7 = new TreeNode(1, 7);
    TreeNode *t8 = new TreeNode(1, 8);
    TreeNode *t9 = new TreeNode(1, 9);
    TreeNode *t10 = new TreeNode(1, 10);
    t1->left = t2;
    t1->right = t3;
    t2->left = t4;
    t3->left = t5;
    t3->right = t6;
    t4->left = t7;
    t4->right = t8;
    t5->left = t9;
    t6->right = t10;
    cout<<solve(t1, 8)->no<<endl; //3
    cout<<solve(t1, 5)->no<<endl; //1
    cout<<solve(t1, 3)->no<<endl; //8
    cout<<solve(t2, 3)->no<<endl; //8
    cout<<solve(t3, 1)->no<<endl; //9
}

/*
                       10
                      / \
                     4  5
                    /\  /\
                   3 0 2 2
                  /\  /\ /\
                 1 1 1 00 1
*/

- Mr.Giraffe November 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node findKth(Node n, int k) {
	// first check if the tree has k node
	if (n.getNum() < k) { return null; }
	
	// otherwise, the kth is in this tree.
	if (n.left.getNum() >= k) {
		// check if kth is in left subtree
		return findKth(n.left, k);
	} else if (n.left.getNum() = k-1) {
		// see if our root is actually the kth
		return n;
	} else {
		// then it has to be in the right subtree
		// need to minus the number of left subtree and the root first.
		int minus = n.left.getNum() + 1;
		return findKth(n.right, k-minus);
	}
}

public Node findKthNonRec(Node n, int k) {
	// first check if the tree has kth.
	if (n.getNum() < k) { return null; }
	
	int count = k;
	Node current = n;
	while (current.left.getNum() != k-1) {// while current is not the kth
		if (current.left.getNum >= k) {// see if kth in left subtree
			current = current.left;
		} else {// kth is in right subtree
			count = count - 1 - current.left.getNum();
			current = current.right;
		}
	}
	return current;
}

- tk November 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Node {
	int value;
	Node left;
	Node right;
	int count;
}

public Node kthInOrder (Node a, int k) {
//return the kth node of an in order traversal
	Node curr = a;
	int n_visited = 0; //visit the root
	while (n_visited <= k) {
		int n_left = curr.left==null ? 0 : curr.left.count;
if (k == n_visited + n_left) return curr;
		//visit more nodes
		if (n_visited + n_left < k) {
			//go right
			n_visited += curr.n_left;
			curr = curr.right;
		} else curr = curr.left;
	}
	return null;
}

- Anonymous November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct CTreeNode{
    int count;
    int val;
    CTreeNode *left;
    CTreeNode *right;
    CTreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

CTreeNode *findNodeInOrder(CTreeNode *root, int k){
    if(root==nullptr || k<0 || k>root->count) return nullptr;
    if(k==root->count){
        if(root->right==nullptr)
            return root;
        return findNodeInOrder(root->right, root->count);
    }
    if(root->left!=nullptr){
        if(root->left->count>=k)
            return findNodeInOrder(root->left, k);
        else if(root->left->count==k-1)
            return root;
        else
            return findNodeInOrder(root->right, k-root->left->count-1);

    }
    return findNodeInOrder(root->right, k);
}

- simon.zhangsm December 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public Node FindKthRecursive(Node n, int k)
    {
        if (k > n.data)
            return null;

        while (n.left != null && n.left.data >= k)
            n = n.left;

        if (n.left != null)
            k -= n.left.data;

        if (--k == 0)
            return n;
        else
            return FindKthRecursive(n.right, k);
    }

    public Node FindKthIterative(Node n, int k)
    {
        if (k > n.data)
            return null;

        while (true)
        {
            while (n.left != null && n.left.data >= k)
                n = n.left;

            if (n.left != null)
                k -= n.left.data;

            if (--k == 0)
                return n;

            n = n.right;
        }
    }

- pavel.kogan January 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tree findkthNode(Tree node, int k)
{
	int parent=0;
	//

	while(node!=null)
	{
		int leftCount=node.leftSubTreeCount;
		int rightCount=node.rightSubTreeCount;

		int currPos=leftCount+parent+1;

		if(currPos==k)
			return node;
		else if(currPos < k)
			node=node.left;
		else{
			node=node.right;
			parent=currPos;
		}

	}

	return null;

}

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

Tree findkthNode(Tree node, int k)
{
int parent=0;
//

while(node!=null)
{
int leftCount=node.leftSubTreeCount;
int rightCount=node.rightSubTreeCount;

int currPos=leftCount+parent+1;

if(currPos==k)
return node;
else if(currPos < k)
node=node.left;
else{
node=node.right;
parent=currPos;
}

}

return null;

}

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

Tree findkthNode(Tree node, int k)
{
	int parent=0;
	//

	while(node!=null)
	{
		int leftCount=node.leftSubTreeCount;
		int rightCount=node.rightSubTreeCount;

		int currPos=leftCount+parent+1;

		if(currPos==k)
			return node;
		else if(currPos < k)
			node=node.left;
		else{
			node=node.right;
			parent=currPos;
		}

	}

	return null;

}

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

Java Implementation.

import java.util.*;
/***
 *                       5
 *             3                  9
 *       2          4         6
 ***/
class TreeNode{
    int val;
    int size;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val, int size) {
        this.val = val;
        this.size = size;
    }
}
public class KthNodeBinaryTree{
    public TreeNode getKthNode(TreeNode root, int kth) {
        TreeNode curt = root;
        if (curt == null) {
            return curt;
        }
        while (curt != null) {
            if (kth > curt.size) {
                return null;
            }
            TreeNode left = curt.left;
            if (left == null) {
                if (kth == 1) {
                    return curt;
                }
                curt = curt.right;
                kth--;
            } else {
                if (kth >= left.size + 1) {
                    kth = kth - left.size;
                    if (kth == 1) {
                        return curt;
                    } else {
                        kth = kth - 1;
                        curt = curt.right;
                    }
                } else {
                    curt = curt.left;
                }
            }
        }
        return curt;
    }
    public static void main(String[] args) {
        KthNodeBinaryTree code = new KthNodeBinaryTree();
        TreeNode root = new TreeNode(5, 6);
        TreeNode node1 = new TreeNode(3, 3);
        TreeNode node2 = new TreeNode(9, 2);
        TreeNode node3 = new TreeNode(2, 1);
        TreeNode node4 = new TreeNode(4, 1);
        TreeNode node5 = new TreeNode(6, 1);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        TreeNode res = code.getKthNode(root, Integer.parseInt(args[0]));
        System.out.println((res != null ? res.val : "Your input number is larger than the tree size"));
    }
}

- zhangboryan March 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

function findNode(N,k) {
    if(k <= 1) {
        return N;
    }
    if((N.left != undefined) && N.left.count >= k - 1) {
        return findNode(N.left, k - 1);
    } else {
        return findNode(N.right, k - 1 - N.left.count);
    }
}

- JavaScript - Recursive November 07, 2014 | 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