Вопросы к собеседованию Java-backend, Java core (60 вопросов)09.03.2020 15:02

Секция Concurrency:

• synchronized. wait/notify/notifyAll. Как есть примитивы аналоги из пакета j.u.c? (**)
  
  Краткий ответ

  Дальше тезисы:
  

  • synchronized — ключевое слово, обозначающее скоуп критической секции. Можно ставить напротив объявления метода, или в виде блока в коде.
  • wait () — ожидание треда до тех пор, пока он не будет разбужен другим тредом через notify/notifyAll.
  • У wait () есть перегруженные версии с таймаутами.
  • Тред ставится в wait-set на объекте
  • Перед вызовом wait () нужно захватить монитор на данном объекте (через synchronized)
  • Магия wait () — он отпускает лок на мониторе объекта после вызова, так чтобы в дальнейшем другой тред мог захватить монитор и вызвать notify/notifyAll
  • notify () — будит один из ожидающих тредов, но Важно!  — лок на объекте не отпускает, т.е ожидающий тред разбужен будет, но с ожиданием входа в критическую секцию объекта (т.к как будто остановился на synchronized). Так что если после notify есть тяжелые операции, это затормозит ожидающий тред, т.к тред с notify еще не отпустил монитор
  • notifyAll () — будут разбужены все треды в wait-set, но при этом далее между тредами происходит contention («сражение») за монитор
  • Тред на wait () может быть разбужен также через interrupt, или через spurious wake-up, или по таймауту
  • Так что условие выполнения, которого ожидает тред, проверяется в цикле while, а не в if
  • Примитив-аналог — Condition
• volatile. happens-before. (**)
  
  Краткий ответ

  • Ключевое слово volatile устанавливает отношение happens-before над операциями записи-чтения на поле
  • Таким образом, операции чтения из читающих тредов будут видеть эффекты записи пишущих тредов.
  • В частности, решается проблема double checked locking. Для double/long типов есть проблема атомарности, она решается через атомики
• AtomicInteger, AtomicLong, AtomicBoolean, AtomicDouble (**)
  
  Краткий ответ

  • Атомики предоставляют возможность изменения переменной в нескольких потоках без эффекта гонок.
  • Например, 10 тредов инкрементят AtomicInt = 0, основной тред ждет их выполнения через countdown-latch, далее проверка атомика должна показать 10.
  • Основной механизм под капотом атомиков — цикл cas (compare-and-set). На примере increment:
    
    1. Читаем старое значение
    2. Перед set’ом проверяем старое значение, если оно не изменилось, сетаем старое + 1
    3. Если изменилось, в след. итерации получаем «новое» старое, далее см. п. 1
    
    
• Редкий вопрос — как поймать exception из другого треда? (***)
  
• ReentrantLock (**)
  
  Краткий ответ

  Примитив синхронизации, с помощью которого можно установить границы критической секции. Тред, перед входом в критическую секцию должен сделать захват c операцией lock(), после выхода из крит. секции — сделать unlock(). Другой тред в это время ожидает на lock’е (можно указывать таймаут ожидания), либо может проверить доступность через tryLock().

  ReentrantLock обязательно нужно освобождать (такое кол-во раз, сколько раз он был захвачен), в противном случае будет thread starvation у других тредов, ожидающих у границы критической секции.
  ReentrantLock может быть «честным» (fairness = true), тогда приоритет отдается тредам, ждущих на нем наибольшее кол-во времени, но это вроде как уменьшает производительность

  
  lock.lock();  // block until condition holds
  try {
  	// ... method body
  } finally { 
  	lock.unlock()
  }
  			

• Countdown Latch/Cyclic Barrier (**)
  
  Краткий ответ

  CountdownLatch («защелка») — примитив синхронизации, с помощью которого, например, основной thread может ожидать выполнения работы остальных N тредов. Треды, выполняющие работу, выполняют countDown () на защелке, основной тред ожидает на операции await (). Когда счетчик достигает нуля, основной тред продолжает работу.

  Для синхронизации N тредов (все ждут всех) и переиспользования используется CyclicBarrier, ему также можно указывать действие (через Runnable), выполняемое после синхронизации всех-со-всеми

• ThreadLocal (**)
  
  Краткий ответ

  Класс, предоставляющий доступ к операциям get/set в области видимости треда. Под капотом содержит кастомную реализацию мапы со слабыми ссылками на ключи-треды. Каждый тред имеет доступ только к своим данным.

