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

Under the data-export wording, this asks for the longest contiguous stretch of an ordered sequence with no repeat, plus one twist at the start. The cells are text, and the same id can carry extra leading zeros, so '007' and '7' are one id: parse each cell to an integer before comparing anything. Almost everyone produces a number. What separates candidates is turning down two shortcuts and avoiding one subtle slip. Sorting fails because the answer is defined on arrival order. Counting the different ids is more tempting because it sometimes matches, but it measures total variety, not the longest unbroken run. The slip comes when you remember where each id was last seen and jump the start of the stretch past it on a repeat: if that earlier sighting is already behind the start, jumping to it drags the start backward and lets a duplicate back in. On '3', '8', '8', '3' that slip reports 3 instead of 2.

Why the obvious moves fail

Distinct count
Parse every cell, count how many different ids exist, and return that count. On 4, 1, 2, 1, 3, 5 that gives 5, but the longest run without a repeat is 2, 1, 3, 5, length 4. The count forgot where each id sat. Sorting first fails the same way: it throws away the order the answer is measured along.
Forward-only stretch
Walk left to right, remembering each id's last position. A repeat inside the stretch moves the start just past its earlier copy; a sighting already behind the start is ignored. On the same input it reports 4, in one pass, and it never loses arrival order.

Break down the requirements

Step 1: Read each cell by its numeric value

'007' and '7' are equal only once read as numbers. Convert each cell with int(cell) up front. Skip this and the two forms look like different ids, which inflates the answer, as the '10' and '010' example shows.

Step 2: Remember where each id was last seen

Map each id to its latest position in last_seen. A dict lookup is O(1), which is what keeps the pass linear without re-scanning the stretch.

Step 3: Move the start only forward

On a repeat, set window_start to the earlier position plus one, but only when that position is at or after window_start. This is the line people get wrong: a sighting the start has already passed is not a repeat inside the stretch, and acting on it pulls the start backward.

Step 4: Track the widest stretch

After recording the position, the stretch spans position - window_start + 1. Keep the maximum across the pass. Starting it at 0 means an empty column returns 0 with no extra code.

The solution

Forward-only stretch over last-seen positions
def longest_distinct_window(id_cells: list[str]) -> int:
    ids = [int(cell) for cell in id_cells]
    last_seen: dict[int, int] = {}
    window_start = 0
    longest = 0
    for position, current in enumerate(ids):
        previous = last_seen.get(current)
        # A sighting behind the start is outside the stretch; ignore it.
        if previous is not None and previous >= window_start:
            window_start = previous + 1
        last_seen[current] = position
        window_length = position - window_start + 1
        if window_length > longest:
            longest = window_length
    return longest

Parse once so leading-zero twins match; the previous >= window_start guard keeps the start moving forward only, so the stretch always holds unique ids.

Common follow-up questions