LinkedIn High-Frequency Algorithm: Phone Keypad Word Mapping

oavoservice Original Review: The core is not brute-force enumeration of letters, but reverse mapping known words into numeric patterns.

Problem (Restated)

Given a phone keypad mapping (2->abc, 3->def, ..., 9->wxyz), and a list of KNOWN_WORDS.

For an input phoneNumber, output all words from KNOWN_WORDS that can be mapped to this number.

Example:

• KNOWN_WORDS = ['careers', 'linkedin', 'hiring', 'interview', 'linkedgo']
• phoneNumber = 2273377 -> Output ['careers']
• phoneNumber = 54653346 -> Output ['linkedin', 'linkedgo']

Efficient Approach: Word Reverse Encoding

Instead of generating all combinations (exponential), a more practical approach:

1. Build a Letter -> Digit mapping table.
2. Encode each known word into a digit string code(word).
3. For input number, just check if code(word) == phoneNumber.

Complexity: O(total_chars_in_dict + candidates).

Python Implementation

from typing import List, Dict


def build_char_to_digit() -> Dict[str, str]:
    mapping = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }
    char_to_digit = {}
    for d, letters in mapping.items():
        for ch in letters:
            char_to_digit[ch] = d
    return char_to_digit


def word_to_digits(word: str, char_to_digit: Dict[str, str]) -> str | None:
    out = []
    for ch in word.lower():
        if ch not in char_to_digit:
            return None
        out.append(char_to_digit[ch])
    return "".join(out)


def phone_keypad_word_mapping(phone: str, known_words: List[str]) -> List[str]:
    char_to_digit = build_char_to_digit()
    res = []

    for w in known_words:
        code = word_to_digits(w, char_to_digit)
        if code == phone:
            res.append(w)

    return res

Advanced Optimizations (Interview Bonus)

• Multi-query: Precompute a digits -> [words] hash map to make queries O(1).
• Prefix Matching / Segmentation: If the problem allows splitting the phone number into multiple words, use Trie + DFS or DP.

This type of question is common at LinkedIn because it combines "Product Scenario (Search/IME)" with "Algorithm Optimization". oavoservice training focuses on: provide a runnable baseline first, then explain why reverse mapping is better.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.