K Largest Elements | Dataford Interview Questions

Otter.ai may need to identify the highest-scoring transcript segments, speakers, or search results for a ranking feature. Given a list of integers, return the k largest elements while preserving duplicate values. The result must be sorted in descending order.

Use an algorithm that avoids fully sorting the input when k is much smaller than n.

Formal Specification

Implement k_largest(nums, k).

Input: nums, a list of integers, and k, an integer.
Output: a list containing exactly the k largest values from nums, sorted from largest to smallest.
Duplicate values count as separate elements.
Do not modify nums.

Constraints

1 <= k <= len(nums)
1 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
Duplicate values must be preserved
The input list must not be modified

Function Signature

def k_largest(nums, k):

Your question is K Largest Elements. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem