Най-добрите структури от данни, които трябва да знаете за следващото си интервю за кодиране

Никлаус Вирт, швейцарски компютърен учен, написа книга през 1976 г., озаглавена „ Алгоритми + структури от данни = програми“.

40+ години по-късно това уравнение все още важи. Ето защо кандидатите за софтуерно инженерство трябва да демонстрират своето разбиране за структурите на данни заедно с техните приложения.

Почти всички проблеми изискват от кандидата да демонстрира задълбочено разбиране на структурите от данни. Няма значение дали току-що сте завършили (университет или кодиращ лагер за кодиране) или имате десетилетия опит.

Понякога въпросите за интервюта изрично споменават структура на данни, например „дадено двоично дърво“. Друг път е неявно, като „искаме да проследим броя книги, свързани с всеки автор“.

Изучаването на структури от данни е от съществено значение, дори ако просто се опитвате да се подобрите в настоящата си работа. Нека започнем с разбирането на основите.

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

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

Защо се нуждаем от структури от данни?

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

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

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

Често използвани структури от данни

Нека първо изброим най-често използваните структури от данни и след това ще ги покрием една по една:

  1. Масиви
  2. Стекове
  3. Опашки
  4. Свързани списъци
  5. Дървета
  6. Графики
  7. Опитва се (те са ефективно дървета, но все пак е добре да ги извикате отделно).
  8. Хеш таблици

Масиви

Масивът е най-простата и широко използвана структура от данни. Други структури от данни като стекове и опашки са получени от масиви.

Ето изображение на прост масив с размер 4, съдържащ елементи (1, 2, 3 и 4).

На всеки елемент от данни се присвоява положителна числова стойност, наречена Индекс , която съответства на позицията на този елемент в масива. Повечето езици определят началния индекс на масива като 0.

По-долу са двата типа масиви:

  • Едномерни масиви (както е показано по-горе)
  • Многомерни масиви (масиви в масиви)

Основни операции върху масиви

  • Вмъкване - Вмъква елемент с даден индекс
  • Get - Връща елемента при даден индекс
  • Изтриване - Изтрива елемент с даден индекс
  • Размер - Получава общия брой елементи в масив

Често задавани въпроси за интервю за Array

  • Намерете втория минимален елемент на масив
  • Първи неповтарящи се цели числа в масив
  • Обединете два сортирани масива
  • Пренаредете положителни и отрицателни стойности в масив

Стекове

Всички сме запознати с известната опция за отмяна , която присъства в почти всяко приложение. Чудили ли сте се как работи? Идеята: съхранявате предишните състояния на работата си (които са ограничени до определен брой) в паметта в такъв ред, че последният се появява първи. Това не може да се направи само с помощта на масиви. Това е мястото, където стекът е полезен.

Пример от реалния живот на Stack може да бъде купчина книги, поставени във вертикален ред. За да получите книгата, която е някъде по средата, ще трябва да премахнете всички книги, поставени върху нея. Ето как работи методът LIFO (Last In First Out).

Ето изображение на стека, съдържащо три елемента от данни (1, 2 и 3), където 3 е отгоре и първо ще бъде премахнат:

Основни операции на стека:

  • Push - Вмъква елемент в горната част
  • Pop - Връща горния елемент след премахване от стека
  • isEmpty - Връща true, ако стекът е празен
  • Top - Връща горния елемент, без да се премахва от стека

Често задавани въпроси за интервю за Stack

  • Оценете израза на постфикс с помощта на стек
  • Сортирайте стойностите в стека
  • Проверете балансираните скоби в израз

Опашки

Подобно на Stack, Queue е друга линейна структура от данни, която съхранява елемента по последователен начин. Единствената съществена разлика между Stack и Queue е, че вместо да използва метода LIFO, Queue изпълнява FIFOметод, което е съкратено от First in First Out.

Перфектен пример от реалния живот на Queue: ред хора, чакащи на касата за билети. Ако дойде нов човек, той ще се присъедини към линията от края, а не от самото начало - и човекът, който стои отпред, ще бъде първият, който ще получи билета и следователно ще напусне линията.

Ето изображение на Queue, съдържащо четири елемента с данни (1, 2, 3 и 4), където 1 е отгоре и първо ще бъде премахнат:

Основни операции на Queue

  • Enqueue () - Вмъква елемент в края на опашката
  • Dequeue () - Премахва елемент от началото на опашката
  • isEmpty () - Връща true, ако опашката е празна
  • Top () - Връща първия елемент от опашката

Често задавани въпроси за интервю за опашка

  • Внедрете стека, като използвате опашка
  • Обърнете първите k елементи на опашката
  • Генерирайте двоични числа от 1 до n, като използвате опашка

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

Свързаният списък е друга важна линейна структура от данни, която в началото може да изглежда подобно на масивите, но се различава по разпределението на паметта, вътрешната структура и как се извършват основните операции по вмъкване и изтриване.

