# CodeFights Solves It: pressingButtons

Time to call 1-800-CODEFIGHTS (that’s 1-800-2633344487)! Given a number, your job is to find all the possible strings that the number could represent on a telephone’s number pad. This week’s Interview Practice Task of the Week was pressingButtons. This programming problem has been asked in technical interviews at Google, Amazon, Uber, *and* Facebook. In other words, this is a classic question!

In classic CodeFights Solves It fashion, I’m going to tell you to go solve the problem yourself first. After all, you have to actually practice solving interview questions in order to become a better coder! Once you’ve solved it, head back here and I’ll talk you through two variations on a solution.

Done? Okay, let’s get dialed in!

## The technical interview question

We are given a picture of a standard number pad to help us:

Given a number as a string, for example “42”, we are supposed to write a function `pressingButtons`

that returns a (sorted) list of all possible strings associated with that number. In the case of “42”, the “4” maps to a “g”, “h”, or “i”, and the “2” maps to an “a”, “b”, or “c”, so:

1 2 3 |
print pressingButtons("42") ["ga","gb","gc","ha","hb","hc","ia","ib","ic"] |

### The politics of programming languages

One of the interesting things about this challenge is that we have written our solutions in Python. In Python, there is a very easy way of approaching this problem using the *itertools* package. When solving a problem in the real world (i.e. not in a technical interview) it is *great* when your problem is solved in a standard package! But in an interview setting, an interviewer asking you to sort a list is probably wanting you to implement a sorting algorithm instead of just using the language’s built-in sorting method.

*Itertools* is a borderline package. On the one hand, it’s built into the language. You need to show that you understand iterators in order to use it. It is also typically not taught in computer science classes, where they want you to make iterators by hand. So the fact that you know about itertools shows your real-word experience. Making your own custom solution when interviewing for a position that needs 3 years of Python experience might leave your interviewer wondering “doesn’t this candidate know about itertools?”

On the other hand, we try to serve a wide audience here at CodeFights. Knowing that the itertools package is built in to Python doesn’t help when you are applying for that senior Java engineer position! I will show the itertools solution, and then show a solution that will work in a broader range of lower level languages.

Even if you are using Python in a technical interview, my advice would be to *ask* your interviewer if you are allowed to use the itertools package. Chances are your interviewer will say “no”, but at least you’ve demonstrated to her that you know the standard way of approaching one of these problems.

## A solution using itertools

Here is the Python code that uses itertools:

1 2 3 4 5 6 7 8 9 |
from itertools import product def pressingButtons(buttons): numPad = ["" ,"" ,"abc","def" ,"ghi","jkl", "mno","pqrs","tuv","wxyz"] charArr = [numPad[int(digit)] for digit in buttons] return [''.join(s) for s in product(*charArr) if s] |

The array `numPad`

stores the possible letters for each character. There are no letters associated with 0 or 1, so the entries are empty strings. We see `numPad[4] = "ghi"`

and `numPad[2] = "abc"`

, for example. Next, we make an array of all the possible numbers we can substitute in `charArr`

. Continuing with the example of `42`

, we would have `charArr=["ghi","abc"]`

.

So far, everything looks the same as it does in the more general solution. We now have to find a way of getting all the possible ways of getting a single letter from each of these strings. This is where the itertools `product`

function does all the heavy lifting.

What `product`

does is take an arbitrary number of iterables (think lists or strings) and returns a generator. Generators are really cool – they allow us to produce values “on demand” so we don’t have to stress the machine too much – but they are a whole other topic on their own. For the moment, we can force `product`

to produce a list by casting it. The product operator is easy to understand from an example:

1 2 |
list(product([1,2,3],"ab")) = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')] |

i.e. `list(product( it1, it2, it3, ..., itN ) )`

returns a list where each element is a tuple where the first element is from `it1`

, the second elements is from `it2`

, the third is from `it3`

, and so on. Every possible combination is represented once.

Notice that if we have `charArr = ["ghi","abc"]`

that `list(product(charArr))`

doesn’t give us quite what we want:

1 2 |
list(product(charArr)) = [('ghi',), ('abc',)] |

This is because we have passed only one argument, `charArr`

. It is iterable since there are two elements (“ghi” and “abc”), so it takes the first element and then the second. Python’s notation for a tuple with a single element looks strange: `("ghi",)`

is a tuple with only one element `"ghi"`

. The comma shows that this is a tuple and not just standard parenthesis. Notice that if we pass the two strings `"ghi"`

and `"abc"`

, we get a different result:

1 2 3 4 |
list(product("ghi","abc")) = [('g', 'a'), ('g', 'b'), ('g', 'c'), ('h', 'a'), ('h', 'b'), ('h', 'c'), ('i', 'a'), ('i', 'b'), ('i', 'c')] |

The Python star operator (`*`

) allows us to “unpack” a list, and pass the entries directly to a function. So we can write:

1 2 3 4 5 |
# charArr = ["ghi","abc"] as before list(product(*charArr)) = [('g', 'a'), ('g', 'b'), ('g', 'c'), ('h', 'a'), ('h', 'b'), ('h', 'c'), ('i', 'a'), ('i', 'b'), ('i', 'c')] |

Now we just have to join each of these tuples such as `('g','a')`

into a string such as `"ga"`

. We can accomplish this with the `join`

functions:

1 2 3 4 |
[''.join(s) for s in list(product(*charArr))] = ['ga', 'gb', 'gc', 'ha', 'hb', 'hc', 'ia', 'ib', 'ic'] |

We can get rid of the list statement now since we are feeding the output of `product`

to a for loop. This is just the thing that generators were built for!

We have covered *almost* all the code in the return statement in our original function. The only missing piece is an `if s`

at the end! The `if s`

at the end deals with the corner case of what happens when you pass in an empty string for `buttons`

(i.e. “” instead of “42”). The comments section on this question are all addressing what the answer should be – you should have a look and see what you think the question statement instructions say about what should happen with the empty string – but our tests only pass if `pressingButtons("")`

returns an empty list `[]`

## Recursive approaches to this question

Let’s try to do this without resorting to itertools. We want a function `allStrings`

that takes a list of strings `charArr`

, and returns a list of all the possible strings with the first character from `charArr[0]`

, the second character from `charArrr[1]`

, etc. Our approach will be:

- If
`charArr`

only has one element, then return a list of the letters of`charArr[0]`

. For example, if`charArr=["abc"]`

then return`['a','b','c']`

. - If
`charArr`

has more than one element, find the list of all the strings of every element except for the first by using the recursive call`allStrings(charArr[1:])`

. Then append every string in this list with every letter from`charArr[0]`

.

In code, we have:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def allStrings(charArr): # base cases: charArr only has 0 or one element if len(charArr) == 0: return [] if len(charArr) == 1: return list(charArr[0]) # find the list of strings remaining = allStrings(charArr[1:]) output = [] for start_char in charArr[0]: # place start_char at the beginning of each string in # remaining output.extend([start_char + s for s in remaining]) return output |

Putting our solution together, we have:

1 2 3 4 5 6 7 8 |
# uses the earlier function allStrings def pressingButtons(buttons): numPad = ["" ,"" ,"abc","def" ,"ghi","jkl", "mno","pqrs","tuv","wxyz"] charArr = [numPad[int(digit)] for digit in buttons] return allStrings(charArr) |

## Tell us…

Have you ever been in an interview where you could have used a built-in method to solve a challenge, but were told not to? Or the opposite – the interviewer told you to go ahead and use it? Let us know over on the CodeFights forum!