Алгоритмы на C++ для технических собеседований

Основы анализа сложности алгоритмов и нотация Big O

Представь, что ты пишешь программу для поиска контакта в телефонной книге на 10 000 имён. Один вариант — листать страницы по порядку. Другой — открыть нужную букву алфавита и искать только там. Оба способа найдут результат, но сколько времени займёт каждый? Именно этот вопрос — сколько времени и памяти потребует алгоритм — и решает анализ сложности.

На собеседовании тебя не попросят доказать математическую теорему. Но попросят ответить: «Какова сложность твоего решения?» — и от этого ответа зависит, пройдёшь ты дальше или нет.

Что такое Big O и зачем она нужна

Нотация Big O — это способ описать, как растёт время выполнения алгоритма при увеличении входных данных. Она не говорит «программа работает 3 миллисекунды». Она говорит: «если данных станет вдвое больше, время вырастет вдвое» или «время вырастет вчетверо».

Почему нас не интересует точное время? Потому что оно зависит от процессора, операционной системы, компилятора. А скорость роста — это свойство самого алгоритма, которое не меняется от железа.

> Big O — это не про секунды. Это про то, как алгоритм масштабируется. Два решения одной задачи могут отличаться не в разы, а в тысячи раз при больших входах.

Основные классы сложности

Разберём самые частые классы от лучшего к худшему:

— константная сложность. Время не зависит от размера входа. Пример: доступ к элементу массива по индексу.

— логарифмическая. На каждом шаге задача делится пополам. Классический пример — бинарный поиск в отсортированном массиве.

При бинарный поиск сделает около 20 итераций. Это в 50 000 раз быстрее линейного перебора.

— линейная. Время растёт пропорционально количеству элементов. Любой цикл, который проходит по всем элементам один раз.

— линейно-логарифмическая. Характерна для эффективных сортировок: merge sort, quick sort (в среднем). Это лучшая возможная сложность для сравнительной сортировки.

— квадратичная. Два вложенных цикла по итераций каждый. Сортировка пузырьком, наивное сравнение всех пар.

— экспоненциальная. Время удваивается с каждым новым элементом. Наивная рекурсия для чисел Фибоначчи — классический пример.

Сложность по памяти

Кроме времени, на собеседовании часто спрашивают про 空间复杂度 — сложность по памяти. Принцип тот же: сколько дополнительной памяти потребляет алгоритм.

| Сложность | Пример | Память | |-----------|--------|--------| | | Обмен двух переменных | Константа | | | Копирование массива | Линейно от входа | | | Матрица | Квадратично |

Когда интервьюер спрашивает «Can you do it in-place?», он спрашивает: можешь ли ты решить задачу без выделения дополнительной памяти — с по памяти.

Как определять сложность на практике

Три простых правила:

Типичная ошибка: скрытые операции внутри цикла

На первый взгляд — два цикла, . Но push_back внутри может вызвать перевыделение памяти. В худшем случае каждая вставка — из-за копирования. Итого: . На собеседовании именно такие нюансы отделяют сильных кандидатов от остальных.

Amortized complexity — амортизированная сложность

Иногда операция иногда дорогая, но в среднем дешёвая. Например, push_back в std::vector: обычно это , но при расширении буфера — . Однако если усреднить по серии операций, получается амортизированно. Это важное понятие — интервьюеры ценят, когда кандидат его понимает и может объяснить.

Что запомнить

На собеседовании тебе нужно мгновенно определять сложность по структуре кода: один цикл — , два вложенных — , деление пополам — . И всегда уточняй: «Это худший случай или средний?»

Работа с массивами и строками в C++

На собеседовании массивы и строки — это 60–70% всех задач уровня Junior и Middle. Не потому что они сложные, а потому что они проверяют фундамент: умеешь ли ты итерировать, сравнивать, трансформировать данные, не допуская ошибок на границах. Одна ошибка с индексом — и кандидат вылетает.

Массивы в C++: что нужно знать

Массив в C++ — это непрерывный блок памяти фиксированного размера. Доступ по индексу — , потому что адрес элемента вычисляется по формуле: базовый адрес + индекс × размер элемента.

