Алгоритмы с нуля
Инструментарий: распознавание паттернов в коде
Суть Прочти четыре наброска кода, распознай, какую технику каждый реализует (или должен), и выбери верную структуру данных или самую рычажную правку.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеНа собеседовании или код-ревью тебе редко дают помеченную задачу — тебе дают фрагмент и ограничение. Навык в том, чтобы прочесть цикл и назвать технику, которую он реализует, или заметить, что выбранная структура неверна. Прочти каждый набросок, затем ответь.
Цель
Потренируй распознавательную половину инструментария: по коду определи паттерн, оцени, подходит ли структура данных доминирующей операции, и выбери изменение, которое реально сдвигает сложность.
Фрагмент 1 — вложенный цикл по отсортированным данным
def has_pair_with_sum(a, target): # a is sorted ascending
n = len(a)
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return True
return False Викторина
Completed
Вход отсортирован, но это O(n^2). К какому паттерну зовёт отсортированный вход и какова итоговая сложность?
Heads-up Здесь нет перекрывающихся подзадач — каждая пара рассматривается один раз. Мемоизация кэширует повторные подрезультаты, которых нет. Правка — использовать отсортированный порядок через two pointers, а не кэшировать.
Heads-up Пара-с-суммой на отсортированном входе — это O(n) через two pointers, либо O(n) в среднем через hash set на неотсортированном входе. Грубая сила O(n^2) игнорирует самую сильную подсказку задачи: массив отсортирован.
Heads-up Куча даёт экстремальный элемент, а не отношения между парами, и данные уже отсортированы, так что куча ничего не добавляет. Паттерн, на который указывает отсортированность, — проход two pointers.
Фрагмент 2 — рекурсия, которая пересчитывает
def ways(n, coins):
if n == 0: return 1
if n < 0 or not coins: return 0
# use coins[0] again, or drop it
return ways(n - coins[0], coins) + ways(n, coins[1:]) Викторина
Completed
Это корректно, но экспоненциально при большом n. Каков точный диагноз и стандартная правка?
Heads-up Базовые случаи (n==0 даёт 1, n<0 или пусто даёт 0) корректны, и рекурсия завершается. Цена — не баг, а экспоненциальный повторный обход одинаковых состояний (остаток, индекс) — это и есть сигнал DP.
Heads-up Жадность считает максимум один способ, а не все различные, и может ошибаться для неканонических номиналов. Подсчёт комбинаций требует суммирования по подзадачам — это DP; жадность отвечает на другой вопрос.
Heads-up Two pointers решает задачи отношения на отсортированной последовательности, а не подсчёт по рекурсивному пространству выборов. Перекрывающиеся состояния (остаток, индекс) — безошибочный сигнал к мемоизации или табуляции.
Фрагмент 3 — текущий k-й элемент
import heapq
def stream_kth_largest(stream, k):
h = [] # what kind of heap?
for x in stream:
heapq.heappush(h, x) # Python heapq is a MIN-heap
if len(h) > k:
heapq.heappop(h) # pops the smallest
return h[0] # the k-th largest seen so far Викторина
Completed
Этот код держит текущий k-й наибольший через min-heap размера k. Почему именно MIN-heap (а не max-heap) — верная структура здесь?
Heads-up Max-heap кладёт наибольший в корень, так что вытеснение нужного элемента (наименьшего из хранимых k) стоило бы O(k)-скана каждый раз. Min-heap делает вытеснение O(log k). Зеркальная логика даёт max-heap для k наименьших.
Heads-up Выбор задан тем, какой элемент нужно дёшево вытеснять. Хранить k наибольших значит выбрасывать текущий наименьший, поэтому наименьший должен быть в корне — это min-heap. Ориентация не произвольна.
Heads-up Поддержка отсортированного списка стоит O(k) на вставку (сдвиг элементов), давая O(n*k) в сумме против O(n log k) у кучи. Для потокового top-k куча — верная структура именно потому, что вставка и вытеснение оба O(log k).
Фрагмент 4 — неограниченное окно
def longest_unique_substring(s):
seen = set()
best = 0
for r in range(len(s)):
while s[r] in seen:
seen.add(s[r]) # BUG: should shrink from the left
seen.add(s[r])
best = max(best, len(seen))
return best Викторина
Completed
Задумана техника скользящего окна по строке. Окно никогда не сжимается, поэтому цикл сломан. Каков верный механизм?
Heads-up Сортировка разрушает подстрочную (непрерывную) структуру, о которой задача — подстрока обязана быть непрерывным срезом исходного порядка. Скользящее окно с левым указателем сохраняет непрерывность и работает за O(n).
Heads-up Это та грубая сила O(n^2), которую окно призвано заменить. Вся ценность окна в том, что левый указатель движется только вперёд, поэтому суммарная работа O(n) — никогда не перезапускай внутренний скан.
Heads-up Куча выдаёт экстремум по приоритету, что не имеет отношения к поддержке непрерывного диапазона без дубликатов. Паттерн, на который указывает 'длиннейшая непрерывная подстрока при условии', — скользящее окно, а не куча.
Итог
Чтение кода ради паттерна — тот же поток, прогнанный в обратную сторону: вложенный цикл по отсортированным данным должен быть two pointers (O(n)); рекурсия, пересчитывающая одинаковые состояния, кричит о мемоизации или табуляции (DP); текущий k-й элемент задаёт конкретную ориентацию кучи тем, какой элемент нужно дёшево вытеснять; а ‘длиннейший непрерывный диапазон при условии’ — это скользящее окно, чей левый указатель движется только вперёд. Назови паттерн, сверь структуру данных с доминирующей операцией, затем измени то единственное, что сдвигает сложность.