# The Sequel Spotter

> Spot the sequels hiding in the catalog.

Canonical URL: <https://datadriven.io/problems/the_sequel_spotter>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given a list of title strings, return the list of titles that begin with another shorter title from the same list (plus at least one more character). Preserve input order.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **string prefix matching** and **nested iteration with filtering**. It checks whether a candidate can efficiently compare strings using `startswith` while avoiding self-matches and understanding what "shorter" means in context.

---

### Break down the requirements

#### Step 1: Identify candidate prefixes from the title list

Every title in the list is a potential prefix for another title. A sequel starts with a shorter title from the same list.

#### Step 2: For each title, check if any other shorter title is a prefix

Use `startswith` to test prefix relationships. The prefix must be strictly shorter than the title being checked.

#### Step 3: Collect and return matching titles

Build a result list of titles that have at least one matching prefix in the input list.

---

### The solution

**Nested prefix scan with early break**

```python
def find_sequels(titles: list) -> list:
    sequels = []
    for title in titles:
        for other in titles:
            if other != title and len(other) < len(title) and title.startswith(other):
                sequels.append(title)
                break
    return sequels
```

> **Time and Space Complexity**
>
> **Time:** O(n^2 * m) in the worst case where n is the number of titles and m is the average title length for the `startswith` check. The `break` avoids redundant checks once a match is found.
> 
> **Space:** O(n) for the result list.

> **Interviewers Watch For**
>
> Do you correctly handle the case where two titles are identical? Identical titles are not sequels of each other since the prefix must be strictly shorter.

> **Common Pitfall**
>
> Forgetting the `len(other) < len(title)` guard. Without it, a title would match itself as a prefix, producing false positives.

---

## 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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.