Interview Question for Software Engineer In Linguistics at Nuance:

Assume we have a hash containing all valid words. Trim all 0s and 1s off the ends of the phone number; they don't have letters on them so we can't use them. Then, from left to right, make a tree like this: if the first two numbers are 56, for example, the tree would have JKL (for 5) in its first row, and each of those would branch into MNO. And so on. The worst case is a ternary tree with 7 levels, meaning 2187 possible words which then have to be looked up in the hash to see if they exist or not. Better yet: keep the valid words in a prefix tree. Then you can prune the tree of possible words as you go: for example, when you add the second row, you could omit JM, KM, JN, LM and LN because no words (that I know of) start with those. This will reduce the number of final possibilities much more.