# Medium Interview Question

In this lesson, you’ll use what you learned in the previous sections to solve a medium **real world interview question**. Medium means something you might find in a technical phone screen or an onsite interview.

Here’s the question:

```
def keypad_string(keys):
'''
Given a string consisting of 0-9,
find the string that is created using
a standard phone keypad
| 1 | 2 (abc) | 3 (def) |
| 4 (ghi) | 5 (jkl) | 6 (mno) |
| 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
| * | 0 ( ) | # |
You can ignore 1, and 0 corresponds to space
>>> keypad_string("12345")
'adgj'
>>> keypad_string("4433555555666")
'hello'
>>> keypad_string("2022")
'a b'
>>> keypad_string("")
''
>>> keypad_string("111")
''
'''
```

The entire solution will be available at the end of the course. Try the problem yourself and then watch the video for the solution.

You heard about Big O analysis, which is a way to analyze the speed and memory usage of a function or block of code. See Wikipedia Time complexity for more information.

**00:00**
In this video, you’ll use some of the concepts you learned in this course to solve a medium-level interview problem. Let’s get started. Here’s a function `keypad_string()`

.

**00:10**
This function will take a string consisting of 0-9 and find the string that is created using a standard phone keypad. Here’s a standard phone keypad. *1*, *2*, *3*, *4*, *5*, *6*, *7*, *8*, *9*, ***, *0*, *#*. *2* maps to *(abc)*, *3* maps to *(def)*, *4*—*(ghi)*, et cetera. *0* maps to space, *1* doesn’t map to anything, and same with *** and *#*—don’t map to anything.

**00:37**
Let’s look at some tests. I wrote a bunch of tests, but the interviewer might not give you this many, so you should always try to come up with your own. Here is `keypad_string()`

with the string `"12345"`

.

**00:48**
It returns a string `'adgj'`

, because `"1"`

corresponds to nothing, `"2"`

corresponds to `'a'`

—because *2* is only pressed once—`"3"`

corresponds to `'d'`

, `"4"`

corresponds to `'g'`

, `"5"`

corresponds to `'j'`

.

**01:02**
So, how do you get the second or third letter? Well, you have to press the number multiple times. So, `"44335"`

—this many times—`"666"`

is going to be the string `'hello'`

, because `"44"`

maps to the character `'h'`

—because you press it once, then twice.

**01:18**
`"33"`

maps to `'e'`

. `"55"`

—so, this `"5"`

actually appears six times, because if you press the key more than this many times, then it will add the last letter and then sort of loop back around.

**01:32**
This corresponds to `'l'`

, and then this corresponds to `'l'`

. `"666"`

corresponds to `'o'`

, because `"6"`

, `"6"`

, and then `"6"`

again.

**01:43**
Here’s an example using the *0*: `"2022"`

. `"2"`

corresponds to `'a'`

, `"0"`

is a space, `"22"`

corresponds to `'b'`

. Empty string should return empty string, and something just consisting of 1’s should also return the empty string. I highly recommend you try this on your own.

**01:59**
Maybe take—in this case—30 to 45 minutes to try to solve this problem. I will go over the solution in five, four, three, two, one.

**02:09**
What’s the first thing we should do? Well, there’s two steps. `# build the map from keys to letters`

, so basically, how to map `"2"`

to `"abc"`

, `"3"`

to `"def"`

, et cetera.

**02:21**
Then, `# loop through the keys and add the corresponding letter`

`(taking into account keys pressed multiple times)`

. So, this is going to be the harder of the two, but let’s start with building the map.

**02:36**
This is somewhere the `string`

constants can come in handy. So, `import string`

. What are the possible letters? Well, `possible_letters`

are going to be `string.ascii_lowercase`

. This is going to be `'a'`

, `'b'`

, `'c'`

, `'d'`

, `'e'`

, `'f'`

, `'g'`

, all the way to `'z'`

. What are the possible keys?

**02:55**
`possible_keys = string.digits`

. This is going to be the strings `'0'`

, `'1'`

, `'2'`

, `'3'`

, `'4'`

, all the way to `'9'`

.

**03:02**
Then, we’ll need a variable for our final mapping—`key_to_letters`

.

**03:09**
Then, we might need some more variables, but let’s just try to get started. So, `for key in possible_keys`

