Що можуть запитати на співбесіді: структури даних Java. Частина 1

Вітання! Як не крути, вам не стати розробником без успішного проходження вхідної технічної співбесіди. Технологій, пов'язаних з Java, дуже багато і вивчити все неможливо. Щось специфічне, як правило, на співбесідах запитують лише в тому випадку, якщо шукають розробника з гарним досвідом у якомусь важливому для проекту фреймворку. Якщо це так, вас будуть ганяти цим фреймворком на весь зріст, ви вже не сумнівайтеся. Але ми зараз говоримо про базу, яку має знати кожен Java developer. Про ті класичні знання, з яких все і починається. Сьогодні хотілося б торкнутися однієї з основних тем будь-якої співбесіди — структури даних у Java. Отже, замість ходіння навкруги, ми почнемо. Ловіть список питань, які можуть вам поставити на цю тему на співбесіді.

1. Розкажіть трохи про структури даних

Структура даних — це сховище даних, де лежить інформація, структурована певним чином. Ці структури заточені під ефективне виконання певних операцій. Типовими прикладами структур даних є:

• масиви,
• стеки,
• черги,
• пов'язані списки,
• графи,
• дерева,
• префіксні дерева,
• таблиці хеш.

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

2. Що ви знаєте про Масиви?

Масив – це контейнер для зберігання однотипних значень, кількість яких було задано заздалегідь. Приклад створення масиву з рядковими значеннями:

String[] strArray = {"Java","is","the","best","language"};

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

int[] arr = new int[10];

