Where They Part

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

Domain
Python
Difficulty
hard
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. The 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', whose shared start is only 'a'.
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 '?' in the extremes hid the real constraint. Only reading every pattern per 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 no character yet, otherwise compare 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 (i >= len(p)) 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 i in range(len(patterns[0])):
        concrete = None
        for p in patterns:
            if i >= len(p):
                return ''.join(resolved)
            ch = p[i]
            if ch == '?':
                continue
            if concrete is None:
                concrete = ch
            elif ch != concrete:
                return ''.join(resolved)
        resolved.append(concrete if concrete is not None else '?')
    return ''.join(resolved)

Common follow-up questions