Algoritms, Collections

Question 1

В чем идея merge sort?

Answer 1

Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.

Question 2

В чем идея quick sort?

Answer 2

1. из массива выбирается некоторой опорный элемент a[i]
2. запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
3. для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.

Question 3

Что такое двоичный поиск?

Answer 3

Это алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины.

Question 4

Что такое Big O notation?

Answer 4

Обозначение для описания предельного поведения алгоритма.

Question 5

принадлежит ли интерфейс Map к иерархии интерфейсов Collection?

Answer 5

Нет, это разные иерархии.

Question 6

Почему интерфейс Map не наследуется от Collection?

Answer 6

Потому что у Map принцип хранения данных: пара ключ-значение, а у Collection - только значение.

Question 7

Что такое NavigableSet и NavigableMap?

Answer 7

Это интерфейсы являются расширениями интерфейсов SortedSet и SortedMap и добавляют возможности перемещения по отсортированной коллекции.

Question 8

Что такое интерфейс Enumeration?

Answer 8

Это быстрая версия интерфейса Iterator. У Enumeration есть всего два метода: hasMoreElements() и nextElement().

Question 9

Какое отличие Enumeration и Iterator

Answer 9

Enumeration быстрее и использует меньше памяти чем Iterator

Iterator безопаснее потому что запрещает изменять коллекцию, а также может удалять элементы из коллекции.

Question 10

Чем отличается Iterator от ListInterator?

Answer 10

Iterator для List и Set, а ListIterator только для List.
Iterator может проходить только в одном направлении, а ListIterator в двух.
ListIterator наследуется от Iterator и может также добавлять , заменять элементы,и возвращать индекс элементов.

Question 11

Что такое ConcurrentModificationException?

Answer 11

Это исключительная ситуация которая возникает, когда модифицируем коллекцию во время прохождения по ней итератором, не используя итератор.

Question 12

Какое отличие свойств итератора fail-fast от fail-safe?

Answer 12

Fail-Fast итератор бросает ConcurrentModificationException, а Fail-Safe нет.
Fail-Safe внутри работает с клонированной коллекцией.

Question 13

Какая внутренняя организация HaspMap в Java?

Answer 13

HashMap - Внутри это массив, элементы в документации называются бакетами(buckets). В бакете хранится первый эемент связанного списка. Таким образом, HashMap имеет внутри - массив связанных списков. Элемент связанного списка - объект класса Entry, содержит ключ, значение и ссылку на следующий Entry.

Question 14

Что значит маркерный интерфейс java.util.RandomAccess?

Answer 14

Означает что доступ к элементам коллекции происходит за константное время О(1)

Question 15

Какие коллекции реализует интерфейс RandomAccess?

Answer 15

ArrayList
CopyOnWriteArrayList
Stack
Vector

Question 16

Чем отличаются интерфейсы List, Set, Queue?

Answer 16

List - Представляет собой не упорядоченную коллекцию, в которой допустимы дублирующие значения.
Set - описывает не упорядоченную коллекцию, не содержащую повторяющихся элементов.
Queue - коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки.

Question 17

Что такое TreeMap

Answer 17

Класс TreeMap разширяет класс AbsractMap и реализует интерфейс NavigableMap.
Хранение элементов в дереве
Объекты сохраняются в отсортированном порядке по возрастанию

Question 18

Чем отличается ArrayList от Vector?

Answer 18

Методы класса Vector синхронизированны, в то время как ArrayList -нет

Question 19

Чем отличается ArrayList от LinkedList?

Answer 19

В первом массив, во втором список.

Question 20

Какой тип списка LinkedList?

Answer 20

Двухсвязный список

Question 21

Что такое java.util.EnumSet?

Answer 21

EnumSet это реализация интерфейса для работы с enum типами. Все элементы должны принадлежать к одному типу enum
EnumSet не синхронизирован и не позволяет использовать null как элемент

Question 22

Какие есть thread-safe коллекции?

Answer 22

Vector, Hashtable, Properties, Stack

Question 23

Что такое Iterator?

Answer 23

Итератор - это стандартный способ доступа к элементам коллекции. Это объект, связанный с коллекцией, и предоставляет доступ к элементам по одному.

Question 24

Назовите реализации интерфейсов Iterator и ListIterator?

Answer 24

Каждая коллекция, которая возвращает итератор, имеет свою собственную реализацию итератора как вложенный класс.

Question 25

Контракт equls() и hashcode()?

Answer 25

1. Для одного и того же объекта, хэш-код всегда будет одинаковым;
2. Если объекты равно то хэшкоды тоже равны
3. Если хэш коды равны то объекты не всегда равны
4. Если хэшкоды разный то и объекты разные

Question 26

Какая разница между TreeSet и LinkedHashSet?

Answer 26

LinkedHashSet в основе лежит LinkedHashMap вместо HashSet

TreeSet - содержит в себе объект NavigableMap что и обуславливает его поведение

Question 27

Внутренняя реализация HashSet и HashMap?

Answer 27

HashSet - реализация интерфейса Set, базирующаяся на HashMap.
HashMap - внутри массив связанных списков. Элемент связанного списка - объект класса Entry

Question 28

Как разница между Hashtable и HashMap?

Answer 28

HashMap не синхронизированна и HashMap позволяет использовать null в качестве ключа и в качестве значения

Question 29

Какое отличие между ConcurrentHashMap, HashTable и SynchronizedMap?

Answer 29

все методы в HashTable synchronized
SynchronizedMap подобна к HashTable, но можно любую Map обернуть в SynchronizedMap используя Collections.synchronizedMap()
ConcurrentHashMap - синхронизация по частям коллекции
SynchronizedMap и HashTable блокируют коллекции целиком

Question 30

Что такое не модифицированная коллекция?

Как ее создать?

Answer 30

read-only коллекция

Collections.unmodifiableList(List extends T> list)

Question 31

Как и когда происходит увеличение количества корзин в HashMap?

Answer 31

По достижению предельного значения, число корзин увеличивается в 2 раза. Для всех хранимых элементов вычисляется новое местоположение с учетом нового числа корзин.

Question 32

Как найти средний элемент в связном списке за один проход?

Answer 32

Использовать два указателя. Один будет итерировать каждый раз и так найдем длину списка второй будет будет итерировать каждый второй раз.