Границы: пустая строка,
повторы, ответа нет

Категория

Проверка решения

Уровень

Начальный

Опирается на

Главы 10.4 и 10.5: обе задачи КТП; глава 9.6: тесты границ и исключения

Зачем это знать

Контроль занятия по КТП и вопросы интервьюера о крайних случаях

§1Разбор двух функций по строкам

В главах 10.4 и 10.5 функции собраны из строк и пройдены по шагам на обычных входах. Здесь каждая строка разобрана с другой стороны: на каком граничном входе она проявляется и что получится, если записать её иначе. Граничный вход — это вход на краю допустимого: пустой список, один элемент, порог, которого не достигает сумма, строка из одинаковых символов. На таких входах цикл выполняется ноль раз или один раз, и ошибки, незаметные на обычном примере, дают неверный ответ.

def shortest_window(nums, s):
    if s < 1:
        raise ValueError("s должно быть не меньше 1")
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= s:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            total -= nums[l]
            l += 1
    return best

У второй функции проверки входа нет: у единственного параметра неверных значений не бывает. Граничные входы у неё другие — пустая строка, повторы и вопросы о том, что считать одинаковыми символами.

def longest_unique(text):
    count = {}
    best = 0
    l = 0
    for r in range(len(text)):
        ch = text[r]
        count[ch] = count.get(ch, 0) + 1
        while count[ch] > 1:
            count[text[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best

§2Запуск изменённых версий

Четыре изменения из таблиц, которые в главах 10.3–10.5 ещё не запускались. На каждой вкладке сначала прогон версии с изменённой строкой, под ним — верная версия на том же входе. Вход подобран так, чтобы изменение проявилось.

Если интервьюер ответил бы, что регистр не различается, верной стала бы версия с приведением регистра, но приводить нужно всю строку до цикла: text = text.lower(). Тогда и расширение, и сжатие работают с одними и теми же символами, и KeyError не возникает.

§3Граничные входы всех функций

В модуле шесть функций. Значения в таблицах получены запуском эталонных решений. Первая таблица — функции с порогом или лимитом.

У shortest_window и longest_within ноль в списке ведёт себя по-разному. Для порога сумма из нулей никогда не достигает 1, поэтому ответ 0. Для лимита 0 нули допустимы, и самый длинный отрезок — весь список. Вторая таблица — функции главы 10.5 и задачи с LeetCode.

longest_ones из главы 10.4 — решение LeetCode 1004, где условие гарантирует 0 ≤ k ≤ len(nums) и непустой список, поэтому проверки входа в ней нет. На пустом списке она возвращает 0, на [0, 0] с k = 0 — тоже 0. На k = −1 она заканчивается исключением IndexError: условие zeros > −1 истинно и для пустого окна, как условие total >= 0 в первой вкладке §2.

§4Ответ «отрезка нет» и ошибка вызова

В задаче о минимальном отрезке два разных случая, когда ответа в обычном смысле нет. Первый — подходящего отрезка в списке нет, например сумма всех чисел меньше порога. Второй — неверный вызов: порог 0 или отрицательный. Интервьюер в главе 10.2 дал на них разные ответы: в первом случае вернуть 0, во втором — исключение ValueError.

Различие следует из того, где источник проблемы: в данных или в вызове функции. Список без подходящего отрезка — обычные данные: за час с маленькими продажами ответ «не набралось» правильный, и программа продолжает работу. Порог 0 — ошибка в коде, который вызвал функцию: задача с таким порогом не имеет смысла, и продолжать работу с ответом на неё нельзя. Об ошибках вызова, как в главе 9.6, сообщают исключением.

Для longest_unique вопроса «что вернуть, если ответа нет» не возникает: в любой непустой строке есть подстрока из одного символа без повторов. Остаётся только пустая строка, для неё ответ 0 — длина пустой подстроки.

§5Тесты границ

Тесты ниже — файл tests.py стартового набора занятия 10 в его нынешнем виде: проверки границ обеих функций. Остальные тесты будут добавлены к нему в главе 10.10, эти при этом не изменятся. Каждый тест параметризован: один набор строк parametrize даёт несколько проверок, а параметр ids задаёт им короткие имена, которые видны в выводе pytest.

import pytest

from solution import longest_unique, shortest_window


@pytest.mark.parametrize("s", [0, -1], ids=["s_zero", "s_negative"])
def test_bad_s_raises(s):
    with pytest.raises(ValueError):
        shortest_window([1, 2], s)


@pytest.mark.parametrize("nums, s, want", [
    ([], 3, 0),
    ([1, 1, 1, 1], 5, 0),
    ([7], 7, 1),
    ([7], 8, 0),
    ([1, 2, 3], 6, 3),
], ids=["empty", "no_window", "one_exact", "one_short", "whole_list"])
def test_shortest_edges(nums, s, want):
    assert shortest_window(nums, s) == want


@pytest.mark.parametrize("text, want", [
    ("", 0),
    ("z", 1),
    ("bbbbb", 1),
    ("pwwkew", 3),
    ("abba", 2),
    ("aA", 2),
    ("a b a", 3),
], ids=["empty", "one_char", "all_same", "adjacent_repeat", "repeat_left_window", "case", "space"])
def test_unique_edges(text, want):
    assert longest_unique(text) == want

Контроль КТП назван в тестах прямо. Пустая строка — test_unique_edges[empty]. Дубликаты — четыре случая: все символы одинаковые, повтор рядом, повтор символа, который уже вышел из окна, и повтор пробела. Вывод на эталонном решении:

collected 14 items

tests.py::test_bad_s_raises[s_zero] PASSED                               [  7%]
tests.py::test_bad_s_raises[s_negative] PASSED                           [ 14%]
tests.py::test_shortest_edges[empty] PASSED                              [ 21%]
tests.py::test_shortest_edges[no_window] PASSED                          [ 28%]
tests.py::test_shortest_edges[one_exact] PASSED                          [ 35%]
tests.py::test_shortest_edges[one_short] PASSED                          [ 42%]
tests.py::test_shortest_edges[whole_list] PASSED                         [ 50%]
tests.py::test_unique_edges[empty] PASSED                                [ 57%]
tests.py::test_unique_edges[one_char] PASSED                             [ 64%]
tests.py::test_unique_edges[all_same] PASSED                             [ 71%]
tests.py::test_unique_edges[adjacent_repeat] PASSED                      [ 78%]
tests.py::test_unique_edges[repeat_left_window] PASSED                   [ 85%]
tests.py::test_unique_edges[case] PASSED                                 [ 92%]
tests.py::test_unique_edges[space] PASSED                                [100%]

============================== 14 passed in 0.01s ==============================

Вывод, если в shortest_window убрать проверку порога и начать с best = len(nums), а в longest_unique приводить символ к нижнему регистру, — три изменения из §2:

FAILED tests.py::test_bad_s_raises[s_zero] - IndexError: list index out of range
FAILED tests.py::test_bad_s_raises[s_negative] - IndexError: list index out o...
FAILED tests.py::test_shortest_edges[no_window] - assert 4 == 0
FAILED tests.py::test_shortest_edges[one_short] - assert 1 == 0
FAILED tests.py::test_unique_edges[case] - AssertionError: assert 1 == 2
5 failed, 9 passed in 0.02s

Тест whole_list с изменённой версией проходит: на нём best = len(nums) совпадает с верным ответом. Ошибку находят только тесты, где отрезка нет. Тест empty для shortest_window тоже проходит: на пустом списке len(nums) равно 0. Поэтому в наборе есть оба случая «отрезка нет» — пустой список и короткая сумма.

§6Исправьте функции

В окне ниже обе функции занятия, в каждой по две ошибки из §2. В shortest_window нет проверки порога, и ответ начинается с длины списка. В longest_unique ответ начинается с 1, и символ приводится к нижнему регистру. Исправьте их так, чтобы прошли все девять тестов. Сначала запустите тесты и посмотрите, какие падают и с каким сообщением.

§7Как объяснить условие while и состояние окна

Первая часть контроля КТП — «кандидат объясняет условие while и состояние окна». На собеседовании это звучит как вопросы «что хранится в этой переменной между итерациями?» и «почему здесь while с таким условием?». Ответ строится из трёх частей, они одинаковы для всех задач модуля.

1. Состояние окна. Назвать переменную и то, что она хранит для окна с l по r. Например: «total — сумма элементов окна», «count — для каждого символа окна, сколько раз он в нём встречается». Назвать, как она меняется при сдвиге каждой границы.
2. Условие цикла. Назвать условие допустимости и объяснить, почему цикл проверяет его или его отрицание. Для короткого отрезка: «сжимаем, пока окно подходит, — total >= s». Для длинного: «сжимаем, пока окно недопустимо, — count[ch] > 1». Назвать, почему здесь нужен цикл: одного сжатия может не хватить, и if оставит повтор в окне.
3. Инвариант после цикла. Сказать, что верно, когда цикл закончился: «после цикла в окне нет повторов, и это самая длинная подстрока без повторов с концом в r». Из инварианта следуют место записи ответа и время O(n).

while total >= s:
    length = r - l + 1
    ...
    total -= nums[l]
    l += 1

def test_example():
    assert longest_unique("abcabcbb") == 3

def test_all_different():
    assert longest_unique("abcdef") == 6

def test_case():
    assert longest_unique("aA") == 2