DSA Flashcards
Какво е алгоритъм?
Последователност от инструкции, използвани за разрешаване на даден проблем.
Какво е алгоритмична сложност?
Колко време и памет са нужни за определяне на сложността на алгоритъма и неговото приключване.
Какво е евристика (heuristic)? *bonus
Евристиката е подход за решаване на проблем, който не ни гарантира правилен отговор, но близък.
Как се прогнозира ефикасността на алгоритъм, когато данните нарастват? Какво е Big O Notation?
Класифицираме проблема спрямо ресурсите, които използва, а сложността му е количеството ресурси нужни за изпълнението му (време, памет). Измерваме я чрез Big O Notation.
Big O Notation - класифицира алгоритъма според времето и паметта използвани за изпълнение. Показва как растат броя операции при нарастане на инпута.
Какво е масив и как се съхраняват елементи? Какви са сложностите на обичайните операции?
Линейна структура от данни, която съхранява всякакъв тип данни, има нулева индексация, елементите се съхраняват последователно в паметта, има вградени функции.
Сложности:
.add(item): O(1) -> добавя елемент в края
.get(index): O(1) -> взима и връща елемент от подаден индекс
.insert(index, item): O(n) -> добавяне на елемент на индекс
.remove(index): O(n) -> ппремахва елемент на индекс
.size() : O(1) -> връща броя елементи в масива
Какво са Linked Lists и Doubly Linked Lists и как се съхраняват елементи? Какви са сложностите на обичайните операции на Linked List?
Linked Lists - линейна структура от данни, елементите се съхраняват под формата на нодове. Едната част държи value, другата държи връзка към следважия node - next / null (ако е последен); Не се съхраняват поседователно в паметта.
Сложности:
.addFirst(value): O(1) -> създава node в началото;
.removeFirst(): O(1) -> маха пъривя node;
.insertAfter(node, item): O(1) -> създава нов node след подаден node;
.removeAfter(node): O(1) -> премахва node след подадения node;
.find(value): O(n) -> връща node с неговия value;
Doubly Linked Lists - същото като LL, имаме допълнителен поделемент, който сочи към предишния node.
DLL е верига от нодове, където всеки сочи към предишния и следважия нод.
Какво е dynamic array?
В JS всички масиви са динамични.
Автоматично си променя размера, създаваме го по 3 начина:
literal - const array = [];
default constructor = const array = new Array();
default + parameters = const array = new Array(‘Hi’, ‘1’, 3);
Какво е ‘stack’ и за какво се използва? Какви сложности имат базовите операции?
Линейна структура от данни, First-In/Last-Out (FILO). Нов елемент се добавя само в единия край и премахването е от същия край. Реализира се с масив или LL. Пример за това е купчина чинии, само която е най-отгоре, можем да махнем нея.
Прилага се в backtracking, memory management, expression conversion (DFS Trees - pre-; post-; in-order);
Сложности:
.push(value): O(1) -> добавя най-отгоре на стака
.pop(): O(1) -> връща стойност и я премахва от топа на стака
.peek(): O(1) - връща стойноста на топа без да го премахва
Какво е ‘queue’ и за какво се използва? Какви сложности имат базовите операции?
Линейна структура от данни, First-In/First-Out (FIFO). Който е влязъл първи, излиза първи, реализира се с масив или LL.
Прилага се в BFS обхождане на дървета, рутери, музикални плейлисти, управление на заявки към общ ресурс (CPU, HDD).
Сложности:
.enqueue(value): O(1) -> добавя елемент в края queue
.dequeue(): O(1) -> връща стойност и премахва в началото
.peek(): O(1) -> връща стойност на първия елемент без да го премахва.
Какво е Hash Table и как съхранява елементи? Каква е сложността на обичайните операции в хаш таблицата?
Структура от данни, съхранява елементи по асоциативен начин (ключ/стойност) във форма на масив, като генерира уникален индекс чрез хеш функция.
Сложности:
add();
remove();
get();
update();
За всички се прилага амортизирана константна сложност (O(1)), без значение размера на таблицата.
Амортизирана О(1) е когато средната сложност е константна, но някои елементи задействат повторно хеширане.
Какво е хеширащ алгоритъм?
Функция, която генерира хеш стойност. На всеки елемент му се дава преобразуван ключ, чрез който го достъпваме в хаш таблица.
hash = hashFunc(key);
index = hash % arraySize;
Какво са колизиите и как да се справим с тях?
Колизиите се получават, когато два или повече елемента имат еднаква хеш стойност. Някои оттехниките за справяне с тях са:
1. Separate Chaining - създаваме LL и при поява на колизия, колизиращите елементи ги вкарваме в този списък. Може да съхранява много колизии в един списък.
2. Linear Probing - линейно обхождаме в цикличен ред и търсим свободен слот. Хеш функцията се променя (H(x, i) = (H(x) + i) % table.length). Лесна за изчисление, но намаля ефективността при търсене на свободен слот.
Кои са важните характеристики на Set? Кои алгоритми могат да се подобрят със Set?
Сетът може да съдържа всякакъв тип данни, не поддържа ред и може да има само уникални стойности. Има константсна сложност за базовите операции:
.add(element)
.remove(element)
.contains(element
Ползваме го, когато ни трябват уникално стойности.
НЕ го ползваме, ако подредбата е от значение и ни трябват дубликати.
Алгоритми:
-махане на дубликати от iterable колекции;
-проверка дали всички елементи са уникални в iterable колекции;
-intersection;
-union;
-symmetric difference;
Кои са важните характеристики на Map? Кои алгоритми могат да се подобрят с Map?
Мапът поддържа ключ/стойност, приема всякакъв тип данни, помни редът и ключът е уникален. Има константна сложност за базовите операции:
add(key, value) - set(key, value)
remove(key) - delete(key)
update(key, newValue) - set(key, newValue)
get(key)
Използваме го за групиране. Може да презаписва елементи в себе си.
Алгоритми:
counting occurrences;
grouping by key;
Какво е рекурсия?
Процес, в който функцията се извиква сама докато не спре. Вика копие на себе си и разбива големи проблеми на по-малки. Важно да предоставим base case, който да прекрати рекурсията.
