Return the Most Frequent Values in an Array
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a non-empty integer array, return the `k` values that appear most frequently. Ties are broken by smaller value first.
Implement:
```python
def top_k_frequent(nums: list[int], k: int) -> list[int]:
pass
```
Overview: Practice a Google coding interview problem focused on return the most frequent values in an array. The prompt emphasizes edge cases, clean implementation, and verifiable test behavior without revealing the solution.
Return k values with highest frequency, breaking ties by smaller value.
Examples
Input: {"nums":[1,1,1,2,2,3],"k":2}
Expected Output: [1,2]
Explanation: Common sample.
Input: {"nums":[1],"k":1}
Expected Output: [1]
Explanation: Single.
Community answers
Answer by sourabh.19.cse
Bucket Sort in Java
package prac_hub.top_k_frequent;
import java.util.*;
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map freqMap = new HashMap<>();
int maxFreq = 0;
// 1. Build frequency map AND track maximum frequency seen
for (int num : nums) {
int freq = freqMap.getOrDefault(num, 0) + 1;
freqMap.put(num, freq);
maxFreq = Math.max(maxFreq, freq); // Track max frequency
}
// 2. Allocate buckets based on maxFreq instead of nums.length
TreeSet[] buckets = new TreeSet[maxFreq + 1];
for (Map.Entry entry : freqMap.entrySet()) {
int num = entry.getKey();
int freq = entry.getValue();
if (buckets[freq] == null) {
buckets[freq] = new TreeSet<>();
}
buckets[freq].add(num);
}
// 3. Iterate from maxFreq down to 0
int[] result = new int[k];
int idx = 0;
for (int i = maxFreq; i >= 0 && idx < k; i--) {
if (buckets[i] != null) {
for (int num : buckets[i]) {
result[idx++] = num;
if (idx == k) return result;
}
}
}
return result;
}
}