Where They Part

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

Problem

You are given patterns, a batch of object-storage key globs where ? matches any single character. Return the longest leading run of positions where the patterns can all agree, resolved to its characters: a position holds when every non-? character there is identical, and the run ends the instant two concrete characters clash or any pattern runs out. Return an empty string when patterns is empty.

They all start the same way. How far?

Example 1

Input:

patterns = ["l?gs/a?","l?gs/ap","l?gs/a?"]

Output:

"l?gs/ap"

Example 2

Input:

patterns = ["c?g","cfg-prod","cfg-dev"]

Output:

"cfg"

Worked solution and explanation

What this really is

Strip the costume: this is a column-by-column agreement scan across every pattern at once, and the wildcards are the whole game. At each position you are collecting the single concrete character that column is allowed to have, while every '?' quietly abstains. The run ends at the first column where two real characters disagree or any pattern runs out. Candidates who fall here reach for the classic longest-common-prefix reflexes: sort and compare the lexicographic min and max, or call os.path.commonprefix. Both lean on transitivity, and '?' destroys transitivity. Pattern A can agree with B, and B with C, through wildcards while A and C hold different concrete characters, so any answer built from only two patterns is wrong.

Why the shortcuts lie

The two-string shortcut
For plain prefixes, min(patterns) and max(patterns) bound the answer, so comparing just those two is enough. On ['a?c', 'abc', 'a?d'] the extremes are 'a?c' and 'abc'. Read literally they share only 'a'; resolved through the wildcard they give 'abc'. Both are wrong.
Why it breaks here
The true resolved run is 'ab': the middle pattern 'abc' supplies the concrete 'b' at column 1, and 'a?d' clashes with 'abc' at column 2. The extremes never see that clash. Only reading every pattern at every column recovers it.

Walk the columns

Step 1: Guard the empty batch

No patterns means no column has a constraint to share, so return the empty string immediately, before you index anything.

Step 2: Collect the one concrete character per column

Anchor the column count on the first pattern's length (nothing can be shared past where it ends) and, at each column, walk every pattern. Skip the '?' entries. For a concrete character, record it if the column has none yet; otherwise compare it against the one already recorded.

Step 3: Stop at the first clash or exhausted pattern

Two stop conditions live in the inner loop. A pattern with no character at this column (pos >= len(pattern)) caps the run, and a concrete character that differs from the recorded one is a real clash. On either, return what you have resolved so far. Otherwise commit the column: the shared concrete character, or '?' when every pattern abstained.

The solution

Wildcard-aware column scan across all patterns
def longest_prefix(patterns):
    if not patterns:
        return ''
    resolved = []
    for pos in range(len(patterns[0])):
        concrete = None
        for pattern in patterns:
            if pos >= len(pattern):
                return ''.join(resolved)
            char = pattern[pos]
            if char == '?':
                continue
            if concrete is None:
                concrete = char
            elif char != concrete:
                return ''.join(resolved)
        resolved.append(concrete if concrete is not None else '?')
    return ''.join(resolved)

Common follow-up questions