T9 Dictionary Implementation

MediumPython00:00

Practice interviewer

In session

5 left

00:00

Your question is T9 Dictionary Implementation. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

Chime's mobile app can offer word suggestions while a user enters digits on a T9-style keypad. Given a dictionary of lowercase words, return all words whose T9 encoding starts with a supplied digit prefix.

Implement t9_suggestions(words, digits, limit). The result must be sorted lexicographically and contain at most limit words. Each input word is unique, and the digit mapping is 2=abc, 3=def, 4=ghi, 5=jkl, 6=mno, 7=pqrs, 8=tuv, and 9=wxyz.

Follow-ups

How would you support adding or removing words without rebuilding the entire dictionary?
How would you rank suggestions by usage frequency while preserving lexicographic order for ties?

Constraints

1 <= len(words) <= 10^5
1 <= len(word) <= 30
1 <= len(digits) <= 30
Each word contains only lowercase English letters.
digits contains only characters from 2 through 9.
1 <= limit <= 10^4

Function Signature

def t9_suggestions(words, digits, limit):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output