Katkat
Back

Find the kth largest element

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.