Word Frequency - Video Solutions

Problem Overview: You receive a text file containing words separated by spaces. The task is to count how many times each word appears and print the result sorted by frequency in descending order. The challenge focuses on efficient text processing using shell utilities or frequency counting techniques.

Approach 1: Using Command-line Utilities (O(n log n) time, O(n) space)

This approach uses standard Unix text-processing tools. First normalize the input so each word appears on its own line using tr or similar utilities. Then sort the words with sort, count duplicates using uniq -c, and finally sort again by frequency in descending order. The key insight is that uniq only counts adjacent duplicates, so sorting groups identical words together. This pipeline-based solution is concise and idiomatic for shell scripting tasks.

Approach 2: Using grep, sort, and uniq (O(n log n) time, O(n) space)

Another shell-based solution relies on grep -o to extract individual words from the file, printing each match on a new line. Once extracted, the pipeline continues with sort to group identical words and uniq -c to compute counts. A final descending sort arranges results by frequency. This approach works well when the input format may contain punctuation or irregular spacing, because grep can precisely control the word pattern being extracted.

Approach 3: Recursive Approach with Memoization (O(n) time, O(k) space)

If implemented in languages like Python or Java, the problem becomes a classic frequency counting task. Iterate through the list of words and store counts in a hash map. A recursive helper can process one word at a time while memoizing previously seen counts in the map. Each insertion or lookup in the hash table runs in average O(1) time. After counting, convert the map entries into a list and sort them by frequency before printing.

Approach 4: Iterative Dynamic Programming (O(n) time counting + O(k log k) sorting, O(k) space)

An iterative approach processes the text sequentially and updates a frequency table for each encountered word. The “DP” aspect is simply building results from previous counts: each step updates count[word] = count[word] + 1. The main data structure is a hash map keyed by the word string. Once all words are processed, sort the unique entries by frequency. This approach is common in general string processing problems and works well outside shell environments.

Recommended for interviews: Interviewers usually expect the hash map frequency-count solution because it demonstrates understanding of constant-time lookups and sorting results by value. Showing the shell pipeline solution proves strong command-line skills, but the hashmap approach highlights core algorithmic thinking.