Algoritms, Collections Flashcards Preview

Java Core > Algoritms, Collections > Flashcards

Flashcards in Algoritms, Collections Deck (32)
Loading flashcards...
1

В чем идея merge sort?

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

2

В чем идея quick sort?

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

3

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

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

4

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

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

5

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

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

6

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

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

7

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

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

8

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

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

9

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

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

10

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

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

11

Что такое ConcurrentModificationException?

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

12

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

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

13

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

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

14

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

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

15

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

ArrayList
CopyOnWriteArrayList
Stack
Vector

16

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

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

17

Что такое TreeMap

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

18

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

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

19

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

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

20

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

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

21

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

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

22

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

Vector, Hashtable, Properties, Stack

23

Что такое Iterator?

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

24

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

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

25

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

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

26

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

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

27

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

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

28

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

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

29

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

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

30

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

read-only коллекция
Collections.unmodifiableList(List extends T> list)