Добър начин да се подготвите за интервю за софтуерно инженерство е да внедрите структури от данни на езика по ваш избор. Това е чудесен начин да практикувате кодиране на езика, на който планирате да проведете техническото си интервю, и помага да засилите разбирането си за различните структури на данни. Бихте могли наистина да впечатлите вашия интервюиращ, като използвате една от тези структури от данни в проблем с бял борд, ако е подходящо.

В този блог ще направя основно внедряване на следните структури от данни в Ruby.

  • Свързан списък
  • Двойно свързан списък
  • Двоично дърво за търсене
  • Опашка
  • Набор
  • Хеш таблица

Преди да започна:

Какво представляват структурите от данни?

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

Определението на Уикипедия:

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

Връзка: https://en.wikipedia.org/wiki/Data_structure

Ако учите визуално като мен, може да искате да разгледате тези уебсайтове, които предоставят визуални представянияна различни структури от данни (и алгоритми):

Други инструменти за обучение:

Свързани списъци

Какво е свързан списък?

„Свързаният списък е структура от данни, състояща се от група възли, които заедно представляват последователност. В най-простата форма всеки връх е съставен от данни и препратка (връзка) към следващия връх в последователността.“ — VisuAlgo

За/против

  • Не е необходимо да знаете колко артикула имате
  • Поставянето и премахването са постоянно време
  • Едносвързаният списък използва по-малко RAM от двойносвързания списък

Случаи на употреба:

  • Ако трябва да направите много вмъквания и/или изтривания в средата на вашия списък
  • Ако не се движите „назад“ в списъка
  • Единичен свързан списък почти винаги е подходящата структура от данни за внедряване на стек или опашка
  • Пример: Внедряване на мениджър на списък със задачи.

Голямо О:

Възелът за връзка

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) е свързан списък, който съдържа допълнителен указател, обикновено наричан предишен указател, заедно със следващия указател и данни, които са там в единично свързан списък.“ — Отрепки за отрепки

За/против

  • Добър за списъци, които трябва да се поддържат сортирани, особено ако елементите се добавят и изтриват, след като списъкът е бил първоначално попълнен
  • Премахването на елемент от списъка означава промяна на стойността на указателите, които сочат към елемента. Няма нужда отново да съставяте отново списъка.

Случаи на употреба:

  • Обхождане на списък двупосочно

Голямо О:

Връзка: 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 Document Object Model разглежда HTML страницата като дърво с вложени тагове като родителски дъщерни отношения.“ — Отрепки за отрепки

Голямо О:

Възелът на дървото

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

Голямо О:

Опашката (с помощта на масив)

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

Голямо О:

Стекът (с помощта на масив)

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

Хеш таблица

Какво е Хеш таблица?

„Хеширането е важна структура от данни, която е проектирана да използва специална функция, наречена хеш функция, която се използва за съпоставяне на дадена стойност с определен ключ за по-бърз достъп до елементи. Ефективността на картографирането зависи от ефективността на използваната хеш функция.“ — Отрепки за отрепки

Случаи на употреба:

  • Използва се за бързо търсене на данни

Голямо О:

Хеш таблицата

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 има вградени хеш таблици