Я подумал, что, возможно, захочу ответить на некоторые часто задаваемые вопросы на собеседовании о структурах данных. Я знаю, что это определенно то, что я пытаюсь понять. Чем больше я встречусь с выпускниками Bootcamp, тем больше понимаю, насколько плохо мы понимаем эти концепции. Хотя и не без причины. Так много можно узнать только за такой короткий промежуток времени. Нам дали инструменты, необходимые для строительства дома, но мы действительно не знаем, откуда берется наша древесина и почему она важна для инфраструктуры.
Линейные и нелинейные структуры данных:
- Линейная - структура данных называется линейной, если ее элементы образуют последовательность или линейный список. Примеры включают массивы, связанные списки, стопки или очереди.
- Нелинейная - структура данных называется нелинейной, если обход узлов нелинейный по своей природе. Примеры включают графы и деревья.
SIDENOTE:
Что такое стопки и очереди, спросите вы?
Стек. Стек можно рассматривать как контейнер объектов, которые вставляются и удаляются в соответствии с принципом LIFO (Last In First Out). Стек - это так называемая структура данных с ограниченным доступом, в которой элементы могут добавляться и удаляться из стека только наверху.
- Хорошим примером этого является представление стопки книг. Было бы непрактично складывать или брать книги из середины стопки, так как вы рискуете опрокинуть ее. Единственное логичное место для выполнения этих двух действий - сверху.
Очередь. С другой стороны, очередь представляет собой линейный набор объектов, которые вставляются и удаляются по принципу FIFO (First In First Out). В очереди разрешены только две операции: постановка в очередь и удаление из очереди. Enqueue означает вставку элемента в конец очереди, а dequeue означает удаление элемента из начала очереди.
- Отличным примером очереди может быть очередь на обед в кафетерии. Новые люди подключаются к сети сзади, а люди впереди покидают очередь после того, как их обслужили.
Чем они отличаются?
Эти два метода различаются удалением. В стеке мы удаляем последний добавленный элемент, а в очереди удаляем элемент, который добавлялся не так давно.
Какие различные операции можно выполнять со структурами данных?
Вставка - Добавить новый элемент данных в данную коллекцию элементов данных.
Удаление - удаление существующего элемента данных из данной коллекции элементов данных.
Обход. Получите доступ к каждому элементу данных ровно один раз, чтобы его можно было обработать.
Поиск - определение местоположения элемента данных, если он существует в данной коллекции элементов.
- В основном есть два типа поиска. Последовательный поиск и бинарный поиск.
Последовательный поиск - начинается с начала списка и проверяет каждый элемент списка.
Двоичный поиск - ищет определенный элемент, сравнивая самый средний элемент коллекции. Делит исходный массив на два и выбирает тот, к которому применяется аргумент поиска, затем повторяет процесс.
- Массив уже должен быть отсортирован.
- Работает по принципу разделяй и властвуй.
- Алгоритм быстрого поиска со сложностью выполнения O (log n).
Сортировка - упорядочивание элементов данных в определенном порядке. Примеры представлены в порядке возрастания или убывания в случае числовых данных или в порядке словаря в случае буквенно-цифровых данных.
В основном существует два типа методов сортировки:
- Сортировка на месте - эти алгоритмы не требуют дополнительного места, и считается, что сортировка происходит на месте или, например, внутри самого массива. Пузырьковая сортировка - это пример сортировки на месте.
- Сортировка без места - в некоторых алгоритмах сортировки программе требуется пространство, которое больше или равно сортируемым элементам. Сортировка, в которой используется равное или большее пространство, называется сортировкой без места. Сортировка слиянием - это пример сортировки не по месту.
SIDENOTE:
- Если алгоритм сортировки после сортировки содержимого не изменяет последовательность аналогичного содержимого, в котором они появляются, это называется стабильной сортировкой.
- Если алгоритм сортировки после сортировки содержимого изменяет последовательность аналогичного содержимого, в котором они появляются, это называется нестабильной сортировкой.
- Алгоритм сортировки называется адаптивным, если он использует уже «отсортированные» элементы в списке, который нужно отсортировать. То есть при сортировке, если в исходном списке уже есть отсортированный элемент, адаптивные алгоритмы учтут это и не будут пытаться переупорядочить их.
- Неадаптивный алгоритм - это алгоритм, который не принимает во внимание уже отсортированные элементы. Затем попробуйте принудительно переупорядочить каждый элемент, чтобы подтвердить их сортировку.
Это все, что у меня есть на сегодня. Ниже вы можете увидеть некоторые ссылки, в которых я нашел всю свою информацию.
