Count decodings of a numeric string

Q: Count decodings of a numeric string

This is a Coding & Algorithms interview question from Snapchat for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given a string s of digits representing an encoded message where '1' maps to 'A', ..., '26' maps to 'Z', and '0' cannot appear alone (it must be part of '10' or '20'), count the number of distinct decodings of s. Design an O(n)-time, O( 1)-extra-space algorithm. Follow-ups: handle very large n by returning the count modulo 1,000,000,007; extend the API to support streaming input where characters arrive one by one and you must update the count online.

Count decodings of a numeric string

Comments (0)