Walmart Labs Interview Question for Applications Developers


Country: India
Interview Type: In-Person




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

If you have a tree that stores the height of each branch, then you can use that information to locate the Kth element by simply traversing to the Kth element in the tree. This would take only O(log n) operations. However, most tree implementations do not store height information so this operation can be done in O(log n + k) time by traversing the tree to the smallest element and then navigating the tree until you find the k th item. I've implemented the second approach below:

static class Node<T>{
	Node<T> left, right;
	T value;
}

public static Object getKthSmallest(Node<T> tree, int k){
	if(tree == null){
		throw new NullPointerException();
	}
	if(k < 1){
		throw new IllegalArgumentException();
	}
	Object[] results = getKthSmallestRecur(tree, k);
	return results[1];
}

private static Object[] getKthSmallest(Node<T> node, int k){
	Object[] tracker;
	int found = 0;
	//consider left
	if(node.left != null){
		tracker = getKthSmallest(node.left, k);
		if(tracker[1] != null){
			return tracker;
		}
		found += tracker[0];
	}
	//consider self
	found++;
	if(found == k){
		return new Object[]{k, node.value};
	}
	if(node.right != null){
		tracker = getKthSmallest(node.right, k-found);
		if(tracker[1] != null){
			return tracker;
		}
		found += tracker[0];
	}
	return new Object[]{found, null};
}

- zortlord December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simple inorder traversal should work here. In the current implementation there are two methods with the same signature but different return types. I'm not a Java person but this looks like trouble.

This is what I lashed up in C++:

template <typename T>
struct Node
{
    Node<T>* Left;
    Node<T>* Right;
    T Value;
};

template <typename T>
static const Node<T>*
GetKthSmallestWorker(const Node<T>* node, int& k)
{
    const Node* found = nullptr;

    if (node->Left)
    {
        found = GetKthSmallestWorker(node->Left, k);
    }

    if (nullptr == found)
    {
        if (--k == 0)
        {
            found = node;
        }
        else if (Node->right)
        {
            found = GetKthSmallestWorker(Node->Right, k);
        }
    }

    return found;
}

template <typename T>
Node<T>*
GetKthSmallest(const Node<T>& node, int k)
{
    return (k > 0) ? GetKthSmallestWorker(&node, k) : nullptr;
}

- MrZipf December 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming that nodes in the BST hold counters for the number of elements in each of its subtrees. This is pretty much the approach zortlord presented but did not code.

In C:

int kth(Node *p, int k)
{
	if (!p)
		return ERROR;

	if (k == p->left_count+1)
		return p->element;

	if (k <= p->left_count) {
		return kth(p->left, k);
	}
	else {
		return kth(p->right, k - p->left_count - 1);
	}
}

- Victor December 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Doing inorder traversal and keeping a counter for kth min number

int smallest=0;
void kthNode(treeNode *head, int k)
{
        static int counter = 0;
        if (!head || (k < 0))
                return;
        kthNode(head->left, k);
        counter++;
        if (k == counter) {
                smallest = head->data;
                return;
        }
        kthNode(head->right, k);
}

- aka December 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is O(n) if you want the largest number.

- Victor December 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Just implemented below logic given in stackoverflow:
Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.
Now, suppose we are at node T:

k == num_elements(left subtree of T), then the answer we're looking for is the value in node T
k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

int total(treeNode *head)
{
        if (!head)
                return 0;
        return 1 + total(head->left) + total(head->right);
}

void kthNode(treeNode *head, int k)
{
        int to;
        if (k < 0 || !head) {
                printf("couldn't find it\n");
                return;
        }
        if (k == 0) {
                printf("got it%d\n", head->data);
                return;
        }
        to = total(head->left);
        if ((to+1) == k) {
                printf("found the rising star %d\n", head->data);
                return;
        }
        if ((to+1) > k)
                kthNode(head->left, k);
        else
                kthNode(head->right, k-(to+1));
}

- aka December 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Doubt that a O(log n) solution can be given for this problem, unless the BST is balanced probably?

