Rakuten interview question

Find the Kth largest number in an array.

Interview Answers

Anonymous

22 Mar 2019

Create a min heap of size k. Iterate down the list. If element is larger than the min number in min heap, replace the min heap's min element with it. Time complexity is O(k log k + n + n log k) worse case. Space complexity is O(n+k)

Anonymous

14 Mar 2019

Multiple approaches - efficient one is maintaining the K elements max heap. other are modified quick sort and brute force.