Подготовка к алгоритмическому собеседованию в Яндекс

Оценка сложности (Big O), массивы и строки: базовые техники манипуляции данными

Алгоритмическое собеседование в Яндекс — это не просто проверка знания синтаксиса языка программирования. Это тест на способность писать эффективный код, который будет работать с огромными объемами данных. Когда вы работаете с миллионами запросов в секунду, разница между эффективным и неэффективным алгоритмом означает разницу между работающим сервисом и упавшим сервером.

Фундаментом для написания такого кода является умение оценивать сложность алгоритмов и глубокое понимание базовых структур данных: массивов и строк.

Асимптотическая сложность (Big O Notation)

Big O (О-большое) — это математическая нотация, которая описывает, как возрастает время выполнения алгоритма или потребление памяти при увеличении размера входных данных. Мы не измеряем время в секундах, так как оно зависит от железа. Мы измеряем количество операций.

!Сравнение скорости роста различных алгоритмических сложностей

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

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

— Логарифмическая сложность. На каждом шаге объем данных уменьшается вдвое. Пример: бинарный поиск.

— Линейная сложность. Время растет прямо пропорционально количеству данных. Пример: простой проход циклом по массиву.

— Линеарифимическая сложность. Характерна для эффективных алгоритмов сортировки (Merge Sort, Quick Sort).

— Квадратичная сложность. Обычно возникает при вложенных циклах. Пример: сортировка пузырьком.

Как считать сложность?

Рассмотрим пример кода. Допустим, у нас есть функция, которая суммирует элементы матрицы:

Здесь мы видим два вложенных цикла. Внешний цикл выполняется раз (количество строк), внутренний — раз (количество столбцов). Общее количество операций можно выразить формулой:

Где — общее время выполнения, — константа времени выполнения одной операции сложения, — количество строк, — количество столбцов.

В нотации Big O мы отбрасываем константы и младшие порядки, поэтому сложность будет . Если матрица квадратная (), то сложность составляет .

Пространственная сложность (Space Complexity)

Помимо времени (), важно оценивать память. Если ваш алгоритм создает копию массива длины , его пространственная сложность — . Если вы используете только несколько переменных для хранения промежуточных итогов, сложность — (дополнительная память).

Массивы (Arrays)

Массив — это структура данных, хранящая элементы одного типа в непрерывном блоке памяти. Это ключевое определение: непрерывный блок.

Доступ к памяти

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

Где — искомый адрес в памяти, — начальный адрес массива, — порядковый номер элемента, — размер одного элемента в байтах.

Операции с массивами

* Чтение/Запись по индексу: . Мы просто переходим по адресу. * Поиск элемента (без сортировки): . В худшем случае нужно проверить каждый элемент. * Вставка/Удаление в конец: (амортизированная сложность для динамических массивов). * Вставка/Удаление в середину или начало: . Это дорогая операция, так как требуется сдвинуть все последующие элементы, чтобы освободить или заполнить место.

!Сдвиг элементов массива при удалении элемента из середины

Динамические массивы

В Python (list), Java (ArrayList) и C++ (std::vector) массивы могут менять размер. Как это работает, если память должна быть непрерывной?

Когда место в выделенном блоке заканчивается, создается новый блок памяти (обычно в 1.5 или 2 раза больше), и все старые элементы копируются туда. Копирование занимает , но так как оно происходит редко, средняя (амортизированная) сложность добавления в конец остается .

Строки (Strings)

Строки во многих отношениях похожи на массивы символов, но имеют свои особенности в зависимости от языка программирования.

Неизменяемость (Immutability)

В Python, Java, Go и JavaScript строки неизменяемы. Это значит, что вы не можете просто заменить символ в строке. Любая операция модификации создает новую строку.

Рассмотрим опасный паттерн:

На каждой итерации создается новая строка, копирующая содержимое предыдущей. Сумма длин копируемых строк образует арифметическую прогрессию:

Где — общее количество скопированных символов, — количество итераций. Это приводит к сложности .

Решение: Используйте массив символов или специальные строители строк (StringBuilder в Java, list c последующим .join() в Python, strings.Builder в Go). Это снижает сложность до .

Техника двух указателей (Two Pointers)

Это один из самых популярных паттернов на собеседованиях в Яндекс при работе с массивами и строками. Суть метода заключается в использовании двух индексов (указателей), которые движутся по структуре данных по определенным правилам.

Сценарий 1: Встречное движение

Используется, когда нужно найти пару элементов в отсортированном массиве или проверить симметрию.

Пример: Проверка на палиндром. Нужно проверить, читается ли строка одинаково слева направо и справа налево.

Ставим указатель left на начало (0).

Ставим указатель right на конец (len - 1).

В цикле while left < right:

* Если символы равны, сдвигаем left вправо, right влево. * Если не равны — это не палиндром.

Сложность: , так как мы проходим каждый элемент один раз. Пространство: .

!Работа метода двух указателей при проверке палиндрома

Сценарий 2: Быстрый и медленный указатели (Черепаха и Заяц)

Используется для поиска циклов или середины списка, а также для операций "in-place" (на месте) в массивах.

Пример: Удаление дубликатов из отсортированного массива. Задача: удалить дубликаты, не используя дополнительную память, вернуть новую длину.

slow указывает на место, куда мы запишем следующий уникальный элемент.

fast бежит вперед и ищет уникальные элементы.

Если arr[fast] не равен arr[slow], мы увеличиваем slow и записываем туда arr[fast].