• Создание singleton? (**)
  
  Краткий ответ

  • Наивным способом, с проверкой на null статического поля
  • Double checked locking (объяснить проблемы double checked locking)
  • Простой — инициализация статического поля, или через enum, т.к ленивая инициализация thread-safe по-умолчанию
• Способы запустить поток? (***)
  
  Краткий ответ

  • Переопределить Thread#run (), запустить через Thread#start ()
  • new Thread (Runnable).start ()
  • Через ExecutorService, используя utility-класс Executors
• ConcurrentHashMap (**)
  
  Краткий ответ

  ConcurrentHashMap имеет разные реализации в 1.7 и 1.8 (что стало для меня неожиданностью).
  Раньше параллелизм основывался на идее сегментирования хэштаблицы на основе заданного уровня параллелизма.
  Начиная с Java 8 — это единый массив бакетов с lock-free (локинг на первой ноде бакета с cas-циклом) и конкурентным ресайзингом.
  Частичная реализация ConcHashMap (аля Java 8) с нуля от kuptservol
• ConcurrentSkipListMap
  
  Краткий ответ

  Lock-free структура данных, хранящая упорядоченный набор элементов, с O (log N) временем доступа/удаления/вставки и weakly-consistent итераторами. Под капотом содержит структуру SkipList, предоставляющую собой слои связных списков, от верхнего к нижнему, элементы верхнего списка ссылаются на элементы нижнего списка под ними. Вероятность попадания элемента при вставке в самый нижний список — 1.0, далее она равняется p (либо ½, либо ¼ как правило) — вероятности попадания элемента из нижнего списка в верхний. Таким образом, на самом верхнем будет вставлено минимальное кол-во элементов. Skiplist — вероятностная структура данных. Подробнее и доходчиво про skiplist описано здесь. Полезна, если стоит задача отсортировать поток событий, одновременно читаемый несколькими тредами, которым нужно делать срез по временному интервалу. Более медленные операции по сравнению с ConcurrentHashMap
  
• Thread states (**)
  
  Краткий ответ

  • NEW
  • RUNNABLE
  • BLOCKED (monitor lock)
  • WAITING (Thread.join)
  • TERMINATED
• Deadlocks, условия наступления, как избежать: (***)
  
  Краткий ответ

  • Условия наступления — эксклюзивность доступа к ресурсам, наличие циклов в графе ожиданий ресурсов, отсуствие таймаутов на ожидание
  • Как избежать — задать порядок доступа к ресурсам. Всегда обращение в порядке либо Thread1→Thread2, либо Thread2→Thread1
• ThreadPoolExecutor — описать механизм работы, св-ва, частности (fixed threadpool, scheduled, single thread executor) (***)
  
  Краткий ответ

  ThreadPoolExecutor — средство контроля исполнения параллельных задач, задействует один из свободных тредов в общем пуле, или ставит задание в очередь, если таковых нет, или достигнуты определенные условия (ниже)

  Основными св-вами ThreadPoolExecutor являются corePoolSize и maxPoolSize. Если текущее количество тредов в пуле < corePoolSize — новый тред будет создаваться в независимости от того, есть ли в пуле незанятые треды. В промежутке между corePoolSize и maxPoolSize тред будет создаваться в том случае, если заполнена очередь задач, и удаляться спустя keepAliveTime. Если кол-во тредов стало >= maxPoolSize — новые треды не создаются, а задачи ставятся в очередь.

  Есть возможность регулировать поведение очереди:
  

  • Direct handoffs: немедленная передача задачи тредпулу. Нет понятия очереди задачи. Если свободных тредов нет — кидается exception. Применимо при неограниченных maxPoolSize, но нужно понимать проблему при быстрых записях и медленных чтениях, что может спровоцировать непомерное потребление ресурсов
  • Unbounded queues: очередь без ограничений. Задачи будут добавляться в нее при превышении corePoolSize, при этом maxPoolSize будет игнорироваться. Unbounded queues имеют проблемы потребления ресурсов при больших нагрузках, но сглаживают рост тредов при пиках.
  • Bounded queues: очередь с ограничениями. Задачи будут добавляться в очередь до достижения некоего capacity. Для достижения наилучшей производительности нужно понимать размеры corePoolSize и самой очереди и чем можно пожертвовать — перфомансом (малый corePoolSize и большая очередь), или же памятью (ограниченная очередь, большой corePoolSize)

  Частности ThreadPoolExecutor:
  

  • ScheduleThreadPoolExecutor — применяется для периодичных по времени задач
  • fixed thread pool — частность ScheduleThreadPoolExecutor’а с настроенным corePoolSize и unbounded queue
  • single thread executor — тредпулл, c сorePoolSize = 1, гарантирующий последовательное выполнение задач из очереди

  
  
  
  

