Facebook

www.facebook.com

Interview Question

Software Engineer Interview Chicago, IL

"Reverse" of the problem if finding k-th smallest element

  : I had to find k-th largest.
Tags:
data structure, traversal
Answer

Interview Answer

4 Answers

1

Keep a global or reference counter increase it every time you encounter a tree node. Return when the counter == k.

Interview Candidate on Dec 5, 2012
0

do an in-order traversal which gives you a sorted list. the rest is obvious.

aw on Dec 7, 2012
0

do an in-order traversal which gives you a sorted list. the rest is obvious.

aw on Dec 7, 2012
0

The tree data structure is red herring, it does not help in any way to find the kth element
The solution to this problem is called partial sorting and can achieve O(n) - number of nodes time complexity

Anonymous on Feb 3, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.