Перейти к содержимому
Подготовка к собеседованию

Алгоритмы и live coding

Как оценить сложность кода, какие структуры данных и алгоритмы нужно держать в голове и как решать задачу перед интервьюером. Live coding проверяет не память на алгоритмы, а умение рассуждать вслух, выбрать приём и честно оценить своё решение.

Перед этой темой: Коллекции и LINQ.

Junior+

Что такое O-нотация и как оценить сложность кода?

Заголовок раздела «Что такое O-нотация и как оценить сложность кода?»
Ответ

Что это

O(f(n)) показывает форму роста, а не секунды: во сколько раз вырастет работа, если вход вырастет. Увеличили n в 10 раз — O(n) работает в 10 раз дольше, O(n²) — в 100 раз.

Типичные классы

Сложность Название Пример
O(1) константная элемент массива по индексу
O(log n) логарифмическая бинарный поиск
O(n) линейная один проход по массиву
O(n log n) линейно-логарифмическая сортировка Array.Sort
O(n²) квадратичная все пары элементов
O(2^n) экспоненциальная перебор всех подмножеств

Как оценить

  1. Цикл по n элементам — n × стоимость тела.
  2. Вложенные циклы перемножаются: два по n — O(n²).
  3. Последовательные блоки складываются, остаётся старший: O(n) + O(n²) = O(n²).
  4. Константы отбрасываются: два прохода — O(2n) = O(n).
  5. Диапазон делится пополам на каждом шаге — O(log n).

Частая ошибка

Считать код без вложенных циклов линейным. list.Insert(0, x) или s += x в цикле сами стоят O(n), и весь цикл — O(n²).

Как устроено

Время и память оценивают отдельно. Память — дополнительная, без самого входа: проход с HashSet<T> стоит O(n) памяти, двойной цикл — O(1).

Случай Что значит Пример
Худший граница для любого входа quicksort на неудачных опорных — O(n²)
Средний ожидание на типичном входе поиск в хеш-таблице — O(1)
Амортизированный среднее на серии операций List<T>.Add — O(1)

Амортизированная оценка — не про вероятность. Это гарантия для любой серии: редкие дорогие операции оплачены многими дешёвыми.

Ловушки

  • Скрытая стоимость вызова. string += копирует строку, List<T>.Remove сдвигает элементы — каждый вызов O(n).
  • Два параметра. Цикл по n заказам и вложенный по m товарам — O(n·m), а не O(n²).
  • Рекурсия тратит память. Глубина d занимает O(d) стека, даже без коллекций.
  • Повторный перебор. Count() у ленивого IEnumerable<T> внутри цикла каждый раз проходит последовательность заново.

Правило

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

Под капотом

  • O — верхняя граница, Ω — нижняя, Θ — точная. Сортировка сравнениями в худшем случае не быстрее Ω(n log n).
  • Рекурсию оценивают рекуррентным соотношением. Бинарный поиск: T(n) = T(n/2) + O(1), это O(log n). Mergesort: T(n) = 2T(n/2) + O(n), это O(n log n).
  • Наивная рекурсия Фибоначчи порождает экспоненциальное число вызовов: каждая ветвь делится на две.

Цена

  • O скрывает константы: аллокации, промахи кеша процессора, вызовы делегатов.
  • На малых n константы решают. Поэтому Array.Sort сортирует участки до 16 элементов вставками, хотя это O(n²).

Компромиссы

  • Время против памяти. HashSet<T> превращает O(n²) в O(n) ценой O(n) памяти. Предвычисление — индекс, префиксные суммы — переносит работу в подготовку.
  • Худший случай на чужом вводе. Злоумышленник подбирает вход под худший случай: коллизии хешей, катастрофический откат регулярного выражения. Для регулярок с .NET 7 есть RegexOptions.NonBacktracking с линейным временем по длине входа.

Как проверить в проде

BenchmarkDotNet с [Params] на нескольких n показывает форму роста: время выросло в 4 раза при удвоении n — квадратичный алгоритм. Горячий метод находят в трассе dotnet-trace или PerfView.

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

Пример
int[] data = [3, 8, 1, 9, 4, 8];