Секция Collections:

• Рассказать про java.util.collection. (*)
  
  Краткий ответ

  • Iterable — реализуют коллекции, по которым можно проитерироваться
  • Сollection — общий интерфейс для коллекций
  • List (стандартная реализация ArrayList) — список с массивом элементов, с возможностью случайного доступа элемента по индексу за O (1), вставкой/удалением со сложностью O (n)
  • Set (стандартная реализация HashSet) — мн-во элементов без дубликатов. Нет возможности доступа по индексу, есть вставка и удаление за O (1)
  • Map (стандартная реализация HashMap) — мн-во пар элементов «ключ-значение». Доступ по ключу/добавление/удаление за O (1) при оптимальном случае, O (n) — при вырожденном

  
  Обзор по коллекциям от JournalDev
• Устройство ArrayList, LinkedList, HashMap, HashSet. Когда следует использовать. Контракт equals/hashcode для Map, Set (*)
  
  Краткий ответ

  Обзор по коллекциям от JournalDev
• Итератор по коллекции, его св-ва и интерфейс (*)
  
  Краткий ответ

  • Может только один раз проходить по коллекции. Для прохождения в двух направлениях есть ListIterator
  • Если в foreach цикле структурно модифицировать коллекцию, при последующем обращению к элементу (неявно через итератор) получим ConcurrentModificationException (fail-fast)
  • hasNext (), next () — основные методы
• Hashtable vs HashMap (*)
  
  Краткий ответ

  • Hashtable — legacy, thread safe, методы синхронизированы, поэтому работа с Hashtable (обращение, удаление, добавление) в целом накладнее
  • HashMap — не thread-safe
• Java 8,11: новые методы в Map (**)
  
  Краткий ответ

  • Java 8: compute
  • Java 8: computeIfAbsent
  • Java 8: computeIfPresent
  • Java 8: forEach
  • Java 8: putIfAbsent
  • Java 11: factory-методы of ()
• LinkedHashMap, зачем он нужен (**)
  
  Краткий ответ

  • Позволяет сохранять порядок вставки пар key-value в Map
  • Каждый entry содержит помимо hash, value, next (следующий элемент в бакете) также поля, указывающие на предыдущий и следующий элементы относительно порядка вставки
• Устройство TreeMap (**)
  
  Краткий ответ

  • Cбалансированное красно-черное дерево
  • Реализует интерфейс NavigableMap, что позволяет возвращать из него элементы, больше (меньше) указанного, либо range элементов, находящийся в определенных границах
• Какой контракт Comparator должен соблюдать?
  
  Краткий ответ

  Быть согласованным с equals ()

• Есть ли способ сделать enum ключом Map? (**)
  
  Краткий ответ

  EnumMap — массив, по размеру соотвествующий кол-ву элементов в enum’е. Индекс элемента массива соотвествуют ordinal’у из enum’а
• Расскажите про CopyOnWriteArrayList/CopyOnWriteHashSet (**)
  
  Краткий ответ

  • СopyOnWriteArrayList — иммутабельный list, при добавлении/апдейте/удалении элементов из которого пользователь получает новую модифицированную копию данного списка
  • СopyOnWriteHashSet — иммутабельный set, при добавлении/апдейте/удалении элементов из которого пользователь получает новую модифицированную копию данного set’а 
• IdentityHashMap — когда используется? (**)
  
  Краткий ответ

  IdentityHashMap — используется, только если нужно проверять идентичность двух ссылок, а не эквивалентность двух объектов по ним. Например, если нужно отслеживать уже посешенные ноды в графе, или строить карту объекты-прокси. IdentityHashMap представляет из себя не классическую хэштаблицу со связанными списками, это linear probing map (бонус за объяснение работы linear probing)
