Facebook Coding Interview Question - How Many Ways to Decode This Message?

hey everyone today I have a coding interview question that's being asked by Facebook in this problem you're given a mapping that's like this one so in this mapping the letter A maps to one as you can see and B to 2 and so on up to D which maps to 26 and with this mapping if you're given a message in a string for example a B you can convert it to another string in this case 1 2 because a maps to 1 and B maps to 2 and in this problem you're given the converted version of the string for example 1 2 again let's call it data for now and the problem is can you write a function that takes this data as the input and returns the number of messages that could have been the original message or in other words how many ways are there to decode this message back to the original message so for example if the given input is 1 2 your function let's call it num ways of data should return 2 because there are 2 possible messages that can be encoded into one - one of them is as we saw earlier a B and the other one is actually just L because L maps to 12 and if you're given for example 0 1 instead as the data your function num ways of data should return 0 instead because there's no message that maps to 0 1 okay try solving this problem in off n in time where n is the number of letters in the given string data and by the way just for simplicity you can assume that the given data string has only digits inside you know between 0 and 9 ok pause the video right here if you want to try solving this problem by yourself and by the way this problem came from this website called daily coding problem you can get more problems just like this one through my referral and discount link si esto Jota io / daily anyway here's my solution I would first think about simpler examples so for example what if you're given three as the input then there's only one message that can be encoded into three and that's simply the letter C so your function should return one and what if you're given the empty string then the original message must have been an empty string as well so there's only one possible message here as well so your function should return one okay and what if you're given more complex inputs for example this one one two three four and five well in that case let's examine the input one three four and five then we can think about decoding it from left to right sequentially and at the beginning there are two choices the first one is to look at the first letter one by itself and then decode it back to a because as we saw earlier a maps to one and the second choice is to look at the first and the second letter together and then decode it back to L instead because L maps to 12 now if you go with the first choice and decode one to a then the whole message that you get by decoding the whole string will look like this it'll be a put together with whatever you get by decoding the rest of the message two three four and five and if you go with the second choice and decode one to 2l what's gonna be left will be three four five so the whole message that you get by decoding the whole string will be L put together with whatever you get by decoding three four five the rest of the message so actually the number of ways we can decode this message one two three four five will be the sum of the number of ways we can decode two three four five and the number of ways we can decode three four five so that's what I wrote here num ways of one two three four five is the sum of numbers of two three four five and numb ways of three four five and this is starting to look like recursion anyway let's take a look at another example what if you're given two seven three four five instead well you might say let's try the same thing so let's do that one way to decode this is to look at the first letter and then decode it back to B and that way the whole message you get by decoding the whole string will be be combined with whatever you get by decoding the rest of the message seven three four and five and what if you look at the first and the second letters together well there's no single letter in our mapping system that map's directly to 27 and that's just because we only have up to Z which maps to 26 so actually this is the only way to decode to seven three four and five so the number of ways of decoding this message to seven three four and five is equivalent to the number of ways of decoding seven three four and five and that's what I wrote right here let's take a look at just one more example here what if you're given a string that starts with 0 at the beginning well in that case there's no message that would encode into this string there are 1 1 because no single letter maps to 0 or 0 1 so num ways of 0 1 1 should return there now using all of these let's write our function recursively they're basically two base cases here the first one is when the string is empty and the second one is when the given string starts with at 0 and for the recursive case there are two cases the first one being when we need to call our function recursively twice and the second one is when we need to only call the function recursively once ok let's see how we can turn this idea into code like we saw earlier we're going to call our function num ways of data and instead of calling this function recursively directly we're going to define another function let's call it just helper and we're gonna call this function recursively it's gonna take data the given string and K which is going to be a non-negative integer and in the helper function we're only gonna look at the last K letters of data so for example if the given data is let's say ABCD and if the given K is 3 we're only gonna look at the last three letters BCD and this way we don't have to create a new string every time we call our function recursively and this helper function will return the number of ways we can decode the last K letters of the string and that means from our main function num ways all we need to do is we just need to return helper of data and Dara's length and that's the full string okay now in the helper function let's take care of the two base cases first the first one was when the string is empty we need to return one so we're just going to write if K or the number of letters we're going to look at is 0 then we're gonna return 1 and the second base case was when the first letter is 0 we needed to return 0 and to do this and to make it just a little bit more convenient we're gonna define a new variable called s which is going to be the starting index of the letters that were examining that's there as length minus K and using this we can say if data square brackets S or the letter or the character at the index S of data is equal to 0 then we're gonna return 0 now the next case we need to take care of are the two recursive cases that we saw earlier the case where we need to call the recursive function twice and the case where we need to call the function recursively only once this is the notation we used earlier but since we're not gonna call num ways recursively let's fix this notation so we have everything consistent okay here we're calling the helper function recursively instead we're never gonna change the first argument and in this first case right here we have one two three four five now let's say K right now is five in that case there are two ways to go about this the first one is to interpret the first letter by itself and then decode it back to a and in that case we're gonna call helper with the same string and K minus 1 the second way is to interpret the first two letters together and then they code it back to L instead and for that we're gonna call helper with the same string again and K minus two so with the first we curse we call K minus 1 becomes four and we're gonna look at these four letters and then with the second case K minus two becomes three and we're gonna take a look at the last three letters let's also examine the second case that's one for example we have two seven three four five as the string and five as K in that case there is no letter that maps to 27 so we only need to say we need to interpret two as B and then take a look at the rest of the string the last four characters so we need to only call helper again with two seven three four five and K minus 1 which is 4 so basically what we're gonna return from helper of the string and K will be either the sum of helper of the same string and K minus 1 and helper of the same string and K minus 2 or just helper of the same string and K minus 1 I think you'll notice that in either case we have helper of the same string and K minus 1 so let's store that in a new variable called result by writing results EKOS helper of data k minus 1 and then we need to add helper of the same string k minus 1 to that result only when we can interpret the first two letters of the part of the string that we're examining as a single letter so that's when the first two letters the number that it represents is less than or go to 26 and also greater than or you go to 10 we can check that by writing if K is greater than or equal to 2 and int of data square brackets s con s plus 2 is less than or equal to 26 so we need to first say K greater than or equal to 2 make sure that we have at least 2 letters in the part of the string that we're examining and then let's just say here that data square brackets s : s plus 2 retrieves the substring that we're interested in the first two letters of the part of the string that we're examining and then we need to convert it to an integer and make sure that that's less than or equal to 26 we don't have to worry about that part being greater than or equal to 10 here actually because that part is already taken care of when we check that data square brackets S or the first letter of the part of the string that we're examining is not equal to 0 so if it satisfies these two conditions then we'll add helper of data comma K minus 2 to the results and then after that we just need to return results now this solution works but it can be very inefficient depending on the nature of the input so let's see why that's the case and for that let's examine the worst case for this problem that's when we're given a string that solely consists of ones because then there are many many ways to interpret this string and if that was the case num ways of let's say six ones that would go into helper of the same string and six and to find the value for that we need to find the values for these two helper of the same string and five and helper of that string and four and here if we write this one hopper of six ones and six as age of six we'll see that to find the value for H of six we need to first find the values for H of 5 and H of 4 and to find the return value for H of 5 we need to first find the return values for H of 4 and H of 3 and so on and just like we saw in my video about Fibonacci sequence this is not the most efficient approach because we need to repeat some of the competition's over and over again for example to find H of 4 here and here and this actually takes about of 2 ^ and in time to find the number of ways to interpret a string with n letters inside and to fix this we can just use dynamic programming and memorization to do that let's say if we're trying to find num ways of 1 1 1 then we'll create a new array with n plus 1 elements or 4 elements in this particular case and then we're going to use this to store some of the intermediate results from our function we're gonna store helper of 1 1 1 K at index K so if K is 1 that goes into this one and this way helper of 1 1 1 and N or the last value that we need to find will go into the last index of this array right here and with that our code is going to look like this this is almost identical to what we had earlier except for these orange parts and the first thing that's different well is that we change the names a bit you know we have none ways of DP and helper of DP now and in num ways of DP we first define a new integer array whose length is the original data length plus 1 so that's n plus 1 and then let's say we want to initialize every element of this array to now just like that and then we're going to put it in a new variable called memo and instead of calling helper with data and data as length which is what we did earlier we're passing memo as an argument as well now in helper DP after taking care of the base cases if we have a value already stored at index K of memo then that's not gonna be now so if memo of K is not now we're gonna return that value instead of going through the whole function and otherwise this is the first time we're running this function with this particular K so we'll find the result and then instead of returning results right away we're gonna store it in memo at index K and then we're gonna return results okay and that's my solution and with this solution it only actually takes both n in time to find num ways of the given string instead of two to the power of n that we saw earlier and by the way like I said earlier this problem came from this website called daily coding problem you can find a website through my referral link CS dojo da io / daily it's a website that gives you a daily coding problem to practice with and it's actually a website that's run by a friend of mine I used to work with at Google if you use my referral link it's gonna give you a 10% discount on their premium subscription but I would say even their free option and their blog articles that you're looking at right now are pretty good anyway thank you so much for watching my videos as always and I'll see you guys in the next video

Channel: CS Dojo

Views: 465,206

Keywords: facebook coding interview, facebook programming interview, facebook coding interview question and answer, facebook programming interview question and answer

Id: qli-JCrSwuk

Length: 16min 36sec (996 seconds)

Published: Fri Jul 13 2018