В последнее время меня посещает стойкая мысль, что мое профессиональное развитие сильно замедлилось и я хочу это как-то исправить.
Да, я читаю книги, слушаю курсы, но при этом приходит понимание, что, возможно, пора менять работу, здесь вроде все изучено, мы постепенно впадаем в рутину.
Эта мысль побудила меня разослать резюме в несколько компаний-лидеров рынка.
Пройдя собеседование в 3 из них, я решил, как обычно, внести свои 5 копеек в освещение обширной темы собеседования, а именно технических вопросов, касающихся Java-коллекций, с которыми приходится сталкиваться.
Да, я знаю, скажет читатель: «коллекции — это избитая тема, насколько это возможно», но некоторые вопросы ниже я задал своим знакомым разработчикам, занимающим должности разработчиков («крепких середняков», по-русски).
стандартам подмосковной глубинки, которые на практике уверенно справляются со своей работой, но в теории, скажем так, есть пробелы, потому что работа не требует решения каких-то нетривиальных задач, и потому что не всем интересно учиться как работает структура данных внутри), что вызвало путаницу.
Думаю, что обсуждаемый материал будет не очень интересен разработчикам выше уровня Junior (попрошу их прокомментировать, дополнить и покритиковать представленный здесь материал), но Juniors уверены, что найдут для себя что-то интересное в этой статье.
Честно говоря, во время собеседования я не знал ответов на некоторые вопросы, изложенные ниже, хотя казалось, что я уже прошел юниорский этап.
Это вдвойне обидно, учитывая, что позиции в тех компаниях, где мне нравилось всё, от общения с HR до возможной будущей сферы деятельности, не смогли получить оффер и были вопросы по коллекторам, с которыми я не смог справиться (я уверен, они внесли свой негативный вклад).
А вот там, где с точки зрения собеседования все прошло вполне хорошо, предложенная сфера деятельности и общение в целом с будущими коллегами оставили отрицательный след, так что закон «подлости» во всей красе.
В итоге этой темой я хочу восполнить обнаруженные пробелы в голове + систематизировать эти знания на бумаге.
В этой статье я рассмотрю не только вопросы, которые вызывали у меня затруднения на последних собеседованиях, но и вопросы, которые мне задавались на протяжении всей моей практики собеседований.
Что ж, думаю, пора перейти к вопросам: 1. Чем ArrayList отличается от LinkedList? В моем рейтинге это один из двух самых популярных вопросов о коллекции, задаваемый в 90% случаев.
Вызвал у меня проблему на первом собеседовании с младшим разработчиком.
Короткий ответ на этот вопрос таков: ArrayList — это список, реализованный на основе массива, а LinkedList — это классический связанный список, основанный на объектах со связями между ними.
Плюсы ArrayList: возможность доступа к произвольному элементу по индексу за константное время (так как это массив), минимальные накладные расходы при хранении такого списка, вставка в конец списка в среднем тоже производится за константное время.
В среднем, поскольку массив имеет некий начальный размер n (в коде это параметр емкости), по умолчанию n = 10, при записи n+1 элементов создается новый массив размером (n * 3)/2 + 1 будет создан, там будут размещены Все элементы из старого массива + добавляемый новый элемент. В результате мы получаем, что при добавлении элемента, когда необходимо расширить массив, время добавления будет значительно больше, чем при записи элемента в готовую пустую ячейку.
Однако в среднем время, необходимое для вставки элемента в конец списка, постоянно.
Последний элемент удаляется за постоянное время.
Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это требует перезаписи всех элементов, расположенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов изменяется размер массива.
не уменьшается до тех пор, пока не будет явно вызван метод TrimToSize().
LinkedList, наоборот, может выполнять вставку/удаление элементов в списке за постоянное время (вставка и удаление, поиск позиции вставки и удаления сюда не входят).
Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за постоянное время — ссылки на первый и последний элементы сохраняются всегда, поэтому добавление элемента в конец списка не означает, что вы приходится перебирать весь список в поисках последнего элемента).
В целом LinkedList уступает ArrayList в абсолютных показателях как по потреблению памяти, так и по скорости операций.
LinkedList предпочтительнее использовать при активной работе (вставке/удалении) с серединой списка или в случаях, когда необходимо гарантированное время добавления элемента в список.
Для углубленной и в то же время экспресс-тренировки очень рекомендую прочитать эти замечательные статьи.
тарзан82 О ArrayList И Связанный список .
Еще рекомендую статью Лэни о потреблении памяти коллекций - очень информативно .
2. Что вы обычно используете (ArrayList или LinkedList)? Почему? Этот вопрос является слегка замаскированной версией предыдущего, поскольку ответ на этот вопрос приведет к постепенному предъявлению ответа на предыдущий вопрос.
В 90% случаев ArrayList будет быстрее и экономичнее LinkedList, поэтому обычно используют ArrayList, но все же в 10% случаев всегда есть LinkedList. Я говорю, что обычно использую ArrayList, ссылаясь на тесты и последний абзац из предыдущего вопроса, но не забываю и про LinkedList (в каких случаях? Еще помогает последний абзац предыдущего вопроса).
3. Что быстрее: ArrayList или LinkedList? Еще одна замаскированная версия первого вопроса.
Хитрость вышеперечисленных вариантов заключается в том, что постановка вопроса предполагает односложный ответ с выбором одного из предложенных вариантов, что, по мнению автора вопроса, насколько я понимаю, должно сразу идентифицировать человека с поверхностными знаниями о коллекциях.
.
Правильным действием будет встречный вопрос о том, какие действия будут производиться над конструкцией.
В результате диалог плавно переходит к ответу на первый вопрос.
4. Вам нужно добавить 1 миллион.
элемент, какую структуру вы используете? Также довольно популярная скрытая версия первого вопроса.
Постановка также предполагает выбор одного из предложенных вариантов, хотя на самом деле информации для однозначного выбора нет. Необходимо задать дополнительные вопросы: В какую часть списка добавляются элементы? есть ли информация о том, что тогда будет с элементами списка? Есть ли какие-либо ограничения по памяти или скорости выполнения? В общем, тот же первый вопрос, но немного с другой стороны: посредством дополнительных вопросов вы показываете глубину понимания работы Array и Linked List. Однажды я сам «попался» на этот крючок, думая про себя, что добавление означает «вставку» в конец списка и энергично продвигая ArrayList, хотя о дальнейших действиях с этим списком я ничего не знал (и не пытался узнать) и возможные ограничения.
5. Как удалить элементы из ArrayList? Как в этом случае изменится размер ArrayList? Опять же, ответ на вопрос 1 содержит и ответ на этот вопрос.
При удалении произвольного элемента из списка все элементы, расположенные «правее», смещаются на одну ячейку влево и реальный размер массива (его емкость) никак не меняется.
Есть механизм автоматического «расширения» массива, но нет автоматического «сжатия»; вы можете выполнить «сжатие» только явно, используя команду TrimToSize().
6. Предложите эффективный алгоритм удаления нескольких соседних элементов из середины списка, реализуемый ArrayList. Этот, по моим меркам, не избитый вопрос, попался мне лишь однажды, когда я не знал механизма удаления элементов из ArrayList. В результате это вызвало у меня серьезные трудности.
На самом деле все довольно просто и очевидно, когда знаешь, как удалить один элемент. Допустим, вам нужно удалить n элементов из позиции m в списке.
Вместо того, чтобы выполнять удаление одного элемента n раз (каждый раз сдвигая на 1 позицию элементы, находящиеся в списке «вправо»), нужно сдвинуть все элементы, находящиеся «вправо» на n+m позиций, на n элементов слева от начала списка.
Таким образом, вместо того, чтобы делать n итераций перемещения элементов списка, все делается за 1 проход. 7. Как работает HashMap? Это второй по популярности вопрос о коллекциях в списке.
Я даже не помню, было ли время, когда мне не задавали этот вопрос.
Короче говоря, HashMap состоит из «ведёр».
С технической точки зрения сегменты — это элементы массива, в которых хранятся ссылки на списки элементов.
При добавлении новой пары ключ-значение он вычисляет хеш-код ключа, на основании которого рассчитывается номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пуста, то в ней сохраняется ссылка на вновь добавленный элемент, а если элемент там уже есть, то происходит последовательный переход по ссылкам между элементами цепочки, в поисках последнего элемента.
из которого размещается ссылка на вновь добавленный элемент. Если в списке найден элемент с таким же ключом, он заменяется.
Добавление, поиск и удаление элементов занимает постоянное время.
Вроде все замечательно, с одной оговоркой: хеш-функция должна равномерно распределять элементы по сегментам, в этом случае временная сложность для этих 3-х операций будет не ниже log N, и в среднем случае это будет постоянное время.
В общем, этого ответа вполне достаточно для поставленного вопроса; тогда скорее всего начнется диалог по HashMap, с углубленным пониманием процессов и тонкостей.
Еще раз рекомендую прочитать статью тарзан82 К Хэшмап .
8. Каково первоначальное количество сегментов в HashMap? Довольно неожиданный вопрос, опять же однажды он заставил меня угадать количество корзин при использовании конструктора по умолчанию.
Ответ здесь 16. Отвечая, стоит отметить, что вы можете использовать конструкторы с параметрами: через параметр емкости вы можете задать свое первоначальное количество корзин.
9. Какова оценка временной сложности выбора элемента из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента? Ответ на первую часть вопроса можно найти в ответе на вопрос 7 – для выбора элемента требуется постоянное время.
Вот во второй части вопроса я недавно запутался.
И он знал устройство HashMap, а также знал о хеш-функции, но не был готов к такому вопросу, мысленно он устремился совсем в другом направлении и сосредоточился на структуре HashMap, отбросив проблему хэш-кода , который в голове я всегда привык считать хэш-кодом с равномерным распределением.
На самом деле ответ довольно прост и следует из ответа на вопрос 7. Если вы возьмете хеш-функцию, которая снова и снова возвращает одно и то же значение, HashMap превратится в связанный список с паршивой производительностью.
Тогда даже если вы используете хеш-функцию с равномерным распределением, в предельном случае будет гарантирована только временная сложность lg N. Итак, ответ на вторую часть вопроса – нет, не гарантировано.
10. Роль равенства и хэш-кода в HashMap? Ответ на этот вопрос следует из ответа на вопрос 7, хотя он там прямо не оговорен.
hashCode позволяет вам определить сегмент для поиска элемента, а метод равенства используется для сравнения ключей элементов в списке внутри сегмента и ключа, который вы ищете.
11. Максимальное количество значений hashCode()? Здесь все довольно просто, достаточно запомнить сигнатуру метода: int hashCode().
То есть количество значений равно диапазону типа int — 2^32 (точный диапазон никогда не спрашивали, такого ответа было достаточно).
12. Как и когда увеличивается количество сегментов в HashMap? Это довольно тонкий вопрос.
Как показал мой мини-опрос, хотя суть устройства HashMap многие понимают более-менее ясно, этот вопрос часто ставит собеседника в тупик.
Помимо емкости, в HashMap также есть параметр loadFactor, на основе которого рассчитывается максимальное количество занятых бакетов (capacity*loadFactor).
По умолчанию loadFactor = 0,75. При достижении предельного значения количество корзин увеличивается в 2 раза.
Новое «местоположение» рассчитывается для всех хранящихся элементов на основе нового количества сегментов.
13. В каком случае элемент в HashMap может быть потерян? Мне прислали этот интересный вопрос Леокодер , мне ничего подобного не задавали и я честно признаюсь, что прочитав это, я не смог сразу придумать сценарий потери элемента.
Все снова оказалось довольно просто, хотя и не так очевидно: допустим, в качестве ключа используется не примитив, а объект с несколькими полями.
После добавления элемента в HashMap изменяется одно поле объекта, выполняющее роль ключа, участвующего в вычислении хэш-кода.
В результате при попытке найти заданный элемент по исходному ключу будет обращена правильная корзина, но равно (ведь равно и hashCode должны работать с одним и тем же набором полей) уже не найдут указанный ключ в список элементов.
Однако даже если метод равенства реализован таким образом, что изменение заданного поля объекта не влияет на результат, то после увеличения размера корзин и пересчета хэш-кодов элементов указанный элемент с измененным полем ценность, скорее всего, окажется совсем в другой корзине и тогда он будет полностью потерян.
14. Почему byte[] нельзя использовать в качестве ключа в HashMap? Еще вопрос от Леокодер .
Как обычно, все оказалось довольно просто — хеш-код массива не зависит от хранящихся в нем элементов, а присваивается при создании массива (метод расчета хеш-кода массива не переопределяется и рассчитывается с помощью стандартный Object.hashCode() на основе адреса массива).
Кроме того, функция равенства не переопределяется для массивов и выполняет сравнение указателей.
Это приводит к тому, что к элементу, сохраненному с ключом массива, невозможно будет обратиться при использовании другого массива того же размера и с теми же элементами; доступ может быть достигнут только в одном случае - при использовании той же ссылки на массив, которая использовалась для сохранения элемента.
За ответ на этот вопрос отдельная благодарность пользователю @dark_dimius. 15. В чем разница между TreeSet и HashSet? Начнем с того, что Set — это набор (также называемый «набором»).
Set не позволяет хранить два одинаковых элемента.
Формально говоря, термин «множество» уже обозначает совокупность различных элементов; очень важно, что это разные элементы, так как это главное свойство Сета.
С учетом этого определения пояснения о хранении одинаковых элементов не требуется, но в повседневной жизни понятие «множество» утратило строгий смысл относительно уникальности входящих в него элементов, поэтому все же уточним это свойство множества.
в отдельности.
TreeSet обеспечивает упорядоченное хранение элементов в виде красно-черного дерева.
Сложность выполнения базовых операций в TreeSet lg N. HashSet использует тот же подход для хранения элементов, что и HashMap, с той разницей, что в HashSet сам элемент выступает в роли ключа, кроме того, HashSet (как и HashMap) не поддерживает упорядоченное хранение.
элементов и обеспечивает временную сложность для выполнения операций, аналогичных HashMap. 16. Устройство TreeSet? Этот вопрос задается вместо вопроса 14, и краткий ответ здесь таков: TreeSet основан на красно-черном дереве.
Как правило, этого достаточно и собеседник сразу переходит к следующему вопросу; Меня ни разу не спросили о механизме балансировки деревьев или других деталях его реализации.
Для экспресс-углубления знаний по красно-черной древесине рекомендую Эта статья .
17. Что произойдет, если добавить элементы в TreeSet в порядке возрастания? Обычно собеседник предваряет этот вопрос фразой о том, что TreeSet основан на бинарном дереве и если добавлять элементы в порядке возрастания, то как они будут распределяться по дереву.
Если нет точного представления о структуре TreeSet, но есть общее понимание, что это бинарное дерево (в чем нас дополнительно уверяет собеседник), то этот вопрос может привести к интересному результату: все элементы, будучи добавленные в обычное двоичное дерево, будут располагаться в одной и той же ветке длиной N элементов, что сводит на нет все преимущества такой структуры, как дерево (фактически оно оказывается списком).
Фактически, как упоминалось выше, TreeSet основан на красно-черном дереве, которое может самобалансироваться.
В результате TreeSet не волнует, в каком порядке вы добавляете в него элементы, преимущества этой структуры данных сохранятся.
Заключение Надеюсь, обсуждаемые вопросы будут полезны хабраузерам.
Еще прошу меня простить за некоторую возможную наивность в том, что приведенные выше вопросы требуют столь детального рассмотрения, но в свое время такая статья мне бы серьезно помогла.
Уверен, что в статье есть неточности - спрашиваю в комментариях, кроме того, надеюсь, что более опытные товарищи в комментариях будут активно делиться вопросами из своей практики и, если статья будет положительно воспринята сообществом Хабра, то вполне можно продолжить обзор технических вопросов для собеседований по Java. P.S. Немного меркантильного интереса: поиск новой работы продолжается, и если кто-то из хаброузеров находится в процессе поиска Java-разработчика в компанию с современным подходом к разработке и интересными задачами, или может просто порекомендовать присмотреться посмотрите любую подходящую вакансию, буду благодарен, свяжитесь со мной в личном сообщении.
Теги: #коллекции #вопросы на собеседовании #java #java #Алгоритмы
-
О Пользе Ограничений В Коллективном Блоге
19 Oct, 24 -
Старикам Нравится Сервис Presto
19 Oct, 24