• Интерфейсы Queue/Deque и их реализации (***)
  
  Краткий ответ

  • Queue — коллекция, предоставляющая возможности упорядочения элементов в порядке вставки согласно принципу FIFO. Поддерживает два набора операций добавления/удаления/взятия элемента с конца — с возвращением спец. значения при исключительной ситуации (пустая или заполненная очередь), и с киданием exception’а
  • Deque — коллекция, предоставляющая возможность вставки значений в начала и в конец, позволяющая организовать очереди по принципам FIFO/LIFO. Предпочтительна для реализации стэка вместо Stack. Ниже приведен набор операций для Deque:
    
    
  • BlockingQueue — очередь, блокирующая операции чтения take при пустой очереди или операции записи put при полной очереди. Есть наборы операций и с неблокирующей семантикой. Ниже определен полный список операций чтения/записи.
    
  • ArrayBlockingQueue — кольцевой bounded-buffer с внутренним capacity и fairness policy. Все операции чтения и записи защищены внутренним lock’ом (j.u.c.l.ReentrantLock), неявно связанным с двумя condition’ами — notFull, notEmpty. Соотвественно, если пишущий тред, захвативший общий lock, застрял на condition’е notFull, он неявно освобождает lock, чтобы читающий тред мог освободить очередь, и сигнализировать producer’у о том, что можно продолжать. Ровно и наоборот, читающий тред также захватывает общий lock, застревает на notEmpty, неявно освобождает lock, чтобы пишущий тред мог положить новый элемент и просигналить о непустой очереди. Т.е семантика такая же, как и у synchronized/wait/notify/notifyAll. Fairness = true позволяет предотвратить ситуации thread starvation для консьюмеров и продюсеров, но снизит производительность.
  • LinkedBlockingQueue — очередь, в которой элементы добавляются в связанный список, основанная на two-lock queue, описанного в статье Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.

  
  
  
  

Секция IO:

• InputStream, OutputStream и их buffered версии (*)
  
  Краткий ответ

  Далее, для краткости InputStream — is, OutputStream — os
  is — побайтное чтение из сокета/файла/строки/другого байтового массива
  os — побайтная запись в сокет/файл/другой байтовый массив
  Buffered-версии нужны для оптимизации чтения/записей через отдельный буффер

• Зачем нужен Reader? (*)
  
  Краткий ответ

  Reader позволяет указать Charset при чтении
• Serializable, serialVersionUID (*)
  
  Краткий ответ

  Классы, чьи объекты подвергаются сериализации/десериализации должны реализовывать marker интерфейс Serializable (и иметь статическое поле serialVersionUID для указании при сериализации, с какой версией класса данный объект был сериализован. Если serialVersionUID из сериализованного представления не совпадает c serialVersionUID класса «на том конце провода» — то кидается exception)

  На практике, уже довольно редко используется, т.к тем же Jackson/GSON не обязательно наличие данного интерфейса для сериализации

• try-with-resources. AutoCloseable (*)
  
  Краткий ответ

  try-with-resources — краткая замена стандартному try…catch…finally. Закрывает ресурс после выхода из секции try-with-resources. Ресурс должен имплементить интерфейс AutoCloseable.

  «Ресурс» в данном контексте — это класс, представляющий cобой соединение/cокет/файл/поток
  

  
  try (InputStream is = new FileInputStream("/path/to/file.txt")) {
  	...
  }
  			

Секция Exceptions:

• Отличие checked-exception/unchecked-exception. Error, Exception, RuntimeException (*)
  
  Краткий ответ

  • Checked exceptions (проверяемые исключения). В JDK представлены классом Exception. Исключения, которые нельзя проигнорировать, их обязательно нужно обрабатывать, либо специфицировать в сигнатуре метода, для обработки выше. Как правило, считаются дурным тоном, т.к код со мн-вом конструкций try…catch плохо читабелен, к тому же добавление новых пробрасываемых исключений в сигнатуре метода может сломать контракт вызова у пользователей данного метода.
  • Unchecked exceptions (непроверяемые исключения). В JDK это класс RuntimeException. Можно игнорировать, не требуют обработки через try…catch, или указания в сигнатуре через throws. Минус такого подхода — у вызывающей стороны нет никакого понимания, как обрабатывать ситуацию, когда под капотом «рванет»
  • Error — ошибки, кидаемые JVM в результате нехватки памяти (OutOfMemoryError), переполнения стэка (StackOverflowError) и.т.д

Полезные ссылки:

1. Утечки памяти — статья на TopTal.com
2. Частичная реализация ConcHashMap (аля Java 8) с нуля от kuptservol
3. Структура SkipList
4. Обзор коллекций от JournalDev
5. Обзор коллекций от vedenin1980
6. Обзор пакета java.util.concurrency (Java 7) от Melnosta
7. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott (для сильных духом)

© Habrahabr.ru