Большинство кандидатов подходят к собеседованиям по программированию неправильно.
Они заучивают сотни отдельных задач. Делают grinding на LeetCode, пытаясь охватить каждый возможный вопрос.
Но вот секрет, который знают лучшие: Большинство задач по программированию следуют узнаваемым паттернам.
Освойте эти 10 паттернов, и вы сможете решить 80% вопросов на собеседовании — даже те, которые никогда не видели.
Вместо заучивания 500 задач вы поймёте фундаментальные концепции, которые открывают тысячи вариаций.
Это разница между заучиванием ответов и пониманием того, как думать.
Почему Паттерны Важны
Думайте о паттернах алгоритмов как о шахматных дебютах.
Вы не заучиваете каждую возможную шахматную партию — вы изучаете стратегические паттерны, применимые к тысячам партий.
Тот же принцип работает для собеседований по программированию.
Когда вы видите новую задачу, распознавание паттернов помогает немедленно определить подход. "Это похоже на задачу со скользящим окном," думаете вы, и сразу знаете, с чего начать.
Никаких пустых взглядов. Никакой паники.
Преимущества обучения на паттернах:
Решайте новые задачи быстрее
Вместо того чтобы застывать перед незнакомой задачей, вы распознаете паттерн и примените отработанный шаблон.
Узнавайте вариации известных задач
Большинство "новых" вопросов на собеседовании — просто вариации классических задач. Паттерны помогают видеть сквозь маскировку.
Развивайте реальную интуицию решения задач
С паттернами вы развиваете шестое чувство для того, какой подход сработает лучше — даже до начала кодирования.
Снижайте стресс на собеседовании
Нет ничего более успокаивающего, чем мысль: "Я решал похожие задачи раньше!"
Паттерн #1: Два Указателя
Паттерн двух указателей — одна из самых элегантных техник. Он использует две точки отсчёта, которые движутся по структуре данных для поиска связей или выполнения условий.
Когда использовать: Задачи с массивами, строками или связными списками, где нужно найти пары, тройки или подмассивы.
Ключевые индикаторы:
"Найди пару с суммой X" — Классические два указателя с обоих концов отсортированного массива.
"Удали дубликаты в отсортированном массиве" — Один указатель читает, другой записывает уникальные значения.
"Переверни строку" — Указатели начинают с противоположных концов и меняются местами внутрь.
Базовая структура:
def dva_ukazatelya_template(arr):
lev = 0
prav = len(arr) - 1
while lev < prav:
# Вычислить что-то с arr[lev] и arr[prav]
if uslovie_vypolneno:
return rezultat
elif lev_dolzhen_dvigatsya:
lev += 1
else:
prav -= 1
return rezultat
Пример: Two Sum (отсортированный массив)
def two_sum_sorted(numbers, target):
"""
Найти два числа, которые дают target в отсортированном массиве.
Время: O(n), Память: O(1)
"""
lev, prav = 0, len(numbers) - 1
while lev < prav:
tekushaya_summa = numbers[lev] + numbers[prav]
if tekushaya_summa == target:
return [lev, prav]
elif tekushaya_summa < target:
lev += 1 # Нужна большая сумма
else:
prav -= 1 # Нужна меньшая сумма
return []
# Тест
print(two_sum_sorted([1, 2, 3, 4, 6], 6)) # [1, 3] → 2+4=6
Ещё задачи для практики:
- 3Sum
- Remove Nth Node From End
- Trapping Rain Water
- Valid Palindrome
Паттерн #2: Скользящее Окно
Паттерн скользящего окна идеален для задач с непрерывными последовательностями. Представьте окно, скользящее по массиву или строке, расширяющееся и сжимающееся по мере необходимости.
Когда использовать: Задачи с подмассивами или подстроками с определёнными условиями.
Ключевые индикаторы:
"Самая длинная/короткая подстрока с..." — Окно расширяется для поиска самой длинной, сжимается для самой короткой.
"Максимальная сумма подмассива размера K" — Окно фиксированного размера скользит для поиска максимальной суммы.
"Найди все анаграммы" — Окно отслеживает частоту символов для сопоставления паттернов.
Два типа:
- Фиксированный размер: Размер окна постоянен
- Динамический размер: Окно растёт и сжимается
Шаблон фиксированного окна:
def fiksir_okno(arr, k):
summa_okna = sum(arr[:k])
max_summa = summa_okna
for i in range(k, len(arr)):
# Сдвигаем окно
summa_okna = summa_okna - arr[i - k] + arr[i]
max_summa = max(max_summa, summa_okna)
return max_summa
Шаблон динамического окна:
def dinam_okno(s, uslovie):
lev = 0
rezultat = float('inf')
tekushee_sostoyanie = {}
for prav in range(len(s)):
# Расширяем окно, включая s[prav]
# Обновляем tekushee_sostoyanie
while uslovie_vypolneno:
# Обновляем rezultat если нужно
# Сжимаем окно слева
lev += 1
return rezultat
Пример: Longest Substring Without Repeating Characters
def length_of_longest_substring(s):
"""
Найти длину самой длинной подстроки без повторяющихся символов.
Время: O(n), Память: O(min(n, m)) где m — размер алфавита
"""
char_set = set()
lev = 0
max_dlina = 0
for prav in range(len(s)):
# Сжимаем окно пока есть дубликаты
while s[prav] in char_set:
char_set.remove(s[lev])
lev += 1
# Добавляем текущий символ
char_set.add(s[prav])
max_dlina = max(max_dlina, prav - lev + 1)
return max_dlina
# Тест
print(length_of_longest_substring("abcabcbb")) # 3 (abc)
Паттерн #3: Быстрый и Медленный Указатели
Когда использовать: Задачи с циклами или поиском средних элементов в связных списках.
Ключевые индикаторы:
- "Обнаружить цикл"
- "Найти средний элемент"
- "Happy number"
- "Начало цикла"
Шаблон:
def bystryj_medlennyj(head):
medlennyj = head
bystryj = head
while bystryj and bystryj.next:
medlennyj = medlennyj.next # Движется на 1 шаг
bystryj = bystryj.next.next # Движется на 2 шага
if medlennyj == bystryj:
return True # Цикл обнаружен
return False # Нет цикла
Пример: Linked List Cycle
def has_cycle(head):
"""
Обнаружить, есть ли цикл в связном списке.
Время: O(n), Память: O(1)
"""
if not head or not head.next:
return False
medlennyj = head
bystryj = head
while bystryj and bystryj.next:
medlennyj = medlennyj.next
bystryj = bystryj.next.next
if medlennyj == bystryj:
return True
return False
Паттерн #4: Слияние Интервалов
Когда использовать: Задачи с пересекающимися интервалами или диапазонами.
Ключевые индикаторы:
- "Объединить пересекающиеся интервалы"
- "Вставить интервал"
- "Комнаты для встреч"
- "Конфликтующие встречи"
Шаблон:
def merge_intervals(intervals):
if not intervals:
return []
# Сортируем по времени начала
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]: # Пересекаются
# Объединяем, обновляя время конца
last[1] = max(last[1], current[1])
else:
merged.append(current)
return merged
Паттерн #5: Циклическая Сортировка
Когда использовать: Задачи с массивами, содержащими числа в заданном диапазоне.
Ключевые индикаторы:
- "Найти пропущенное число в диапазоне [1, n]"
- "Найти дубликат"
- Числа в диапазоне [0, n] или [1, n]
Шаблон:
def cyclic_sort(nums):
i = 0
while i < len(nums):
correct_index = nums[i] - 1 # Для диапазона [1, n]
if nums[i] != nums[correct_index]:
# Меняем на правильную позицию
nums[i], nums[correct_index] = nums[correct_index], nums[i]
else:
i += 1
return nums
Паттерн #6: Разворот LinkedList на Месте
Когда использовать: Задачи, требующие разворота связных списков.
Ключевые индикаторы:
- "Разверни связный список"
- "Разверни каждые K элементов"
- "Поверни связный список"
Шаблон:
def reverse_linked_list(head):
prev = None
current = head
while current:
next_node = current.next # Сохраняем следующий
current.next = prev # Разворачиваем ссылку
prev = current # Двигаем prev вперёд
current = next_node # Двигаем current вперёд
return prev # Новая голова
Паттерн #7: Tree BFS (Поиск в Ширину)
Поиск в ширину исследует дерево уровень за уровнем, как круги на воде.
Когда использовать: Задачи, требующие обхода дерева по уровням.
Ключевые индикаторы:
"Обход по уровням" — Посещение узлов уровень за уровнем сверху вниз.
"Зигзагообразный обход" — Чередование направления для каждого уровня.
"Минимальная глубина" — BFS эффективно находит кратчайший путь до листа.
Шаблон:
from collections import deque
def level_order_traversal(root):
if not root:
return []
rezultat = []
ochered = deque([root])
while ochered:
razmer_urovnya = len(ochered)
tekushij_uroven = []
for _ in range(razmer_urovnya):
uzel = ochered.popleft()
tekushij_uroven.append(uzel.val)
if uzel.left:
ochered.append(uzel.left)
if uzel.right:
ochered.append(uzel.right)
rezultat.append(tekushij_uroven)
return rezultat
Паттерн #8: Tree DFS (Поиск в Глубину)
Когда использовать: Задачи с деревьями, требующие обхода путей.
Ключевые индикаторы:
- "Сумма пути"
- "Все пути"
- "Диаметр дерева"
- "Максимальная глубина"
Три типа обхода:
def inorder(root): # Лев, Корень, Прав
if not root:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
def preorder(root): # Корень, Лев, Прав
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
def postorder(root): # Лев, Прав, Корень
if not root:
return []
return postorder(root.left) + postorder(root.right) + [root.val]
Паттерн #9: Две Кучи
Когда использовать: Задачи на поиск медианы или планирование.
Ключевые индикаторы:
- "Найти медиану"
- "Медиана скользящего окна"
- "Максимизировать капитал"
Шаблон:
import heapq
class MedianFinder:
def __init__(self):
self.small = [] # Max heap (инвертируем значения)
self.large = [] # Min heap
def add_num(self, num):
# Добавляем в max heap (small)
heapq.heappush(self.small, -num)
# Балансируем: перемещаем наибольший из small в large
heapq.heappush(self.large, -heapq.heappop(self.small))
# Если large имеет больше элементов, ребалансируем
if len(self.large) > len(self.small):
heapq.heappush(self.small, -heapq.heappop(self.large))
def find_median(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2.0
Паттерн #10: Модифицированный Бинарный Поиск
Когда использовать: Отсортированные или повёрнутые массивы, поиск диапазонов.
Ключевые индикаторы:
- "Поиск в отсортированном массиве"
- "Найти точку поворота"
- "Поиск в повёрнутом массиве"
Шаблон:
def binary_search(arr, target):
lev, prav = 0, len(arr) - 1
while lev <= prav:
mid = lev + (prav - lev) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lev = mid + 1
else:
prav = mid - 1
return -1
Пример: Search in Rotated Array
def search_rotated(nums, target):
"""
Поиск в отсортированном повёрнутом массиве.
Время: O(log n), Память: O(1)
"""
lev, prav = 0, len(nums) - 1
while lev <= prav:
mid = lev + (prav - lev) // 2
if nums[mid] == target:
return mid
# Определяем, какая половина отсортирована
if nums[lev] <= nums[mid]:
# Левая половина отсортирована
if nums[lev] <= target < nums[mid]:
prav = mid - 1
else:
lev = mid + 1
else:
# Правая половина отсортирована
if nums[mid] < target <= nums[prav]:
lev = mid + 1
else:
prav = mid - 1
return -1
Как Практиковать Эти Паттерны
Неделя 1-2: Изучите Паттерны
Изучайте один паттерн в день. Глубоко погрузитесь в механику паттерна, когда использовать и типичные вариации.
Поймите шаблон. Не просто копируйте код — понимайте, зачем существует каждая строка.
Решите 2-3 лёгкие задачи на каждый паттерн. Применяйте шаблон к простым задачам, пока это не станет естественным.
Неделя 3-4: Практикуйте Вариации
- Решайте задачи средней сложности
- Смешивайте паттерны (некоторые задачи используют несколько)
- Засекайте время
Неделя 5-6: Осваивайте Сложные Задачи
- Беритесь за сложные задачи
- Проводите пробные собеседования
- Анализируйте и оптимизируйте решения
Шпаргалка по Распознаванию Паттернов
| Если задача упоминает... | Рассмотрите паттерн... |
|---|---|
| Отсортированный массив/строка | Два указателя, Бинарный поиск |
| Пары/тройки | Два указателя |
| Подмассив/подстрока | Скользящее окно |
| Цикл в связном списке | Быстрый и медленный указатели |
| Пересекающиеся интервалы | Слияние интервалов |
| Числа в диапазоне [1,n] | Циклическая сортировка |
| Разворот связного списка | Разворот на месте |
| Дерево по уровням | BFS |
| Пути в дереве | DFS |
| Найти медиану | Две кучи |
| Поиск в отсортированном | Бинарный поиск |
Заключение
Вместо заучивания 500 отдельных задач освойте эти 10 паттернов:
- ✅ Два указателя — Пары и тройки
- ✅ Скользящее окно — Подмассивы и подстроки
- ✅ Быстрый и медленный — Циклы и средние элементы
- ✅ Слияние интервалов — Пересекающиеся диапазоны
- ✅ Циклическая сортировка — Числа в заданном диапазоне
- ✅ Разворот на месте — Разворот LinkedList
- ✅ Tree BFS — Обход по уровням
- ✅ Tree DFS — Задачи с путями
- ✅ Две кучи — Поиск медианы
- ✅ Модифицированный бинарный поиск — Отсортированные массивы
С этими паттернами вы будете узнавать подход к большинству задач за секунды.
Готовы практиковаться с ИИ-помощником? Скачайте Interview Whisper и получайте помощь в реальном времени с распознаванием паттернов.
Связанные Статьи:
