Чек-лист для .NET программиста: Алгоритмы и структуры данных

Алгоритмы представляют собой готовые решения проблем, периодически возникающих в процессе разработки программного обеспечения. Фактически программист лишается необходимости изобретать велосипед, а только проанализировать набор существующих алгоритмов и выбрать из них тот, который лучше всего подходит для решения поставленной задачи.

Выполнение алгоритма занимает определенное процессорное время и использует некоторое количество оперативной памяти. Обычно выбор программистом алгоритма представляет собой поиск золотой середины между временем и памятью, так как один алгоритм работает быстро, потребляя много памяти, другой медленнее, занимая меньший объем. Именно с точки зрения расходуемого времени и памяти оценивают сложность алгоритма и записывают с помощью Big O нотации, задача которой показать, как изменится поведение алгоритма при возрастании объема входящих данных.

К базовым алгоритмам можно отнести линейный поиск (Linear Search), двоичный поиск (Binary Search), пузырьковую сортировку (Bubble Sort), быструю сортировку (Quick Sort), сортировку слиянием (Merge Sort), реализацию хеш-таблиц и обход бинарных деревьев.

Структуры данных, к которым относятся массивы (Array), стеки (Stack), очереди (Queue), списки (Linked List), двоичные деревья (Binary Tree), хеш-таблицы (Hash Table) и другие, являются ключевыми строительными блоками любой программы. Каждая структура данных имеет свои принципы работы, а их операции чтения, поиска, добавления и удаления элементов имеют свою собственную сложность. Следовательно, правильный выбор структуры данных, как и выбор наиболее подходящего под задачу программиста алгоритма является одним из ключевых моментов разработки качественного ПО.

Вопросы

  1. Какая структура данных работает по принципу LIFO, какая по FIFO?
  2. Какая структура данных оптимизирована для частых вставок и удалений элементов?
  3. Как реализовать бинарный поиск?
  4. Какие разновидности двусвязного списка существуют?
  5. Как реализована структура данных двусвязный список?
  6. Какова временная сложность (O большое) удаления элемента из Стека?
  7. Какова временная сложность (O большое) вставки элемента из хеш-таблицу?
  8. Какие существуют алгоритмы борьбы с коллизиями в хеш-таблицах?
  9. Какие существуют алгоритмы обхода бинарных деревьев?
  10. Какое бинарное дерево является сбалансированным/не сбалансированным?
  11. При каких условиях для бинарного дерева более оптимальным будет поиск в ширину чем в глубину?
  12. Каково предназначение АВЛ-деревьев?
  13. Как работают алгоритмы быстрой сортировки и сортировки слиянием?
  14. Какие преимущества рекурсивных алгоритмов над итеративными и наоборот?
  15. В чем отличие между ориентированными и неориентированными графами?
  16. Какую проблему решает алгоритм Дейкстры?

Книги

Ресурсы

  • bigocheatsheet.com — сложности ключевых алгоритмов
  • visualgo.net — анимированная визуализация алгоритмов и структур данных
  • toptal.com — визуализация алгоримов сортировок и примеры реализаций
  • leetcode.com — огромное количество различных логических задач

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход /  Изменить )

Google photo

Для комментария используется ваша учётная запись Google. Выход /  Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход /  Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход /  Изменить )

Connecting to %s