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 CodeSignal 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:
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 CodeSignal. 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:
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]
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 = "ghi" and
numPad = "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
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.
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:
list(product([1,2,3],"ab")) = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b'), (3, 'a'), (3, 'b')]
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:
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
"abc", we get a different result:
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:
# 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(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, the second character from
charArrr, etc. Our approach will be:
charArronly has one element, then return a list of the letters of
charArr. For example, if
charArrhas 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
In code, we have:
def allStrings(charArr): # base cases: charArr only has 0 or one element if len(charArr) == 0: return  if len(charArr) == 1: return list(charArr) # find the list of strings remaining = allStrings(charArr[1:]) output =  for start_char in charArr: # 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:
# 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)
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 CodeSignal forum!