Console.WriteLine(HasDuplicatesPairs(data));  // True
Console.WriteLine(HasDuplicatesHashSet(data)); // True
Console.WriteLine(HasDuplicatesSorted(data));  // True


// Все пары: время O(n²), память O(1)
static bool HasDuplicatesPairs(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++) // n(n-1)/2 сравнений
            if (a[i] == a[j]) return true;
    return false;
}


// Один проход: время O(n) в среднем, память O(n)
static bool HasDuplicatesHashSet(int[] a)
{
    var seen = new HashSet<int>();
    foreach (int x in a)
        if (!seen.Add(x)) return true; // Add вернёт false для повтора
    return false;
}


// Сортировка копии и соседи: время O(n log n), память O(n) на копию
static bool HasDuplicatesSorted(int[] a)
{
    int[] copy = [.. a];
    Array.Sort(copy);
    for (int i = 1; i < copy.Length; i++)
        if (copy[i] == copy[i - 1]) return true;
    return false;
}

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

Источники
Junior+

Какие структуры данных нужно знать и для чего каждая?

Заголовок раздела «Какие структуры данных нужно знать и для чего каждая?»
Ответ

Что это

  • Стек — LIFO: последним положили, первым взяли. Очередь — FIFO: первым пришёл, первым ушёл.
  • Дерево поиска хранит ключи по порядку, куча всегда знает минимальный элемент.
  • Граф — вершины и рёбра: дороги, зависимости, связи между людьми.

Как пользоваться

Структура Тип .NET Типичная задача
Массив T[], List<T> данные по индексу
Стек Stack<T> скобки, отмена действий, обход в глубину
Очередь Queue<T> задачи по порядку, обход в ширину
Хеш-таблица Dictionary, HashSet<T> поиск, подсчёт, дубли
Дерево поиска SortedSet<T>, SortedDictionary порядок, минимум, диапазоны
Куча PriorityQueue<TElement, TPriority> задачи по приоритету, top-k

Частая ошибка

Писать свою структуру на собеседовании, когда есть готовая. Интервьюер обычно ждёт Stack<T> или PriorityQueue, а не самописный класс, если не просит иначе.

Как устроено

Структура Поиск Вставка и удаление
Массив, List<T> по индексу O(1), по значению O(n) в конец O(1) аморт., в середину O(n)
LinkedList<T> O(n) O(1) по известному узлу
Stack<T>, Queue<T> только вершина или голова, O(1) O(1) аморт.
Dictionary, HashSet<T> O(1) в среднем O(1) в среднем
SortedSet<T>, SortedDictionary O(log n) O(log n)
PriorityQueue минимум O(1) O(log n)

Дерево и куча

  • Дерево поиска. Поиск спускается от корня: меньше — налево, больше — направо. Стоимость равна высоте дерева. Без балансировки отсортированный ввод вытягивает дерево в список и даёт O(n), поэтому в .NET используется сбалансированное красно-чёрное дерево.
  • Куча. Дерево в массиве, где родитель не больше потомков, поэтому минимум лежит в корне. Вставка поднимает элемент вверх, извлечение опускает новый корень вниз — O(log n).

Ловушки

  • PriorityQueue не сохраняет порядок вставки при равных приоритетах, а UnorderedItems перебирает элементы не по приоритету.
  • Stack<T> перебирается от вершины, а не в порядке добавления.
  • Устройство Dictionary и цена хеширования — в теме Коллекции и LINQ.

Правило

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

Под капотом

  • PriorityQueue<TElement, TPriority> — 4-арная мин-куча на массиве: дерево ниже двоичного, а дети одного узла лежат рядом в памяти.
  • Операции «изменить приоритет» нет. Remove с .NET 9 ищет элемент линейно, O(n).
  • Граф хранят списками смежности, Dictionary<int, List<int>>: память O(V + E). Матрица смежности bool[,] проверяет ребро за O(1), но занимает O(V²) — она для плотных графов.

Цена

  • Узловые структуры (LinkedList<T>, SortedSet<T>) создают объект на элемент: аллокация, заголовок, ссылки, разброс по куче.
  • Массивные структуры (List<T>, Queue<T>, PriorityQueue) хранят элементы подряд и лучше попадают в кеш процессора.

Компромиссы

Задача Вариант Цена
top-k из n PriorityQueue размера k O(n log k) вместо O(n log n)
Дейкстра PriorityQueue с дубликатами лишние записи, пропуск устаревших
Дейкстра с удалением SortedSet пар (расстояние, вершина) O(log n) на удаление, но узлы
Редкие вставки в упорядоченное отсортированный List<T> и BinarySearch вставка O(n), зато непрерывная память

Как проверить в проде

Число узловых объектов видно в dotnet-gcdump. Выбор между двумя структурами на реальных объёмах подтверждают BenchmarkDotNet с [MemoryDiagnoser].

Итог: асимптотика задаёт выбор структуры, а представление в памяти и недостающие операции определяют, как она поведёт себя в проде.

Пример
// Куча: первым выходит наименьший приоритет
var tasks = new PriorityQueue<string, int>();
tasks.Enqueue("deploy", 2);
tasks.Enqueue("hotfix", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine(tasks.Dequeue()); // hotfix — O(log n)


// Дерево поиска: порядок, минимум и диапазоны
var prices = new SortedSet<int> { 50, 10, 40, 20, 30 };
Console.WriteLine(prices.Min);                                      // 10
Console.WriteLine(string.Join(",", prices.GetViewBetween(15, 40))); // 20,30,40


// Стек: проверка скобок — классическая задача
Console.WriteLine(IsBalanced("([]{})")); // True
Console.WriteLine(IsBalanced("(]"));     // False


static bool IsBalanced(string s)
{
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else if (stack.Count == 0 || stack.Pop() != Opening(c)) return false;
    }
    return stack.Count == 0; // незакрытые скобки — тоже ошибка
}


static char Opening(char close) => close switch { ')' => '(', ']' => '[', _ => '{' };
Источники
Middle+

Какие алгоритмы сортировки и поиска стоит знать?

Заголовок раздела «Какие алгоритмы сортировки и поиска стоит знать?»
Ответ

Что это

  • Линейный поиск проверяет элементы по очереди: O(n), работает на любом массиве.
  • Бинарный поиск требует отсортированного массива и делит диапазон пополам: O(log n). Миллион элементов — не больше 20 шагов.

Как работает бинарный поиск

  1. Границы: lo = 0, hi = n - 1.
  2. Середина: mid = lo + (hi - lo) / 2.
  3. a[mid] == target — нашли.
  4. a[mid] < target — ищем правее: lo = mid + 1. Иначе левее: hi = mid - 1.
  5. Повторяем, пока lo <= hi. Границы разошлись — элемента нет.

Как пользоваться

  • Сортировка: Array.Sort(array), list.Sort(), items.OrderBy(x => x.Name).
  • Поиск: Array.BinarySearch и List<T>.BinarySearch. Если элемента нет, они возвращают отрицательное число, а ~result — индекс, куда его вставить.

Частая ошибка

Вызвать бинарный поиск по неотсортированному массиву. Исключения не будет — просто неверный ответ.

Как устроено

Алгоритм Время Память и стабильность
Вставками O(n²), почти O(n) на почти отсортированных O(1), стабильная
Quicksort O(n log n) в среднем, O(n²) в худшем O(log n) стека, нестабильная
Слиянием O(n log n) всегда O(n), стабильная
Пирамидальная O(n log n) всегда O(1), нестабильная

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

Что использует .NET

Метод Алгоритм Стабильность
Array.Sort, List<T>.Sort, Span<T>.Sort() introsort на месте нет
OrderBy, ThenBy (LINQ) сортировка в буфере да

Ловушки

  • Границы поиска. Смешали lo < hi с hi = mid - 1 или lo <= hi с hi = mid — пропуск элемента или бесконечный цикл.
  • Дубли. Array.BinarySearch возвращает индекс одного из равных, не обязательно первого. Для первого вхождения нужен вариант «нижняя граница».
  • Компаратор a - b. Переполняется на больших числах. Используйте a.CompareTo(b).

