Katkat
Back

Count Words in Lexicographic Order

UpstartSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to efficiently process a collection of strings, count their occurrences using a hash map, and output them in a sorted format.

Problem Statement

Given a list of strings (words) containing only lowercase English letters, write a function that returns a list of unique words along with their frequency counts, ordered lexicographically by the word.

Function Signature

def get_word_frequencies(words: list[str]) -> list[tuple[str, int]]:

Constraints

  • The input list words contains between 0 and 1,000,000 strings.
  • Each string has a length between 1 and 50 characters.
  • Total memory available for the operation is 512 MB.

Examples

Example 1: Input: ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'] Output: [('apple', 3), ('banana', 2), ('cherry', 1)] Explanation: 'apple' appears 3 times, 'banana' 2 times, and 'cherry' once. The result is sorted alphabetically.

Example 2: Input: [] Output: []

Edge Cases

  • Empty input list.
  • A list containing only one unique word repeated many times.
  • A list where all words are unique.
  • Very long strings that share common prefixes.

Hints

Hint 1

Use a hash map (dictionary) to store the word as the key and its frequency as the value to achieve O(N) average time complexity for counting.

Hint 2

After counting, extract the keys from the hash map into a list and sort them alphabetically.

Hint 3

Consider that sorting a list of K unique words takes O(K log K) time, where K is the number of unique words.

Follow-up questions

  • How would your approach change if the input was a massive stream of words that could not fit into memory at once?
  • If you needed to return the top K most frequent words instead of lexicographical order, how would the algorithm change?
  • How would you optimize the solution if the input contained billions of words and you had access to a distributed computing cluster?