Перейти до вмісту
Підготовка до співбесіди

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

Як оцінити складність коду, які структури даних і алгоритми треба тримати в голові та як розв’язувати задачу перед інтерв’юером. Live coding перевіряє не пам’ять на алгоритми, а вміння міркувати вголос, обрати прийом і чесно оцінити своє рішення.

Перед цією темою: Колекції та LINQ.

Junior+

Що таке O-нотація і як оцінити складність коду?

Section titled “Що таке 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+

Які структури даних треба знати і для чого кожна?

Section titled “Які структури даних треба знати і для чого кожна?”
Відповідь

Що це

  • Стек — 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+

Які алгоритми сортування й пошуку варто знати?

Section titled “Які алгоритми сортування й пошуку варто знати?”
Відповідь

Що це

  • Лінійний пошук перевіряє елементи по черзі: 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+

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

Section titled “Рекурсія й динамічне програмування: як розпізнати й розв’язати задачу?”
Відповідь

Що це

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

  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 і які прийоми трапляються найчастіше?

Section titled “Як розв’язувати задачу на 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;
}
Джерела