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

Facebook coding interview question and answer - how many ways to decode this message?

(That’s a referral link, and you can get a 10% discount through that link. Their free option and blog articles are good, too, though.)

[CSDojo]

As I mentioned in the video, if you’re looking for more problems like this, I’d recommend this website called Daily Coding Problem. It’s actually run by a friend of mine who I used to work with at Google.

EDIT: By the way, the code I used in this video is pseudocode. I should've clarified it in the video - sorry about that!

[haneulbae]

I recently started watching your channel for preparing my interview and think it's got the perfect difficulty I am looking for. Thank you !

[maheshs]

At the beginning of this video, It looked like a difficult problem to solve. But you've managed to simplify it so much! The solution now seems so obvious!
The key is to know what is the first step in the solution. Here, it was to consider smaller examples to identify the base cases. Then, we simply break the given problem into smaller pieces until they all fit into the base cases.

[prernasharma]

You explain BRILLIANTLY!!!


thanks a lot ☺

[RaulLopez-phzh]

Been subbed for a while, the quality of your videos has always been good but I would say it has improved a lot. Enjoying your choice of problem, this difficulty is perfect to try out and learn from.

[budhachandrayumkhaibam]

I really look forward to your videos as I think you're method of teaching is really good. Keep up the good work and please don't get discouraged as I am sure many people look up to you the way that i do.

[jackvicky]

At first I was tryied some logics then I giveup, but you just Nailed it bro... thanks for the good video ❤.

[FWTteam]

I was afraid of coding interviews before I met you. Thanks again !!

[droctogonapus]

I love this channel. I totally didn't understand the dynamic programming solution at first and then your explanation made it make sense. Thank you!

[jamesdvc]

The best explanation I can find on the internet for this problem!

[uppubhai]

the reason this is such a excellent explanation is that we got to know your thought process and how a person should approach a problem

[iphoneeating]

Just amazing. Very well explained. One of the best solutions I understood from all the relevant videos on this problem on Youtube. Keep on posting more such problems

[himanshujotwani]

A plausible solution is adding 1 initially (if all the letters are decoded separately) and then iterating over the string with 2 chars at a time if < 26 do +1, all iterations can be counted ( but have to deal with 0 cases at the same time )

[anukulchand]

Man, the way you explain the problem is excellent and I learn a lot from your videos. Keep it up !!!

[andrewjackson]

Firstly, I'm a big fan of your videos and I appreciate the work you put in to make the videos so great.

I approached the problem quite differently but seem to be getting reasonable results.
I assigned a pointer = 0 that iterates through the list once (O(n)?) and a total_ways counter = 0 and said that if the value at data[pointer] < 3 AND data[pointer + 1] < 7 (in other words, is the value of where I'm looking and the next one less than 26), total_ways += 2 (there are two possible encoded letters) then increment the pointer += 1 else: total_ways +=1 pointer +=1 (in other words, the value is bigger than 26 and can only be encoded as a single letter). Finally, return total_ways + 1 as the while loop needs to go to len(data) - 1 and we need to account for the last letter in the list

I am new to coding and so this will probably not be right but here is what I got:

def num_ways(data):
if data == "":
return 1
if int(data[0]) == 0:
return 0
total_ways = 0
pointer = 0
while pointer < len(data)-1:
if int(data[pointer]) < 3 and int(data[pointer + 1]) < 7:
total_ways += 2
pointer +=1
else:
total_ways += 1
pointer += 1
return total_ways + 1

[bensge]

Good coding problem and solution! You get extra credit for being very honest and disclosing that the website is from a friend of yours. Cheers!

[bardamu]

Thanks YK for the time to do and share this valuable video! Correct me if I am wrong but the memo array needs to be defined in the num_ways_dp function rather than within the helper_dp function because it acts as a global variable for the helper_dp function and is therefore not reinitialized for every recursive call of the helper_dp function. This may clarify why memo arry is not defined locally in the helper_dp function. Hope that I am not mistaken and making things confusing.

[cyjexdc]

Wow, now I understood that I have to spent more time practicing. And thank you for your amazing videos!

[deanroddey]

A simple iteration through the string would work fine, and be the lightest weight way possible probably. Check the empty and 0 first character bits. If not, then call a helper with start and end indices or iterators. Then it just loops. On each round, while it still has input, it knows one character is always good, so add 1 to return. If there's another available, it looks at the value of the first one. If it's 1, then the next character has to be valid. If it's 2, then the next character is valid if less than 7. So in those cases move up and add another 1 to the return. Now you are on the next character and just repeat until out of data. On each round you add 1 or 2 to the return value and move up 1 or 2 positions. At the end, return the accumulated count.

[dikidsaputra]

As always your video is very interactive, thank you so much for sharing