Count decodings of a numeric string
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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.
Quick 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.
Count distinct A1-Z26 decodings modulo 1e9+7.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ('12',)
Expected Output: 2
Explanation: AB or L.
Input: ('226',)
Expected Output: 3
Explanation: Three decodings.
Input: ('06',)
Expected Output: 0
Explanation: Invalid leading zero.
Input: ('10',)
Expected Output: 1
Explanation: Only J.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.