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:

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:43**
`+= num_letters`

.

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

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