Правило

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

Под капотом

Introsort в Array.Sort, по документации:

  1. Участок до 16 элементов — сортировка вставками.
  2. Число разбиений превысило 2·log n — пирамидальная сортировка.
  3. Иначе — quicksort.

Так quicksort защищён от худшего случая O(n²). .NET Framework 4 и раньше использовали чистый quicksort.

Цена

  • Array.Sort для примитивов без компаратора не вызывает делегат на каждое сравнение. С Comparison<T> каждое сравнение — косвенный вызов.
  • OrderBy копирует элементы в буфер, вычисляет массив ключей и сортирует индексы — O(n) дополнительной памяти.
  • Нижняя граница Ω(n log n) действует только для сортировок сравнением. Подсчётом или поразрядно целые числа из малого диапазона сортируют за O(n + k).

Компромиссы

  • Полная сортировка или частичная. Нужны k минимальных — куча за O(n log k) дешевле сортировки за O(n log n).
  • Сортировка или хеш. Разовый поиск по неотсортированным данным — линейный проход. Много поисков — сортировка плюс бинарный поиск или HashSet<T>.
  • Данные не помещаются в память. Внешняя сортировка слиянием: сортируют куски и сливают. Так сортирует и СУБД, когда не хватает памяти.

Как проверить в проде

BenchmarkDotNet с [MemoryDiagnoser] на реальных данных сравнивает Array.Sort и OrderBy: разница в аллокациях видна сразу.

Итог: introsort даёт O(n log n) в худшем случае без буфера ценой стабильности, и выбор метода сортировки — это выбор между стабильностью и памятью.

Пример
int[] sorted = [1, 3, 5, 7, 9, 11];


Console.WriteLine(BinarySearch(sorted, 7));       // 3
Console.WriteLine(BinarySearch(sorted, 4));       // -1
Console.WriteLine(BinarySearch([], 4));           // -1 — пустой массив
Console.WriteLine(Array.BinarySearch(sorted, 4)); // -3: ~(-3) = 2 — сюда вставить 4


static int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;     // ищем в [lo, hi] включительно
    while (lo <= hi)                   // <=, иначе пропустим последний кандидат
    {
        int mid = lo + (hi - lo) / 2;  // не (lo + hi) / 2: переполнение int
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1; // mid уже проверен
        else hi = mid - 1;
    }
    return -1;
}
Стабильность сортировки
Order[] orders = [new(1, "B"), new(2, "A"), new(3, "B"), new(4, "A")];


// OrderBy стабилен: при равных Customer сохраняется исходный порядок
var byCustomer = orders.OrderBy(o => o.Customer).Select(o => o.Id);
Console.WriteLine(string.Join(" ", byCustomer)); // 2 4 1 3


// Array.Sort нестабилен: для гарантии добавляем второй ключ
var copy = orders.ToArray();
Array.Sort(copy, (x, y) =>
{
    int byName = string.CompareOrdinal(x.Customer, y.Customer);
    return byName != 0 ? byName : x.Id.CompareTo(y.Id);
});
Console.WriteLine(string.Join(" ", copy.Select(o => o.Id))); // 2 4 1 3


record Order(int Id, string Customer);

На четырёх элементах Array.Sort сортирует вставками и случайно сохранит порядок, но на больших массивах гарантии нет — поэтому второй ключ.

Источники
Middle+

Рекурсия и динамическое программирование: как распознать и решить задачу?

Заголовок раздела «Рекурсия и динамическое программирование: как распознать и решить задачу?»
Ответ

Что это

Рекурсивная функция состоит из двух частей:

  1. Базовый случай — ответ без рекурсии: Fib(0) = 0, Fib(1) = 1.
  2. Рекурсивный шаг — сведение к меньшей задаче: Fib(n) = Fib(n - 1) + Fib(n - 2).

Зачем динамическое программирование

Наивная Fib(n) считает одно и то же много раз: Fib(5) вызывает Fib(3) дважды, а Fib(2) — трижды. Число вызовов растёт экспоненциально, и Fib(50) требует десятков миллиардов вызовов.

Как пользоваться