Но на собеседованиях чаще используется std::vector — динамический массив из STL. Он умеет расти, знает свой размер и предоставляет удобные методы.

Ключевое отличие от обычного массива: vector хранит данные в куче и при нехватке места удваивает буфер, копируя все элементы. Именно поэтому push_back — амортизированно, но отдельная операция вставки может быть .

Типичные паттерны работы с массивами

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

Этот приём встречается в задачах на каждом втором собеседовании. Идея: два индекса движутся навстречу друг другу или в одном направлении.

Задача: проверить, есть ли в отсортированном массиве пара с заданной суммой.

Сложность: по времени, по памяти. Без двух указателей пришлось бы перебирать все пары — .

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

Когда нужно найти подмассив или подстроку с определённым свойством — максимальная сумма подмассива длины , самая длинная подстрока без повторяющихся символов.

Сложность: вместо наивных .

Строки в C++

Строка — это массив символов. В C++ есть два представления:

На собеседовании всегда используй std::string, если интервьюер не просит обратного.

Частые операции со строками

| Операция | Метод | Сложность | |----------|-------|-----------| | Длина строки | s.length() | | | Доступ по индексу | s[i] | | | Конкатенация | s1 + s2 | | | Подстрока | s.substr(pos, len) | | | Поиск символа | s.find('a') | | | Сравнение | s1 == s2 | |

Палиндром — классическая задача

Проверить, является ли строка палиндромом. Два указателя — снова они:

Если нужно игнорировать пробелы и регистр — добавляем предобработку:

Анаграммы — проверка через частотный массив

Две строки являются анаграммами, если содержат одни и те же символы в одинаковом количестве. Решение — подсчитать частоты:

Сложность: по времени, по памяти (массив фиксированного размера 26). Это оптимальное решение — интервьюеры ожидают именно его.

Ловушки, которые встречаются на собеседованиях

Off-by-one ошибки. Забыл <= вместо < — и цикл не обработал последний элемент. Всегда проверяй граничные случаи: пустой массив, массив из одного элемента, максимальный индекс.

Модификация контейнера во время итерации. Удаляешь элемент из vector внутри range-based for-loop — undefined behavior. Используй итераторы с erase:

Переполнение при сложении. Если складываешь два int, и сумма может превысить — используй long long.

Массивы и строки — это фундамент. Освоив два указателя, скользящее окно и частотные массивы, ты закроешь значительную часть задач уровня Junior/Middle.

Использование STL для поиска и сортировки

Кандидат, который пишет сортировку пузырьком на собеседовании, когда можно вызвать std::sort, выглядит так же, как человек, который собирает компьютер из транзисторов, когда на столе лежит готовый ноутбук. STL — это твой главный инструмент. Знание стандартной библиотеки шаблонов показывает интервьюеру, что ты пишешь промышленный код, а не учебные упражнения.

std::sort — универсальная сортировка

std::sort использует introsort — гибрид quicksort, heapsort и insertion sort. Сложность: в худшем случае. Этого достаточно для 95% задач на собеседованиях.

Сортировка с пользовательским компаратором — частый приём:

Лямбда-выражение ... { body } — это анонимная функция. На собеседовании она незаменима для кастомных компараторов.

std::binary_search и его друзья

Если массив отсортирован, линейный поиск — расточительство. STL даёт целое семейство бинарных функций:

Разница между lower_bound и upper_bound критична:

Это позволяет находить все вхождения элемента в отсортированном массиве:

Все эти функции работают за .

Контейнеры STL: когда что использовать

Выбор правильного контейнера — это уже половина решения. Неправильный выбор может превратить в .

| Контейнер | Вставка | Поиск | Удаление | Когда использовать | |-----------|---------|-------|----------|-------------------| | vector | конец | / если отсортирован | конец | Основной выбор по умолчанию | | deque | оба конца | | оба конца | Нужен доступ к обоим концам | | set | | | | Уникальные элементы + порядок | | unordered_set | среднее | среднее | среднее | Быстрый поиск без порядка | | map | | | | Пары ключ-значение + порядок | | unordered_map | среднее | среднее | среднее | Частотные подсчёты, хеш-таблицы | | priority_queue | | максимум | максимум | Нахождение min/max |

