Prompt and context
Given an array words and integer k, return the k most frequent words. Break ties by ascending lexicographic order.
The interview focuses on maintaining a candidate set of size k and deciding whether the heap root represents the worst or best candidate. Java is used only to demonstrate a comparator; the algorithm is language-independent.
What the interviewer is testing
Counting
Use a hash map to count each word and distinguish array length n from unique-word count m.
Ordering rules
Higher frequency wins; equal frequency uses smaller lexicographic order. The min-heap root should be the worse candidate so excess entries can be removed.
Complexity
Full sorting is O(m log m). A size-k heap is O(n + m log k), useful when k is much smaller than the number of unique words.
Correctness
Explain why heap order for eviction differs from final output order: the heap removes the worst candidate, while the answer must list the best candidates first.
Clarifying questions to ask
- Are words lowercase English and case-sensitive?
- Is k guaranteed to be between 1 and the number of unique words?
- Is lexicographic order ASCII, Unicode, or a business locale?
- Must the input be processed as a stream?
- Must output be stable, or is any order acceptable?
- Can frequencies exceed a 32-bit integer?
30-second answer framework
“I would count frequencies with a hash map. For each unique word I maintain a size-k min-heap whose root is the worse candidate: lower frequency, or larger lexicographic order on a tie. After inserting, I pop when the heap exceeds k. Finally I emit heap entries in descending frequency and ascending lexicographic order. Counting costs O(n), heap maintenance O(m log k), and space is O(m).”
Step-by-step deep dive
Step 1: Count frequencies
Map each word to its count. A streaming log could use external aggregation or an approximate counter, but this problem assumes the unique-word map fits in memory.
Step 2: Define the worst candidate
Candidate A is worse than B when A has lower frequency; on a tie, A has larger lexicographic order. The comparator puts that candidate at the heap root.
Step 3: Maintain size k
Insert each entry from the frequency map and pop when the heap exceeds k. The heap therefore retains the k entries most likely to belong in the final answer.
Step 4: Produce output
Heap pops run from worst to better, so they cannot be returned directly. Reverse the collected entries or sort them with frequency descending and lexicographic ascending.
Step 5: Prove correctness
Whenever size exceeds k, remove the worst member of the current set. That member cannot outrank any of the k retained members. By induction, the final heap contains the global Top K.
Step 6: Handle boundaries
Test k=1, equal frequencies, one unique word, many duplicates, and k=m. The comparator must not reverse ties accidentally.
Model high-quality answer
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String word : words) {
count.merge(word, 1, Integer::sum);
}
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
int byFrequency = Integer.compare(count.get(a), count.get(b));
if (byFrequency != 0) return byFrequency;
return b.compareTo(a); // larger lexicographic value is worse
});
for (String word : count.keySet()) {
heap.offer(word);
if (heap.size() > k) heap.poll();
}
List<String> answer = new ArrayList<>();
while (!heap.isEmpty()) answer.add(heap.poll());
Collections.reverse(answer);
return answer;
}
}Counting costs O(n). With m unique words, heap operations cost O(log k), for O(n + m log k) total time and O(m) space.
Common mistakes
- Putting the best candidate at the heap root → the correct answer is evicted → put the worst candidate at the root.
- Reversing the tie comparator → output order is wrong → retain smaller lexicographic words first on equal frequency.
- Returning heap pops directly → output runs from worst to best → reverse or perform a final sort.
- Claiming O(n log k) after full sorting → complexity is false → full sorting costs O(m log m).
- Testing only different frequencies → tie behavior is untested → include all-equal frequencies and many ties.
- Ignoring k=m → unnecessary eviction or bounds errors → allow the heap to contain all unique words.
- Using locale-dependent ordering accidentally → results vary across environments → state the required order explicitly.
- Naming a hash map without space analysis → scale is unclear → state n, m, and k complexity.
Follow-up questions and responses
Follow-up 1: Would you still use a heap when k is near m?
Full sorting may have better constants and simpler code. A heap remains valid, but O(m log k) approaches O(m log m).
Follow-up 2: What if the input is an unbounded stream?
Exact counts still require state. Use windows, external aggregation, or approximation; exact Top K needs enough retained frequency state.
Follow-up 3: What if unique words exceed memory?
Partition-hash to disk, count each partition, and merge candidates, or use external sorting. Do not load the full array into memory.
Follow-up 4: How would you support case-insensitive words?
Normalize with an explicit locale before counting. Define whether output preserves original spelling and avoid counting equivalent forms twice.
Follow-up 5: How would you test the comparator?
Assert equal frequencies with opposite lexicographic order, k=1, k=m, and duplicate-heavy inputs; compare random cases with a full-sort reference.
Source 1: LeetCode 692
The problem defines descending frequency, ascending lexicographic ties, and an O(n log k) follow-up, establishing the output and complexity target.
Source 2: NeetCode Top K
NeetCode demonstrates frequency-map and Top K approaches and highlights comparator and heap-versus-sort tradeoffs.
Source 3: Oracle PriorityQueue
Oracle documents PriorityQueue ordering by natural order or Comparator, supporting the custom min-heap comparator and poll semantics.