Запоминайте ответ подзадачи в словаре или массиве и перед вычислением проверяйте, нет ли его. Тогда Fib(50) — это 50 вычислений.

Частая ошибка

Забыть базовый случай или сделать шаг, который не уменьшает задачу. Рекурсия станет бесконечной, и StackOverflowException завершит процесс — try/catch его не поймает.

Как устроено

Каждый вызов кладёт в стек кадр с аргументами и локальными переменными. Глубина d — это O(d) памяти, а размер стека ограничен: по документации .NET по умолчанию 1,5 МБ в Windows и macOS и 8 МБ в Linux.

Как решать задачу ДП

  1. Состояние. Что значит dp[s]: например, минимум монет для суммы s.
  2. Переход. dp[s] = min(dp[s - c] + 1) по всем монетам c.
  3. База. dp[0] = 0.
  4. Порядок и ответ. Суммы от 0 до amount, ответ — dp[amount].
  5. Сложность. Состояния × переход: O(amount · k) для k монет.

Когда что выбирать

Подход Плюс Минус
Мемоизация (сверху вниз) код повторяет формулу, считает только нужные состояния рекурсия и её глубина, накладные расходы словаря
Табуляция (снизу вверх) без рекурсии, легко сжать память нужно знать порядок заполнения

Классика

  • Фибоначчи — O(n) времени, O(1) памяти при табуляции.
  • Размен монет — O(amount · k).
  • Наибольшая общая подпоследовательность (LCS) двух строк длиной n и m: если символы равны, dp[i, j] = dp[i - 1, j - 1] + 1, иначе max(dp[i - 1, j], dp[i, j - 1]). O(n·m).

Ловушки

Жадный выбор не всегда оптимален. Монеты 1, 3 и 4, сумма 6: жадно 4 + 1 + 1 — три монеты, а оптимально 3 + 3 — две.

Под капотом

  • Кадр стека держит аргументы, локальные переменные и адрес возврата. StackOverflowException нельзя перехватить: процесс завершается.
  • RuntimeHelpers.EnsureSufficientExecutionStack() выбрасывает обычное InsufficientExecutionStackException, если стека осталось мало. Так защищают рекурсивные обходы деревьев выражений и разборщики.
  • Компилятор C# не помечает хвостовые вызовы. JIT иногда оптимизирует их сам, но рассчитывать на это нельзя.

Цена

  • Мемоизация словарём — хеширование и аллокации. Если состояние — небольшие целые, массив быстрее.
  • Таблица LCS занимает O(n·m) памяти. Если нужна только длина, хватит двух строк: O(min(n, m)).

Компромиссы

  • Рекурсия против явного стека. Рекурсия читаемее для деревьев и обхода в глубину. Если глубина зависит от входа — вложенный JSON, длинная цепочка ссылок, — нужен Stack<T> и цикл.
  • Мемоизация против табуляции. Мемоизация проще написать на собеседовании из рекурсивной формулы. Табуляция безопаснее и позволяет сжать память.

Как проверить в проде

Переполнение стека завершает процесс без записи в обычный лог. Рантайм печатает в stderr Stack overflow. и повторяющиеся кадры, а крэш-дамп (DOTNET_DbgEnableMiniDump=1) открывают в dotnet-dump и смотрят стек.

Итог: ДП — это состояния и переходы, а в .NET рекурсию по чужим данным заменяют циклом, потому что переполнение стека не ловится.

Фибоначчи: мемоизация и табуляция
Console.WriteLine(FibMemo(50, new Dictionary<int, long>())); // 12586269025
Console.WriteLine(FibTable(50));                             // 12586269025


// Сверху вниз: рекурсия плюс кеш, O(n) времени и O(n) памяти
static long FibMemo(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;                               // базовый случай
    if (memo.TryGetValue(n, out long cached)) return cached;
    return memo[n] = FibMemo(n - 1, memo) + FibMemo(n - 2, memo);
}