std::unordered_map — хеш-таблица для подсчётов

Самый частый контейнер на собеседованиях после vector. Подсчёт частот, группировка, проверка наличия — всё это через хеш-таблицу.

Сложность поиска и вставки — в среднем. В худшем случае (при коллизиях) — , но на практике это почти никогда не происходит.

std::set и std::unordered_set

set хранит уникальные элементы в отсортированном порядке (красно-чёрное дерево). unordered_set — без порядка, но быстрее (хеш-таблица).

Сложность: по времени, по памяти. Без множества пришлось бы сравнивать каждый с каждым — .

std::priority_queue — очередь с приоритетом

Когда нужно быстро находить минимальный или максимальный элемент. По умолчанию — max-heap (наибольший элемент наверху).

Классическая задача: найти -й наибольший элемент.

Сложность: — значительно лучше полной сортировки , когда .

std::accumulate и другие алгоритмы

STL богата на готовые алгоритмы. Не пиши вручную то, что уже написано:

Когда STL недостаточно

Иногда задача требует кастомной структуры данных или модификации стандартного алгоритма. Но даже тогда ты строишь решение поверх STL-контейнеров. Например, LRU Cache — это unordered_map + list (двусвязный список). Знание внутреннего устройства STL помогает комбинировать контейнеры эффективно.

Помни: на собеседовании интервьюер сначала оценивает, знаешь ли ты стандартные инструменты. Только потом — можешь ли ты написать что-то с нуля.

Связные списки и базовые структуры данных

Почему на собеседованиях так любят связные списки, хотя в реальном коде они почти не используются? Потому что связный список проверяет, понимаешь ли ты указатели, работу с памятью и манипуляции структурами данных на уровне, который скрывает std::vector. Если ты не можешь развернуть связный список — ты не понимаешь, как устроена память.

Устройство связного списка

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

Сравнение с массивом:

| Операция | Массив / Vector | Связный список | |----------|----------------|----------------| | Доступ по индексу | | | | Вставка в начало | | | | Вставка в конец | амортиз. | без хвоста | | Удаление из начала | | | | Память | Непрерывный блок | Разрозненные узлы |

Связный список выигрывает, когда нужны частые вставки/удаления в начале. Проигрывает, когда нужен произвольный доступ.

Создание и обход списка

Разворот связного списка — задача №1

Самая частая задача на собеседовании. Три указателя: prev, current, next.

Сложность: по времени, по памяти. Рекурсивная версия — по памяти из-за стека вызовов, поэтому на собеседовании предпочитай итеративную.

Обнаружение цикла — алгоритм Флойда

Если в списке есть цикл, обычный обход зациклится навсегда. Алгоритм «черепахи и зайца» — два указателя: медленный движется на один шаг, быстрый — на два. Если есть цикл, они встретятся.

Сложность: по времени, по памяти. Альтернатива — unordered_set<ListNode*> для хранения посещённых узлов, но это по памяти.

Нахождение середины списка

Ещё одно применение двух указателей с разной скоростью:

Двусвязный список

Каждый узел хранит указатель и на следующий, и на предыдущий элемент. Это даёт обход в обоих направлениях и удаление, если есть указатель на узел.

std::list в STL — это реализация двусвязного списка. Используй его, когда нужны частые вставки/удаления в середине:

Стек и очередь

Стек — LIFO (последний пришёл — первый ушёл). Очередь — FIFO (первый пришёл — первый ушёл). Обе структуры можно реализовать на связном списке, но STL даёт готовые контейнеры.

На собеседованиях стек используется для проверки корректности скобок, вычисления выражений, обхода графов в глубину. Очередь — для BFS, задач на скользящее окно.

Проверка корректности скобок — классика со стеком

Когда использовать связный список на практике

В реальном промышленном коде связные списки редки — std::vector почти всегда быстрее из-за локальности кэша (элементы лежат рядом в памяти). Но связные списки — основа для более сложных структур: LRU Cache, adjacency list в графах, реализация std::deque. Понимание списков необходимо для работы с этими структурами.

