Count decodings of a numeric string

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Snapchat.

Q: What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Snapchat during technical 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.

PracHub · Accepted Answer

This question evaluates dynamic programming and string-processing skills, along with attention to edge-case handling, modular arithmetic for large results, and online algorithm design for streaming input.

Quick Overview

Count decodings of a numeric string

Constraints

Examples

Hints