10 ключевых паттернов DSA для собеседований и кода

Зачем изучать паттерны DSA?

На собеседованиях в топовые компании и в реальных проектах вы сталкиваетесь с одними и теми же типами задач: поиск подмассива, обход графа, оптимизация рекурсии. Вместо того чтобы каждый раз изобретать велосипед, можно использовать проверенные паттерны DSA — готовые шаблоны решений. В этой статье я разберу 10 ключевых паттернов, которые покроют 90% задач на LeetCode и помогут писать эффективный код. К каждому паттерну дам пример на Python и советы по применению.

1. Скользящее окно (Sliding Window)

Этот паттерн незаменим для задач с подмассивами или подстроками. Идея: поддерживать окно (диапазон индексов) и двигать его по структуре данных, обновляя результат за O(1).

def max_sum_subarray(arr, k):
    """Максимальная сумма подмассива длины k"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        # сдвигаем окно: убираем левый элемент, добавляем правый
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

print(max_sum_subarray([1, 3, -1, -3, 5, 3, 6, 7], 3))  # 16

Применяйте для задач: «максимальная сумма подмассива», «самая длинная подстрока без повторяющихся символов», «анаграммы в строке».

2. Два указателя (Two Pointers)

Паттерн для работы с отсортированными массивами или связными списками. Два указателя движутся навстречу или в одном направлении, сокращая время до O(n).

def pair_sum_sorted(arr, target):
    """Найти пару чисел, дающих заданную сумму (массив отсортирован)"""
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return (arr[left], arr[right])
        elif current_sum < target:
            left += 1  # увеличиваем сумму
        else:
            right -= 1  # уменьшаем сумму
    return None

print(pair_sum_sorted([1, 2, 4, 7, 11, 15], 15))  # (4, 11)

Используйте для: поиск пары с заданной суммой, удаление дубликатов, проверка палиндрома.

3. Бинарный поиск (Binary Search)

Классика для отсортированных данных. Делит массив пополам, отбрасывая половину на каждом шаге. Сложность O(log n).

def binary_search(arr, target):
    """Бинарный поиск элемента в отсортированном массиве"""
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))  # 3

Применяйте не только для поиска числа, но и для поиска границ (first/last occurrence) и в задачах с монотонными функциями.

4. Жадные алгоритмы (Greedy)

На каждом шаге выбирается локально оптимальное решение. Подходит для задач, где локальный оптимум ведёт к глобальному.

def coin_change_greedy(coins, amount):
    """Размен монет (жадный — работает только для канонических систем)"""
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        if amount == 0:
            break
        count += amount // coin
        amount %= coin
    return count if amount == 0 else -1

print(coin_change_greedy([1, 5, 10, 25], 63))  # 6 (25+25+10+1+1+1)

Типичные задачи: задача о рюкзаке (дробная версия), интервальное планирование, минимальное количество шагов.

5. Динамическое программирование (Dynamic Programming)

Разбиваем задачу на подзадачи, решаем каждую один раз и сохраняем результат. Подходит для задач с перекрывающимися подзадачами и оптимальной подструктурой.

def fibonacci_dp(n):
    """Число Фибоначчи через DP (bottom-up)"""
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fibonacci_dp(10))  # 55

Классические задачи: задача о рюкзаке (0/1), наибольшая общая подпоследовательность, редактирование расстояния.

6. Поиск в глубину (DFS — Depth-First Search)

Обходит граф или дерево, углубляясь до конца ветки, затем возвращается. Использует стек (явный или рекурсию).

def dfs_tree(root):
    """Обход дерева в глубину (pre-order)"""
    if not root:
        return
    print(root.value)  # посещаем узел
    dfs_tree(root.left)
    dfs_tree(root.right)

# Пример для бинарного дерева
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
dfs_tree(root)  # 1, 2, 3

Применяйте для: поиск пути в лабиринте, топологическая сортировка, проверка связности графа.

7. Поиск в ширину (BFS — Breadth-First Search)

Обходит граф уровнями: сначала все вершины на расстоянии 1, потом 2 и т.д. Использует очередь.

from collections import deque

def bfs_graph(graph, start):
    """Обход графа в ширину"""
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)

graph = {
    0: [1, 2],
    1: [2],
    2: [0, 3],
    3: [3]
}
bfs_graph(graph, 2)  # 2, 0, 3, 1

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

8. Топологическая сортировка (Topological Sort)

Упорядочивает вершины ориентированного ациклического графа (DAG) так, что для любого ребра (u, v) вершина u идёт до v. Используется для задач с зависимостями.

from collections import defaultdict, deque

def topological_sort(vertices, edges):
    """Топологическая сортировка графа (алгоритм Кана)"""
    in_degree = {v: 0 for v in vertices}
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return result

vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (1, 2), (3, 2), (4, 0)]
print(topological_sort(vertices, edges))  # [3, 4, 0, 1, 2]

Типичные задачи: планирование задач с зависимостями, порядок компиляции модулей.

9. Дерево отрезков (Segment Tree)

Структура для эффективных запросов на отрезке (сумма, минимум, максимум) и точечных обновлений. Сложность O(log n) на запрос.

class SegmentTree:
    def __init__(self, data):
        n = len(data)
        self.tree = [0] * (4 * n)
        self.build(data, 0, 0, n - 1)

    def build(self, data, node, left, right):
        if left == right:
            self.tree[node] = data[left]
        else:
            mid = (left + right) // 2
            self.build(data, 2*node + 1, left, mid)
            self.build(data, 2*node + 2, mid + 1, right)
            self.tree[node] = self.tree[2*node + 1] + self.tree[2*node + 2]

    def query(self, node, left, right, ql, qr):
        if ql > right or qr < left:
            return 0
        if ql <= left and right <= qr:
            return self.tree[node]
        mid = (left + right) // 2
        return self.query(2*node + 1, left, mid, ql, qr) + self.query(2*node + 2, mid + 1, right, ql, qr)

arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
print(st.query(0, 0, len(arr)-1, 1, 3))  # 3 + 5 + 7 = 15

Используйте для: динамические запросы суммы/минимума на отрезке, задачи с обновлением элементов.

10. Мемоизация (Memoization)

Кеширование результатов функций для ускорения рекурсивных вычислений. Часто реализуется через декоратор @lru_cache или словарь.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    """Число Фибоначчи с мемоизацией"""
    if n < 2:
        return n
    return fib_memo(n-1) + fib_memo(n-2)

print(fib_memo(50))  # 12586269025 (мгновенно)

Применяйте для: рекурсивные задачи с перекрывающимися подзадачами (Фибоначчи, задача о рюкзаке, комбинаторные задачи).

Что делать прямо сейчас?

Не пытайтесь выучить все паттерны за один день. Выберите один — например, скользящее окно — и решите 5-10 задач на LeetCode, используя только его. Затем переходите к следующему. Через месяц вы заметите, что 80% новых задач укладываются в знакомые шаблоны. Удачи на собеседованиях!