Пошук, сортування, зв'язування

Пошук максимуму, мінімуму

Розділити проблему, вирішити підзадачі, об'єднати результати

Які кроки описують принцип 'divide and conquer' (розділяй і володарюй)?

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

Яка найгірша часовa складність quicksort (наприклад, при поганому виборі pivot)?

Послідовність чітко визначених кроків для розв'язання задачі

Тип даних у пам'яті комп'ютера

Формат збереження файлів на диску

Інструмент для малювання графіків

Тільки витрати на розробку

Час виконання та використана пам'ять

Тип мови програмування

За якими основними критеріями оцінюють ефективність алгоритму?

Точну кількість операцій на конкретному вході

Максимальний розмір пам'яті в байтах

Як росте кількість операцій при збільшенні розміру вхідних даних

Швидкість процесора, необхідну для алгоритму

Що показує нотація «Big O» (О-біг O)?

Яка з наведених складностей є константною?

Яка складність характерна для алгоритмів, що ділять проблему навпіл на кожному кроці (наприклад, бінарний пошук)?

Коли складність не залежить від розміру даних

Коли кожен елемент обробляється постійну кількість раз

Коли виконується факторіальна кількість операцій

Коли часову складність називають лінійною O(n)?

Рекурсія з підзадачами логарифмічного розміру

Використання хеш-таблиці

Вкладений цикл (цикл в циклі) над тими ж даними

Що зазвичай призводить до квадратичної складності O(n^2)?

Зростає надзвичайно швидко і стає нецільною навіть для малих n

Зростає повільніше за логарифмічну функцію

Як описують факторіальну складність O(n!)?

Ігноруються, оскільки не впливають на асимптотичний ріст

Конвертуються в логарифмічні терміни

Як поводяться константи при оцінці у Big O?

Яка часовa складність доступу до елемента масиву за індексом?

Яка амортизована складність додавання елемента в кінець динамічного масиву (push) у більшості реалізацій?

