Find Top K Frequent Elements
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
LeetCode 347. Top K Frequent Elements – given an integer array nums, return the k most frequent elements. Initial requirement: return the top 3 elements; follow-up: generalize to arbitrary k.
https://leetcode.com/problems/top-k-frequent-elements/description/
Quick Answer: This question evaluates a candidate's proficiency with frequency counting, selection techniques, use of appropriate data structures, and algorithmic time and space complexity analysis.
Given an integer array nums and an integer k, return a list of the k elements that appear most frequently in nums. Order the result by descending frequency; for elements with equal frequency, order them by ascending numeric value. Assume 1 <= k <= the number of distinct elements in nums.
Constraints
- 1 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= number of distinct elements in nums
- Output length is exactly k
- Order: descending frequency; ties by ascending value
Hints
- Count occurrences with a hash map (e.g., collections.Counter).
- Sort distinct elements by (-frequency, value) and take the first k.
- Alternatively, use a heap of size k keyed by (frequency, -value) or bucket sort for linear-time selection.