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.