Свързаният списък е като верига от възли, където всеки възел съдържа информация като данни и указател към следващия възел във веригата. Има указател за глава, който сочи към първия елемент от свързания списък и ако списъкът е празен, той просто сочи към нула или нищо.

Свързаните списъци се използват за внедряване на файлови системи, хеш таблици и съседни списъци.

Ето визуално представяне на вътрешната структура на свързан списък:

Следват типовете свързани списъци:

  • Единично свързан списък (еднопосочен)
  • Двойно свързан списък (двупосочен)

Основни операции на свързания списък:

  • InsertAtEnd - Вмъква даден елемент в края на свързания списък
  • InsertAtHead - Вмъква даден елемент в началото / главата на свързания списък
  • Изтриване - Изтрива даден елемент от свързания списък
  • DeleteAtHead - Изтрива първия елемент от свързания списък
  • Търсене - Връща дадения елемент от свързан списък
  • isEmpty - Връща true, ако свързаният списък е празен

Често задавани въпроси за интервю за свързан списък

  • Обърнете свързан списък
  • Откриване на цикъл в свързан списък
  • Върнете N-ти възел от края в свързан списък
  • Премахване на дубликати от свързан списък

Графики

Графиката е набор от възли, които са свързани помежду си под формата на мрежа. Възлите също се наричат ​​върхове. Една двойка (х, у) , се нарича край , което показва, че връх X е свързан към връх у . Ръбът може да съдържа тегло / цена, показваща колко разходи са необходими за преминаване от връх x към y .

Видове графики:

  • Ненасочена графика
  • Насочена графика

В език за програмиране графиките могат да бъдат представени с помощта на две форми:

  • Матрица на съседство
  • Списък на съседство

Общи алгоритми за обхождане на графики:

  • Широчина Първо търсене
  • Дълбочина Първо търсене

Често задавани въпроси за интервю за Graph

  • Приложете първо търсене на широчина и дълбочина
  • Проверете дали графиката е дърво или не
  • Пребройте броя на ръбовете в графика
  • Намерете най-краткия път между два върха

Дървета

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

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

Ето изображение на просто дърво и основни терминологии, използвани в структурата на дървесните данни:

По-долу са видовете дървета:

  • N-арно дърво
  • Балансирано дърво
  • Двоично дърво
  • Двоично дърво за търсене
  • AVL дърво
  • Червено черно дърво
  • 2–3 Дърво

От гореизброените, двоичното дърво и двоичното дърво за търсене са най-често използваните дървета.

Често задавани въпроси за интервю за Tree

  • Намерете височината на двоично дърво
  • Намерете k-та максимална стойност в бинарно дърво за търсене
  • Намерете възли на разстояние „k” от корена
  • Намерете предци на даден възел в двоично дърво

Трие

Trie, което е известно още като „Prefix Trees“, е дървовидна структура от данни, която се оказва доста ефективна за решаване на проблеми, свързани със низове. Той осигурява бързо извличане и се използва най-вече за търсене на думи в речник, предоставяне на автоматични предложения в търсачката и дори за IP маршрутизиране.

Ето илюстрация на това как в Trie се съхраняват три думи „отгоре“, „по този начин“ и „техните“:

Думите се съхраняват отгоре надолу, където зелено оцветените възли „p”, „s” и „r” означават съответно края на „отгоре”, „по този начин” и „техния”.

Често задавани въпроси за интервю за Трие:

  • Пребройте общия брой думи в Trie
  • Отпечатайте всички думи, съхранени в Trie
  • Сортирайте елементи от масив с помощта на Trie
  • Формирайте думи от речник с помощта на Trie
  • Изградете речник T9

Хеш таблица

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

Хеш таблиците обикновено се реализират с помощта на масиви.

Ефективността на структурата на хеширащите данни зависи от тези три фактора:

  • Хеш функция
  • Размер на хеш таблицата
  • Метод за обработка на сблъсък

Ето илюстрация на това как хешът се картографира в масив. Индексът на този масив се изчислява чрез хеш функция.

Често задавани въпроси за интервю за хеширане

  • Намерете симетрични двойки в масив
  • Проследете пълния път на пътуване
  • Намерете дали масивът е подмножество на друг масив
  • Проверете дали дадени масиви не са свързани

Горните са осемте най-добри структури от данни, които определено трябва да знаете, преди да влезете в интервю за кодиране.

Ако търсите ресурси за структури от данни за кодиране на интервюта, погледнете интерактивните и базирани на предизвикателства курсове: Структури на данни за интервюта за кодиране (Python, Java или JavaScript).

За по-напреднали въпроси погледнете Coderust 3.0: По-бърза подготовка на интервю за кодиране с интерактивни предизвикателства и визуализации.

Ако се подготвяте за интервюта за софтуерно инженерство, ето подробна пътна карта за подготовка за кодиране на интервюта.

Успех и щастливо учене! :)