# The Sequel Spotter > Spot the sequels hiding in the catalog. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 · Asked in: Meta ## Problem We're deduping a media catalog where each sequel was named by extending an existing title, so a sequel's name begins with a shorter title already in the catalog. Return the titles that extend another title from the list, preserving the original order. ## Example Input: ``` titles = ["GOT","Troy","Batman","Batman Returns","GOT Part 2"] ``` Output: ``` ["Batman Returns","GOT Part 2"] ``` ## Worked solution and explanation ### The self-match trap Underneath the movie-catalog framing this is a proper-prefix scan with a self-exclusion trap. Every string `startswith()` itself, so the moment you test a title against the whole list you match it to itself and flag it as its own sequel. Anyone can write the two loops; what separates candidates is remembering to exclude a title from prefixing itself. Miss that and every single title comes back as a sequel: 100 percent false positives. --- ### Break down the requirements #### Step 1: Every entry is a candidate prefix There is no separate list of 'originals'. Any title in the input can play the shorter original, so for each title you test it against all the others in the same list. #### Step 2: Make the prefix proper, not just any prefix `startswith()` is necessary but not sufficient: 'Batman'.startswith('Batman') is True, so you must exclude a title from matching itself. Two guards do this identically here: `len(other) < len(title)` and `other != title`. When a prefix actually matches, equal length forces the two strings to be equal, so both guards accept exactly the same pairs. Prefer the length form: it names the real requirement, a shorter original, and it drops duplicate titles with no special case. #### Step 3: Keep the survivors in input order Collect the titles that have at least one qualifying shorter prefix, walking front to back so the output order matches the input order. --- ### The solution **Proper-prefix scan with short-circuit** ```python def find_sequels(titles: list[str]) -> list[str]: return [ title for title in titles if any(len(other) < len(title) and title.startswith(other) for other in titles) ] ``` *any() stops at the first shorter title that prefixes this one; the length guard is what excludes the title from prefixing itself.* > **Time and Space Complexity** > > **Time:** O(n^2 * m): for each of n titles you scan up to n others, and each `startswith()` costs up to m characters. `any()` short-circuits on the first match, so the constant stays small in practice. Space: O(n) for the result list. For a huge catalog you would build a trie for O(m) lookups, but at interview scale the double scan is the right call. > **Why the two guards are the same predicate** > > The length guard and a plain `other != title` are not two competing choices here, they are the same predicate. If `title.startswith(other)` holds, `other` can be at most as long as `title`, and equal length forces the two strings to be identical. So `len(other) < len(title)` and `other != title` accept exactly the same pairs. Reach for whichever you like, but the length form reads as 'a shorter original', which is the requirement in plain words. > **Interviewers Watch For** > > The tell is how a candidate justifies the self-exclusion, not which form they type. A strong one recognizes that for a matching prefix, excluding equal length is the same as excluding the title itself, so duplicate titles fall out for free with no special case. > **Common Pitfall** > > Forgetting the self-exclusion entirely. Because every string `startswith()` itself, the self-comparison matches and every title comes back as a sequel: the 100-percent-false-positive result. The second-most-common miss is reaching for substring containment (`in`) instead of `startswith()`, which would wrongly flag 'The Dark Knight' off 'Dark'. --- ## Common follow-up questions - How would you optimize this for a very large title list? _(Tests whether you would use a trie data structure for O(m) prefix lookups.)_ - What if the sequel relationship needed to be case-insensitive? _(Tests adding `.lower()` normalization before comparison.)_ - What if you needed to return the original title each sequel extends? _(Tests returning pairs instead of a flat list, changing the data structure.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_sequel_spotter) - [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.