Count Words in Lexicographic Order
Company: Upstart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
# Count Words in Lexicographic Order
Implement `word_counts(words)` for a list of lowercase words. Return a list of `(word, count)` pairs sorted in ascending lexicographic order by word.
## Constraints
- `0 <= len(words) <= 200000`
- Every word contains one to fifty lowercase English letters.
- The input list may contain many duplicates and must not be mutated.
## Example
`["pear", "apple", "pear", "banana", "apple"]` returns `[("apple", 2), ("banana", 1), ("pear", 2)]`.
## Clarifications
Comparison is case-sensitive, but inputs are already lowercase. State the time and space complexity in terms of the number of words and distinct words.
## Hints
Separate frequency aggregation from ordering the distinct keys.
## Extensions
- Stream input too large to fit in memory.
- Sort under locale-aware collation.
- Return the most frequent words with lexicographic tie-breaking.
Quick Answer: Count repeated lowercase words and return the distinct words with their frequencies in lexicographic order. Preserve the input while analyzing large collections, many duplicates, time and space costs, streaming limits, locale-aware ordering, and frequency-based extensions.
Implement `word_counts(words)` for a list of lowercase words. Return a list of `(word, count)` pairs sorted in ascending lexicographic order by word. The input list may contain many duplicates and must not be mutated.
Comparison is case-sensitive, although every input word is already lowercase.
Example: `["pear", "apple", "pear", "banana", "apple"]` returns `[("apple", 2), ("banana", 1), ("pear", 2)]`.
Constraints
- 0 <= len(words) <= 200000.
- Every word contains 1 to 50 lowercase English letters.
- The input list may contain many duplicates and must not be mutated.
- Return exactly one pair per distinct word in ascending lexicographic order by word.
Examples
Input: (['pear', 'apple', 'pear', 'banana', 'apple'],)
Expected Output: [('apple', 2), ('banana', 1), ('pear', 2)]
Explanation: This is the source example: the two repeated words are counted and the three distinct keys are returned in ascending lexicographic order.
Input: ([],)
Expected Output: []
Explanation: An empty input has no distinct words, so the ordered result is empty.
Hints
- Separate frequency aggregation from ordering the distinct keys.
- Build the result only after sorting the distinct words.