192. Word Frequency
Model: qwen3.5:9b
Topics:
FAANG asked: 1
Acceptance rate: 25.6%
Problem Breakdown
The task requires reading a text file (words.txt), counting the occurrences of each word, and printing them sorted by frequency in descending order.
Inputs: A single string or file path containing words separated by whitespace (spaces/newlines). The content contains only lowercase letters and spaces.
Outputs: Lines formatted as word count, sorted strictly by count from highest to lowest.
Constraints & Edge Cases:
- Whitespace Handling: Words are separated by one or more whitespaces; the solution must ignore multiple consecutive spaces (not just single space).
- Empty Input: If the file is empty, output should be empty without crashing.
- Ties: The problem guarantees unique frequencies for each word, so secondary sort keys aren’t needed.
- Punctuation: Assumed not to exist based on constraints (only lowercase chars and spaces).
Intuition
A naive approach would read the file character-by-character or line-by-line into a list of strings, then iterate through that list to build counts using a dictionary/hash map. While this works in Python, it’s inefficient if we manually manage string parsing for every word.
The key insight is leveraging built-in tokenization (split()) which automatically handles multiple spaces and newlines as delimiters. For counting, collections.Counter provides an optimized hash-map implementation that runs faster than a raw dictionary loop.
If this were Bash (as the original problem suggests), we would use pipes: tr ' ' '\n' | sort | uniq -c. In Python, we replicate this logic using standard library tools to avoid external dependencies or manual parsing loops.
Approach
- Read Input: Open and read all content from
words.txt(or stdin). - Tokenize: Use the string method
.split()without arguments; it treats any sequence of whitespace as a single delimiter, handling multiple spaces automatically. - Count: Pass the list of words to
collections.Counter, which builds an O(1) lookup table for frequencies in one pass over the data. - Sort & Output: Extract items from the Counter and sort them by their count value (
key=lambda x: x[1]) in descending order. Iterate through the sorted list, printing each word-count pair formatted as required.
Complexity Analysis
- Time Complexity: , where is the total number of words (for reading and counting) and is the number of unique words (for sorting). Since we must read every character/word at least once to count them, this dominates. Sorting takes logarithmic time relative to unique keys.
- Space Complexity: , where is the number of unique words stored in the Counter hash map and the sorted list.
Solution
import collections
from sys import stdin # Or open('words.txt') depending on environment usage
def word_frequency(filename):
"""
Calculates frequency of each word in a text file
and prints them sorted by descending frequency.
"""
try:
with open(filename, 'r') as f:
content = f.read()
# split() handles multiple spaces/newlines automatically
words = content.split()
if not words:
return
counter = collections.Counter(words)
# Sort by count (value), descending.
# Key is x[1] because Counter items are tuples (word, count).
sorted_words = sorted(counter.items(), key=lambda item: item[1], reverse=True)
for word, freq in sorted_words:
print(f"{word} {freq}")
except FileNotFoundError:
# Graceful handling if file doesn't exist
pass
# Example usage (assuming words.txt exists):
if __name__ == "__main__":
word_frequency('words.txt')
Edge Cases Handled
- Empty File: The
split()returns an empty list; the Counter is empty, resulting in no output lines. - Multiple Spaces/Blank Lines: Python’s
.split()without arguments treats consecutive whitespace as a single separator and ignores trailing whitespace at line ends or file end automatically. - Missing File: Wrapped in try-except to prevent runtime crash if
words.txtis not found (though typically LeetCode environments guarantee input existence).