The Encoded Signal

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Fivetran

Problem

A device firmware emits letter-frequency telemetry as a compact code with no literal letters in it, and you expand it into counts for the 26 lowercase letters a through z. A single digit from 1 to 9 names one of the first nine letters (1 is a, 9 is i), while two digits immediately followed by # name a letter by position, so 10# is j and 26# is z. Either token may carry a parenthesized repeat count like 1(3), and a bare token counts once.

Letters folded into digits, counts hidden in the punctuation.

Example 1

Input:

encoded = "1(2)2(3)1324#26#(5)"

Output:

[3,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,5]

Example 2

Input:

encoded = "1234"

Output:

[1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Worked solution and explanation

What this really is

Strip the telemetry costume and this is a single-pass tokenizer with one branch that bites: at every cursor position you have to decide whether the next letter is one digit or two digits plus a #, and the only way to tell is to peek two characters ahead for that #. Anyone can map a digit to a letter. What separates people is committing to the right token width before they move the cursor. Read one digit when the token was really 24# and the entire rest of the string shears off by one, silently, with no crash to warn you.

The decision at every cursor

Step 1: Read the three token shapes

A single digit 1-9 is a letter a-i. Two digits followed by # are a letter j-z by position. A trailing (n) is a repeat count.

Step 2: Pick the token width before advancing

At each position, look two characters ahead. A # there means consume two digits and skip the #; otherwise consume one digit. This single check is what keeps the cursor aligned.

Step 3: Apply the count and accumulate

After the letter is known, if the next character is (, read up to the matching ) as a whole number and use it as the count, else the count is 1. Add that count into the letter's slot so repeats accumulate.

The solution

Single pass with two-ahead lookahead
def the_encoded_signal(encoded: str):
    freq = [0] * 26
    i = 0
    n = len(encoded)
    while i < n:
        if i + 2 < n and encoded[i + 2] == '#':
            letter = int(encoded[i:i + 2]) - 1
            i += 3
        else:
            letter = int(encoded[i]) - 1
            i += 1
        count = 1
        if i < n and encoded[i] == '(':
            close = encoded.index(')', i)
            count = int(encoded[i + 1:close])
            i = close + 1
        freq[letter] += count
    return freq

Decide token width, then read an optional count, then accumulate.

Greedy on the digit
Treat each digit as a letter the instant you see it. The first digit of a 24# token becomes its own letter, the cursor lands on 4#, and everything after it is off by one. The output is quietly wrong, never throwing.
Greedy on the hash
Before consuming anything, peek two slots ahead. A # there means the two digits here are one letter (j through z) and the cursor jumps 3; otherwise it is a single-digit letter and the cursor jumps 1. The width is settled before you advance.

Common follow-up questions