Этот алгоритм работает за по времени и по памяти, что является идеальным решением.

Итоги

* Big O позволяет оценить масштабируемость алгоритма. Стремитесь к , или . Избегайте на больших данных. * Массивы обеспечивают мгновенный доступ по индексу, но вставка и удаление из середины требуют . * Строки в большинстве языков неизменяемы. Конкатенация в цикле — частая ошибка, ведущая к . Используйте буферы. * Два указателя — мощная техника для оптимизации задач с до , особенно на отсортированных данных.

Хеш-таблицы, два указателя и скользящее окно: популярные методы оптимизации

На алгоритмических собеседованиях в Яндекс часто встречается ситуация: вы написали рабочее решение, оно проходит тесты на корректность, но интервьюер просит его оптимизировать. Чаще всего это означает, что ваше решение имеет сложность (квадратичную), а ожидается (линейная) или .

Переход от квадратичной сложности к линейной часто требует смены парадигмы: вместо перебора «всех со всеми» мы используем структуры данных для быстрого доступа или умные способы обхода массива. Три кита такой оптимизации — это хеш-таблицы, метод двух указателей (в продвинутом варианте) и метод скользящего окна.

Хеш-таблицы: обмен памяти на время

Хеш-таблица (в Python — dict, в C++ — std::unordered_map, в Java — HashMap) — это структура данных, которая позволяет искать, вставлять и удалять элементы в среднем за . Это самый мощный инструмент для устранения вложенных циклов.

Принцип работы

В основе лежит хеш-функция. Она преобразует ключ (например, строку или число) в индекс массива (бакета), где хранится значение.

Где — вычисленный индекс в массиве хранения, — хеш-функция, возвращающая целочисленный хеш ключа, — сам ключ, — оператор взятия остатка от деления, — размер массива (количество бакетов).

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

!Преобразование ключей в индексы и хранение значений

Классическая задача: Two Sum

Рассмотрим задачу, которая является «Hello World» в мире алгоритмов. Дан массив чисел nums и целевое число target. Нужно найти индексы двух чисел, сумма которых равна target.

Наивное решение (): Зафиксировать первое число и пробежать вложенным циклом по всем остальным в поисках пары.

Оптимизация с хеш-таблицей (): Мы проходим по массиву один раз. Для каждого числа x мы проверяем, есть ли в хеш-таблице число target - x. Если есть — пара найдена. Если нет — добавляем текущее число x и его индекс в таблицу.

Здесь мы обменяли память ( для хранения словаря) на скорость (время выполнения сократилось с квадратичного до линейного).

Метод скользящего окна (Sliding Window)

Этот метод применяется для задач, связанных с поиском подмассивов или подстрок, удовлетворяющих определенному условию. Вместо того чтобы перебирать все возможные подстроки (что часто ведет к или даже ), мы поддерживаем «окно», которое скользит по данным.

Окно определяется двумя указателями: левым () и правым (). Все элементы между ними составляют текущее окно.

Типы скользящего окна

Окно фиксированного размера. Расстояние между и постоянно. Мы сдвигаем оба указателя на 1 шаг вправо на каждой итерации.

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

!Динамика изменения границ окна [L, R при проходе по массиву]

Пример: Самая длинная подстрока без повторяющихся символов

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

Алгоритм:

Используем хеш-сет (множество) для отслеживания символов в текущем окне.

Двигаем вправо, добавляя символы в сет.

Если символ под уже есть в сете (дубликат), мы начинаем двигать вправо, удаляя символы из сета, пока дубликат не исчезнет.

На каждом шаге обновляем максимальную длину.

Почему это ?

Может показаться, что здесь из-за цикла while внутри for. Однако давайте посчитаем количество операций для каждого символа. Каждый символ добавляется в множество ровно один раз (когда движется ) и удаляется из множества не более одного раза (когда движется ).

Общее количество операций:

Где — общее количество операций с множеством, — длина строки. Так как константы отбрасываются, сложность алгоритма — .

Продвинутые два указателя

В предыдущей статье мы рассматривали два указателя для проверки палиндромов (движение навстречу). Рассмотрим более сложный сценарий, где решение требует жадной стратегии.

Задача: Container With Most Water

Дан массив высот height. Нужно найти две линии, которые вместе с осью X образуют контейнер, вмещающий наибольшее количество воды.

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

Где — площадь (объем воды), — высота левой стенки, — высота правой стенки, и — индексы правой и левой стенок соответственно.

Стратегия:

Ставим указатели на края массива (). Это дает максимальную ширину.

Считаем площадь.

Как увеличить площадь? Ширина () будет только уменьшаться. Значит, нам нужно попытаться найти более высокую стенку. Мы сдвигаем тот указатель, который указывает на меньшую высоту. Если мы сдвинем указатель с большей высотой, площадь гарантированно уменьшится (ширина меньше, а высота ограничена той же низкой стенкой).

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

Комбинирование методов

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

Задача: Найти все анаграммы строки p в строке s. Здесь мы используем окно фиксированного размера (равного длине p) и хеш-таблицу (или массив частот символов) для сравнения содержимого окна с эталоном.

> Знание паттернов важнее заучивания решений конкретных задач. Если вы видите задачу на поиск подстроки — думайте о скользящем окне. Если нужно найти пару элементов — думайте о хеш-таблице или двух указателях.

Итоги

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

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

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

Два указателя эффективны не только на отсортированных массивах, но и в задачах на оптимизацию площади/объема, где можно применить жадную логику отбрасывания заведомо неоптимальных вариантов.