Find the kth largest element
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
Given an unsorted array of n integers and an integer k (1 ≤ k ≤ n), return the k-th largest element without fully sorting the array. Design two methods:
(
1) an expected linear-time selection algorithm and
(
2) a heap-based approach. For each, describe the algorithm, analyze time and space complexity, and discuss how you would adapt it to find the k-th largest element in a data stream.
Quick Answer: This question evaluates a candidate's mastery of finding the k-th largest element using selection algorithms and heap data structures, along with algorithmic time and space complexity analysis and techniques for adapting solutions to streaming inputs.