Ways of Reading

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
mid
Asked in
Qube Research & Technologies

Problem

A metrics pipeline names each time series by gluing known segments together into one separator-free key, so a single string like diskmemio can be read more than one way. Given the key and the vocab of known segments, produce every sequence of segments drawn from the vocabulary whose concatenation is exactly the key.

One key, no separators, and more than one story it could tell.

Example 1

Input:

key = "cpuhostprod", vocab = ["cpu","host","prod","cpuhost","hostprod"]

Output:

[["cpu","host","prod"],["cpu","hostprod"],["cpuhost","prod"]]

Example 2

Input:

key = "netnetnet", vocab = ["net","netnet"]

Output:

[["net","net","net"],["net","netnet"],["netnet","net"]]

Worked solution and explanation

Why this problem exists in real interviews

This is word-break-all-segmentations wearing a metrics-parsing costume. The skill being probed is enumerating every way a string factors into dictionary segments, not just finding one. Everyone reaches for the greedy move first, grab the longest prefix that is in the vocab and march forward, and it fails twice over. It only ever yields a single split, so it misses the others outright; and on a key where that longest prefix strands an unsplittable tail, it dead-ends and reports no split exists when several do. Get this wrong on memprod with vocab mem, memp, prod and you return nothing, because greedy takes memp and chokes on rod. Two families of correct answers exist: backtracking that rewinds to the last choice, and an iterative table that accumulates every way to reach each position. This dive shows the backtracking form and points at the table form in the follow-ups.

Greedy longest-prefix
At each position take the longest vocab match and continue. One string of work, no memory of alternatives. On memprod it grabs memp, hits the dead tail rod, and cannot rewind, so it returns nothing. It also never sees cpu + host + prod once it has committed to cpuhost.
Backtracking
Try every vocab prefix at each position. When a branch dead-ends the call stack rewinds to the last choice point and tries the next prefix, and every branch that reaches the end of the string is one recorded segmentation. It finds all of them, and it never falsely reports failure.

Break down the requirements

Step 1: Convert vocab to a set once

Membership is checked inside the inner loop, once per candidate prefix. A list makes each in an O(v) scan and turns the whole thing quadratic in the vocab size for no reason; set(vocab) makes it O(1) average.

Step 2: Recurse on the remaining suffix

Carry a start index. From start, try each end position; if key[start:end] is a known segment, append it to the current path and recurse from end. The recursion frame IS your backtracking memory: it remembers exactly where to resume when a deeper branch fails. An iterative dp[i]-holds-all-ways table reaches the same answer by building solutions for every prefix bottom-up instead of top-down.

Step 3: Record a copy at the base case, then undo

When start reaches the end of the key, the path spells a full segmentation, so append a COPY of it. Then pop the last segment before trying the next prefix. Appending the path object itself (not a copy) is the classic bug: every stored result aliases the same list, which the pops later empty out.

The solution

Recursive enumeration with append-recurse-pop
def segment_key(key, vocab):
    words = set(vocab)
    results = []

    def build(start, path):
        if start == len(key):
            results.append(path[:])
            return
        for end in range(start + 1, len(key) + 1):
            piece = key[start:end]
            if piece in words:
                path.append(piece)
                build(end, path)
                path.pop()

    build(0, [])
    return results

Common follow-up questions