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 :)
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.
Got inspired to code the least trivial divide and conquer solution in Python:
kth biggest/smallest without sorting
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). ;->
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.