Katkat
Back

Find Top K Largest Elements

MicrosoftMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to efficiently find the K largest elements in an unsorted array while managing time complexity constraints through heap-based or selection-based algorithms.

Problem Statement

Given an integer array nums and an integer k, write a function to return the k largest elements in the array. You should return the elements in descending order.

Function Signature

def find_k_largest(nums: List[int], k: int) -> List[int]:

Constraints

  • 1 <= k <= len(nums) <= 10^6
  • -10^9 <= nums[i] <= 10^9
  • The array may contain duplicates.

Examples

Example 1:

  • Input: nums = [3, 2, 1, 5, 6, 4], k = 2
  • Output: [6, 5]
  • Explanation: The two largest elements are 6 and 5.

Example 2:

  • Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
  • Output: [6, 5, 5, 4]
  • Explanation: Duplicate values are included in the result as they appear in the count.

Considerations

  • Aim for an approach more efficient than sorting the entire array, which takes O(n log n) time.
  • Think about how a min-heap or a quickselect-based approach can be applied here.

Hints

Hint 1

Consider using a min-heap of size k to keep track of the largest elements encountered so far while iterating through the array.

Hint 2

If using a heap, after processing all elements, the heap will contain exactly the k largest values; you can then sort these and reverse them for the final output.

Hint 3

For an average O(n) time complexity approach, consider the Quickselect algorithm, which uses partitioning similar to Quicksort to isolate the kth largest element.

Follow-up questions

  • What is the time and space complexity of your chosen solution, and how does it change if k is very small compared to n?
  • How would your approach change if the input array is provided as a stream of data that is too large to fit into memory?
  • If the array contained billions of items and you were restricted by memory, how would you handle the requirement?