Worst case, take a BST that is build completely with just the right tree
Example:

1
   2
      3
         4
            5
               6

In order to find the 6th element, we have to traverse through down the right chain and we will have a complexity of O(n).

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

int count;

int main()
{

int K;
printf( "Enter value of K \n");
scanf ("%d", &K);
count = k;
inorder(head);
}

void inorder( struct node *head)
{
if(head == NULL)
return ;
inorder(head->left);
count --;
if (count == 0)
{
printf("Kth smallest element = %d ", head->data);
return;
}
inorder(head->right);
}

- Shivaprasad December 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question has certain amount of uncertainty/ambiguity. It is actually pretty good question if the goal is to trigger the discussion to resolve that.
For instance, O(log(N)) possible when tree is balanced and one of the following condition is met
a) k << N, so we can use in-order traversal
b) each node store the count of nodes in the subtree rooted by the node, so we can find kth element recursively.

- 0xF4 December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursive approach

public int findSmallest(int k) {
        return findSmallest(root, k);
    }

    private int size(BSTNode node) {
        if (node != null) {
            return 1 + size(node.getLeft()) + size(node.getRight());
        }
        return 0;
    }

    private int findSmallest(BSTNode node, int k) {
        int count;
        count = size(node.getLeft()) + 1;

        if (count== k) {
            return node.getData();
        }
        if(count > k){
            return findSmallest(node.getLeft(),k);
        }else{
            return findSmallest(node.getRight(),k-count);
        }
        
    }

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

We can keep track of the elements in a subtree of any node while building the tree. As we have to find the kth smallest element so we can maintain the no. of elements in the subtree of a node. Even we have to maintain the no. of element in the left subtree only.

Let us assume that root is having x elements in its left subtree then
1) if k=x+1 ,then root is kth smallest element.
2)if k<x ,we continue our search in the left subtree.
3)if k>x+1 , then we have to find (k-x-1)th element in the right subtree of the root.

here is a c code implementation of O(logn):

int k_smallest_element(node_t *root, int k)
{
    int ret = -1;
 
    if( root )
    {
        node_t *pTraverse = root;
 
        while(pTraverse)
        {
            if( (pTraverse->lCount + 1) == k )
            {
                ret = pTraverse->data;
                break;
            }
            else if( k > pTraverse->lCount )
            {
                k = k - (pTraverse->lCount + 1);
                pTraverse = pTraverse->right;
            }
            else
            {
                pTraverse = pTraverse->left;
            }
        }
    }
 
    return ret;
}

- Sunny Jain April 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can keep track of the elements in a subtree of any node while building the tree. As we have to find the kth smallest element so we can maintain the no. of elements in the subtree of a node. Even we have to maintain the no. of element in the left subtree only.

Let us assume that root is having x elements in its left subtree then
1) if k=x+1 ,then root is kth smallest element.
2)if k<x ,we continue our search in the left subtree.
3)if k>x+1 , then we have to find (k-x-1)th element in the right subtree of the root.

here is a c code implementation of O(logn):

int k_smallest_element(node_t *root, int k)
{
    int ret = -1;
 
    if( root )
    {
        node_t *pTraverse = root;
 
        while(pTraverse)
        {
            if( (pTraverse->lCount + 1) == k )
            {
                ret = pTraverse->data;
                break;
            }
            else if( k > pTraverse->lCount )
            {
                k = k - (pTraverse->lCount + 1);
                pTraverse = pTraverse->right;
            }
            else
            {
                pTraverse = pTraverse->left;
            }
        }
    }
 
    return ret;
}

- Sunny Jain April 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int findSmallestElement( TreeNode node, int finalValue ) {
		if(node != null) {
			  finalValue = findSmallestElement(node.left, finalValue);
			  finalValue = findSmallestElement(node.right, finalValue);
			if( node.data < finalValue ) {
				finalValue = node.data;
			}
		}
		return finalValue;
	}

- Krishna April 27, 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