Top K Frequent Words
Asked at Rippling
Problem
Given an array of words and an integer k, return the k most frequent words. If multiple words have the same frequency, return them in lexicographical order. The solution must run in O(n log k) time.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | MEDIUM | View all Rippling questions → |
How to Think About It
Count word frequencies using a hash map
Use a min-heap of size k to keep track of top k frequent words
Compare words by frequency first, then lexicographically if tied
Extract elements from heap in reverse order for final result
Consider bucket sort as an alternative O(n) approach
Optimal Approach
Count word frequencies using a hash map. Use a min-heap of size k that compares words by frequency first, then lexicographically in reverse for proper ordering. Iterate through all words, adding each to the heap and removing the smallest when size exceeds k. Extract elements from the heap and reverse the result for correct order.
What Trips People Up in Real Interviews
Clarify tie-breaking rules early—frequency then lexicographical order
Mention the time complexity trade-offs between heap and bucket sort
Edge case: all words appear exactly once, return lexicographically smallest k
Explain why a min-heap is used instead of max-heap for efficiency
Discuss how you would modify the solution for streaming data
Solution Code
from collections import Counter
import heapq
def topKFrequent(words, k):
count = Counter(words)
heap = []
for word, freq in count.items():
heapq.heappush(heap, (-freq, word))
result = []
for _ in range(k):
result.append(heapq.heappop(heap)[1])
return resultFrequently Asked Questions
What is the Top K Frequent Words problem?
Given an array of words and an integer k, return the k most frequent words. If multiple words have the same frequency, return them in lexicographical order. The solution must run in O(n log k) time.
How do you solve Top K Frequent Words?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Top K Frequent Words?
Top K Frequent Words is asked at Rippling. It is a medium difficulty problem.
What are common mistakes on Top K Frequent Words?
- Clarify tie-breaking rules early—frequency then lexicographical order
- Mention the time complexity trade-offs between heap and bucket sort
- Edge case: all words appear exactly once, return lexicographically smallest k
- Explain why a min-heap is used instead of max-heap for efficiency
- Discuss how you would modify the solution for streaming data