Добър начин да се подготвите за интервю за софтуерно инженерство е да внедрите структури от данни на езика по ваш избор. Това е чудесен начин да практикувате кодиране на езика, на който планирате да проведете техническото си интервю, и помага да засилите разбирането си за различните структури на данни. Бихте могли наистина да впечатлите вашия интервюиращ, като използвате една от тези структури от данни в проблем с бял борд, ако е подходящо.
В този блог ще направя основно внедряване на следните структури от данни в Ruby.
- Свързан списък
- Двойно свързан списък
- Двоично дърво за търсене
- Опашка
- Набор
- Хеш таблица
Преди да започна:
Какво представляват структурите от данни?
По принцип структурите от данни са ефективни начини за съхраняване, организиране, четене и манипулиране на данни.
Определението на Уикипедия:
В компютърните науки структурата на данните е формат за организация, управление и съхранение на данни, който позволява ефективен достъп и модифициране. По-точно, структура от данни е колекция от стойности на данни, връзките между тях и функциите или операциите, които могат да бъдат приложени към данните.
Връзка: https://en.wikipedia.org/wiki/Data_structure
Ако учите визуално като мен, може да искате да разгледате тези уебсайтове, които предоставят визуални представянияна различни структури от данни (и алгоритми):
- https://visualgo.net/en
- https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
- https://www.quora.com/How-do-I-visualize-some-basic-data-structures-and-algorithms * По-изчерпателен списък с ресурси в тази връзка
Други инструменти за обучение:
Свързани списъци
Какво е свързан списък?
„Свързаният списък е структура от данни, състояща се от група възли, които заедно представляват последователност. В най-простата форма всеки връх е съставен от данни и препратка (връзка) към следващия връх в последователността.“ — 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 има вградени хеш таблици