Guys , for this question, i have been able to come up with the
O(n logn) - by sorting, and
O(n.k) - by Tournament Principle algorithms,

I read in a few places about Ordered Statistics but couldnt get anything out of it.
Please can some1 give me an O(n) algo ????

I have a Microsoft Interview tomorrow :)

4
Contributors
5
Replies
6
Views
7 Years
Discussion Span
Last Post by JeffGrigg

Just want to make it clear that i m looking for kth largest in a single array, and not in the union of 2 sorted arrays..

I would use moving maximums to k array or keeping sorted k length array built from the long array. Or I would adapt quicksort to take pivots from correct side.

Edited by pyTony: n/a

priority queue with some adaptation , but O(n) is quite hard

Keeping a sorted list/tree of k values would be O(n log k), I think.

If someone asserts that k is a constant, making this O(n), then I'll assert that for any given run, n is a constant, so it's really O(1). ;->

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.