Алгоритмы и Структуры Данных

Темы:

• Понимание Big O нотации

• Простые алгоритмы поиска: линейный поиск и бинарный поиск

• Понимание основных алгоритмов сортировки: пузырьковая сортировка (Bubble Sort), сортировка вставками (Insertion Sort), быстрая сортировка (Quick Sort), сортировка слиянием (Merge Sort)

• Работа с основными структурами данных и понимание их внутреннего устройства: массив, стек, очереди, списки односвязные/двусвязные, хеш-таблица | Принципы LIFO и FIFO

• Значения Big O для операций со структурами данных и алгоритмов сортировок

• Внутреннее устройство хеш-таблиц, Хеш-функции, Коллизии

• Деревья и Бинарные деревья: Структура, Построение, Обход (Pre-Order, In-Order, Post-Order), Поиск (DFS, BFS), Вставка элементов

• Оценка сложности алгоритмов

• Виды графов: Однонаправленные и Двунаправленные, Алгоритмы поиска на графах: DFS, BFS, Дейкстра

Контрольные вопросы:

• Что показывает Big O нотация?

• По каким двум параметрам можно оценивать сложность алгоритма?

• Чему равна Big O для бинарного поиска?

• Чему равна Big O для операции обращения к ячейке массива по индейсу?

• Опишите алгоритм Сортировки слиянием (Merge Sort)?

• Чему равна Big O для операции извлечения значения по ключу из хеш-таблицы?

• Опишите реализацию алгоритма поиска в ширину (BFS) для дерева?

• В какие случаях для деревьев лучше использовать DFS, а в каких BFS?

• Почему может возникнуть коллизия в хеш-таблицах?

• Как оценить сложность алгоритма?

• Опишите принцип работы алгоритма Дейкстры.

Источники:

Книги:

• The Algorithm Design Manual

Курсы:

• Алгоритмы: теория и практика. Методы

Статьи:

• Big O

• Описание алгоритмов сортировки и сравнение их производительности

• Важнейшие структуры данных, которые вам следует знать к своему собеседованию по программированию

• Know Thy Complexities!

• Алгоритмы на графах

• Префиксное дерево