Хороший способ подготовиться к собеседованию по разработке программного обеспечения - реализовать структуры данных на выбранном вами языке. Это отличный способ попрактиковаться в программировании на языке, на котором вы планируете проходить техническое собеседование, и он помогает лучше понять различные структуры данных. Вы могли бы действительно произвести впечатление на своего интервьюера, используя одну из этих структур данных в задаче «белой доски», если это уместно.
В этом блоге я сделаю базовую реализацию следующих структур данных в Ruby.
- Связанный список
- Двусвязный список
- Дерево двоичного поиска
- Очередь
- Стек
- Хеш-таблица
Прежде чем я начну:
Что такое структуры данных?
По сути, структуры данных - это эффективные способы хранения, организации, чтения и управления данными.
Определение Википедии:
В информатике структура данных - это формат организации, управления и хранения данных, обеспечивающий эффективный доступ и изменение. Точнее, структура данных - это набор значений данных, взаимосвязей между ними, а также функций или операций, которые могут быть применены к данным.
Ссылка: https://en.wikipedia.org/wiki/Data_structure
Если вы такой же визуальный ученик, как я, возможно, вы захотите проверить эти веб-сайты, которые предоставляют визуальные представления различных структур данных (и алгоритмов):
- Https://visualgo.net/ru
- Https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- Https://www.quora.com/How-do-I-visualize-some-basic-data-structures-and-algorithms * Более полный список ресурсов по этой ссылке
Другие инструменты обучения:
Связанные списки
Что такое связанный список?
«Связанный список - это структура данных, состоящая из группы узлов, которые вместе представляют собой последовательность. В простейшей форме каждая вершина состоит из данных и ссылки (ссылки) на следующую вершину в последовательности ». - VisuAlgo
Плюсы / минусы
- Вам не нужно знать, сколько у вас вещей
- Установка и удаление - постоянное время
- Односвязный список использует меньше ОЗУ, чем двусвязный список
Примеры использования:
- Если вам нужно сделать много вставок и / или удалений в середине вашего списка
- Если вы не двигаетесь «назад» по списку
- Единый связанный список почти всегда является подходящей структурой данных для реализации стека или очереди.
- Пример: реализация менеджера списка дел.
Большой O:
Узел связи
class LinkNode attr_accessor :next attr_reader :value def initialize(value) @value = value @next = nil end end
Связанный список
class LinkedList def initialize() @head = nil end def initialize(array) array.each {|value| append(value)} return self end def append(value) if @head find_tail.next = LinkNode.new(value) else @head = LinkNode.new(value) end end def find_tail node = @head while node.next node = node.next end return node end def find(value) node = @head while node.next && node.value != value node = node.next end if !node.next && node.value != value return false else return node end end def find_before(value) node = @head while node.next && node.next.value != value node = node.next end if !node.next return false else return node end end def append_after(target,value) node = find(target) if node != false temporary = node.next node.next = LinkNode.new(value) node.next.next = temporary end return node end def print node = @head puts node while node.next node = node.next puts node end end end
Двусвязный список
Что такое двусвязный список?
«Двусвязный список (DLL) - это связанный список, который содержит дополнительный указатель, обычно называемый предыдущий указатель, вместе со следующим указателем и данными, которые находятся в односвязном списке». - Вундеркинды для гиков
Плюсы / минусы
- Подходит для списков, которые необходимо сохранять отсортированными, особенно если элементы добавляются и удаляются после того, как список был изначально заполнен.
- Удаление элемента из списка означает изменение значения указателей, указывающих на этот элемент. Нет необходимости заново составлять список.
Примеры использования:
- Двунаправленный обход списка
Большой O:
Ссылка: https://www.quora.com/What-are-the-advantages-of-a-single-linked-list-over-the-double-linked-list
Узел двойной связи
class DoubleLinkNode attr_accessor :value, :next, :last def initialize(value) @value = value @next = nil @last = nil end end
Двусвязный список
class DoublyLinkedList def initialize() @head = nil end def initialize(array) array.each {|value| append(value)} return self end def append(value) if [email protected]? temporary = DoubleLinkNode.new(value) temporary.last = find_tail find_tail.next = temporary else @head = DoubleLinkNode.new(value) end end def find_tail node = @head while node.next node = node.next end return node end def find(value) node = @head while node.next && node.value != value node = node.next end if !node.next && node.value != value return false else return node end end def find_before(value) node = @head while node.next && node.next.value != value node = node.next end if !node.next return false else return node end end def append_after(target,value) node = find(target) if node != false temporary = node.next node.next = DoubleLinkNode.new(value) node.next.last = node node.next.next = temporary node.next.next.last = node.next end return node end def append_before(target,value) node = find(target) if node != false temporary = node.last node.last = DoubleLinkNode.new(value) node.last.last = temporary node.last.last.next = node.last node.last.next = node end return node end def print node = @head puts node while node.next node = node.next puts node end end end
Дерево двоичного поиска
Что такое дерево?
«В отличие от массивов, связанных списков, стека и очередей, которые представляют собой линейные структуры данных, деревья представляют собой иерархические структуры данных». - Вундеркинды для гиков
Что такое двоичное дерево?
Дерево, в котором у каждого элемента не более 2 дочерних элементов.
Что такое двоичное дерево поиска?
Бинарное дерево со следующими свойствами:
• Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
• Правое поддерево узла содержит только узлы с ключами больше ключа узла.
• Левое и правое поддерево также должны быть двоичным деревом поиска.
- Вундеркинды для гиков
Примеры использования:
«Одна из причин использовать двоичное дерево или дерево в целом - это элементы, образующие иерархию».
• «Они полезны в файловых структурах, где каждый файл находится в определенном каталоге и существует определенная иерархия, связанная с файлами и каталогами».
• «Другой пример, когда деревья полезны, - это хранение иерархических объектов, таких как объектная модель документа JavaScript, рассматривающая HTML-страницу как дерево с вложением тегов в качестве родительских дочерних отношений». - Вундеркинды для гиков
Большой O:
Узел дерева
class TreeNode attr_accessor :value, :left, :right def initialize(value) @value = value @left = nil @right = nil end end
Дерево двоичного поиска
class BinarySearchTree def initialize() @root = nil end def insert(val,node=@root) if [email protected]? if !node.nil? if val < node.value if node.left.nil? node.left = TreeNode.new(val) else insert(val, node.left) end elsif val > node.value if node.right.nil? node.right = TreeNode.new(val) else insert(val, node.right) end elsif val = node.value return false end end elsif @root.nil? @root = TreeNode.new(val) end end def inOrderTraversal(node = @root) if !node.nil? inOrderTraversal(node.left) puts node.value inOrderTraversal(node.right) end end def preOrderTraversal(node = @root) if !node.nil? puts node.value preOrderTraversal(node.left) preOrderTraversal(node.right) end end def postOrderTraversal(node = @root) if !node.nil? postOrderTraversal(node.left) postOrderTraversal(node.right) puts node.value end end def search(val, node = @root ) if !node.nil? if val < node.value search(val, node.left) elsif val > node.value search(val, node.right ) else return node end else return nil end end end
Примечание. Вам должно быть комфортно обходить деревья любым способом (кроме простых обходов до / после / по порядку). Интервьюеры могут попросить вас распечатать значения дерева любым способом.
Очередь
Что такое очередь?
«Очередь - это линейная структура, которая следует определенному порядку выполнения операций. Порядок - «первым пришел - первым обслужен» (FIFO) ». - Вундеркинды для гиков
Примеры использования:
- Очередь используется в алгоритме BFS (поиск в ширину)
- Когда данные передаются асинхронно
- Очередь людей в любом пункте обслуживания, таком как билетная касса и т. Д.
- Очередь процессов в ОС.
- В сетевых принтерах, например. если несколько человек печатают документы с одного и того же принтера
- Очередь самолетов в ожидании указаний на посадку.
Ссылка: https://www.quora.com/What-are-some-real-world-applications-of-a-queue-data-structure-1
Большой O:
Очередь (с использованием массива)
class Queue def initialize @store = Array.new end def enqueue(element) @store << element end def dequeue(element) @store.shift end def length @store.length end def empty? @store.empty? end end
Куча
Что такое стек?
«Стек - это линейная структура данных, которая следует определенному порядку выполнения операций. Порядок может быть LIFO (последний пришел - первым ушел) или FILO (первым пришел последний ушел) ». - Вундеркинды для гиков
Примеры использования:
- Стек используется в алгоритме DFS (поиск в глубину).
- Чтобы перевернуть слово. Вы помещаете заданное слово в стопку - букву за буквой - а затем выталкиваете буквы из стопки.
- Отменить \ повторить операцию в текстовых редакторах
- Используется в IDE для проверки правильности соответствия скобок (синтаксический анализ)
Ссылка: https://www.quora.com/What-are-the-real-life-applications-of-stack-data-structure
Ссылка: https://www.quora.com/What-are-the-real-world-examples-of-stacks
Большой O:
Стек (с использованием массива)
class Stack def initialize @store = Array.new end def push(element) @store << element end def pop(element) @store.pop end def length @store.length end def empty? @store.empty? end end
Хеш-таблица
Что такое хеш-таблица?
«Хеширование - это важная структура данных, которая предназначена для использования специальной функции, называемой функцией хеширования, которая используется для сопоставления заданного значения с определенным ключом для более быстрого доступа к элементам. Эффективность сопоставления зависит от эффективности используемой хеш-функции ». - Вундеркинды для гиков
Примеры использования:
- Используется для быстрого поиска данных
Большой O:
Хеш-таблица
class HashTable def initialize(bucket_amount = 20) @size = bucket_amount @table = Array.new(bucket_amount) end def insert(key,value) location = hash_function(key) @table[location] ||= [] # if @table[location].find { |hash_pair| hash_pair.first == key } if @table[location].assoc(key) return "Key exists" else @table[location] << [key, value] end end def lookup(key) location = hash_function(key) if @table[location] return @table[location].assoc(key) else return nil end end def delete(key) hashed_key = lookup(key) if !hashed_key.nil? location = hash_function(key) @table[location].delete(hashed_key) end end def hash_function(key) return key.hash % @size end
Примечание:
@table[location].assoc(key) is the same as @table[location].find {|hash_pair| hash_pair.first == key}
* Ruby имеет встроенные хеш-таблицы