Пользователь Константин
Константин
36 уровень
Одесса

Что могут спросить на собеседовании: структуры данных в Java. Часть 1

Статья из группы Java Developer
Привет! Как ни крути, вам не стать разработчиком без успешного прохождения входного технического собеседования. Что могут спросить на собеседовании: структуры данных в Java - 1Технологий, связанных с Java, очень много, и выучить все невозможно. Что-то специфическое, как правило, на собеседованиях спрашивают только в том случае, если ищут разработчика с хорошим опытом в каком-то важном для проекта фреймворке. Если это так, вас будут гонять по этому фреймворку во весь рост, вы уж не сомневайтесь.Что могут спросить на собеседовании: структуры данных в Java - 2Но мы сейчас говорим о базе, которую должен знать каждый 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());
При выводе в консоли можно получить что-то вроде:
[I@4769b07b
Подробнее об особенностях массивов в Java рассказывается в этой статье o Java Array. Чтобы закрепить знания, можно решить несколько задач из этой подборки.

3. Расскажите об иерархии коллекций

Коллекции используются в ситуациях, когда нужна гибкость при работе с данными. Коллекции могут добавлять элемент, удалять элемент и выполнять множество других операций. В Java есть множество различных реализаций, а нам нужно всего лишь выбрать правильную коллекцию для текущей ситуации. Как правило, когда вы упоминаете интерфейс Collection, вас просят перечислить некоторые его реализации и отношение с Map. Что ж, давайте разбираться. Итак, Collection и Map — это две разные иерархии для структур данных. Как выглядит иерархия Collection:Что могут спросить на собеседовании: структуры данных в Java - 3Интерфейс Collection является ключевым верховным звеном с перечнем базовых методов, от которого и берут начало три базовых вида структур данных — Set, List, Queue. Set<T> — интерфейс, представляющий собой совокупность объектов, в которой каждый объект является уникальным. List<T> — интерфейс, представляющий упорядоченную последовательность объектов, которая называется списком. Queue<T> — интерфейс, отвечающий за структуры, которые организованы в виде очереди (последовательное хранение элементов). Как говорилось раньше, Map является отдельной иерархией:Что могут спросить на собеседовании: структуры данных в Java - 4Map<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);
И в консоли мы получим вывод:
[1, 2, 3, 4]
То есть, в данном 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 отработает корректно и выведет результат:
[Cat{age=2, name='Барсик'}, Cat{age=3, name='Гарфилд'}, Cat{age=4, name='Мурзик'}]
Другой способ — создание отдельного класса, ответственного за сортировку, который реализует интерфейс 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Что могут спросить на собеседовании: структуры данных в Java. Часть 1 - 5
Комментарии (9)
Чтобы просмотреть все комментарии или оставить свой, перейдите в полную версию
Arjun 37 уровень, Санкт-Петербург
21 октября 2020
3. Расскажите об иерархии коллекций Вершина иерархии интерфейс Iterable, а не Collection. На этом моменте любят подловить на собеседованиях, сам один раз попался.
Юрий 26 уровень, Калининград
17 октября 2020
Класс!!!
Андрей 19 уровень, Москва
15 октября 2020
Здорово!👍