, how do we know what to map? Well, let’s start with `"0"`

and `"1"`

.

**03:23**
Those, we know for a fact, don’t really follow this rule of `'abcdefg'`

, and they won’t even use the `possible_letters`

. So, `if key == "0":`

then `key_to_letters[key]`

is going to be a space. `if key == "1":`

then `key_to_letters[key]`

is going to be the empty string.

**03:46**
Now, let’s look at this logi: how to build this dynamically so that we’re not just hardcoding each number. Well, you can think about it like this. Basically, it’s slicing three letters at a time, or sometimes four letters at a time, from the `possible_letters`

.

**04:04**
So, how do you slice a string? Well, you can have a start index, so maybe `start_index`

,

**04:12**
and then the `letters`

is going to be equal to `possible_letters`

sliced from the

**04:19**
`start_index`

to the `start_index + <some number here>`

. Well, it changes from `3`

or `4`

, so let’s do something like, let’s put an `else:`

because this should all be under here, and then something like `num_letters`

.

**04:36**
This is the number of letters that we should be slicing. It’s going to be equal to `3`

, but if the `key`

is in the set `{"7", "9"}`

—so, instead of writing `if key == "7" or key == "9"`

, just put it in a set and do this `in`

—it’s a lot cleaner.

**04:57**
`num_letters = 4`

. So now, slicing `possible_letters`

to `start_index + num_letters`

, and then `key_to_letters[key] = letters`

.

**05:11**
Let’s just print out the `key_to_letters`

and make sure that this worked.

**05:18**
`'0'`

—`'abc'`

, `'1'`

—blank, `'2'`

—`'abc'`

, `'3'`

— `'abc'`

, `'4'`

—okay, so this clearly didn’t work. There are two issues.

**05:27**
`'0'`

mapped to `'abc'`

, which it shouldn’t have, and that’s because we forgot an `elif`

, here, instead of an `if`

, because `if`

is going to execute this, then not execute this, and then execute the `else`

. So—`elif`

.

**05:38**
And then, it’s because we forgot to increment the `start_index`

…

**05:48**
`'0'`

maps to space, `'1'`

maps to empty string, `'2'`

—`'abc'`

. `'def',`

`'ghi'`

, `'jkl'`

, `'mno'`

, `'pqrs'`

, `'tuv'`

, `'wxyz'`

.

**05:58**
Perfect. This is actually a perfect place to introduce a helper function to store all of this, because this is basically completely separate from what we need to do below, and sometimes it might be hard to keep scrolling up or read through the code.

**06:13**
It just gets a little confusing or maybe we’ll end up reusing variables, so let’s just put this all in a helper function. This will look really good in interviews when you start to compartmentalize code. Let’s call this, `get_key_to_letters()`

…

**06:31**
and then return `key_to_letters`

.

**06:36**
Now, just put that over there. `key_to_letters = get_key_to_letters()`

.

**06:44**
Save, make sure it worked. It worked correctly. Okay, so now the second part. `# loop through the keys and add the corresponding letter`

`(taking into account keys pressed multiple times)`

.

**06:53**
So, let’s try to do the case where they aren’t pressed multiple times. Just do `for key in keys`

and make a `result`

.

**07:03**
`result += key_to_letters[key]`

, then maybe just the `[0]`

, just to be naive, and then return `result`

.

**07:15**
So, this is going to error for some of them. Here, we got `'gg'`

—blah, blah, blah, blah, blah. It actually passed the first test, so that’s cool.

**07:23**
And here you get `'a aa'`

, instead of `'b'`

. So now, we’ll definitely have to introduce a `count`

to count the number of times the key has been pressed, and also the current key, because if the key changes, then we’ll need to reset the `count`

, and in order to know if the key changed, you’ll need to introduce a new variable, `curr_key`

. Okay.

**07:47**
Now, instead of doing this, what cases do we have? Well, we can do basically `if key ==`

the string `"1"`

, just `pass`

, because basically, in those cases, do nothing. Otherwise, if there has been no `curr_key`

pressed, then the `curr_key = key`

and `count = 1`

.

**08:09**
This is basically just doing the first letter, because `curr_key`

will be nothing, and so you know that you’re not going to add anything to your resulting string yet, because nothing’s changed. You’re just pressing a key, you don’t know if that key is going to repeat or not, so let’s just do `curr_key`

