Тренажёр рассуждений
Упражнения этой страницы разбирают, как по условию и ограничениям увидеть, где решение может ошибиться, до того как написан код. Ответы в таблицах получены запуском на Python 3.
Порядок рассуждения
Упражнения ниже разбирают отдельные шаги этого порядка. На собеседовании все шесть шагов укладываются в несколько минут.
- УсловиеПересказать задачу своими словами и назвать вход и выход.
- ВопросыНайти пробелы: пустой вход, дубликаты, размер, изменение данных.
- ПримерыОбычный случай, граница, особый вход — с ожидаемыми ответами.
- Идея и оценкаВыбрать алгоритм под ограничения и оценить время и память.
- ПрогонПройти код на коротком примере и назвать инвариант.
- Код и тестыНаписать код и запустить примеры из третьего шага.
Какой вопрос меняет решение
К любой задаче можно задать много вопросов, а время собеседования ограничено. Полезен вопрос, ответ на который меняет алгоритм, контракт или набор тестов. Если при любом ответе код останется прежним, такой вопрос можно не задавать. В каждой задаче ниже четыре вопроса: решите, какие из них полезны, и сверьтесь с пояснениями.
Найдите индекс числа x в массиве.
Выберите вопрос, который задали бы первым. Откройте остальные и сравните.
- Меняет алгоритм
Да — бинарный поиск за O(log n). Нет — линейный проход за O(n).
- Меняет контракт
−1, None или исключение. Пока ответа нет, для этого случая нельзя записать ожидаемый результат теста.
- Меняет контракт
Нужен первый, последний или любой индекс. В бинарном поиске «первый индекс» требует другой работы с границами.
- Решение не меняет
Такая проверка иногда даст ответ раньше, но в худшем случае поиск всё равно проходит весь массив. Ни оценка сложности, ни тесты от неё не меняются.
Удалите дубликаты из списка.
Выберите вопрос, который задали бы первым. Откройте остальные и сравните.
- Меняет алгоритм
Если нет, хватит
list(set(numbers)). Если да, нужен проход со множеством уже встреченных: set порядок не хранит. - Меняет контракт и память
Новый список занимает O(n) памяти. Изменение на месте экономит память, но вызывающий код теряет исходные данные.
- Меняет алгоритм
Списки нельзя положить в set:
set([[1], [2]])вызываетTypeError. Для них нужен другой способ сравнения. - Решение не меняет
Включение — другая запись того же прохода: и результат, и сложность те же. Выбирают по читаемости, у интервьюера это не уточняют.
Найдите самое частое слово в тексте.
Выберите вопрос, который задали бы первым. Откройте остальные и сравните.
- Меняет обработку
Если одно, текст приводят к нижнему регистру до подсчёта. В тестах появляется вход с разным регистром.
- Меняет контракт
Первое в тексте, первое по алфавиту или любое. Без договорённости тест с ничьей не проверить.
- Меняет обработку
Знаки препинания убирают до подсчёта, иначе одно слово попадёт в словарь дважды.
- Уточняет детали
Подсчёт через словарь не меняется. Язык влияет на то, какие символы считать частью слова.
Одна задача при разных ограничениях
Задача: вернуть True, если в списке есть повторяющиеся элементы. У неё четыре правильных решения, и какое выбрать, зависит от ответов на уточняющие вопросы. Переключайте ограничения и сравнивайте код, время и память.
def has_duplicate(numbers):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] == numbers[j]:
return True
return FalseПочему подходитОколо 500 тысяч сравнений в худшем случае. Код короткий, в нём мало мест для ошибки, и дополнительной памяти он не требует.
Где перестаёт подходитьПри n = 10⁵ сравнений уже около 5·10⁹. На Python это минуты.
def has_duplicate(numbers):
seen = set()
for value in numbers:
if value in seen:
return True
seen.add(value)
return FalseПочему подходитПроверка value in seen в среднем занимает O(1), поэтому весь проход линейный. Цена — память: set хранит до n чисел.
Где перестаёт подходитьЕсли память ограничена, миллион чисел в set может не поместиться в лимит.
def has_duplicate(numbers):
numbers.sort()
for i in range(len(numbers) - 1):
if numbers[i] == numbers[i + 1]:
return True
return FalseПочему подходитПосле сортировки одинаковые значения стоят рядом, и хватает проверки соседей. list.sort() сортирует на месте.
Где перестаёт подходитьЕсли исходный порядок нужен вызывающему коду, сортировка на месте его потеряет. Поэтому для этого решения важен ответ на вопрос, можно ли менять список.
def has_duplicate(numbers):
counts = [0] * 101
for value in numbers:
counts[value] += 1
if counts[value] == 2:
return True
return FalseПочему подходитЗначение само служит индексом в массиве из 101 ячейки. Размер массива не зависит от n, поэтому дополнительная память постоянная.
Где перестаёт подходитьДля значения 10⁹ такой массив не построить. Для отрицательного значения индексация пойдёт с конца списка, и ошибка не проявится.
Все четыре функции запускались на одних и тех же входах и дали одинаковые ответы:
| Вход | Ответ всех четырёх версий |
|---|---|
[] | False |
[7] | False |
[1, 2, 3] | False |
[3, 1, 3] | True |
[5, 5] | True |
[100, 1, 50, 1] | True |
Для прикидки считают, что простой цикл на Python выполняет порядка 10⁷ шагов в секунду. Точное время показывает только замер. Подставьте n в формулу сложности и сравните результат с этим числом.
| n | n² шагов | n log₂ n шагов | Что это значит |
|---|---|---|---|
| 1 000 | 10⁶ | ≈ 10⁴ | Подходит любое из решений |
| 100 000 | 10¹⁰ | ≈ 1,7·10⁶ | O(n²) слишком медленно, O(n log n) быстро |
| 1 000 000 | 10¹² | ≈ 2·10⁷ | Нужно O(n) или O(n log n) |
Поиск контрпримера
В каждой функции ниже одна ошибка. Прочитайте, что функция должна делать, и её код, затем выберите входы, на которых она, по-вашему, ошибётся. После каждого выбора появится строка с результатом запуска. Найдите хотя бы один такой вход и объясните, почему функция на нём ошибается.
Среднее значение
Функция возвращает среднее; для пустого списка — None.
def average(numbers):
return sum(numbers) / len(numbers)На каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
average([5]) | 5.0 | 5.0 | проходит |
average([]) | None | ZeroDivisionError | ломает |
average([1, 2]) | 1.5 | 1.5 | проходит |
average([-3, 3]) | 0.0 | 0.0 | проходит |
average([0]) | 0.0 | 0.0 | проходит |
Пустой список: len(numbers) равна нулю, и деление падает с ZeroDivisionError. Остальные входы проходят, потому что в них есть элементы.
Максимум
Функция возвращает наибольший элемент непустого списка.
def find_max(numbers):
best = 0
for value in numbers:
if value > best:
best = value
return bestНа каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
find_max([3, 1]) | 3 | 3 | проходит |
find_max([0]) | 0 | 0 | проходит |
find_max([-1]) | -1 | 0 | ломает |
find_max([2, 2]) | 2 | 2 | проходит |
find_max([-5, -2]) | -2 | 0 | ломает |
Старт best = 0 работает, пока в списке есть число не меньше нуля. Для списка из отрицательных функция возвращает 0, которого во входе нет.
Есть ли ноль
Функция возвращает True, если в списке есть 0.
def contains_zero(numbers):
for i in range(len(numbers) - 1):
if numbers[i] == 0:
return True
return FalseНа каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
contains_zero([0, 1]) | True | True | проходит |
contains_zero([2, 3]) | False | False | проходит |
contains_zero([0]) | True | False | ломает |
contains_zero([1, 0]) | True | False | ломает |
contains_zero([]) | False | False | проходит |
range(len(numbers) - 1) не доходит до последнего индекса. Ноль в последней ячейке и список из одного нуля не проверяются.
Палиндром
Функция проверяет, читается ли строка одинаково в обе стороны.
def is_palindrome(text):
for i in range(len(text) // 2):
if text[i] != text[len(text) - i]:
return False
return TrueНа каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
is_palindrome('') | True | True | проходит |
is_palindrome('a') | True | True | проходит |
is_palindrome('ab') | False | IndexError | ломает |
is_palindrome('aba') | True | IndexError | ломает |
is_palindrome('abba') | True | IndexError | ломает |
При i = 0 индекс len(text) - i равен длине строки, это позиция за концом. Пустая строка и один символ проходят только потому, что цикл не выполняется ни разу.
Количество положительных
Функция считает числа строго больше нуля.
def count_positive(numbers):
count = 0
for value in numbers:
if value >= 0:
count += 1
return countНа каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
count_positive([1]) | 1 | 1 | проходит |
count_positive([-1]) | 0 | 0 | проходит |
count_positive([]) | 0 | 0 | проходит |
count_positive([0]) | 0 | 1 | ломает |
count_positive([0, 5]) | 1 | 2 | ломает |
Условие >= считает ноль положительным. Любой вход без нулей эту ошибку не покажет.
Бинарный поиск
Функция возвращает индекс target в отсортированном списке или −1.
def binary_search(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
middle = (left + right) // 2
if numbers[middle] == target:
return middle
if numbers[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1На каких входах функция ошибётся? Выберите входы и проверьте.
| Вызов | Ждём | Код кандидата | Итог |
|---|---|---|---|
binary_search([1, 2, 3], 2) | 1 | 1 | проходит |
binary_search([], 3) | -1 | -1 | проходит |
binary_search([1], 1) | 0 | -1 | ломает |
binary_search([1, 3], 2) | -1 | -1 | проходит |
binary_search([1, 2], 2) | 1 | -1 | ломает |
Цикл while left < right останавливается, когда в диапазоне остался один элемент, и не проверяет его. Поэтому список из одного элемента уже контрпример.
Сверка с медленным решением
Быстрое решение обычно устроено сложнее простого, и ошибку в нём труднее заметить при чтении. Если есть медленное решение, в правильности которого вы уверены, оба решения можно запустить на тысяче маленьких случайных входов и сравнить ответы. Первый вход, на котором ответы разошлись, становится коротким контрпримером. Такую проверку называют стресс-тестом.
import random
def has_pair_slow(numbers, target):
for i in range(len(numbers)):
for j in range(i + 1, len(numbers)):
if numbers[i] + numbers[j] == target:
return True
return False
def has_pair_fast(numbers, target):
seen = set()
for value in numbers:
seen.add(value)
if target - value in seen:
return True
return False
random.seed(1)
for attempt in range(1, 1001):
numbers = [random.randint(-3, 3) for _ in range(random.randint(0, 4))]
target = random.randint(-6, 6)
slow = has_pair_slow(numbers, target)
fast = has_pair_fast(numbers, target)
if slow != fast:
print(f"попытка {attempt}: numbers={numbers} target={target}")
print(f"медленное: {slow}, быстрое: {fast}")
break
else:
print("расхождений нет")попытка 28: numbers=[1, 0, 2, -2] target=-4
медленное: False, быстрое: Truerandom.seed(1) делает случайные входы одинаковыми при каждом запуске, поэтому расхождение воспроизводится. Входы маленькие: до четырёх чисел от −3 до 3. На таком входе каждый шаг можно проследить вручную.
Почему быстрая версия ответила иначе
Пройдите has_pair_fast([1, 0, 2, -2], -4) по шагам. Какой элемент оказался в паре сам с собой?
Открыть разбор
Функция добавляет value в seen до проверки. Когда target - value == value, проверка находит в множестве только что добавленный элемент, и один индекс используется дважды. Если сначала проверить, а потом добавить, в seen будут только предыдущие элементы.
def has_pair_fast(numbers, target):
seen = set()
for value in numbers:
if target - value in seen:
return True
seen.add(value)
return Falseрасхождений нетТрудные моменты на собеседовании
В этих ситуациях код не нужен. Прочитайте описание, запишите, как бы вы поступили, и затем откройте разбор.
«Решите сами»
Вы спросили, что возвращать для пустого списка. Интервьюер отвечает: «Как считаете правильным».
Открыть разбор
Выберите вариант и назовите его: «Верну None и добавлю это в docstring». Коротко объясните выбор и скажите, что изменится при другом решении: «Если нужно исключение, поменяется одна строка и один тест». Так интервьюер видит, что вы заметили неполное условие и можете сами выбрать разумное поведение.
Тесты прошли, но ошибка есть
Все ваши примеры дали верные ответы. Интервьюер говорит: «В коде есть ошибка».
Открыть разбор
Перечитайте контракт и сравните с ним тесты: какие классы входов не проверены? Обычно это пустой вход, один элемент, отрицательные числа, дубликаты, ответ на первой или последней позиции. Возьмите самый короткий непроверенный вход и пройдите код вручную, записывая переменные.
Решение есть, но медленное
Вы написали перебор пар за O(n²). Интервьюер напоминает, что n до 10⁵.
Открыть разбор
Посчитайте: 10¹⁰ шагов не уложатся в лимит. Назовите, какая работа повторяется: для каждого элемента заново просматривается весь список. Повторный просмотр убирают с помощью set или сортировки. Перебор при этом пригодится как медленное решение для стресс-теста.
Контрпример от интервьюера
Интервьюер даёт вход, на котором ваш код ошибается, и молчит.
Открыть разбор
Прогоните код на этом входе по строкам, называя значения переменных. Найдите первое место, где состояние перестало совпадать с инвариантом. Исправьте причину и снова проверьте все прежние тесты: исправление одного случая может сломать другой.
Тест: выберите главное
Для каждой задачи дан длинный список вопросов. Часть из них меняет алгоритм или контракт, часть полезна для тестов, остальные на решение не влияют. Выберите пять самых важных и нажмите «Проверить».
Интервьюер: «Найдите в списке два числа с суммой target». Выберите пять вопросов, от которых зависит решение.
Для
[3]и target = 6 ответ True или False. Меняет перебор и тесты.Обе структуры проверяют принадлежность за O(1) в среднем.
dictнужен, только если возвращают индексы, а это отдельный вопрос из списка.Проверяются те же пары, поэтому ответ «есть пара или нет» от направления не зависит.
Для n = 10⁵ перебор пар — около 5·10⁹ сравнений. Нужен set или сортировка.
Уточняет типы. Решение почти не меняет.
Важно, если возвращаем индексы. Для ответа True/False не нужен.
Если да, работают два указателя с концов: O(n) времени без дополнительной памяти.
Алгоритм с set их обрабатывает так же. Для тестов вопрос полезен.
В Python
intне переполняется, сложение и сравнение работают одинаково при любом размере. Вопрос был бы важен, если бы сумму записывали в поле фиксированного типа.None, пустой кортеж или исключение — без договора нельзя написать тест.
Про два числа сказано в условии. Переспрашивать то, что уже прозвучало, — потеря времени на секции.
Для индексов set значений не подходит, нужен dict «значение → индекс».
Интервьюер: «Сожмите строку: aaabb → a3b2». Выберите пять вопросов, от которых зависит решение.
На пустой строке цикл не выполнится ни разу. Если после цикла код дописывает последнюю серию, для пустой строки он может добавить лишние символы.
Строка
"a33"после сжатия станет"a132", и её нельзя разобрать обратно. Нужен другой формат или запрет цифр.Уточняет формат числа. Код почти не меняется: число переводят в строку целиком.
Частое условие: вернуть исходную строку. Для
"abc"это меняет ответ.Для
"abc"ответ"a1b1c1"или"abc". Меняются и код, и тесты.Уточняет сравнение символов. Алгоритм прохода тот же.
Строки в Python неизменяемы: любая операция возвращает новую строку, исходная остаётся прежней. Для списка такой вопрос был бы важен.
Для длинной строки части собирают в список и соединяют через
join.Оба варианта дают тот же ответ за O(n). Это выбор записи, а не вопрос к условию.
Условие показывает это примером: aaabb → a3b2. Формат, который уже показан, не переспрашивают.
Можно спросить, но идея прохода по сериям останется той же.
Обычно да. Вопрос уточняет тесты, решение не меняет.
Интервьюер: «Слейте два отсортированных списка в один отсортированный». Выберите пять вопросов, от которых зависит решение.
Элементы и их порядок те же, сложность тоже. Это выбор записи, а не вопрос к условию.
Числа и строки сравниваются по-разному, но слияние от этого не меняется.
Проверяет, что код дописывает остаток второго списка и не обращается к несуществующему элементу.
Меняет сигнатуру и расход памяти.
Итоговый список получится тем же: при равных элементах оба варианта возьмут сначала один, потом второй. Знак был бы важен, если бы требовалось сохранить, из какого списка пришёл элемент.
Это O((n + m) log(n + m)). Если нужна линейная сложность, пишут слияние за O(n + m).
Слияние двумя указателями опирается на эту гарантию. Если порядок разный, алгоритм другой.
Для
[1, 2]и[2, 3]ответ[1, 2, 2, 3]или[1, 2, 3].Обычно да. Нужен тест, но вопрос почти всегда подразумевается.
Проход тот же, сложность та же. Форму записи выбирают сами.
Это сказано в самом условии: слить два отсортированных списка в один отсортированный. Переспрашивать сказанное — потеря времени.
Карточка рассуждения
Карточку можно распечатать и держать перед собой, когда решаете задачи из банка кейсов. После нескольких задач эти вопросы запоминаются.
- Что на входе и что на выходе?
- Бывает ли вход пустым, из одного элемента, с дубликатами, с отрицательными?
- Какой наибольший размер входа и значений?
- Можно ли менять входные данные?
- Что вернуть, если ответа нет?
- Какая сложность получится при наибольшем n?
- Что хранит каждая переменная после k шагов?
- Откуда начинается и где кончается цикл?
- Какой тип у промежуточных значений?
- Какой класс входов проверяет каждый тест?
- Какой вход короче всех может сломать код?
- Совпал ли ручной прогон с запуском?
- Не сломало ли исправление прежние тесты?