Jobs

Interviews

Discussions

Word Frequency

Medium

Asked by:

33 views

Topics:

Strings

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.

Example:

Assume that words.txt has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

Note:

Don't worry about handling ties, it is guaranteed that each word's frequency count is unique.
Could you write it in one-line using Unix pipes?

Try coding it in LeetCode

Word Frequency

Medium

Asked by:

33 views

Topics:

Strings

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

words.txt contains only lowercase characters and space ' ' characters.
Each word must consist of lowercase characters only.
Words are separated by one or more whitespace characters.

Example:

Assume that words.txt has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

Note:

Don't worry about handling ties, it is guaranteed that each word's frequency count is unique.
Could you write it in one-line using Unix pipes?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input case-sensitive? Should I treat 'The' and 'the' as the same word?
Should punctuation be removed or considered part of the word? For example, should 'hello!' be counted differently from 'hello'?
What data type will the input be? Is it a string, a list of strings, or something else?
If the input is empty or null, what should the output be? An empty dictionary, null, or an error?
What is the expected output format? Should the word frequencies be returned as a dictionary (word: count), a list of tuples (word, count), or something else?

Brute Force Solution

Approach

The brute force approach for word frequency involves counting how many times each word appears in a given text. We meticulously go through each word and compare it against every other word in the text. This ensures we don't miss any occurrences.

Here's how the algorithm would work step-by-step:

Start by picking the very first word from the text.
Compare this word to every other word in the text, one by one.
Every time you find a match, increase a counter for that word.
Once you have compared the first word to all the other words, move on to the second word.
Repeat the process of comparing the second word to every other word (including the first one).
Continue this process for every word in the text.
After going through all the words, you will have a count for how many times each word appears.

Code Implementation

def word_frequency_brute_force(text):
    words = text.split()
    word_counts = {}

    for first_word_index in range(len(words)):
        current_word = words[first_word_index]
        word_count = 0

        # Iterate over all words in the list
        # to compare with the current word
        for second_word_index in range(len(words)):

            comparison_word = words[second_word_index]

            if current_word == comparison_word:
                word_count += 1

        # Store the count for the current word.
        word_counts[current_word] = word_count

    return word_counts

Big(O) Analysis

Time Complexity

O(n²) – The described algorithm iterates through each of the 'n' words in the text. For each word, it compares it to every other word in the text to count its occurrences. This involves a nested loop structure where the outer loop iterates 'n' times, and the inner loop, for each outer loop iteration, also iterates 'n' times. Therefore, the total number of comparisons grows proportionally to n * n, resulting in O(n²) time complexity. Essentially, every word is compared against every other word.

Space Complexity

O(1) – The provided algorithm does not use any auxiliary data structures. It iterates through the input text, comparing words directly without needing to store intermediate results or create temporary collections. The space required is limited to a few variables such as loop counters, which consume a constant amount of space regardless of the input size N, where N is the number of words in the text. Thus, the space complexity is O(1).

Optimal Solution

Approach

The task is to count how often each word appears in a given text. We can efficiently solve this by using a structure that quickly tells us how many times we've seen each word.

Here's how the algorithm would work step-by-step:

First, prepare the text by making all the words lowercase and removing any punctuation so that variations of the same word are counted together.
Then, go through each word in the prepared text one by one.
For each word, check if you've seen it before. If you have, increase its count by one. If it's the first time you're seeing the word, start its count at one.
Keep doing this until you've processed all the words.
Finally, present each word along with its total count.

Code Implementation

def word_frequency(text):
    text = text.lower()
    
    for punctuation in ".,!?:;":
        text = text.replace(punctuation, "")

    words = text.split()
    word_counts = {}

    # Iterate through each word in the cleaned text
    for word in words:
        # If word is not present, add the word
        if word not in word_counts:

            word_counts[word] = 1
        # If word is present, increment count
        else:
            word_counts[word] += 1

    # Present each word along with its frequency
    for word, count in word_counts.items():
        print(f'{word}: {count}')

    return word_counts

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of words in the input text. The first step involves preprocessing the text, which iterates through the text once performing constant time operations (lowercase conversion, punctuation removal) for each word. The second step iterates through the preprocessed list of n words. Inside the loop, checking if a word exists in a hash map (or dictionary) and updating its count takes constant time on average. Therefore, the dominant operation is iterating through the n words once resulting in O(n) time complexity.

Space Complexity

O(N) – The auxiliary space is dominated by the dictionary (or hash map) used to store the word counts. In the worst-case scenario, where all words in the input text are unique after preprocessing, the dictionary will store N unique words, where N is the number of words in the input text. Therefore, the dictionary requires space proportional to the number of unique words, which can be up to N. Other variables used for iteration and temporary storage have constant space requirements and are insignificant compared to the dictionary.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty dictionary or an appropriate error message as no words exist to count.
String with only whitespace characters	Treat as an empty string and return an empty dictionary or error.
Very large input string exceeding memory capacity	Consider using techniques like streaming or processing the input in chunks to avoid memory overflow.
String with extremely long words exceeding reasonable limits	Implement a word length limit and truncate or ignore excessively long words to prevent resource exhaustion.
Input string contains special characters, punctuation, and numbers	Preprocess the string by removing or normalizing these characters based on the problem's requirements (e.g., lowercase, remove punctuation).
Case sensitivity: 'The' vs 'the'	Convert the input string to lowercase to ensure case-insensitive word counting.
Different word delimiters: spaces, tabs, newlines	Split the string based on any whitespace character, treating them as delimiters.
High frequency of certain words skewing results	Consider using stop word removal (e.g., 'the', 'a', 'is') to focus on more meaningful words.

