Какие вопросы по Java Collection вы задаете (или вам задавали) на собеседовании?

Question

sphinks @sphinks

Какие вопросы по Java Collection вы задаете (или вам задавали) на собеседовании?

После нескольких интересных собеседованиям, набрал список «постоянных» вопрос по коллекциям. Хочу поинтересоваться, что еще из распространенных вопросов пропустил? Вот мой список (авторская постановка вопросов оставлена, так что прошу не писать некорректный вопрос:-):

Иерархия коллекций.
Чем отличается ArrayList от LinkedList?
Что вы обычно используете (ArrayList или LinkedList)? Почему?
Что быстрее работает ArrayList или LinkedList?
Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?
Предложите эффективный алгоритм удаления нескольких элементов из середины списка, реализуемого ArrayList.
Необходимо добавить 1млн. элемент, какую структуру вы используете?

Как устроена HashMap?
Какое начальное количество корзин в HashMap?
Какая оценка временной сложности выборки элемента из HashMap?
Гарантирует ли HashMap указанную сложность выборки элемента?
Роль equals и hashCode в HashMap?
Максимальное число значений hashCode()?
Как и когда происходит увеличение количества корзин в HashMap?

Что такое set?
TreeSet и HashSet? Отличия?
Устройство TreeSet?
Что будет, если добавлять элементы в TreeSet по возрастанию?

Вопрос задан более трёх лет назад
9220 просмотров

Комментировать

Подписаться 10 Оценить Комментировать

Пригласить эксперта

Ответы на вопрос 4

8 комментариев

TheHorse @TheHorse

А вы ответьте на вопросы, если не затруднит.

Написано более трёх лет назад
TheHorse @TheHorse

Мне интересны ответы на эти вопросы:
Необходимо добавить 1млн. элемент, какую структуру вы используете?
Гарантирует ли HashMap указанную сложность выборки элемента?
Что будет, если добавлять элементы в TreeSet по возрастанию?

Написано более трёх лет назад
darkdimius @darkdimius

первый вопрос некорректен. Вы не сказали какие операции с ними проводить.
2 нет. при совпадении hashcode получите вообще o(n)
3 ничего не будет. внутри TreeSet находиться TreeMap который красно-черное дерево. Ему не важен порядок вставок.

Написано более трёх лет назад
TheHorse @TheHorse

1. Только вставка. Максимально быстро. ArrayList vs LinkedList?
2. При открытой адресации, даже если есть совпадения — оценка о(1). Если все хеши совпадают — да, бида, o(n).
Если в качестве ключа передается enum (может такое быть в Java?), реализация хеш-мапа может использовать двухуровневую схему хеширования с универсальным хешированием, на каждом из уровней. Такое есть в Java? Если есть / может быть — ваш ответ не полный.
3. Уверен что не будет больше поворотов, чем при случайном потоке данных?

Написано более трёх лет назад
TheHorse @TheHorse

*Уверены

Написано более трёх лет назад
darkdimius @darkdimius

1. Если только вставка и вы знаете сколько то ArrayList-у можно «дать совет» о размере(на самом деле он предвыделит место) Метод ensureCapacity
Если не использовать этот метод то вопрос спорный, у linkedList-а большие(в сравнении с ArrayList) накладные расходы, а arrayList будет копировать элементы, выделяя при этом память и фрагментируя ее. Но учетное количество копировании будет 3/2 от размера массива, потому я всеже думаю что ArrayList(кстати то что константа 3/2 забита прямо в код — очень плохое свойство стандартного ArrayList)

2. универсальное хеширование никак не связано с с enum-ом. Но его построение предполагает возможность использовать сколь-угодно большие числа. В тьюринг-полном языке java есть все ;) но речь шла о конкретной коллекции, ключем к которой вы можете сделать что угодно, и у него есть метод hashcode который возвращает int. Если все элементы коллекции вернут одно и тоже то будет O(n) какую бы стратегию не использовать.

3. уверен что асимптотически одинаково.
конкретное число может быть в константу отличаться даже между версиями jvm, потому что гарантия предоставляемая jvm именно
This implementation provides guaranteed log(n) time cost for the containsKey , get, put and remove operations. И ничего более.

Написано более трёх лет назад
sphinks @sphinks Автор вопроса

Смысл данного поста в том, чтобы собрать популярные вопросы по коллекциям и опубликовать топик по ним с комментариями. Многие из приведенных вопросов по прежнему вызывают проблемы по мои наблюдениям.
1. То что вопрос не корректен, это да. Но это провокационный вопрос. Подразумевает короткий ответ, ArrayList или LinkedList, а на самом деле, как вы правильно заметили, необходимо задавать уточняющие вопросы, чтобы определится что лучше взять. Насчет вставки в список, здесь возможно все же LinkedList будет лучше, т.к. при каждой вставке нового элемента в середину списка в ArrayList в среднем N/2 элементов придется каждый раз смещать на 1 ячейку. В целом LinkedList рекомендуют при активных операциях удаления.
2. Да, при плохом хешкоде, можно до О(n) дойти.
3. Тоже верно — ничего не будет, красно-черное дерево — само отбалансирует себя.

Написано более трёх лет назад
TheHorse @TheHorse

2. Связь с енумом в том, что мы точно знаем сколько всего есть ключей.
P. S. Хорошие ответы, которые не многие бы дали. Я просто пытался сказать, что можно еще глубже копать и вопросы — не совсем для новичков.

Написано более трёх лет назад

3 комментария

sphinks @sphinks Автор вопроса