// Снизу вверх: без рекурсии, O(n) времени и O(1) памяти
static long FibTable(int n)
{
    long prev = 0, cur = 1;
    for (int i = 0; i < n; i++)
        (prev, cur) = (cur, prev + cur);
    return prev;
}
Размен монет
Console.WriteLine(MinCoins([1, 5, 10, 25], 63)); // 6: 25 + 25 + 10 + 1 + 1 + 1
Console.WriteLine(MinCoins([1, 3, 4], 6));       // 2: 3 + 3, а жадно было бы 3 монеты
Console.WriteLine(MinCoins([2], 3));             // -1: набрать нельзя


// dp[s] — минимум монет для суммы s; O(amount · k) времени, O(amount) памяти
static int MinCoins(int[] coins, int amount)
{
    var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;                                    // база: сумма 0 — ноль монет
    for (int s = 1; s <= amount; s++)
        foreach (int c in coins)
            if (c <= s && dp[s - c] != int.MaxValue)
                dp[s] = Math.Min(dp[s], dp[s - c] + 1);
    return dp[amount] == int.MaxValue ? -1 : dp[amount];
}
Источники
Senior+

Как решать задачу на live coding и какие приёмы встречаются чаще всего?

Заголовок раздела «Как решать задачу на live coding и какие приёмы встречаются чаще всего?»
Ответ

Что это

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

Как пользоваться

  1. Уточните условие. Размер входа, отрицательные числа, дубли, пустой вход, что вернуть, если ответа нет.
  2. Разберите пример руками. Это проверка, что задача понята верно.
  3. Назовите наивное решение и его сложность, даже если оно медленное.
  4. Улучшите. Найдите повторяющуюся работу и уберите её.
  5. Напишите код с понятными именами.
  6. Проверьте вслух: пример, пустой вход, один элемент, дубли.

Частая ошибка

Молча писать код сразу после условия. Если решение зайдёт в тупик, интервьюеру нечем вам помочь, а оценивать ему нечего.

Когда что выбирать

Признак в условии Приём Сложность
Пара, дубль, частоты хеш-таблица O(n), память O(n)
Отсортированный массив, пара, палиндром два указателя O(n), память O(1)
Самый длинный или короткий подотрезок скользящее окно O(n)
Много запросов суммы на отрезке префиксные суммы O(n) подготовка, O(1) запрос
Кратчайший путь без весов, сетка BFS O(V + E)
Связность, все пути, перебор DFS O(V + E)
Порядок с зависимостями топологическая сортировка O(V + E)
k наибольших PriorityQueue размера k O(n log k)

Разбор: две суммы

Найти индексы двух чисел с суммой target. Наивно — все пары, O(n²). Ускорение: для каждого x искать target - x среди уже увиденных чисел в Dictionary. Итого O(n) времени и O(n) памяти.

Разбор: самая длинная подстрока без повторов

Окно [left, right] расширяется вправо. Если символ уже есть в окне, left прыгает за его прошлую позицию. Каждый индекс сдвигается не больше одного раза — O(n).

Ловушки

  • Переполнение суммы: суммы большого массива int считают в long.
  • BFS и DFS без отметки посещённых вершин зацикливаются на графе с циклом.
  • Изменение коллекции во время foreach даёт InvalidOperationException.

Правило

Сначала узнайте приём по признаку в условии, потом пишите код.

Как говорить во время решения

  • Озвучивайте допущения: «считаю, что вход помещается в память».
  • Называйте сложность варианта до того, как писать код.
  • Сначала план из двух-трёх фраз, потом код.
  • Застряли — скажите, что рассматриваете, и спросите про ограничения.
  • После кода пройдите пример по строкам, как отладчик.

Компромиссы

  • Время против памяти. Хеш-таблица даёт O(n) и O(n) памяти. Сортировка плюс два указателя — O(n log n), но O(1) дополнительной памяти, если вход можно менять.
  • Изменение входа. Сортировка на месте портит массив вызывающего — спросите, можно ли.
  • Рекурсия против явного стека. Рекурсивный DFS короче, а Stack<T> выдержит глубокий граф.

Разбор: топологическая сортировка

Алгоритм Кана:

  1. Считаем входящую степень каждой вершины.
  2. Вершины без входящих рёбер кладём в очередь.
  3. Снимаем вершину, добавляем в ответ, уменьшаем степень её соседей. Обнулилась — в очередь.
  4. Если в ответе не все вершины — в графе цикл.

