Problem
Language models work with tokens, not raw text. A simple tokenizer lowercases the text and treats every run of letters a-z and digits 0-9 as a word; everything else (spaces, punctuation, other characters) separates words.
Build the vocabulary: the distinct words, sorted by how often they appear (most frequent first), with ties broken alphabetically. A word's position in this list is its token ID.
Implement build_vocabulary(text).
Input
text: Any text.
Output
Return the vocabulary as a list of words. Return an empty list if the text has no words.
Constraints
0 ≤ length of text ≤ 100,000
Examples
Input:
text = "The cat sat on the mat. The end!"
Expected output:
expected = ["the", "cat", "end", "mat", "on", "sat"]Input:
std::string text = "The cat sat on the mat. The end!";
Expected output:
std::vector<std::string> expected = {"the", "cat", "end", "mat", "on", "sat"};Input:
string text = "The cat sat on the mat. The end!";
Expected output:
string[] expected = new string[] {"the", "cat", "end", "mat", "on", "sat"};Explanation
Lowercased, the words are the, cat, sat, on, the, mat, the, end. "the" appears 3 times; the rest appear once and are sorted alphabetically: ["the", "cat", "end", "mat", "on", "sat"].
Input:
text = "AI, ai and A.I. (2024)"
Expected output:
expected = ["ai", "2024", "a", "and", "i"]Input:
std::string text = "AI, ai and A.I. (2024)";
Expected output:
std::vector<std::string> expected = {"ai", "2024", "a", "and", "i"};Input:
string text = "AI, ai and A.I. (2024)";
Expected output:
string[] expected = new string[] {"ai", "2024", "a", "and", "i"};Explanation
Words: ai, ai, and, a, i, 2024. "ai" appears twice; the others once, sorted alphabetically with digits before letters: ["ai", "2024", "a", "and", "i"].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
First extract only runs of letters and digits, lowercased, and ignore every other character.
Hint 2
Count how often each word appears, then sort by frequency descending and alphabetically for ties.
Hint 3
If the text contains no valid words, return an empty list instead of a singleton or null result.
Expected complexity
O(n log k) time, O(k) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.