`count`

equals `1`

. Otherwise, here, there are two possibilities: `# press the same key`

, `# press different key`

.

**08:37**
I guess a better name for this `curr_key`

variable would actually be `prev_key`

(previous key).

**08:44**
So then, `# press the same key`

`if prev_key == key`

. Let’s be very explicit so we don’t get confused.

**08:57**
Okay. Otherwise, `# press different key`

. So, what’s the case if it presses the same key? Well, there are two cases here: `# press X times already`

, `X`

being the length of the letters that it maps to—for example, 5, 5, 5, and then 5, one more time.

**09:15**
You’ve pressed it already three times, so now you have to loop back to the beginning and then add that last letter. Otherwise, `# hasn't pressed X times`

yet, so something like `if count == `

`len()`

of the length of the letters.

**09:32**
So, this will be `curr_key_letters = key_to_letters[key]`

. `len(curr_key_letters)`

. Then, what do we do? Well, add to the `result`

, the last letter… the last letter. Reset `count`

to `1`

.

**09:51**
Otherwise, just increment `count`

. Okay, so this takes care of the case where you press the same key. `# press different key`

—well now, you need to look at the previous letters and add, basically, the letter that corresponds to the number of counts that you’ve done.

**10:08**
So, `result += prev_letters[count - 1]`

. It’s `- 1`

because `count`

starts at `1`

—you pressed it once, `2`

—you pressed it two times, but then to get the letter that corresponds to the second press would actually be the first index of the letters. And then `prev_key = curr_key`

and then `count = 1`

. I think this line was just legacy, so let’s remove it. Save. Python doctests. Okay, a bunch of errors, not surprising. `letters`

, `curr_key_letters`

—here.

**10:42**
Let’s see what else is yelling. `key`

—this should be `curr_key`

.

**10:47**
I think that’s good. 3 of 5 failed. Okay. It looks like we’re missing the last letter. Well, that’s because it goes `"2"`

, and then `"0"`

—it will add the count for `"2"`

and `"0"`

goes to `"2"`

, it will add the space, and then `"2"`

, then `"2"`

, and then it will never change keys, so it will never add the `'b'`

.

**11:08**
So after here, we need to do something like `result += curr_key_letters`

, indexed at `count - 1`

.

**11:19**
Okay. `'curr_key_letters'`

[…] `local variable`

[…] `referenced before assignment`

. Okay. So, probably something like…

**11:33**
Redefine it there. Okay, `string index out of range`

. I think this has to do with…unlocal—`local variable 'curr_key'`

…here.

**11:45**
So, a better way would maybe do `curr_key`

is going to be empty string, or you could do this to be fancy. And then, only do this if there is a `curr_key`

. Oh.

**12:01**
`string index out of range`

. `result += curr_key`

length. So, I have to basically check because it could be the case that it could be all 1’s, and so then indexing `count - 1`

, which would be `-1`

would not work, so I have to do something like if `len()`

greater than `0`

, then add to the `result`

. Perfect! So, it all passes.

**12:23**
Something you could add is adding in an `assert`

statement to make sure that the key is a valid key. So, something like move this import so that it’s actually used globally,

**12:34**
and then something like `digits`

here. Maybe set something like `valid_keys = `

a set of `string.digits`

and then

**12:52**
`assert curr_key in valid_keys,`

otherwise, `"Invalid key"`

. Okay, that obviously works. But then, do something like keypad `"*"`

, then do something like `"Traceback (most recent call last):"`

,

**13:19**
do something like `"AssertionError: Invalid key"`

.

**13:26**
Cool! So, that passed. Let’s look at the runtime really quick. So, `get_letters_to_key`

—this is actually taking constant time because even though it has to loop through `"0"`

through `"9"`

and do a bunch of stuff, it doesn’t depend on the input.

**13:41**
And so, really, you can think of it as constant time. Actually, it might be better to make this a global variable, something like

**13:49**
`KEY_TO_LETTERS`

and then use it here, here, and I guess, here. Cool. Still works. So yeah—constant time, there. Here—constant, constant, constant.

**14:04**
This is constant because this length does not depend on the input. This takes *O(n)* time because you’re looping through *n* keys. Assertion is constant, constant—all constant. To access a dictionary is constant. Here—constant. `len(curr_key_letters)`

