 # 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
| 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
'hello'
'a b'
''
''
'''
``````

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. belushkin

Here is my solution before watching the video:

``````def keypad_string(keys):
'''
'hello'
'a b'
''
''
'real python'
'''

'1': '',
'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': ' ',
'': ''
}

s = ''
res = ''
for letter in keys:
if len(s) > 0 and (s[-1] != letter or (s+letter) not in keypad):
s = ''

s += letter

return res
`````` efimius

@belushkin agree much simple and easier to follow James Uejio RP Team

@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

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

'''
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
'iigkn'
'hello'
'a b'
''
'ikn'
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
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

``````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 in ['1', '*', '#', '0']:
return switcher.get(seq) * len(seq)

if seq in ['7', '9']:
return switcher.get(seq) * div4 + switcher.get(seq)[len(seq) - (4 * div4 + 1)]

if seq in ['2', '3', '4', '5', '6', '8']:
return switcher.get(seq) * div3 + switcher.get(seq)[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
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

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

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

@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

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

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

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('#')
})

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

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

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

Here my suggestion before watching the solution:

``````from collections import defaultdict
import string

'''
'a b'
''
''

:param keys:
:return:
'''

phone_digits = defaultdict(list)
possible_letters =[l for l in string.ascii_lowercase]
phone_digits=[' ']
phone_digits=['']
for i in range(2,10):
if i == 7 or i == 9:
phone_digits[i].extend(possible_letters[:4])
possible_letters = possible_letters[4:]
else:
phone_digits[i].extend(possible_letters[:3])
possible_letters=possible_letters[3:]
phone_digits=dict(phone_digits)

# phone_digits = {
#     0: [' '],
#     1: [''],
#     2: ['a', 'b', 'c'],
#     3: ['d', 'e', 'f'],
#     4: ['g', 'h', 'i'],
#     5: ['j', 'k', 'l'],
#     6: ['m', 'n', 'o'],
#     7: ['p', 'q', 'r', 's'],
#     8: ['t', 'u', 'v'],
#     9: ['w', 'x', 'y', 'z']
# }
letterDigits = defaultdict(str)
for k, v in phone_digits.items():
for letter in v:
letterDigits[str(k)*(v.index(letter)+1)]=letter
occ = 1
result = ""
for i, c in enumerate(keys):
if i == len(keys)-1 or keys[i+1] != c:
result += letterDigits[c*occ]
occ=1
else:
occ+=1
return result
`````` jeffmallozzi

Since ‘1’ is ignored, maybe that could be used to break up a sequence of multiple presses. For example to get ‘nn’ someone could press ‘66166’. Anther option is to use a space in the input string to represent the pause between multiple presses of a key that was usually used IRL on the old school feature phones when text messages were still new.

Here’s my solution, mostly from before watching the video. I added both options for using ‘1’ and ‘ ‘ to separate letters after reading the comments.

``````from itertools import groupby
'''
Given a string consiting of 0-9,
find the string that is created using
|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
'hello'
'a b'
''
''
'bbb'
'bbb'
'''

'1': [''],
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z'],
'*': [],
'0': [' '],
'#': []
}

if keys == '':
return ''

key_groups = []
gropper = groupby(keys)
for k, g in gropper:
key_groups.append((k,len(list(g))))

result = ''
for key_group in key_groups:
key, num = key_group
if key == ' ':
continue
for i in range(presses):
if remainder:
else:

return result
`````` jeffmallozzi

A couple of edits from my first post: Added a ‘ ‘ virtual key to the key pad, this allowed me to remove the ‘if key == ‘ ‘: continue Removed a for loop by just using string multiplication

``````from itertools import groupby
'''
Given a string consisting of 0-9,
find the string that is created using
|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
'hello'
'a b'
''
''
'bbb'
'bbb'
'cccb'
'''

'1': [''],
'2': ['a', 'b', 'c'],
'3': ['d', 'e', 'f'],
'4': ['g', 'h', 'i'],
'5': ['j', 'k', 'l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r', 's'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y', 'z'],
'*': [],
'0': [' '],
'#': [],
' ': ['']
}

if keys == '':
return ''

key_groups = []
gropper = groupby(keys)
for k, g in gropper:
key_groups.append((k,len(list(g))))

result = ''
for key_group in key_groups:
key, num = key_group
if remainder:
else:

return result
`````` Jon Scott

Solution before watching the video:

