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 :)