—so, this is actually taking the length, which is constant. All this here, getting the dictionary—constant. `result +=`

, here… So, this function takes *O(n)* time, where *n* is the size of the keys.

**14:40**
So, let’s quickly review the solution in its entirety. First, there’s a function `get_key_to_letters()`

, which helps create a map `key_to_letters`

.

**14:47**
This will help us find what each key, or what number, maps to. We took advantage of the `string`

module and created the `possible_letters`

, which is `ascii_lowercase`

—`'a'`

, `'b'`

, `'c'`

, `'d'`

, all the way to `'z'`

—and `possible_keys`

, which is the digits `'0'`

through `'9'`

.

**15:01**
Then, we created the dictionary that is going to be our mapping, a `start_index`

to see which possible letter we’re currently looking at. And then, we looped through all the keys. Two hardcoded cases for `"0"`

and `"1"`

, because they don’t include any letters from ASCII lowers, and then created this variable `num_letters = 3`

.

**15:19**
That’s the number of letters that maps to the current key. If the key is `"7"`

or `"9"`

, then the number of letters that will map is `4`

. Then, slice the `possible_letters`

—`start_index`

sliced to `start_index + num_letters`

.

**15:32**
So, this is going to pull this number of letters from the `possible_letters`

. Then, map that in the dictionary and then increment the `start_index`

, which is sort of our pointer, to which letter to start slicing at. Then, return the dictionary. Here’s a global variable that’s bound to `get_key_to_letters()`

, so that way, every time we call `keypad_string()`

, it doesn’t re-instantiate this map. This map will only get created once.

**15:57**
Now, scrolling down, here’s where most of the logic happens. Basically, we have a `result`

which will be our resulting string, `count`

to count the number of times a key has been pressed, `prev_key`

, which would be the previous key, and `curr_key`

, which is the current key we’re looking at.

**16:11**
Then, the `valid_keys`

is going to be the set of all the digits. That way, we can validate if the key is a valid key by using the `assert`

statement and then raising an error. So, if the current key is `"1"`

, then do nothing, because that’s a special case. Otherwise, if there’s no previous key, that means we’re at the first key, and the previous key equals the current key, and the number of times we’ve pressed is `1`

. And if there is a previous key, that means we’re at the second—or later—key, and then we get the letters that map to the key, check if the previous key is the same key, and there are two cases, here, where you’ve already pressed *X* times, where *X* is defined as either 3 or 4. Check if the length of the `curr_key_letters`

is equal to the number of times you’ve pressed it already. And if it is, then you add to the `result`

the last letter of the mapping, and then reset the count to `1`

.

**16:59**
Otherwise, you haven’t pressed it *X* times yet, so then just increment the `count`

. And then the case where you’ve pressed a different key, then get the previous letter mapping—add to the `result`

the last letter of that mapping, then reset the previous key to the current key and then `count = 1`

. Then, you need this case at the end, because basically, if you’ve been pressing the same key, the key wouldn’t have changed and you won’t have added the correct letter at the end. So, check if there’s a `curr_key`

. Basically, this is just checking if you’ve went through this `for`

loop, then get the current mappings, then check if the length of the current key mapping is greater than `0`

, because it could be the case you’re pressing 0’s over and over again, and there is no mapping, and this `[count - 1]`

will error.

**17:39**
So, if this check passes, then you add to the `result`

the last letter. Then, you return `result`

. This concludes this pretty long video where you went through a medium-level interview question.

**17:50**
In the next video, you’ll use the topics you learned in this course to solve a hard interview question.

**efimius** on April 27, 2020

@belushkin agree much simple and easier to follow

**James Uejio** RP Team on April 27, 2020

@belushkin thank you for sharing your solution! I agree your solution is better. I was trying to incorporate some topics into a solution and make it more dynamic. But after the fact I realized hard coding might have been better.

**Ksenia** on April 28, 2020