Null or empty input string

How to Handle:

Return an empty dictionary or an appropriate error message as no words exist to count.

String with only whitespace characters

How to Handle:

Treat as an empty string and return an empty dictionary or error.

Very large input string exceeding memory capacity

How to Handle:

Consider using techniques like streaming or processing the input in chunks to avoid memory overflow.

String with extremely long words exceeding reasonable limits

How to Handle:

Implement a word length limit and truncate or ignore excessively long words to prevent resource exhaustion.

Input string contains special characters, punctuation, and numbers

How to Handle:

Preprocess the string by removing or normalizing these characters based on the problem's requirements (e.g., lowercase, remove punctuation).

Case sensitivity: 'The' vs 'the'

How to Handle:

Convert the input string to lowercase to ensure case-insensitive word counting.

Different word delimiters: spaces, tabs, newlines

How to Handle:

Split the string based on any whitespace character, treating them as delimiters.

High frequency of certain words skewing results

How to Handle:

Consider using stop word removal (e.g., 'the', 'a', 'is') to focus on more meaningful words.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input case-sensitive? Should I treat 'The' and 'the' as the same word?
Should punctuation be removed or considered part of the word? For example, should 'hello!' be counted differently from 'hello'?
What data type will the input be? Is it a string, a list of strings, or something else?
If the input is empty or null, what should the output be? An empty dictionary, null, or an error?
What is the expected output format? Should the word frequencies be returned as a dictionary (word: count), a list of tuples (word, count), or something else?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by picking the very first word from the text.
Compare this word to every other word in the text, one by one.
Every time you find a match, increase a counter for that word.
Once you have compared the first word to all the other words, move on to the second word.
Repeat the process of comparing the second word to every other word (including the first one).
Continue this process for every word in the text.
After going through all the words, you will have a count for how many times each word appears.

Code Implementation

def word_frequency_brute_force(text):
    words = text.split()
    word_counts = {}

    for first_word_index in range(len(words)):
        current_word = words[first_word_index]
        word_count = 0

        # Iterate over all words in the list
        # to compare with the current word
        for second_word_index in range(len(words)):

            comparison_word = words[second_word_index]

            if current_word == comparison_word:
                word_count += 1

        # Store the count for the current word.
        word_counts[current_word] = word_count

    return word_counts

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The task is to count how often each word appears in a given text. We can efficiently solve this by using a structure that quickly tells us how many times we've seen each word.

Here's how the algorithm would work step-by-step:

First, prepare the text by making all the words lowercase and removing any punctuation so that variations of the same word are counted together.
Then, go through each word in the prepared text one by one.
For each word, check if you've seen it before. If you have, increase its count by one. If it's the first time you're seeing the word, start its count at one.
Keep doing this until you've processed all the words.
Finally, present each word along with its total count.

Code Implementation

def word_frequency(text):
    text = text.lower()
    
    for punctuation in ".,!?:;":
        text = text.replace(punctuation, "")

    words = text.split()
    word_counts = {}

    # Iterate through each word in the cleaned text
    for word in words:
        # If word is not present, add the word
        if word not in word_counts:

            word_counts[word] = 1
        # If word is present, increment count
        else:
            word_counts[word] += 1

    # Present each word along with its frequency
    for word, count in word_counts.items():
        print(f'{word}: {count}')

    return word_counts

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty dictionary or an appropriate error message as no words exist to count.
String with only whitespace characters	Treat as an empty string and return an empty dictionary or error.
Very large input string exceeding memory capacity	Consider using techniques like streaming or processing the input in chunks to avoid memory overflow.
String with extremely long words exceeding reasonable limits	Implement a word length limit and truncate or ignore excessively long words to prevent resource exhaustion.
Input string contains special characters, punctuation, and numbers	Preprocess the string by removing or normalizing these characters based on the problem's requirements (e.g., lowercase, remove punctuation).
Case sensitivity: 'The' vs 'the'	Convert the input string to lowercase to ensure case-insensitive word counting.
Different word delimiters: spaces, tabs, newlines	Split the string based on any whitespace character, treating them as delimiters.
High frequency of certain words skewing results	Consider using stop word removal (e.g., 'the', 'a', 'is') to focus on more meaningful words.

Null or empty input string

How to Handle:

Return an empty dictionary or an appropriate error message as no words exist to count.

String with only whitespace characters

How to Handle:

Treat as an empty string and return an empty dictionary or error.

Very large input string exceeding memory capacity

How to Handle:

Consider using techniques like streaming or processing the input in chunks to avoid memory overflow.

String with extremely long words exceeding reasonable limits

How to Handle:

Implement a word length limit and truncate or ignore excessively long words to prevent resource exhaustion.

Input string contains special characters, punctuation, and numbers

How to Handle:

Preprocess the string by removing or normalizing these characters based on the problem's requirements (e.g., lowercase, remove punctuation).

Case sensitivity: 'The' vs 'the'

How to Handle:

Convert the input string to lowercase to ensure case-insensitive word counting.

Different word delimiters: spaces, tabs, newlines

How to Handle:

Split the string based on any whitespace character, treating them as delimiters.

High frequency of certain words skewing results

How to Handle:

Consider using stop word removal (e.g., 'the', 'a', 'is') to focus on more meaningful words.