Algoritms, Collections Flashcards
В чем идея merge sort?
Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Наконец, их решения комбинируются, и получается решение исходной задачи.
В чем идея quick sort?
- из массива выбирается некоторой опорный элемент a[i]
- запускается процедура разделения массива, которая перемещает все ключи, меньшие, либо равные a[i], влево от него, а все ключи, большие, либо равные a[i] - вправо,
- для обоих подмассивов: если в подмассиве более двух элементов, рекурсивно запускаем для него ту же процедуру.
Что такое двоичный поиск?
Это алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины.
Что такое Big O notation?
Обозначение для описания предельного поведения алгоритма.
принадлежит ли интерфейс Map к иерархии интерфейсов Collection?
Нет, это разные иерархии.
Почему интерфейс Map не наследуется от Collection?
Потому что у Map принцип хранения данных: пара ключ-значение, а у Collection - только значение.
Что такое NavigableSet и NavigableMap?
Это интерфейсы являются расширениями интерфейсов SortedSet и SortedMap и добавляют возможности перемещения по отсортированной коллекции.
Что такое интерфейс Enumeration?
Это быстрая версия интерфейса Iterator. У Enumeration есть всего два метода: hasMoreElements() и nextElement().
Какое отличие Enumeration и Iterator
Enumeration быстрее и использует меньше памяти чем Iterator
Iterator безопаснее потому что запрещает изменять коллекцию, а также может удалять элементы из коллекции.
Чем отличается Iterator от ListInterator?
Iterator для List и Set, а ListIterator только для List.
Iterator может проходить только в одном направлении, а ListIterator в двух.
ListIterator наследуется от Iterator и может также добавлять , заменять элементы,и возвращать индекс элементов.
Что такое ConcurrentModificationException?
Это исключительная ситуация которая возникает, когда модифицируем коллекцию во время прохождения по ней итератором, не используя итератор.
Какое отличие свойств итератора fail-fast от fail-safe?
Fail-Fast итератор бросает ConcurrentModificationException, а Fail-Safe нет.
Fail-Safe внутри работает с клонированной коллекцией.
Какая внутренняя организация HaspMap в Java?
HashMap - Внутри это массив, элементы в документации называются бакетами(buckets). В бакете хранится первый эемент связанного списка. Таким образом, HashMap имеет внутри - массив связанных списков. Элемент связанного списка - объект класса Entry, содержит ключ, значение и ссылку на следующий Entry.
Что значит маркерный интерфейс java.util.RandomAccess?
Означает что доступ к элементам коллекции происходит за константное время О(1)
Какие коллекции реализует интерфейс RandomAccess?
ArrayList
CopyOnWriteArrayList
Stack
Vector
Чем отличаются интерфейсы List, Set, Queue?
List - Представляет собой не упорядоченную коллекцию, в которой допустимы дублирующие значения.
Set - описывает не упорядоченную коллекцию, не содержащую повторяющихся элементов.
Queue - коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки.
Что такое TreeMap
Класс TreeMap разширяет класс AbsractMap и реализует интерфейс NavigableMap.
Хранение элементов в дереве
Объекты сохраняются в отсортированном порядке по возрастанию
Чем отличается ArrayList от Vector?
Методы класса Vector синхронизированны, в то время как ArrayList -нет
Чем отличается ArrayList от LinkedList?
В первом массив, во втором список.
Какой тип списка LinkedList?
Двухсвязный список
Что такое java.util.EnumSet?
EnumSet это реализация интерфейса для работы с enum типами. Все элементы должны принадлежать к одному типу enum
EnumSet не синхронизирован и не позволяет использовать null как элемент
Какие есть thread-safe коллекции?
Vector, Hashtable, Properties, Stack
Что такое Iterator?
Итератор - это стандартный способ доступа к элементам коллекции. Это объект, связанный с коллекцией, и предоставляет доступ к элементам по одному.
Назовите реализации интерфейсов Iterator и ListIterator?
Каждая коллекция, которая возвращает итератор, имеет свою собственную реализацию итератора как вложенный класс.
Контракт equls() и hashcode()?
- Для одного и того же объекта, хэш-код всегда будет одинаковым;
- Если объекты равно то хэшкоды тоже равны
- Если хэш коды равны то объекты не всегда равны
- Если хэшкоды разный то и объекты разные
Какая разница между TreeSet и LinkedHashSet?
LinkedHashSet в основе лежит LinkedHashMap вместо HashSet
TreeSet - содержит в себе объект NavigableMap что и обуславливает его поведение
Внутренняя реализация HashSet и HashMap?
HashSet - реализация интерфейса Set, базирующаяся на HashMap.
HashMap - внутри массив связанных списков. Элемент связанного списка - объект класса Entry
Как разница между Hashtable и HashMap?
HashMap не синхронизированна и HashMap позволяет использовать null в качестве ключа и в качестве значения
Какое отличие между ConcurrentHashMap, HashTable и SynchronizedMap?
все методы в HashTable synchronized
SynchronizedMap подобна к HashTable, но можно любую Map обернуть в SynchronizedMap используя Collections.synchronizedMap()
ConcurrentHashMap - синхронизация по частям коллекции
SynchronizedMap и HashTable блокируют коллекции целиком
Что такое не модифицированная коллекция?
Как ее создать?
read-only коллекция
Collections.unmodifiableList(List extends T> list)
Как и когда происходит увеличение количества корзин в HashMap?
По достижению предельного значения, число корзин увеличивается в 2 раза. Для всех хранимых элементов вычисляется новое местоположение с учетом нового числа корзин.
Как найти средний элемент в связном списке за один проход?
Использовать два указателя. Один будет итерировать каждый раз и так найдем длину списка второй будет будет итерировать каждый второй раз.
