Хороший способ подготовиться к собеседованию по разработке программного обеспечения - реализовать структуры данных на выбранном вами языке. Это отличный способ попрактиковаться в программировании на языке, на котором вы планируете проходить техническое собеседование, и он помогает лучше понять различные структуры данных. Вы могли бы действительно произвести впечатление на своего интервьюера, используя одну из этих структур данных в задаче «белой доски», если это уместно.

В этом блоге я сделаю базовую реализацию следующих структур данных в Ruby.

  • Связанный список
  • Двусвязный список
  • Дерево двоичного поиска
  • Очередь
  • Стек
  • Хеш-таблица

Прежде чем я начну:

Что такое структуры данных?

По сути, структуры данных - это эффективные способы хранения, организации, чтения и управления данными.

Определение Википедии:

В информатике структура данных - это формат организации, управления и хранения данных, обеспечивающий эффективный доступ и изменение. Точнее, структура данных - это набор значений данных, взаимосвязей между ними, а также функций или операций, которые могут быть применены к данным.

Ссылка: https://en.wikipedia.org/wiki/Data_structure

Если вы такой же визуальный ученик, как я, возможно, вы захотите проверить эти веб-сайты, которые предоставляют визуальные представления различных структур данных (и алгоритмов):

Другие инструменты обучения:

Связанные списки

Что такое связанный список?

«Связанный список - это структура данных, состоящая из группы узлов, которые вместе представляют собой последовательность. В простейшей форме каждая вершина состоит из данных и ссылки (ссылки) на следующую вершину в последовательности ». - 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 имеет встроенные хеш-таблицы