Count Words in Lexicographic Order

Question

This question asks the candidate to write a program that counts the number of words in a given text and returns them in lexicographic order.

Codemia · Accepted Answer

To solve the problem of counting words in lexicographic order, we will first split the input text into words using whitespace as the delimiter. Then, we will sort the list of words and count the occurrences of each unique word. Finally, we will return the sorted list along with their counts.

Here is a step-by-step breakdown of the algorithm:
1. Read the input text.
2. Use a regular expression to extract words, ignoring punctuation.
3. Use a dictionary to count occurrences of each word.
4. Sort the dictionary keys (words) lexicographically.
5. Return the sorted list along with their counts.

The time complexity of this algorithm is O(n log n) due to the sorting step, where n is the number of unique words. The space complexity is O(n) as we need to store the words and their counts in a dictionary.

Here is a Python implementation of the algorithm:
```python
import re
from collections import Counter

def count_words(text):
    # Extract words using regex
    words = re.findall(r'\b\w+\b', text.lower())
    # Count occurrences of each word
    word_count = Counter(words)
    # Sort words lexicographically
    sorted_words = sorted(word_count.keys())
    # Prepare the result
    result = {word: word_count[word] for word in sorted_words}
    return result

# Example usage
text = 'Hello world! Hello everyone.'
print(count_words(text))
```
This code will output the count of each word in lexicographic order.

When implementing this solution, consider edge cases such as:
- Input with punctuation (handled by regex).
- Empty strings should return an empty result.
- Different cases of the same word should be treated as identical (handled by converting to lowercase).

Count Words in Lexicographic Order

Upstart

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Upstart Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string