How do you find the kth largest element efficiently?
Reported in Stripe interview loops. Heap and selection strategy question with multiple valid approaches.
Interview scenario
Context for Stripe candidates:
Find the kth largest number in an unsorted array where duplicates may exist.
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Stripe: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Maintain a min-heap of size k. Push each number, and when heap size exceeds k, pop the smallest. At the end, heap top is the kth largest.
This gives O(n log k) time and O(k) space, which is practical when k is much smaller than n. Mention Quickselect as an average O(n) alternative but with worse-case concerns unless randomized.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.