Kth Largest in Unsorted Array | Dataford Interview Questions

OpenX may need to identify a rank threshold among unsorted bid values before processing an ad request. Given an unsorted array of integers and an integer k, return the kth largest element, counting duplicate values as separate elements.

You must design an algorithm that avoids fully sorting the array. The input array may be modified in place.

Formal Specification

Implement kth_largest(nums, k), where nums is a non-empty list of integers and k is a valid 1-based rank. Return the integer whose position would be k in the array sorted in descending order. The function must return a single integer, not an index.

Constraints

1 <= len(nums) <= 10^5
1 <= k <= len(nums)
-10^9 <= nums[i] <= 10^9
Duplicate values are allowed
The input array may be modified in place

Function Signature

def kth_largest(nums, k):

Your question is Kth Largest in Unsorted Array. 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