Kth Largest Interview Questions
What is a heap, and how do you find the Kth largest element? — spoken sample answer for Indian interviews.
- 5Questions with answers
- 3Difficulty levels
Questions (5)
Browse beginner, intermediate, and advanced questions with answers — hide them when you want to self-test.
What is a heap, and how do you find the Kth largest element?
Find the kth largest element in an unsorted array.
Maintain a min-heap of size k. Push each number; if heap exceeds k, pop the smallest. The root is the kth largest when done. Complexity: Time O(n log k) , Space O(k)
Full sort then pick index n - k. Complexity: Time O(n log n) , Space O(1) or O(n)
Quickselect is average O(n) but worst case O(n²) unless randomized. For kth smallest, use a max-heap of size k or negate values.
Kth largest in a stream versus in a static array — what changes?
Static array: I can sort O(n log n) or use a min-heap of size k, O(n log k) , or quickselect average O(n) . Stream: I keep a min-heap of size k as numbers arrive. Each insert is log k. I cannot quickselect a stream easily because I do not have the full array. Interviewers love the size-k min-heap because it shows I know what the heap is for. I would ask if k is much smaller than n. That decides heap versus sort.
Why a min-heap of size k for kth largest, not a max-heap?
I want the smallest of the k largest sitting at the top. A min-heap of size k does that. If a new number is bigger than the top, I pop the top and push the new one. At the end the top is the kth largest. A max-heap of the whole array would give me the largest first, and I would pop k times, which is extra memory and extra log n factors. I draw this in interviews because people mix min and max.
When would you use quickselect instead of a heap?
Quickselect is average O(n) and in-place. I use it when I have the full array, I can mutate, and I need one kth element, not a live stream. Worst case is O(n squared) unless I pick pivots carefully. In interviews I mention both and I implement the heap if they want simple correct code under time pressure. If they want the linear average, I write quickselect and I say the worst case.
How do you merge k sorted lists using a heap?
I put the head of each list into a min-heap keyed by value, along with which list it came from. I pop the smallest, append it, and push that list's next node. Time O(N log k) where N is total nodes. This is the same family as kth largest: the heap keeps k candidates. I would not nested-merge lists one by one in an interview unless k is 2. k-way merge is the heap showcase.
Practice with AI mock interviews
Run DSA mock interviews with AI follow-ups, instant feedback, and analytics on AiLx.
Free to start · No credit card required