Скользящее окно на собеседовании: самая длинная подстрока без повторов

Это алгоритмическая секция собеседования Data Scientist в VK. Грейд не указан. Кандидату дали две задачи: построить матрицу из уникальных значений и найти самую длинную подстроку без повторяющихся символов.

Как создать матрицу 5 × 5 из уникальных случайных чисел

Короткий ответ: взять последовательность без повторов, перемешать её и изменить форму массива.

import numpy as np

def unique_matrix(size=5):
    # Создаём ровно столько уникальных чисел, сколько ячеек в матрице.
    values = np.arange(size * size)

    # Перемешиваем числа без добавления повторов.
    np.random.shuffle(values)

    # Превращаем одномерный массив в квадратную матрицу.
    return values.reshape(size, size)

Если диапазон должен быть шире, можно использовать np.random.choice с replace=False. Важное ограничение: в диапазоне должно быть не меньше уникальных значений, чем ячеек.

На собеседовании сначала нужно уточнить, что означает «случайные»: целые или вещественные числа, задан ли диапазон и требуется ли воспроизводимость через seed.

Почему полный перебор подстрок не подходит

Короткий ответ: число подстрок квадратичное, а проверка каждой может сделать решение ещё дороже.

Для строки длины n существует порядка n² непрерывных фрагментов. Если каждый заново проверять на повторы, легко получить O(n³). Даже хранение множества для каждой стартовой позиции оставляет O(n²).

Ограничение на большой размер строки подсказывает, что нужен один проход. Мы должны переиспользовать сведения о текущем фрагменте, а не строить все варианты заново.

Как работает скользящее окно

Короткий ответ: правая граница добавляет символы, а левая перескакивает за повтор внутри текущего окна.

Типичная ошибка. Передвигать левую границу к последнему вхождению символа, даже если это вхождение уже осталось за текущим окном. Тогда граница может пойти назад, а длина получится неверной.

Как лучше. Обновляйте левую границу только вперёд: left = max(left, last_position[char] + 1). На интервью отдельно проговорите этот инвариант и проверьте строку с повтором за пределами окна.

def longest_unique_substring(text):
    # Последняя позиция каждого уже встреченного символа.
    last_position = {}

    # Левая граница текущего фрагмента без повторов.
    left = 0
    best = 0

    for right, char in enumerate(text):
        # Двигаем границу только если повтор находится внутри окна.
        if char in last_position and last_position[char] >= left:
            left = last_position[char] + 1

        # Запоминаем новую последнюю позицию символа.
        last_position[char] = right

        # Длина окна включает обе границы.
        best = max(best, right - left + 1)

    return best

Например, для abba при втором b левая граница перейдёт на позицию после первого b. Когда появится последний a, нельзя возвращать границу назад: прошлый a уже за пределами окна. Поэтому используется проверка last_position[char] >= left.

Почему сложность равна O(n)

Короткий ответ: каждый символ обрабатывается один раз, а левая граница никогда не движется назад.

Словарь даёт доступ к последней позиции в среднем за O(1). Основной цикл проходит по строке один раз, поэтому время — O(n). В словаре может оказаться до O(k) символов, где k — размер алфавита или число разных символов во входе.

На интервью полезно отдельно назвать инвариант: подстрока от left до right после обработки не содержит повторов. Это объясняет корректность лучше, чем пересказ строк кода.

Получил ли кандидат оффер

Короткий ответ: алгоритмическую секцию кандидат прошёл.

Обе задачи были решены. Во второй понадобилась подсказка и исправление небольшой ошибки, но кандидат понял идею, довёл код до корректного состояния и объяснил линейную сложность. Реальное итоговое решение зависит и от других этапов, однако эта часть прошла положительно.

Мы тренируем такой разбор в тренажёре собеседований ЮНИКОД: условие, уточнения, идея, код, сложность и граничные случаи.

Источники

• NumPy: random.shuffle
• NumPy: random.choice
• Python: словари