CodeSignal Solves It: pressingButtons

pressingButtons technical interview question solution

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.

pressingButtons Facebook interview question 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:

Amazon web developer interview solution

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")

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.

using Python in technical interviews
Sometimes using Python feels like cheating.

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",
    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:

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:

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:

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 functions:

[''.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:

  1. 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'].
  2. 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:

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:

# uses the earlier function allStrings
def pressingButtons(buttons):
    numPad = [""   ,""    ,"abc","def" ,"ghi","jkl",
    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 CodeSignal forum!