Amazon Interview Question for SDE1s


Country: India




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

What does it mean "you are not allowed to traverse the tree"?
I assume it means you are not allowed to walk the tree node-by-node to get the k-th element or to calculate the sum (so no O(n) solution...)

1) how to find the kth element
if the tree is very large, finding the k-th element with in-order traversal is slow. It takes O(k). Faster is, if you store on each node the size of the subtree and modify the in-order traversal to skip whole subtrees if theire size is larger than k-remaining, this takes O(lg(n)), where n is the
number of nodes (it becomes a pre-order traversal, BST assumed to be balanced):

2) how to calculate the sum
Similar to 1) maintain the sum of the subtree, in addition of the tree-size, per nodes. Now the whole tree is the sum of all nodes. Everytime you skip a subtree, you remove that subtree's
sum from the current sum:

long long getRemainingSum(Node* node, int k)
{
	long long currentSum = node->treeSum;
	stack<pair<Node*, bool>> s;
	s.push(pair<Node*, bool>(node, false));
	while(s.size() > 0) {
		Node *c = s.top().first; 
		if(c->treeSize == k) return currentSum;
		if(c->treeSize < k) {
			// subtree can be jumped over
			k -= c->treeSize;
			currentSum -= c->treeSum;
			s.pop();
		} else if(!s.top().second) {
			// go first left
			s.top().second = true;
			if(c->left != nullptr) s.push(pair<Node*, bool>(c->left, false));
		} else {
			// go right
			s.pop();
			if(c->right != nullptr) s.push(pair<Node*, bool>(c->right, false));			
		}
	}
	return -1; // assume -1 clearly indicates k is out of range
}

3) This requires two additional fields per Node, so space complexity is O(n). Time complexity
is therefore O(lg(n)). In addition all tree operations must maintain this additional fields which has no impact on the big-O of the run-time of insert, delete, update of known self-balancing BSTs like RGB, AVL, 2-3 etc. Further it's worth mentioning it only makes sense if the tree is roughly balanced...

- ChrisK December 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Seems weird. I would say convert to min-heap and while you are looking at each node calculate the sum of the tree. Then pop-off `k` elements from the min-heap and subtract from the sum. But there's an implicit tree traversal there.

I don't see how you can calculate the sum of tree whose nodes you can't look at? Seems like a problem with the question.

- srterpe December 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

The smallest element in BST is at the left most.
The kth smallest element in BST is at the k left most.

Use a Depth-first search ( DFS ) on the k , start with the left most . Iterate k times leave node. And sum them

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

Traverse the tree in in-order and while you're at it, decrement and track K. When K hits zero then sum N nodes (decrement N for each addition after K hits zero) and then short circuit once N reaches zero. Here's the implementation with runtime O(n+k):

public static int findNSumAfterK(TreeNode treeNode, int k, int n) {
        CounterHolder counterHolder = new CounterHolder(k, n);
        findSum(treeNode, counterHolder);
        return counterHolder.sum;
    }

    private static void findSum(TreeNode treeNode, CounterHolder counterHolder) {
        if (treeNode == null || counterHolder.n <= 0) return;
        findSum(treeNode.left, counterHolder);
        track(treeNode.data, counterHolder);
        findSum(treeNode.right, counterHolder);
    }

    private static void track(int data, CounterHolder counterHolder) {
        if (counterHolder.k == 0) {
            if (counterHolder.n > 0) {
                counterHolder.sum += data;
            }
            counterHolder.n--;
        } else {
            counterHolder.k--;
        }
    }

    static class CounterHolder {
        int k, n, sum;

        public CounterHolder(int k, int n) {
            this.k = k;
            this.n = n;
        }
    }

    static class TreeNode {
        final int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
        }
    }

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

If I can traverse, I may leverage inorder

void inorder(Node* nd, int k, int n, int& i, int& sum) { // i&sum is initialized to 0
    if (i<n && nd->left) inorder(nd->left, k, n, i);
    if (i<n) i++;
    if (i >=k) sum += nd->value;
    if (i<n && nd->right) inorder(nd->right, k, n, i);
}

Not that hard. I guess interviewer meant to avoid this kind by "no traversal".
But if I'm not allowed for it ?
Quite naive solution only I can come up with.

extern BSTTree* root;

Node* min(Node* root) {
    if (root !=nullptr) return min(root->left);
    else return root;
}

Node* nextLarge(Node* n) {
    if (n==nullptr) return n;
    else if (n->right != nullptr) return min(n->right);
    else {
        while (n->parent!=nullptr && n->parent->right==n) {
            n = n->parent;
        }
        return n->parent;
    }
}

int getNSumAfterSmallestK(Node* root, int k, int n) {
    Node* nd = min(root);
    for (int i=0; i<k-1; i++) {
        nd = nextLarge(nd); // ignore if n is null 'cause tree is large enough
    }
    int sum = 0;
    for (int i=0; i<n; i++) {
        nd = nextLarge(nd);
        sum += nd->value;
    }
    return sum;
}

- ghcho20 December 21, 2016 | 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