Спасибо за ответ. Интересные вопросы.
1. Почему может потеряться элемент в HashMap?
Мое первое предположение здесь, что функция equals() неверно реализована, из-за чего отличающиеся объекты могут переписывать друг друга при попадании в одну и ту же корзину.
2. Почему нельзя ложить byte[] в hash коллекции? Я так понимаю речь идет про использование byte[] в качестве ключа? Расскажите, почему нельзя, пока мыслей сходу нет.
3. Как реализовывать хеш-функцию? Если в общем, то нужно делать функцию которая обеспечивает отображение хранимых объектов на разные значения, для избежания коллизий.

Написано более трёх лет назад
darkdimius @darkdimius

1. Вы описали не самый частый сценарий(к томуже формально вы заменили элемент на равный, вы ничего не поменяли). Обычно элементы теряются, если после добавления их в HashMap изменить поля, на основании которых считается hashcode
2. hashcode у массивов не зависит от их содержимого и определяется в момент создания. То что он окажется внезапно равным не говорит о равенстве содержимого. equals у массивов также не переопределен и выполняет сравнение указателей.
3. вы не учли то что может вызвать проблемы с пунктом 1

Написано более трёх лет назад
sphinks @sphinks Автор вопроса

Спасибо за пояснения, интересные ньюансы.

Написано более трёх лет назад

1 комментарий

Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации

Похожие вопросы

Android

+3 ещё

Средний
Как получить разрешение для автостарта (чтобы при старте оно загружалось) для приложения под Андройд (Android)?
- 1 подписчик
- 15 часов назад
- 45 просмотров
0

ответов
Java

Простой
Как сделать глобальный чат Chatty?
- 1 подписчик
- 20 апр.
- 67 просмотров
0

ответов
Java

+2 ещё

Простой
Selenide + Spring Boot. Как объявить страницу через метод open(), если класс страницы является bean?
- 1 подписчик
- 19 апр.
- 39 просмотров
0

ответов
Java

+1 ещё

Простой
Почему не видит WebSecurityConfigurerAdapter при попытке импортировать его в класс SecurityConfig?
- 1 подписчик
- 19 апр.
- 56 просмотров
1

ответ
Java

Простой
Почему происходит два пустых вывода при чтении с клавиатуры?
- 1 подписчик
- 19 апр.
- 45 просмотров
1

ответ
Java

+3 ещё

Средний
Пытаюсь подключиться к postgresql 16 через docker-compose, использую spring-boot 3.2.4, что не так?
- 1 подписчик
- 17 апр.
- 193 просмотра
3

ответа
Java

+1 ещё

Простой
Как правильно внедрять зависимости в классы, зависящие от не-бинов?
- 1 подписчик
- 16 апр.
- 71 просмотр
1

ответ
Карьера в IT

Простой
Где можно искать стартапы андроид разработчику?
- 1 подписчик
- 16 апр.
- 168 просмотров
2

ответа
Python

+1 ещё

Простой
Возможно ли соединить работающий java код и так же работающий скрипт python?
- 1 подписчик
- 15 апр.
- 224 просмотра
3

ответа
Java

+2 ещё

Простой
Как заставить Tomcat работать c utf-8 и кириллицей?
- 1 подписчик
- 14 апр.
- 62 просмотра
0

ответов
Показать ещё Загружается…

Lead Java

Bell Integrator • Хабаровск

До 400 000 ₽

Lead Java

Bell Integrator • Ульяновск

До 400 000 ₽

Java-разработчик

ДАЛЕЕ

от 200 000 ₽

Анимация логотипа

24 апр. 2024, в 00:08

20000 руб./за проект

Разработка дизайна раздела «Статьи» на сайте «Мир отходов»

23 апр. 2024, в 23:01

10000 руб./за проект

Дизайн личного кабинета (клиентская часть)

23 апр. 2024, в 22:37

500 руб./в час

Answer 1 · 2012-12-07 00:05:31

Какие-то ну уж слишком несложные и ожидаемые вопросы для серьёзного собеседования.

з.ы. каков смысл такого поста?

Answer 2 · 2012-12-07 01:10:03

по коллекциям еще любят спросить про Concurrent Collections и их устройство, или про то, как бы вы доработали ArrayList для многопотокового использования…

а так обычно спрашивают что-то простое, например, почему в HashMap может потерятся элемент, как надо реализовывать hash функцию, почему нельзя ложить byte[] в hash коллекции, какой контракт у equals, или какова сложность перебора всех элементов для ArrayList и LinkedList… я правда андроидом занимаюсь, поэтому видимо нас не сильно мучают по джаве, больше про андроид распрашивают )

Answer 3 · 2012-12-07 08:51:32

TheHorse, это основы даже не Java а теории структур и алгоритмов. Если нет совсем хитрой подоплёки в вопросах, я действительно даже не знаю что тут отвечать ещё))
1. для вставки я бы задумался, тут есть нюансы. Но я знаю как работает и тот и другой и в теории и в реализации стандартной библиотеки Java, так что придумал бы) как комментатор выше я тоже склонился бы к ArrayList в данном случае
2. в теории сложностей алгоритмов да, гарантирует, разумеется, допуская наихудшее
3. не очень понял, по сути порядок вставки не важен, или речь про выборку

Answer 4 · 2014-08-30 00:21:02

Привет я тут отснял роли и собираю снять еще по теме. Может кому будет полезно.
https://www.youtube.com/watch?v=IyPaSUFrhaM

Какие вопросы по Java Collection вы задаете (или вам задавали) на собеседовании?

Войдите, чтобы написать ответ

Минуточку внимания

Войдите на сайт