Phone Keypad Predictive Text Suggestions
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
# Phone Keypad Predictive Text Suggestions
You are building the predictive-text feature for a classic 9-key phone keypad. Each digit from 2 to 9 maps to a group of lowercase letters:
| Digit | Letters |
|-------|---------|
| 2 | a b c |
| 3 | d e f |
| 4 | g h i |
| 5 | j k l |
| 6 | m n o |
| 7 | p q r s |
| 8 | t u v |
| 9 | w x y z |
Digits `0` and `1` map to no letters.
A word's **digit encoding** is obtained by replacing each of its letters with the digit whose group contains that letter. For example, the word `"cat"` encodes to `"228"` and `"tree"` encodes to `"8733"`.
You are given a dictionary of distinct lowercase words and a list of queries. Each query is a non-empty string of digits (`'0'`–`'9'`) representing the keys a user has pressed so far. For each query, return **all dictionary words whose digit encoding starts with the query string** (i.e., the query is a prefix of the word's digit encoding), sorted in ascending lexicographic order. If no word matches, return an empty list for that query.
Implement:
```
suggestions(words: List[str], queries: List[str]) -> List[List[str]]
```
where the i-th element of the result is the sorted list of suggestions for `queries[i]`.
**Examples**
```
words = ["cat", "bat", "act", "car", "care", "dog"]
queries = ["228", "22", "2273", "364", "9"]
"228" -> ["act", "bat", "cat"] (all three encode exactly to "228")
"22" -> ["act", "bat", "car", "care", "cat"] ("22" is a prefix of "228", "227", "2273")
"2273" -> ["care"] ("care" encodes to "2273")
"364" -> ["dog"]
"9" -> []
```
Note that a query containing the digit `0` or `1` can never match any word, since no letter encodes to those digits.
**Constraints**
- `1 <= len(words) <= 10^5`
- `1 <= len(words[i]) <= 20`; words consist of lowercase English letters and are distinct
- `1 <= len(queries) <= 10^4`
- `1 <= len(queries[i]) <= 20`; queries consist of digit characters `'0'`–`'9'`
- The total number of words returned across all queries fits in memory (at most `10^6`)
Aim for a solution that preprocesses the dictionary once so that each query is answered without rescanning every word.