```
import string
def get_key_to_letters():
KEY_TO_LETTERS = {}
letters = string.ascii_lowercase
digits = string.digits
i = 0
for key in digits:
if key == '0':
KEY_TO_LETTERS[key] = ' '
elif key == '1':
KEY_TO_LETTERS[key] = ''
else:
num_letters = 3
if key in {'7', '9'}:
num_letters = 4
KEY_TO_LETTERS[key] = letters[i:i + num_letters]
i += num_letters
return KEY_TO_LETTERS
KEY_TO_LETTERS = get_key_to_letters() # O(1)
def keypad_string(keys):
'''
Given a string consisting of 0-9, find the string that is created using a standard phone keypad
| 1 | 2 (abc) | 3 (def) |
| 4 (ghi) | 5 (jkl) | 6 (mno) |
| 7 (pqrs) | 8 (tuv) | 9 (wxyz) |
| * | 0 () | # |
You can ignore 1, and 0 corresponds to space
>>> keypad_string('44444445566')
'iigkn'
>>> keypad_string("2345")
'adgj'
>>> keypad_string("4433555555666")
'hello'
>>> keypad_string("2022")
'a b'
>>> keypad_string("")
''
>>> keypad_string('4445566')
'ikn'
>>> keypad_string("*")
Traceback (most recent call last):
...
AssertionError: Invalid key
'''
# 1. build the map from keys to letters
# 2. Loop through the keys and add the corresponding letter
# (taking into account keys pressed multiple times)
if keys == '':
return ''
valid_keys = set(string.digits)
i = 0
message = ''
while i < len(keys):
assert keys[i] in valid_keys, "Invalid key"
j = i
if (j + 1) == len(keys):
pass
else:
while keys[j] == keys[j + 1]:
if (j + 1) == len(keys) - 1:
j += 1
break
else:
j += 1
size_of_keypad_str = len(KEY_TO_LETTERS[keys[i]])
if (j - i) < size_of_keypad_str:
message = message + KEY_TO_LETTERS[keys[i]][j - i]
else:
count = (j - i) // size_of_keypad_str
letter = KEY_TO_LETTERS[keys[i]][-1]
message = message + letter * count
residual = (j - i) % size_of_keypad_str
message = message + KEY_TO_LETTERS[keys[i]][residual]
i = i + (j - i) + 1
return message
```

**AlekS** on April 28, 2020

```
from collections import deque
inp = '255533990625533777702077776668866300***0099990099990999999999999444664'
# map homogeneous group to characters e.g. "88888" to 'vt'
def map_to_letter(seq):
switcher = {
'0': ' ',
'1': '',
'2': "abc",
'3': "def",
'4': "ghi",
'5': "jkl",
'6': "mno",
'7': "pqrs",
'8': "tuv",
'9': "wxyz",
'*': '*',
'#': '#'
}
div4 = (len(seq) - 1) // 4
div3 = (len(seq) - 1) // 3
if seq[0] in ['1', '*', '#', '0']:
return switcher.get(seq[0]) * len(seq)
if seq[0] in ['7', '9']:
return switcher.get(seq[0])[3] * div4 + switcher.get(seq[0])[len(seq) - (4 * div4 + 1)]
if seq[0] in ['2', '3', '4', '5', '6', '8']:
return switcher.get(seq[0])[2] * div3 + switcher.get(seq[0])[len(seq) - (3 * div3 + 1)]
#split given sequence to homogeneous groups e.g. '233311444422' to '2_333_11_44444_22'
def split_to_groups(lst):
qe = deque(inp)
res = []
prev = lst[0]
while qe:
curr = qe.popleft()
if curr == prev:
res.append(prev)
else:
res.append("_")
res.append(curr)
prev = curr
res0 = ''.join(res)
result = res0.split('_')
return result
# joining mapped letters to string e.g. ['a', 'l', 'e'] to 'ale'
def join_to_string(inp):
return ''.join([map_to_letter(each) for each in split_to_groups(inp)])
assert 'alex makes a sound *** z z zzzing' == join_to_string(inp)
```

**WD** on April 30, 2020

This function does not account for the case where someone wants to type two consecutive letters which use the same key. Ex: ‘wade’ would require the user to press ‘9’ for ‘w’, ‘2’ for ‘a’, ‘3’ for ‘d’, and then ‘33’ for ‘e’. However, without inserting a space or some other technique like a time gap between the ‘3’ for ‘d’ and the ‘33’ for ‘e’, the function will see it as ‘333’ for ‘f’ and output ‘waf’ instead of ‘wade’.

**fergusmeiklejohn** on May 7, 2020

