Что могут спросить на собеседовании: структуры данных в 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, если текущий (this) объект считается большим;
• -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