Так, для масиву з елементами типу boolean початкові ( default ) значення дорівнюють false , для масивів з числовими значеннями - 0, з елементами типу char - \u0000 . Для масиву типу класу (об'єкти) - null (не порожні рядки - " а саме null" ). Тобто, у прикладі вищі всі значення масиву arrдорівнюють 0 до тих пір, поки вони не будуть безпосередньо задані. На відміну від колекцій масиви не є динамічними. Після оголошення масиву певного розміру, сам розмір не можна змінити. Щоб додати новий елемент до масиву, необхідно створити новий масив більшого розміру та скопіювати в нього всі елементи зі старого (це принцип роботи ArrayList). Є один момент, який не всі знають і на якому вас можуть непогано підловити. У Java є два види змінних - прості типи та посилання на повноцінні об'єкти. До якого з них належать масиви? Наприклад, ось:

int[] arr = new int[10];

Начебто все просто - це 10 елементів int . Виходить, можна сказати, що це найпростіший тип? Як би не так. У Java масиви є об'єктами, що динамічно створюються і можуть бути призначені змінним типу Object. Усі методи класу Object можна викликати у масиві. Тому ми можемо навіть написати:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

При виведенні в консолі можна отримати щось на зразок: Докладніше про особливості масивів Java розповідається в цій статті o Java Array . Щоб закріпити знання, можна вирішити кілька завдань із цієї добірки .

3. Розкажіть про ієрархію колекцій

Колекції застосовують у ситуаціях, коли потрібна гнучкість під час роботи з даними. Колекції можуть додавати елемент, видаляти елемент та виконувати безліч інших операцій. У Java є безліч різних реалізацій, а нам потрібно лише вибрати правильну колекцію для поточної ситуації. Як правило, коли ви згадуєте інтерфейс Collection , вас просять перерахувати деякі його реалізації та відношення з Map . Що ж, розбираймося. Отже, Collection та Map – це дві різні ієрархії для структур даних. Як виглядає ієрархія Collection : Інтерфейс Collectionє ключовою верховною ланкою з переліком базових методів, від якого беруть початок три базові види структур даних - Set , List , Queue . Set<T> - інтерфейс, що є сукупністю об'єктів, в якій кожен об'єкт є унікальним. List<T> - інтерфейс, що представляє впорядковану послідовність об'єктів, яка називається списком. Queue<T> - інтерфейс, що відповідає за структури, які організовані у вигляді черги (послідовне зберігання елементів). Як говорилося раніше, Map є окремою ієрархією: Map<K, V>- Інтерфейс, що представляє словник, в якому елементи містяться у вигляді пар "ключ-значення". При цьому всі ключі (K) є унікальними в межах об'єкта Map . Цей вид колекції полегшує пошук елемента, якщо нам відомий ключ – унікальний ідентифікатор об'єкта.

4. Що ви знаєте про Set?

Як говорилося раніше, ця колекція представляє безліч унікальних елементів. Інакше кажучи, той самий об'єкт не може зустрічатися в Java Set більше одного разу. Також хотілося б позначити, що з Set ми не можемо витягнути елемент за номером (індексом) лише перебором. Важливо, що різні реалізації Set мають різний спосіб структуризації даних. Конкретні реалізації ми розглянемо далі. Отже, основні реалізації Set : HashSet— безліч, яка заснована на хеш-таблиці, що допомагає при пошуку. Використовує хеш-функцію, яка покращує продуктивність при пошуку та вставці. Незалежно від кількості елементів, в основному, вставка та пошук (іноді і видалення) виконуються за час, близький до постійного – O(1). Докладніше з хеш-функцією ми ознайомимося трохи пізніше. Також хотілося б відзначити, що HashSet містить у собі HashMap , в якому і відбувається вся магія. Ось докладна стаття про HashSet в Java . LinkedHashSet - цей клас розширює HashSet , при цьому не додаючи жодних нових методів. Як і LinkedList, даний клас підтримує зв'язковий список елементів набору в порядку, в якому вони вставлялися. Це дозволяє організувати необхідний порядок у цій реалізації Set . Клас TreeSet створює безліч, яка для організації структури зберігання елементів ґрунтується на червоно-чорному дереві. Інакше кажучи, у цьому безлічі ми можемо сортувати елементи у порядку. Якщо ми використовуємо деякі стандартні об'єкти з “коробки”, наприклад Integer , то для вибудовування безлічі Integer у зростаючому порядку нам нічого і не потрібно робити:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

І в консолі ми отримаємо висновок: Тобто, у цьому set числа зберігаються у відсортованому вигляді. Якщо ми будемо використовувати елементи String у TreeSet , вони будуть відсортовані, але за абеткою. Ну а що якщо у нас є деякий стандартний (користувацький) клас? Яким чином об'єкти даного класу буде структурувати TreeSet ? Якщо ми спробуємо задати довільний об'єкт у цей Set :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Мурзик"));
set.add(new Cat(2, "Барсик"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Ми отримаємо ClassCastException , оскільки TreeSet не знає, як сортувати об'єкти даного типу. У такому разі потрібно, щоб наш кастомний об'єкт реалізував інтерфейс Comparable , і його метод compareTo :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Як ви помітабо, метод compareTo повертає int :

• 1, якщо поточний об'єкт вважається великим;
• -1 якщо поточний об'єкт вважається меншим, ніж той, який прийшов аргументом;
• 0, якщо об'єкти рівні (у разі ми це використовуємо).

У такому випадку наш TreeSet відпрацює коректно та виведе результат: Інший спосіб - створення окремого класу, відповідального за сортування, який реалізує інтерфейс comparator та його метод compare :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

У такому разі для його використання ми повинні задати об'єкт даного класу в конструктор TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

Після цього всі об'єкти класу Cat , що потрапабо до TreeSet , будуть відсортовані за допомогою класу Cat Comparator . Більше про Comparator і Comparable Java можна дізнатися з цієї статті .

5. Розкажіть про Queue

Queue - інтерфейс, що відповідає за структури, які організовані у вигляді черги - структури даних, що зберігає елементи послідовно. Наприклад, із черги людей першою зайде людина, яка прийшла раніше за інших, останнім — той, хто прийшов пізніше за всіх. Цей спосіб називається - FIFO , тобто First in First Out . Унікальні методи Queue спрямовані на роботу з першим або останнім елементом, наприклад:

• add і offer - вставляє елемент у кінець черги,
• remove — витягує та видаляє заголовок цієї черги,
• peek – витягує, але не видаляє заголовок черги.

ЧАСТИНА 2