How interesting :-) I did it a completely different way, with List Comprehensions. I’m not sure if this solution is better though, it must be a slower I’d have thought:

```
num_dict = {
"1": '', "11": '', "111": '', "2": 'a', "22": 'b', "222": 'c', "3": 'd', "33": 'e', "333": 'f', "4": 'g',
"44": 'h', "444": 'i', "5": 'j', "55": 'k', "555": 'l', "6": 'm', "66": 'n', "666": 'o', "7": 'p', "77": 'q',
"777": 'r', "7777": 's', "8": 't', "88": 'u', "888": 'v', "9": 'w', "99": 'x', "999": 'y', "9999": 'z',
"0": ' ', "00": ' ', "000": ' ', "*": '*', "**": '*', "***": '*', "#": '#', "##": '#', "###": '#'
}
def cond(n: str):
if n[0] in {'7', '9'}:
return wrap(n, 4)
else:
return wrap(n, 3)
list_grouped_by_number = [''.join(g) for k, g in groupby(keys)]
list_grouped_max_three_or_four_digits = [cond(n) for n in list_grouped_by_number]
flattened_list_grouped_max_three_or_four_digits = [
lst for sublist in list_grouped_max_three_or_four_digits for lst in sublist]
number_list_to_string_list = [num_dict[n] for n in flattened_list_grouped_max_three_or_four_digits]
return "".join(number_list_to_string_list)
```

**James Uejio** RP Team on May 8, 2020

@WD You are absolutely correct I can’t believe I didn’t think of that case. I think the correct solution would have been to have the * or # be a delimeter between letters, or if you want to solve the problem above, you don’t need to worry about that case. For people reading this, try it out where you have * or # in between letters!

@fergusmeiklejohn That solution works as well! Would definitely recommend putting comments for what each list comprehension is doing but otherwise great use of list comprehensions and higher order functions. Not sure where groupby is imported from though.

**Ignat Domanov** on July 8, 2020

I think I do not understand the problem. What are the exact rules for the numbers-to-letter conversion? For instance, what is the answer for the string “222”? How can we distinguish between “aaa”, “ab”, “ba”, and “c”?

**James Uejio** RP Team on July 11, 2020

Hi Ignat yea that was my mistake, I didn’t think of that case. You can see the comment above to see some potential variants of the problem that are more realistic.

**Eron** on Aug. 8, 2020

Hi everyone, let’s try with **re**

```
from collections import defaultdict
import re
keys_map = defaultdict(tuple, {
'1': ('',),
'2': tuple('abc'),
'3': tuple('def'),
'4': tuple('ghi'),
'5': tuple('jkl'),
'6': tuple('mno'),
'7': tuple('pqrs'),
'8': tuple('tuv'),
'9': tuple('wxyz'),
'*': tuple('*'),
'0': tuple(' '),
'#': tuple('#')
})
def keypad_string(keys):
reg = re.compile(r"(\d)\1*")
string = ''
matches = reg.finditer(keys)
for match in matches:
characters = keys_map.get(match.group(1))
length_of_match = len(match.group(0))
length_of_chars = len(characters)
floor = length_of_match - length_of_chars
while floor >= 0:
literal = find_literal(length_of_chars, characters)
string += literal
floor = floor - length_of_chars
if length_of_match % length_of_chars != 0:
string += characters[length_of_match % length_of_chars - 1]
return string
def find_literal(count_of_repeat, characters):
length = len(characters)
if length > 0:
floor = count_of_repeat % length
if floor == 0:
return characters[length - 1]
else:
return characters[floor - 1]
else:
return ''
```

**Özgür Gündoğan** on Sept. 13, 2020

I think the solution in the video has some bugs.

First of all, you are passing by when key is `1`

. Think about the case `"2212"`

. The correct answer is `'ba'`

, but your function probably returns `'c'`

.

Secondly, at the end the you don’t count the repeating keys. Think about the case `"2122222"`

. The correct answer is `'acb'`

, but your function probably gets index out of range error because the count is `5`

at the end.

**James Uejio** RP Team on Sept. 17, 2020

Hi Ozgur thank you for your comment. If you scroll up you will see my response to this.

Become a Member to join the conversation.

belushkinon April 27, 2020Here is my solution before watching the video: