The Unbroken Line

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
L5
Asked in
EPAM Systems

Problem

You're scanning one column of id values pulled from a data export, where each cell is raw text, the ids arrive in the order they were written, and values repeat. The export wrote ids inconsistently, so the same id can show up with extra leading zeros ('7' and '007' are one id), and you read each cell by its numeric value. Return the length of the longest unbroken stretch of the column in which no id appears more than once.

The longest stretch that never repeats itself.

Example 1

Input:

id_cells = ["4","1","2","1","3","5"]

Output:

4

Example 2

Input:

id_cells = ["10","20","010","30","40","50","20"]

Output:

5

Worked solution and explanation

What this problem really is

Peel off the data-export wording and this is the longest contiguous no-repeat stretch on an ordered sequence, with one twist up front: the cells are text and the same id can wear extra leading zeros, so '007' and '7' are one id and you parse each cell to its integer value before comparing anything. Almost everyone then produces a number; what separates candidates is refusing two shortcuts. Sorting the ids feels natural, but the answer is defined on arrival order, so a sort returns a wrong length. Counting how many different ids exist is more seductive because it sometimes matches, yet it reports total variety, not the longest unbroken stretch, and overcounts the moment a long unique run is split by an earlier repeat. The real skill: slide one window across the data, keep a live set of the ids inside it, and evict from the left until the incoming id is unique again. Get the eviction boundary wrong and you either report a stretch that still holds a duplicate or collapse back to O(n^2).

Why the obvious moves fail

Distinct count (one set)
Parse, then drop every id into a set and return its size. On [4, 1, 2, 1, 3, 5] that is five different values, so it answers 5. But the longest unbroken run without a repeat is [2, 1, 3, 5], length 4. The set forgot where the ids sat, so it counted variety instead of a contiguous stretch. Sorting first fails the same way: it discards the order the answer is defined on.
Sliding window (set plus left edge)
Move left to right adding each id to a window set. When an id is already inside, evict from the left until it is gone, then add it, tracking the largest window size. On the same input it correctly reports 4. Each id enters and leaves once, so it is O(n) and it never loses the arrival order.

Break down the requirements

Step 1: Read each cell by its numeric value

The export wrote the same id in different textual forms, so '007' and '7' are equal only once read as numbers. Convert each cell with int() up front; skip this and the two forms look like distinct ids and inflate the answer.

Step 2: Add each id to a window set

Move a right pointer across the parsed ids, adding each to a set that represents the current stretch. Membership tests are O(1), which is what keeps the pass linear.

Step 3: Evict from the left on a collision

When the incoming id is already in the window, the stretch now has a repeat. Discard ids[left] and advance left, one id at a time, until the duplicate is gone. This is the line people get wrong: move left forward only, never reset it to the start, or an already-evicted id sneaks back in.

Step 4: Track the widest window

After each insert, the current stretch spans right minus left plus one. Keep the maximum across the whole pass; that maximum is the answer, and starting it at 0 means an empty column returns 0 for free.

The solution

Sliding window over a membership set
def longest_distinct_window(id_cells: list[str]) -> int:
    ids = [int(cell) for cell in id_cells]
    seen: set[int] = set()
    left = 0
    longest = 0
    for right, current in enumerate(ids):
        while current in seen:
            seen.discard(ids[left])
            left += 1
        seen.add(current)
        window = right - left + 1
        if window > longest:
            longest = window
    return longest

Parse to int once so leading-zero twins match, then the inner while loop advances left only forward, so the window always holds a distinct set of ids.

Common follow-up questions