TV Remote Channel Search
Filed under Microsoft
Free read 2 of 3Insert all channel names into a Trie structure for efficient prefix searching.
The question
Given a mapping of digits to letters (like a phone keypad) and a list of channel names, implement a search function that takes a digit string and returns all channel names starting with any possible letter combination.
Constraints
- Input string length 1-10
- Channel list size up to 10,000
- Case-insensitive matching
Examples
- Input
- digits='2', channels=['ABC', 'DEF']
- Output
- ['ABC']
- Why
- Digit 2 maps to A, B, C. 'ABC' starts with A.
Approach
Insert all channel names into a Trie structure for efficient prefix searching.
Use DFS to traverse the Trie. At each digit, branch into the possible letters defined by the keypad mapping.
Prune the search if the current path in the Trie does not match any letters for the next digit.
Tips
- What they are testing: Ensure the search handles prefixes correctly and is efficient for large channel lists.
- Common mistake: Generating all permutations of the digit string first, which is exponential, instead of using a Trie.
Related Microsoft questions
Collected from public candidate posts and coding forums. Updated Nov 2026.