На собеседовании задачи на связные списки проверяют не знание списка как структуры, а умение аккуратно работать с указателями и не терять узлы при манипуляциях.

Разбор типовых задач с технических собеседований

Теория без практики — мёртвый груз. Ты знаешь Big O, STL, массивы и списки. Теперь соберём всё вместе и разберём пять задач, которые встречаются на собеседованиях в Google, Яндекс, Amazon и десятках других компаний. Каждая задача — это комбинация паттернов, которые ты уже изучил.

Задача 1: Two Sum (LeetCode #1)

Условие: Дан массив целых чисел и целевое значение target. Найти индексы двух чисел, сумма которых равна target.

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

Наивное решение: Двойной цикл — перебрать все пары. Сложность: , память: .

Оптимальное решение: Хеш-таблица. Для каждого элемента проверяем, есть ли в таблице дополнение target - nums[i].

Сложность: по времени, по памяти. Один проход — и мы одновременно ищем и запоминаем.

Что спросит интервьюер: «А если массив отсортирован?» — тогда два указателя, без дополнительной памяти. «А если нужны все пары, а не одна?» — нужна другая стратегия.

Задача 2: Valid Parentheses (LeetCode #20)

Условие: Определить, корректна ли строка со скобками ()[]{}.

Разбор этой задачи мы уже делали в статье о структурах данных — стек решает её элегантно за . Но на собеседовании интервьюер может усложнить: «А если добавить условие, что скобки могут быть вложены только определённым образом?» — тогда нужно модифицировать логику проверки.

Задача 3: Merge Intervals (LeetCode #56)

Условие: Дан массив интервалов [start, end]. Объединить перекрывающиеся интервалы.

Эта задача встречается повсюду: планирование встреч, распределение ресурсов, обработка временных окон.

Алгоритм:

Сложность: из-за сортировки, по памяти для результата.

Ловушка: Забыть max при расширении — если интервал [1, 10] полностью содержит [2, 5], конец не должен уменьшиться.

Задача 4: Reverse Linked List (LeetCode #206)

Мы разбирали развёртывание списка в предыдущей статье. На собеседовании интервьюер часто просит написать и рекурсивную, и итеративную версии, чтобы проверить понимание стека вызовов.

Рекурсивная версия:

Сложность: по времени, по памяти (стек рекурсии). Интервьюер может спросить: «Как сделать за памяти?» — итеративная версия.

Задача 5: Longest Substring Without Repeating Characters (LeetCode #3)

Условие: Найти длину самой длинной подстроки без повторяющихся символов.

Классическое применение скользящего окна с хеш-таблицей.

Сложность: по времени, по памяти, где — размер алфавита.

Разбор по шагам для строки "abcabcbb":

Стратегия прохождения собеседования

Разбор задач — это техническая часть. Но на собеседовании важен и процесс:

1. Уточни задачу. Задай вопросы: «Массив отсортирован?», «Могут быть отрицательные числа?», «Какой ожидаемый размер входа?». Это показывает системное мышление.

2. Начни с наивного решения. Скажи: «Можно решить за перебором всех пар». Это даёт отправную точку и показывает, что ты можешь решить задачу в принципе.

3. Оптимизируй. Объясни: «Но мы можем использовать хеш-таблицу, чтобы сократить до ». Рассуждай вслух — интервьюер оценивает ход мыслей, а не только финальный код.

4. Тестируй. Прогони код на примерах: обычный случай, пустой вход, один элемент, граничные значения. Найди баг до интервьюера — это сильный позитивный сигнал.

5. Анализируй сложность. Всегда заканчивай фразой: «Сложность — по времени, по памяти». Если можешь улучшить память — скажи об этом.

Паттерны, которые повторяются

За всеми задачами стоит набор повторяющихся паттернов:

Освоив эти шесть паттернов и уметь их комбинировать, ты закроешь 80% задач уровня Junior/Middle. Остальные 20% — это вариации и комбинации, которые приходят с практикой.