Katkat
Back

Decode and Explain Ambiguity in Compression Strings

PinterestData Scientist · Onsite
MediumData ScientistOnsiteCoding & Algorithms

Last updated

This question evaluates parsing of compact count-value encodings, reasoning about ambiguous encodings, and combinatorial enumeration of all valid decodings.

Scenario

Compression library that encodes an array as count-value pairs where value is one digit but count may be many digits.

Question

Implement decode(s) that turns a string such as "1234" into the expanded list [2,4,4,4]. Explain why input "12114" is ambiguous and output all valid decodings.

Hints

DFS with memoisation over index; at each step parse 1–n digit count followed by one digit value.