``````def keypad_string(code:str) -> str:
'''
Given a string consisting of 0-9,
find the string that is created using
|  1        |  2  (abc)  |  3 (def)    |
|  4 (ghi)  |  5  (jkl)  |  6 (mno)    |
|  7 (pqrs) |  8  (tuv)  |  9 (wxyz)   |
|     *     |  0  ( )    |      #      |
we can ignore 1, and 0 corresponds to space
'hello'
'a b'
''
''

The following does not work properly !!! was shooting for (the) 'moon'
'ooo'

But this works as expected (with bogus sep)
'moon'
'''
from itertools import groupby
groupings_of_nums = [list(g) for k, g in groupby(code)]
message = ''
for cluster in groupings_of_nums:
# break clusters up into groups of 3 chars via :
#         [lst[i:i + 3] for i in range(0, len(cluster), 3)]
rep = [cluster[i:i + 3] for i in range(0, len(cluster), 3)]
for r in rep:
if cluster == '2':
message += 'abc'[len(r) - 1]
if cluster == '3':
message += 'def'[len(r) - 1]
if cluster == '4':
message += 'ghi'[len(r) - 1]
if cluster == '5':
message += 'jkl'[len(r)-1]
if cluster == '6':
message += 'mno'[len(r) - 1]
if cluster == '7':
message += 'pqrs'[len(r) - 1]
if cluster == '8':
message += 'tuv'[len(r) - 1]
if cluster == '9':
message += 'wxyz'[len(r) - 1]
if cluster == '0':
# REDUCE MORE THAN ONE 0 DOWN TO JUST ONE SPACE
message += ' '
return message
`````` Jon Scott

found error in previous post:

``````...
for cluster in groupings_of_nums:
if cluster in ['7','9']:
size_of_r = 4
else:
size_of_r = 3
rep = [cluster[i:i + size_of_r] for i in range(0, len(cluster), size_of_r)]
...
`````` reebaabu

I got this way optimised a bit after watching the video.

``````from rp_collections_counter import defaultdict

'2' : ['a','b','c'],
'3' : ['d','e','f'],
'4' : ['g','h','i'],
'5':  ['j','k','l'],
'6': ['m', 'n', 'o'],
'7': ['p', 'q', 'r','s'],
'8': ['t', 'u', 'v'],
'9': ['w', 'x', 'y','z'] }

count = defaultdict(int)
l1 = []
if keys == "" :
return ''
for i,x  in enumerate(keys):
num_letters = 3
if x in {"7", "9"}:
num_letters = 4
if x == "0" :
l1.append(' ')
if int(x) in range(2,10):
j = x
count[j] +=1
k = count[j]
if i != len(keys) - 1 and keys[i + 1] != j:
count[j] = 0
elif i == len(keys) - 1:
count[j] = 0
elif k == num_letters:
count[j] = 0
return(''.join(l1))
`````` linus-g

Here is my solution from before watching the video. The benefit of this solution is that it is short and I think relatively easy to follow, but this comes at the cost of having to search through the string many times to find possible matches.

``````def keypad_string(keys):
# create list with mapping from digit to letters
mapping = [
(2, "abc"),
(3, "def"),
(4, "ghi"),
(5, "jkl"),
(6, "mno"),
(7, "pqrs"),
(8, "tuv"),
(9, "wxyz"),
(0, " "),
(1, "")
]

for key, letters in mapping:
if key == 1:
keys = keys.replace(str(key), letters)
for times_pressed in range(len(letters), 0, -1):
keys = keys.replace(str(key) * times_pressed, letters[times_pressed - 1])
return keys
`````` andr3yk

Below is my solution:

1. Create a `key_mapping` dictionary with `enumerate` and list of strings
2. Create a list of key mappings to be looked up in `key_mapping` dictionary in sequential order. I look back if the previous key is pressed again and check the maximum presses in the `key_mapping` dictionary. (Accepted edge case based on the `hello`)
3. Create a final result based on the `key_input_count`, I guess I could do it straight in the original logic to save on another loop, but it was already getting tricky to read. :)
``````    [{'4': 2}, {'3': 2}, {'5': 3}, {'5': 3}, {'6': 3}]
'hello'
``````
``````    key_mapping = {str(i): k for i, k in enumerate([
[' '], [''], 'abc', 'def', 'ghi', 'jkl',
'mno', 'pqrs', 'tuv', 'wxyz'
])
}
result = ''
key_input_count = []
for position, number in enumerate(keys):
if position == 0:
key_input_count.append({number: 1})
else:
if key_input_count[-1].get(number):
if key_input_count[-1].get(number) == len(key_mapping[number]):
key_input_count.append({number: 1})
else:
key_input_count[-1][number] += 1
else:
key_input_count.append({number: 1})

for keystrokes in key_input_count:
for key, value in keystrokes.items():
result = result + (key_mapping.get(key)[value - 1])
return result
``````

to join the conversation.