Найпопулярніші структури даних, які ви повинні знати для наступного співбесіди з кодування

Ніклаус Вірт, швейцарський інформатик, у 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, Queue - це ще одна лінійна структура даних, яка зберігає елемент послідовно. Єдина суттєва різниця між Stack і Queue полягає в тому, що замість використання методу LIFO, Queue реалізує FIFOметод, що скорочено від First in First Out.

Прекрасний приклад реального життя Черги: черга людей, що чекають біля каси. Якщо приходить нова людина, вона приєднується до лінії з кінця, а не з самого початку - і той, хто стоїть спереду, першим отримає квиток і, отже, покине лінію.

Ось зображення Черги, що містить чотири елементи даних (1, 2, 3 і 4), де 1 знаходиться вгорі і буде видалено першим:

Основні операції черги

  • Enqueue () - вставляє елемент у кінець черги
  • Dequeue () - Видаляє елемент із початку черги
  • isEmpty () - Повертає true, якщо черга порожня
  • Top () - повертає перший елемент черги

Поширені запитання щодо інтерв’ю в черзі

  • Впровадити стек за допомогою черги
  • Змінити перші k елементів черги
  • Створіть двійкові числа від 1 до n, використовуючи чергу

Зв’язаний список

Зв’язаний список - це ще одна важлива лінійна структура даних, яка спочатку може виглядати схожою на масиви, але відрізняється розподілом пам’яті, внутрішньою структурою та тим, як виконуються основні операції вставки та видалення.

Зв’язаний список схожий на ланцюжок вузлів, де кожен вузол містить таку інформацію, як дані та вказівник на наступний вузол у ланцюжку. Існує вказівник на голову, який вказує на перший елемент пов'язаного списку, і якщо список порожній, то він просто вказує на нуль або нічого.

Зв’язані списки використовуються для реалізації файлових систем, хеш-таблиць та списків суміжності.

Ось наочне зображення внутрішньої структури пов’язаного списку:

Нижче наведено типи пов’язаних списків:

  • Список з єдиним зв’язком (односпрямований)
  • Список подвійних зв’язків (двонаправлений)

Основні операції зв'язаного списку:

  • InsertAtEnd - Вставляє заданий елемент в кінець пов'язаного списку
  • InsertAtHead - Вставляє даний елемент на початок / заголовок пов'язаного списку
  • Видалити - видаляє даний елемент зі зв’язаного списку
  • DeleteAtHead - Видаляє перший елемент зв’язаного списку
  • Пошук - повертає даний елемент зі зв’язаного списку
  • isEmpty - Повертає true, якщо зв'язаний список порожній

Запитання до співбесіди, що часто задаються

  • Змінити зв’язаний список
  • Виявити цикл у зв’язаному списку
  • Повернути N-й вузол з кінця у зв’язаному списку
  • Видаліть дублікати зі зв’язаного списку

Графіки

Графік - це сукупність вузлів, які з’єднані між собою у вигляді мережі. Вузли також називають вершинами. Пара (х, у) називається ребро , яке вказує , що вершина х з'єднана з вершиною у . Ребро може містити вагу / вартість, показуючи, скільки витрат потрібно для переходу від вершини x до y .

Типи графіків:

  • Непрямий графік
  • Направлений графік

У мові програмування графіки можуть бути представлені у двох формах:

  • Матриця суміжності
  • Список суміжності

Поширені алгоритми обходу графіка:

  • Ширина - перший пошук
  • Глибина Перший пошук

Поширені запитання щодо інтерв’ю у Graph

  • Впровадити пошук по ширині та глибині
  • Перевірте, чи є графік деревом чи ні
  • Підрахуйте кількість ребер на графіку
  • Знайдіть найкоротший шлях між двома вершинами

Дерева

Дерево - це ієрархічна структура даних, що складається з вершин (вузлів) та ребер, що їх з'єднують. Дерева схожі на графіки, але ключовим моментом, який відрізняє дерево від графіка, є те, що цикл не може існувати в дереві.

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

Ось зображення простого дерева та основні термінології, що використовуються в структурі деревних даних:

Нижче наведені типи дерев:

  • N-арне дерево
  • Збалансоване дерево
  • Бінарне дерево
  • Бінарне дерево пошуку
  • Дерево AVL
  • Червоне чорне дерево
  • 2–3 Дерево

З усіх вищезазначених, Бінарне дерево та Бінарне дерево пошуку є найбільш часто використовуваними деревами.

Поширені запитання щодо інтерв’ю щодо дерева

  • Знайдіть висоту двійкового дерева
  • Знайти k-те максимальне значення в двійковому дереві пошуку
  • Знайдіть вузли на відстані “k” від кореня
  • Знайдіть предків даного вузла у двійковому дереві

Тріє

Trie, яка також відома як «Префіксні дерева», - це деревоподібна структура даних, яка виявляється досить ефективною для вирішення проблем, пов’язаних із рядками. Він забезпечує швидкий пошук і в основному використовується для пошуку слів у словнику, надання автоматичних пропозицій у пошуковій системі та навіть для IP-маршрутизації.

Ось ілюстрація того, як три слова “top”, “Таким чином” і “їх” зберігаються в Trie:

Слова зберігаються зверху донизу, де зелені кольорові вузли "p", "s" і "r" вказують на кінець "top", "таким чином" і "їх" відповідно.

Запитання, що часто задаються Трі:

  • Підрахуйте загальну кількість слів у Тріє
  • Надрукувати всі слова, що зберігаються в Trie
  • Сортування елементів масиву за допомогою Trie
  • Утворіть слова зі словника за допомогою Trie
  • Створіть словник T9

Хеш-таблиця

Хешування - це процес, який використовується для однозначної ідентифікації об’єктів та зберігання кожного об’єкта за деяким заздалегідь розрахованим унікальним індексом, який називається його „ключем”. Отже, об’єкт зберігається у формі пари «ключ-значення», а колекція таких предметів називається «словником». Кожен об’єкт можна шукати за допомогою цієї клавіші. Існують різні структури даних, засновані на хешуванні, але найбільш часто використовуваною структурою даних є хеш-таблиця .

Хеш-таблиці, як правило, реалізуються з використанням масивів.

Ефективність структури даних хешування залежить від цих трьох факторів:

  • Хеш-функція
  • Розмір Хеш-таблиці
  • Метод обробки зіткнень

Ось ілюстрація того, як хеш відображається в масиві. Індекс цього масиву обчислюється за допомогою хеш-функції.

Поширені запитання щодо співбесіди з Hashing

  • Знайдіть симетричні пари в масиві
  • Простежте повний шлях подорожі
  • Знайдіть, чи є масив підмножиною іншого масиву
  • Перевірте, чи задані масиви не перетинаються

Вище наведено вісім найкращих структур даних, які ви обов’язково повинні знати, перш ніж брати участь у співбесіді з кодуванням.

Якщо ви шукаєте ресурси щодо структур даних для кодування інтерв’ю, подивіться на інтерактивні та викликові курси: Структури даних для кодування інтерв’ю (Python, Java або JavaScript).

Щоб отримати додаткові запитання, зверніться до Coderust 3.0: Швидша підготовка інтерв’ю до кодування з інтерактивними викликами та візуалізацією.

Якщо ви готуєтесь до співбесід з програмної інженерії, ось вичерпна дорожня карта для підготовки до кодування інтерв’ю.

Успіхів та щасливого навчання! :)