Питання на співбесіді з алгоритмів і структур даних з відповідями

Приклади запитань

Кілька запитань із кожного рівня з правильною відповіддю й поясненням.

Алгоритми та структури даних · Junior

1. Що описує нотація Big O?

   Правильна відповідь: Як зростають час роботи чи пам'ять зі зростанням розміру вхідних даних

   Big O описує швидкість зростання: як змінюється вартість, коли росте n, без констант і молодших доданків. Про абсолютний час на конкретній машині вона нічого не каже: цикл O(n) на малих даних буває повільнішим за O(n²).

2. Чому O(2n + 10) записують просто як O(n)?

   Правильна відповідь: Бо константи й молодші доданки не змінюють швидкість зростання

   Big O описує форму зростання для великих n. Множення на 2 чи додавання 10 не змінює того, що вартість росте лінійно, тому їх відкидають. На практиці константи все одно важливі, для цього й існують бенчмарки.

3. Яка складність зростає найповільніше зі збільшенням n?

   Правильна відповідь: O(log n)

   Логарифм росте дуже повільно: подвоєння n додає лише один крок. Для мільйона елементів log₂ n приблизно 20. O(n) і O(n log n) зростають значно швидше.

4. Яка складність читання arr[i] з масиву в JavaScript?

   Правильна відповідь: O(1)

   Доступ за індексом виконується за сталий час: рушій обчислює, де лежить елемент, а не проходить масив. Це головна перевага масивів над зв'язними списками.

Алгоритми та структури даних · Middle

1. Як працює сортування злиттям?

   Правильна відповідь: Ділить масив навпіл, сортує кожну половину й зливає їх

   Сортування злиттям ділить масив до окремих елементів, а потім зливає відсортовані половини двома вказівниками. Воно O(n log n) у будь-якому разі й стабільне, але потребує O(n) додаткової пам'яті для злиття.

2. Який головний недолік сортування злиттям на масивах?

   Правильна відповідь: Потребує O(n) додаткової пам'яті для злиття

   Крок злиття пише в тимчасовий буфер. Час O(n log n) незалежно від даних, і класична реалізація стабільна. Для зв'язних списків злиття можна зробити без додаткового буфера.

3. Який найгірший випадок швидкого сортування і коли він трапляється?

   Правильна відповідь: O(n²), коли опорні раз у раз ділять масив нерівно

   Якщо опорний елемент завжди найменший чи найбільший (наприклад, перший елемент відсортованого масиву), кожне розбиття відокремлює лише один елемент. Випадковий опорний або медіана трьох роблять це малоймовірним; у середньому O(n log n).

4. Чому швидке сортування на практиці часто швидше за злиття, хоча в середньому обидва O(n log n)?

   Правильна відповідь: Воно сортує на місці й звертається до пам'яті послідовно

   Розбиття працює всередині масиву з доброю локальністю кешу й малими константами. Його найгірший випадок насправді гірший (O(n²)), а звичайна версія на місці нестабільна.

Алгоритми та структури даних · Senior

1. Чому алгоритм Дейкстри дає хибні результати з від'ємними вагами ребер?

   Правильна відповідь: Завершена вершина ще може скоротитися через від'ємне ребро

   Дейкстра вважає, що коли найближчу вершину взято з черги, жоден пізніший шлях не буде коротшим. Від'ємне ребро руйнує це припущення. Беллман-Форд працює з від'ємними вагами за O(V × E) і ще й знаходить від'ємні цикли.

2. Яку додаткову можливість має Беллман-Форд порівняно з Дейкстрою?

   Правильна відповідь: Працює з від'ємними вагами й знаходить від'ємні цикли

   Він релаксує всі ребра V - 1 разів; якщо V-й прохід ще покращує відстань, є від'ємний цикл. Ціна - O(V × E), значно повільніше за O((V + E) log V) у Дейкстри.

3. Чим A* відрізняється від алгоритму Дейкстри?

   Правильна відповідь: Він додає оцінку відстані, що лишилася

   A* упорядковує вершини за g + h: відома вартість плюс оцінка до цілі, наприклад відстань по прямій на мапі. Якщо h ніколи не переоцінює (допустима евристика), шлях лишається оптимальним, а вершин переглядається значно менше.

4. Яка складність Флойда-Воршелла і коли він доречний?

   Правильна відповідь: O(V³); для найкоротших шляхів між усіма парами на малих щільних графах

   Це три вкладені цикли по вершинах, що оновлюють dist[i][j] через кожну проміжну k. Простий і працює з від'ємними ребрами (без від'ємних циклів), але при V = 10 000 це вже 10¹² кроків.