Яка складність вставки елемента у кінець масиву у найгіршому випадку (коли потрібно виділити нову пам'ять і скопіювати дані)?

Яка складність вставки елемента на початок масиву?

Статичний має фіксований безпосередньо виділений суміжний блок пам'яті, динамічний може змінювати розмір

Статичний працює тільки з рядками

Динамічний зберігається виключно на стеку

Статичний підтримує хешування під капотом

Чим відрізняється статичний масив від динамічного?

Масив, в якому всі елементи йдуть підряд і мають однотипні значення

Масив з пробілами (holes) між індексами

Масив, що зберігається у файлі

Масив, реалізований через зв'язаний список

Що таке «плотний» (dense) масив у контексті реалізації мов, наприклад JS?

По посиланню на спільну область пам'яті

За значенням, копіюючи самі дані

Завжди через серіалізацію

Через стекова перезапис

Як відбувається присвоєння примітивних типів (наприклад, чисел) між змінними?

Завжди копіюються повністю

Тільки їхні типи копіюються

За значенням як примітиви

За посиланням — копіюється адреса на область у купі

Як передаються об'єкти або масиви при присвоєнні між змінними?

Примітиви в купі, об'єкти на диску

Примітиви в базі даних, об'єкти в стеку

Примітиви в стеку, об'єкти — у купі (heap)

Де зазвичай зберігаються примітивні значення і де — об'єкти у пам'яті (спрощено)?

Яка складність лінійного пошуку (послідовного перебору) у масиві?

Масив повинен бути відсортований; O(log n)

Масив повинен мати парну кількість елементів; O(n^2)

Масив повинен бути в пам'яті GPU; O(1)

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

Функція без аргументів

Базовий випадок (умова виходу)

Щонайменше два рекурсивних виклики

Використання циклу всередині

Що обов'язково має бути у рекурсивної функції, щоб вона завершилась?

O(log n) незалежно від глибини

O(n) у випадку лінійної глибини рекурсії

Як впливає рекурсія на просторову складність при n рівнів викликів?

Тільки для сортування бульбашкою

Тільки для читання файлів

Тільки для однорідних масивів

Обходи дерев/графів і підходи 'divide and conquer' (розділяй і володарюй)

Для яких задач рекурсія зазвичай є природним вибором?

На кожному кроці знаходити мінімальний елемент і ставити його в початок

Періодично перемішувати елементи випадковим чином

Використовувати хеш-таблицю для сортування

Робити один прохід і завершуватися

Яка ідея сортування вибором (selection sort)?

Розбиває масив на два підмасиви і сортує їх окремо

Порівнює і обмінює сусідні елементи, щоб найбільші «спливали» вправо

Використовує хеш-функцію для впорядкування

Проводить вибір випадкового півоту і розподіл

Як працює bubble sort (пузиркова сортування)?

Яка середня часовa складність для bubble sort і selection sort?

Злиття двох відсортованих масивів без ділення

Лінійний пошук мінімуму

Вибір опорного елемента (pivot) і розбиття на частини менші/більші від pivot

Хешування і сортування по ключу

Який підхід використовує quicksort (сортування Хоара)?

Через сортування підряд і сортування по стовпцях

З використанням бінарного дерева і хеш-таблиці

З розбиттям на нові підмасиви (конкатенація) і in-place реалізація через два вказівники (partition)

Через графову модель і через стек

Які два загальні варіанти реалізації quicksort згадуються найчастіше?

Яка середня часовa складність quicksort?

Selection sort (сортування вибором)

Який із наведених алгоритмів сортування зазвичай є стабільним за замовчуванням?

Коли кожна операція завжди має однакову вартість

Сумарна вартість операцій ділиться на їх кількість, даючи середню вартість на операцію

Повна завадність операцій через кеш-пам'ять

Спосіб визначення складності рекурсивних функцій

Що таке амортизована складність у контексті динамічних масивів?

Яка складність вставки нового елемента на початок пов'язного списку (маючи вказівник на голову)?

Яка складність доступу до k-го елемента у однозв'язному списку?

Зменшення пам'яті на вказівники

Швидший випадковий доступ до елементів

Автоматичну сортування

Можливість двосторонньої навігації і O(1) видалення за наявності вказівника на вузол

Що дає двусвязний список у порівнянні з однозв'язним?

Сортування за пріоритетом

Яким принципом керується черга (queue)?

Яким принципом керується стек (stack)?

Чергова структура тільки для FIFO

Система кешування даних

Колекція, що дозволяє додавати/видаляти елементи з обох кінців

Вершини (nodes) та ребра (edges)

З яких двох основних компонентів складається граф?

Список для дуже щільних графів, матриця для розріджених

Матриця лише для неорієнтованих графів

Список тільки для взважених графів

Список підходить для розріджених графів, матриця — для щільних (dense) графів

Яка пара представлень графа: список суміжності і матриця суміжності, для яких умов вони підходять краще?

Яка структура даних використовується при реалізації BFS (пошук в ширину)?

Яка структура або метод використовується для реалізації DFS (пошук в глибину)?

BFS завжди працює для зважених графів

BFS знаходить найкоротший шлях у невзваженому графі

BFS завжди потребує O(n^3) часу

BFS не може обходити циклічні графи

Яке твердження про BFS і найкоротший шлях є вірним?

Bellman-Ford тільки для від'ємних циклів

Який алгоритм призначений для пошуку найкоротшого шляху у зваженому графі з невід'ємними вагами ребер?

Яка часовa складність обходу графа (BFS або DFS) при представленні списком суміжності?

Який обсяг пам'яті займає матриця суміжності для графа з V вершинами?

Один цикл із хеш-операціями

Вкладені цикли (дві петлі)

Тільки рекурсія без циклів

Використання декількох стеків одночасно

При обході двовимірної матриці (матриці) якою технікою зазвичай користуються?

Коли потрібен швидкий випадковий доступ до елементів

Коли працюємо з великими числовими операціями

Коли дані мають бути розташовані в суміжному блоці пам'яті

Коли часті вставки/видалення елементів та змінний розмір структури

Коли доцільніше використовувати зв'язаний список замість масиву?

Яка структура даних найприродніша для представлення стеку викликів функцій та рекурсії?

Питання 48 з 50