Ошибки
и объяснение решения

def longest_within(nums, limit):
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total > limit:
            total -= nums[l]
            l += 1
        best = max(best, r - l)
    return best

• Пустой список, лимит 5

  Цикл не выполняется, ответ 0 верный.

• [9], лимит 3

  Окно сжимается до пустого, r − l равно −1, max(0, −1) равно 0 — верный ответ: отрезка нет.

• [2], лимит 5

  Верно. Окно [2] допустимо, его длина 1, а r − l равно 0. Функция возвращает 0 вместо 1: окно с l по r включительно содержит r − l + 1 элементов.

def shortest_window(nums, s):
    best = 0
    total = 0
    l = 0
    for r in range(len(nums)):
        total += nums[r]
        while total >= s and l < r:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            total -= nums[l]
            l += 1
    return best

• [1, 2, 3], порог 6

  Подходит только весь список длины 3, и он записывается при l = 0, r = 2. Ответ 3 верный.

• [4, 40, 1], порог 30

  Верно. Окно из одного элемента [40] подходит, но при l = r условие цикла ложно, и длина 1 не записывается. Функция возвращает 2.

• [1, 1, 1, 1], порог 5

  Сумма не достигает порога, цикл не выполняется, ответ 0 верный.

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

• 'abc'

  Повторов нет, сжимать не нужно, ответ 3 верный.

• 'aba'

  Верно. Счётчик пришедшего символа каждый раз записывается равным 1, и условие цикла никогда не выполняется. Функция возвращает длину всей строки, 3 вместо 2.

• Пустая строка

  Цикл не выполняется, ответ 0 верный.

def shortest_window(nums, s):
    best = 0
    l = 0
    for r in range(len(nums)):
        while sum(nums[l:r + 1]) >= s:
            length = r - l + 1
            if best == 0 or length < best:
                best = length
            l += 1
    return best

• Функция падает на пустом списке

  На пустом списке цикл не выполняется, функция возвращает 0 — это верный ответ.

• Отрезок с суммой точно на пороге пропускается

  Условие >= s включает равенство. На 5000 случайных входах ответы совпали с верной версией.

• Время O(n²): сумма окна считается заново

  Верно. Состояния окна нет: каждая проверка условия складывает срез длиной с окно. На 20 000 чисел от 1 до 9 с порогом 25 000 эта версия работала 488 мс, верная — 1,2 мс.

Вопрос 1Тест shortest_window([2, 3, 1, 2, 4, 3], 7) вернул 1, хотя ни один элемент списка не достигает 7. Какое место проверить первым?

• Знак сравнения в условии цикла while total >= s

  Строгий знак пропускает окна с суммой точно 7 и даёт ответ длиннее верного. Ответ короче верного он не даёт.

• Место записи длины относительно цикла while

  Верно. Длина 1 записана для окна, которое не подходит. Так бывает, когда запись стоит после цикла: там сумма окна уже меньше порога.

• Начальное значение переменной best перед циклом

  Неверное начальное значение даёт 0 или длину списка. Длину 1 на этом входе оно не создаёт.

Вопрос 2Интервьюер спрашивает: «Почему в задаче о подстроке нельзя написать if вместо while?» Какой ответ полный?

• «Так принято писать все решения на скользящее окно»

  Ответ не называет причину. Интервьюер ждёт вход, на котором if ошибается, и объяснение.

• «С if время работы функции станет O(n²)»

  С if время остаётся O(n). Ошибка в ответе: повтор может остаться в окне.

• «Повтор может стоять не на краю окна, как в 'abba'»

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