LinkedIn T9 Coding Question: Phone-Keyboard Word Match

You are asked to implement T9-style phone-keypad word matching against a fixed dictionary. Given a digit string (2–9) and a list of alphabetic words, return the subset of words whose characters map position-by-position to the digits under the classic T9 mapping (2->abc, 3->def, 4->ghi, 5->jkl, 6->mno, 7->pqrs, 8->tuv, 9->wxyz). Matching is case-insensitive but returned words must preserve their original casing and order.

Stages you may be asked to walk through:

• Naïve per-query matching: iterate words, skip different lengths, check each char->digit mapping. This tests string handling and simple hashing.
• Precomputation: convert each word to its numeric digit-string and store an index (map from digit-sequence to list of words) to support fast repeated queries.
• Production concerns: describe API shape, cache vs. recompute trade-offs, memory vs. latency, and safe updates when the dictionary changes.

Skills you should demonstrate

• String processing and case-insensitive comparisons
• Use of hash maps or tries for indexing and grouping
• Complexity analysis (time/space) and design trade-offs for throughput and latency
• Practical considerations: caching, invalidation, concurrency and monitoring

Common reference function signatures you can use in discussion:

def t9_match(words: list[str], digits: str) -> list[str]:
    """Return words from `words` that match `digits` under T9 mapping."""


def build_numeric_index(words: list[str]) -> object:
    """Return an index or mapping to support fast T9 queries on the provided words."""


def query_t9(index: object, digits: str) -> list[str]:
    """Return matching words using a precomputed index."""


def group_by_t9_sequence(words: list[str]) -> list[list[str]]:
    """Group words that map to the same T9 digit-sequence.

    Returns groups ordered by first occurrence; each group preserves input order.
    """