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.
belushkin on April 27, 2020
Here is my solution before watching the video: