Алгоритмы представляют собой готовые решения проблем, периодически возникающих в процессе разработки программного обеспечения. Фактически программист лишается необходимости изобретать велосипед, а только проанализировать набор существующих алгоритмов и выбрать из них тот, который лучше всего подходит для решения поставленной задачи.
Выполнение алгоритма занимает определенное процессорное время и использует некоторое количество оперативной памяти. Обычно выбор программистом алгоритма представляет собой поиск золотой середины между временем и памятью, так как один алгоритм работает быстро, потребляя много памяти, другой медленнее, занимая меньший объем. Именно с точки зрения расходуемого времени и памяти оценивают сложность алгоритма и записывают с помощью Big O нотации, задача которой показать, как изменится поведение алгоритма при возрастании объема входящих данных.
К базовым алгоритмам можно отнести линейный поиск (Linear Search), двоичный поиск (Binary Search), пузырьковую сортировку (Bubble Sort), быструю сортировку (Quick Sort), сортировку слиянием (Merge Sort), реализацию хеш-таблиц и обход бинарных деревьев.
Структуры данных, к которым относятся массивы (Array), стеки (Stack), очереди (Queue), списки (Linked List), двоичные деревья (Binary Tree), хеш-таблицы (Hash Table) и другие, являются ключевыми строительными блоками любой программы. Каждая структура данных имеет свои принципы работы, а их операции чтения, поиска, добавления и удаления элементов имеют свою собственную сложность. Следовательно, правильный выбор структуры данных, как и выбор наиболее подходящего под задачу программиста алгоритма является одним из ключевых моментов разработки качественного ПО.
Вопросы
- Какая структура данных работает по принципу LIFO, какая по FIFO?
- Какая структура данных оптимизирована для частых вставок и удалений элементов?
- Как реализовать бинарный поиск?
- Какие разновидности двусвязного списка существуют?
- Как реализована структура данных двусвязный список?
- Какова временная сложность (O большое) удаления элемента из Стека?
- Какова временная сложность (O большое) вставки элемента из хеш-таблицу?
- Какие существуют алгоритмы борьбы с коллизиями в хеш-таблицах?
- Какие существуют алгоритмы обхода бинарных деревьев?
- Какое бинарное дерево является сбалансированным/не сбалансированным?
- При каких условиях для бинарного дерева более оптимальным будет поиск в ширину чем в глубину?
- Каково предназначение АВЛ-деревьев?
- Как работают алгоритмы быстрой сортировки и сортировки слиянием?
- Какие преимущества рекурсивных алгоритмов над итеративными и наоборот?
- В чем отличие между ориентированными и неориентированными графами?
- Какую проблему решает алгоритм Дейкстры?
Книги
- Алгоритмы. Руководство по разработке — Стивен С. Скиена
- Cracking the Coding Interview: 189 Programming Questions and Solutions 6th Edition — Gayle Laakmann McDowell
- Алгоритмические трюки для программистов — Генри С. Уоррен мл.
- Искусство программирования. Том 1. Основные алгоритмы — Дональд Эрвин Кнут, Игорь Красиков
Ресурсы
- bigocheatsheet.com — сложности ключевых алгоритмов
- visualgo.net — анимированная визуализация алгоритмов и структур данных
- toptal.com — визуализация алгоримов сортировок и примеры реализаций
- leetcode.com — огромное количество различных логических задач
