Microsoft student Interview Question for Students


Country: India
Interview Type: Written Test




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

The answers above are flawed in that not all recursive calls return value.

Here is my answer to the question. I think that this is the correct one. The time complexity of my approach is O(k).

basicalgos.blogspot.com/2012/03/23-find-kth-node-in-binary-search-tree.html

Comments are welcome!

- Andy March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another possible answer is :-

convert this given BST to a sorted doubly linked list in place (this also has 2 pointers analogous to prev and next ptrs).

Now. from the end of the list, find the kth node. This gives the kth maximum element in the given BST.

may be this is an O(n) algorithm and not O(logn).

- Anonymous March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

K’th Largest Element in BST . Learn how to think for such problem and solve with recursion gohired.in/2015/03/kth-largest-element-in-bst-when.html

- dd March 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

K’th Largest Element in BST . Learn how to think for such problem and solve with recursion gohired.in / 2015/03/kth-largest-element-in-bst-when.html

- dd March 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gohired.in/2015/03/kth-largest-element-in-bst-when.html

- dd March 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

I am fixing my previous wrong implementation here:

struct Node {
    Node *left;
    Node *right;
    int data;
};

Node* find_kth_largest(Node *pNode, int& K)
{
    Node *pTmp = NULL;

    if (pNode == NULL)
        return NULL;

    if (pNode->right){
        pTmp = find_kth_largest(pNode->right, K);
        if (pTmp) {
            return pTmp;
        }
    }

    if (0 == K) {
        return pNode;
    }
    else {
        K--;
        if (pNode->left){
            pTmp = find_kth_largest(pNode->left, K);
            if (pTmp)
                return pTmp;
        }
    }

    return NULL;

}

- ashot madatyan March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wont work for edge case when the tree has one node and k = 1. it is supposed to return the same node instead of null.

- Anonymous March 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just please notice that the find utility uses a 0-based logic. So, if the K=1, then this will actually request the second largest item. For the rest of the logic, you can use the code and have it run with any data you find appropriate.

- ashot madatyan March 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can do using inorder traversal.

- Anonymous March 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what you did is find min kth and your code won't return data if i is not k which could be wrong

- qualcommer March 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

For finding the Kth maximum number, use reverse inorder traversal.

- codewarrior March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int inorder(node *root ,int k)
{
static int i=0;
if(node)
{
inorder(root->left,k);
i++;
if(i==k)
return node->data;
inorder(root->right,k);
}
}

- Anonymous March 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Before this need to check whether the tree is already sorted or not.

- akp March 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I got it it is already given it is the binary search tree and it should be sorted in descending order.

- Anonymous March 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this returns the kth minimum element. Return (n-k)th element. OR do a reverse inorder traversal.

- Sasi March 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int FindElement(Node n , int k, int counter){
	if(n==null) return 0;
	FindElement(n.right,counter);
	counter++;
	If(k==counter)  
		return n.data;
	FindElement(n.left,counter);
}

- Anonymous March 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Perform an inorder traversal (if find Kth minimum number) or reverse inorder traversal (if find Kth maximum number), we shall need to maintain the stack ourselves.

- codewarrior March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Tree is BST with unique number, So if you perform inorder operation,WE will get element in shorted order(ascending order). So perform reverse Inorder operation means RNL(right ,node ,left) that will give element in descending order and we can directly choose Nth maximum from there. worst case complexity O(n)

- javed March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void FindKthMax(BTNODE* root, int k)
{
    if (root == NULL)
    {
        return;
    }

    std::stack<BTNODE*> stkNode;
    BTNODE* p = root;
    int nVisited = 0;

    while (p != NULL || !stkNode.empty())
    {
        if (p != NULL)
        {
            stkNode.push(p);
            p = p->rchild;
        }
        else
        {
            p = stkNode.top();
            stkNode.pop();
            if (++nVisited == k)
            {
                printf("We've got it, Kth maximum number is %c", p->chVal);
                break;
            }
            p = p->lchild;
        }
    }

    if (nVisited < k)
    {
        printf("Sorry, K overflowed.");
    }
}

- codewarrior March 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I doubt the code may need deal with the case when the tree is extremely unbalanced, for example having no right branch at all

- Anonymous March 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

suppose we have K as global variable or class member initialized for Kth biggest member.
you just need to traverse in In-Order ( visit Right before Left for biggest, else visit Left then Right)

void FindKthBiggest(TreeNode *pNode)
	{
		if(pNode==NULL)
			return;
		FindKthBiggest(pNode->Right);
		K--;
		if(K==0)
                 {
			cout <<endl<<K <<"th biggest="<<pNode->Data<<endl;
                        return;
                 }
		FindKthBiggest(pNode->Left);
	}

- hmonfared-Sky March 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct tree* kthMax(struct tree *root, int *k)
{
struct tree *ptr;

if(root == NULL)
return NULL;
ptr = kthMax(root->right, k);
if(ptr)
return ptr;

*k = *k - 1;
if(*k == 0)
return root;
return kthMax(root->left, k);

}

- Rajesh Kumar March 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The technique is rather opposite to in-order. We visit the right subtree, then root, then left subtree. Whenever we visit a node, we decrement a counter (k). This has to be passed by reference.
Here is the code below in C#

public TreeNode FindKthLargestInBST(TreeNode root, int K)
        {
            int counter = K;
            return FindKthLargestInBST(root, ref counter);
        }
        
        public TreeNode  FindKthLargestInBST(TreeNode root,  ref int K)
        {
            if (root == null)
                return null;
     
            TreeNode result;
            result = FindKthLargestInBST(root.right,  ref K);
            if (result != null) return result;
            if (K == 1) return root;
            K--;
            result = FindKthLargestInBST(root.left,  ref K);
            if (result != null) return result;

            return null; 
        }

- Mourad June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Finding the kth Maximum in a BST
int found=0,node* nd;
node* k_th_max(node *root,int k)
{

	static int count=0;

	if(!root)
		return (node *)0;

	if(root && !found)
	{
		nd=k_th_max(root->right,k);
		
		if((++count)==k)
		{
			found=1;
			return root;
		}
		
		
		
		nd=k_th_max(root->left,k);
							
	}	
	return nd;
}

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

Flawless Code... Enjoy!!!

node* KthMax(node* root, int k, int &count)
{
	if(!root)
		return NULL;
	node* result = KthMax(root->right,k,count);
	if(result)
		return result;
	else if ( ++count == k )
		return root;
	else
		return KthMax(root->left,k,count);
}

- Avinash September 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//.... finding the Kth maximum element ......here will use...reversed inorder traversal..and while doing that we will get 2nd element.....will take benifit of sorted reversed onorder traversal

..int count =0; // will use this to track no to reach K
public void getKMaximum(Node root, Int k)
{
if(!root && count<=k)
{

getKMaximum(root.right,K);

count++;
if(count== k )
display root.data.
getKMaximum(root.left,K);
}
}

- just begin April 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

learn how to think with recuirsion and why to use post order or inorder
K’th Largest Element in BST gohired.in/2015/03/kth-largest-element-in-bst-when.html

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

1. inorder traversal
2. instead of displaying element just push the element in a stack of size K.
3. once the stack is full, return stack.pop();

- ABHI.AKS.SINGH June 18, 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