Сложность — O(V + E). Так упорядочивают шаги сборки, миграции и задачи с зависимостями.

Как проверить решение

  • Краевые случаи: пустой вход, один элемент, все элементы равны, отрицательные числа, максимальный n.
  • Оценка по ограничениям: при n = 10^5 решение O(n²) — это 10^10 операций, секунды вместо миллисекунд.

Итог: на сеньорском уровне оценивают не только алгоритм, но и то, как вы ведёте решение: допущения, компромиссы и самопроверку.

Хеш-таблица и скользящее окно
Console.WriteLine(string.Join(",", TwoSum([2, 7, 11, 15], 9))); // 0,1
Console.WriteLine(LongestUniqueRun("abcabcbb"));                // 3: "abc"
Console.WriteLine(LongestUniqueRun(""));                        // 0 — краевой случай


// Для каждого x ищем target - x среди увиденных: O(n) времени, O(n) памяти
static int[] TwoSum(int[] nums, int target)
{
    var indexOf = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
    {
        if (indexOf.TryGetValue(target - nums[i], out int j)) return [j, i];
        indexOf[nums[i]] = i;
    }
    return [];
}


// Окно [left, right] без повторов: O(n), каждый индекс сдвигается один раз
static int LongestUniqueRun(string s)
{
    var lastSeen = new Dictionary<char, int>();
    int best = 0, left = 0;
    for (int right = 0; right < s.Length; right++)
    {
        if (lastSeen.TryGetValue(s[right], out int prev) && prev >= left)
            left = prev + 1;                      // перескакиваем за повтор
        lastSeen[s[right]] = right;
        best = Math.Max(best, right - left + 1);
    }
    return best;
}
Два указателя и префиксные суммы
int[] sorted = [1, 2, 4, 7, 11, 15];
Console.WriteLine(PairWithSum(sorted, 15)); // (4, 11)
Console.WriteLine(PairWithSum(sorted, 100) is null); // True — пары нет


int[] sales = [3, 1, 4, 1, 5, 9];
var prefix = new int[sales.Length + 1];      // prefix[i] — сумма первых i элементов
for (int i = 0; i < sales.Length; i++)
    prefix[i + 1] = prefix[i] + sales[i];
Console.WriteLine(prefix[5] - prefix[2]);    // 10: sales[2] + sales[3] + sales[4] за O(1)


// Отсортированный массив, указатели с двух концов: O(n) времени, O(1) памяти
static (int, int)? PairWithSum(int[] a, int target)
{
    int left = 0, right = a.Length - 1;
    while (left < right)
    {
        int sum = a[left] + a[right];
        if (sum == target) return (a[left], a[right]);
        if (sum < target) left++;            // нужна сумма больше
        else right--;                        // нужна сумма меньше
    }
    return null;
}
Топологическая сортировка (алгоритм Кана)
// Ребро a → b: шаг a должен выполниться раньше b
var graph = new Dictionary<string, string[]>
{
    ["restore"] = ["build"],
    ["build"] = ["test", "pack"],
    ["test"] = ["deploy"],
    ["pack"] = ["deploy"],
    ["deploy"] = [],
};
Console.WriteLine(string.Join(" ", TopoSort(graph))); // restore build test pack deploy


// O(V + E): BFS по вершинам, у которых не осталось входящих рёбер
static List<string> TopoSort(Dictionary<string, string[]> graph)
{
    var inDegree = graph.Keys.ToDictionary(v => v, _ => 0);
    foreach (var targets in graph.Values)
        foreach (var t in targets) inDegree[t]++;


    var queue = new Queue<string>(inDegree.Where(p => p.Value == 0).Select(p => p.Key));
    var order = new List<string>();
    while (queue.Count > 0)
    {
        var v = queue.Dequeue();
        order.Add(v);
        foreach (var t in graph[v])
            if (--inDegree[t] == 0) queue.Enqueue(t);
    }
    if (order.Count != graph.Count) throw new InvalidOperationException("Cycle detected");
    return order;
}
Источники