Algorithms and Data Structures · Junior · Question 61 of 75
How do you count how many times each word appears in a list in O(n)?
- 1Use nested loops comparing every word with every other
- ✓Correct answer: Use a
Mapfrom word to count and increment it in one pass - 3Sort the words and call
indexOffor each
Explanation
One pass with counts.set(w, (counts.get(w) ?? 0) + 1) is O(n) on average. Frequency counting with a hash map is one of the most common building blocks in interview problems.