Kth Largest Without Sorting | Dataford Interview Questions

Tencent Video analytics may need a ranking threshold from an unsorted batch of engagement scores without fully ordering every score. Given an unsorted integer array and an integer k, return the kth largest element, counting duplicate values as separate elements.

You must not sort the entire array. Modify nums in place if needed, and use an algorithm that achieves average O(n) time.

Formal Specification

Implement find_kth_largest(nums, k):

Input: nums, a mutable list of integers, and k, a 1-based integer rank.
Output: The integer value at rank k when the array is ordered from largest to smallest.
The input array may be rearranged during execution.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= len(nums)
-10^9 <= nums[i] <= 10^9
Duplicate values count as separate elements
The full array must not be sorted

Function Signature

def find_kth_largest(nums, k):

Your question is Kth Largest Without Sorting. 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