# Where They Part > They all start the same way. How far? Canonical URL: 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. ## 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. > **Trick to solving** > > The constraint at a column belongs to whichever pattern happens to spell a real character there, and that can be any pattern in the batch. So you cannot shortcut with the extremes: at every column, walk all patterns, keep the first concrete character you see, and bail the instant a different concrete character shows up. A column of all '?' resolves to '?' and keeps going. --- ### 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** ```python 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) ``` > **Time and space complexity** > > Time: O(S) where S is the total characters across all patterns, since each character is inspected at most once and we bail on the first clash. Space: O(1) beyond the resolved output, no sorting and no auxiliary structures. > **Interviewers watch for** > > The two things a strong candidate does without prompting: put the exhausted-pattern check (i >= len(p)) BEFORE reading p[i] so a shorter pattern never gets indexed out of bounds, and resolve an all-wildcard column to '?' instead of dropping it or stopping. Getting both right is the tell that they modeled '?' as an abstaining constraint rather than a literal. > **Common pitfall** > > Calling os.path.commonprefix(patterns) or comparing only min and max. Both treat '?' as an ordinary character and both trust transitivity, so they stop early at a wildcard or miss a constraint a middle pattern carries. They pass a naive test set and then fail the moment a real batch mixes wildcards and concrete characters. --- ## Common follow-up questions - What if a pattern could also contain '*', matching zero or more characters? _(Tests whether the candidate recognizes that '*' turns a linear column scan into a matching problem with backtracking or dynamic programming.)_ - How would you adapt this to the longest common suffix? _(Tests reversing each pattern, running the same wildcard-aware scan, then reversing the result, and whether length caps still apply from the other end.)_ - What changes if you only need the longest run shared by at least k of the patterns? _(Tests moving from all-must-agree to a threshold, which breaks the single-concrete-per-column invariant and pushes toward per-column character counts or a trie.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/where_they_part) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.