Java собеседование. Коллекции

    С недавнего времени у меня появилась настойчивая мысль, что профессиональное развитие сильно замедлилось и это хочется как-то исправить. Да, читаю книги, слушаю курсы, но в то же время приходит и понимание того, что возможно пришло время сменить работу, здесь вроде как все изучено, плавно уходим в рутину. Данная мысль сподвигла меня на рассылку своего резюме в несколько компаний — лидеров рынка. После прохождения собеседования в 3 из них, я решил, как водится внести свои 5 копеек в освещение обширной темы собеседования, а именно технических вопросов по Java коллекциям, с которыми приходится сталкиваться. Да, знаю, читатель скажет: «коллекции — избитая тема, сколько можно», но часть из приведенных ниже вопросов, я задавал своим знакомым разработчикам, которые занимают именно позиции разработчиков («крепких середнячков», по меркам недалекой от Москвы глубинки, которые уверенно справляются со своей работой на практике, а вот в теории скажем так есть пробелы, потому, что работа не требует решения каких-то нетривиальных задач, да и потому что не всем это интересно — изучать как внутри работает структура данных), вызывало растерянность. Думаю, что рассмотренный материал будет не очень интересен разработчикам выше уровня Junior (я попрошу их комментировать, дополнять и критиковать изложенный здесь материал), а вот Junior`ы уверен, найдут в этой статье интересное для себя.

    Признаюсь честно, сам при прохождении интервью не знал ответы на некоторые из изложенных ниже вопросов, хотя вроде как уже прошел этап джуниорства. Это вдвойне обидно, с учетом того, что позиции в те компании, где симпатию вызывало все, начиная от общения с HR и заканчивая возможной будущей сферой деятельности не удалось получить оффер и как раз там были вопросы по коллекциям, с которыми я не справился (уверен они внесли свою негативную лепту). А вот там, где все прошло вполне неплохо с точки зрения собеседования, предложенная сфера деятельности и общение в целом с будущими коллегами оставили негатив, так что закон «подлости» во всей красе. В итоге, данным топиком я хочу и в своей голове заполнить обнаруженные пробелы+систематизировать на «бумаге» эти знания.

    В статье я рассмотрю не только вопросы, вызвавшие у меня сложности на последних собеседованиях, но и вопросы, которые мне задавали за всю мою практику прохождения собеседований. Ну что ж, думаю пора переходить к вопросам:

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

    В моем рейтинге это один из двух самых популярных вопросов о коллекции, задают в 90% случаев. Вызвал у меня проблему на моем первом собеседовании на Junior Developer`а. Вкратце ответ на этот вопрос сводится к следующему: ArrayList это список, реализованный на основе массива, а LinkedList — это классический связный список, основанный на объектах с ссылками между ними.

    Преимущества ArrayList: в возможности доступа к произвольному элементу по индексу за постоянное время (так как это массив), минимум накладных расходов при хранении такого списка, вставка в конец списка в среднем производится так же за постоянное время. В среднем потому, что массив имеет определенный начальный размер n (в коде это параметр capacity), по умолчанию n = 10, при записи n+1 элемента, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый, добавляемый элемент. В итоге получаем, что при добавлении элемента при необходимости расширения массива, время добавления будет значительно больше, нежели при записи элемента в готовую пустую ячейку. Тем не менее, в среднем время вставки элемента в конец списка является постоянным. Удаление последнего элемента происходит за константное время. Недостатки ArrayList проявляются при вставке/удалении элемента в середине списка — это взывает перезапись всех элементов размещенных «правее» в списке на одну позицию влево, кроме того, при удалении элементов размер массива не уменьшается, до явного вызова метода trimToSize().

    LinkedList наоборот, за постоянное время может выполнять вставку/удаление элементов в списке (именно вставку и удаление, поиск позиции вставки и удаления сюда не входит). Доступ к произвольному элементу осуществляется за линейное время (но доступ к первому и последнему элементу списка всегда осуществляется за константное время — ссылки постоянно хранятся на первый и последний, так что добавление элемента в конец списка вовсе не значит, что придется перебирать весь список в поисках последнего элемента). В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда происходит активная работа (вставка/удаление) с серединой списка или в случаях, когда необходимо гарантированное время добавления элемента в список.

    Для углубленного и в то же время экспресс обучения очень рекомендую к прочтению замечательные статьи tarzan82 о ArrayList и LinkedList. Так же порекомендую статью от lany о потреблении памяти коллекциями — очень познавательно.

    2. Что вы обычно используете (ArrayList или LinkedList)? Почему?

    Это вопрос является слегка замаскированной версией предыдущего, так как ответ на этот вопрос приведет к постепенному изложению ответа на предыдущей вопрос. В 90% случае ArrayList будет быстрее и экономичнее LinkedList, так что обычно используют ArrayList, но тем не менее всегда есть 10% случаев для LinkedList. Я говорю, что обычно ArrayList использую, ссылаясь на тесты и последний абзац из предыдущего вопроса, но не забываю и про LinkedList (в каких случаях? так же последний абзац предыдущего вопроса помогает).

    3. Что быстрее работает ArrayList или LinkedList?

    Еще одна замаскированная версия первого вопроса. Хитрее приведенных выше вариантов, что постановка вопроса подразумевает односложный ответ с выбором одного из предложенных вариантов, что, по задумке автора вопроса, как я понимаю, должно сразу выявить человека с неглубокими познаниями в collections. Правильным же действием будет встречный вопрос о том, какие действия будут выполняться над структурой. В итоге, диалог плавно переходит к ответу на первый вопрос.

    4. Необходимо добавить 1млн. элемент, какую структуру вы используете?

    Тоже довольно популярная скрытая версия первого вопроса. Так же постановка предполагает выбор одного из предложенных вариантов, хотя на самом деле информации для однозначного выбора нет. Нужно задавать дополнительные вопросы: в какую часть списка происходит добавление элементов? есть ли информация о том, что потом будет происходить с элементами списка? какие то ограничения по памяти или скорости выполнения? В целом, все тот же первый вопрос, но немного с другой стороны: вы через дополнительные вопросы, показываете глубину понимания работы Array и Linked List.
    Однажды я сам «клюнул» на этот крючок, домыслив про себя, что добавить — это «вставить» в конец списка и усиленно продвигал ArrayList, хотя ничего не знал (и не пытался узнать) про дальнейшие действие с этим списком и возможные ограничения.

    5. Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList?

    Опять же, ответ на вопрос 1 содержит ответ и на этот вопрос. При удалении произвольного элемента из списка, все элементы находящиеся «правее» смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой trimToSize().

    6. Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList.

    Неизбитый, по моим меркам вопрос, встречался мне всего однажды, когда я не знал механизма удаления элементов из ArrayList. В итоге вызвал у меня серьезные затруднения. На самом деле все довольно просто и очевидно, когда знаешь как происходит удаление одного элемента. Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n+m позиции на n элементов левее к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход.

    7. Как устроена HashMap?

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

    Вкратце, HashMap состоит из «корзин» (bucket`ов). С технической точки зрения «корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение, вычисляет хеш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время. Вроде все здорово, с одной оговоркой, хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время.

    В целом, этого ответа вполне хватит на поставленный вопрос, дальше скорее всего завяжется диалог по HashMap, с углубленным пониманием процессов и тонкостей.

    Опять же, рекомендую к прочтению статью tarzan82 по HashMap.

    8. Какое начальное количество корзин в HashMap?

    Довольно неожиданный вопрос, опять же меня он когда-то заставил угадывать число корзин при использовании конструктора по умолчанию.

    Ответ здесь — 16. Отвечая, стоит заметить, что можно используя конструкторы с параметрами: через параметр capacity задавать свое начальное количество корзин.

    9. Какая оценка временной сложности выборки элемента из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?

    Ответ на первую часть вопроса, можно найти в ответе на вопрос 7 — константное время необходимо для выборки элемента. Вот на второй части вопроса, я недавно растерялся. И устройство HashMap знал и про хеш-функцию тоже знал, а вот к такому вопросу не был готов, в уме кинулся вообще в другом направлении и сосредоточился на строении HashMap откинув проблему хеш-кода, который в голове всегда привык считать хеш-кодом с равномерным распределением. На самом деле ответ довольно простой и следует из ответа вопроса 7.

    Если вы возьмете хеш-функцию, которая постоянно будет возвращать одно и то же значение, то HashMap превратится в связный список, с отвратной производительностью. Затем даже, если вы будете использовать хеш-функцию с равномерным распределением, в предельном случае гарантироваться будет только временная сложность lg N. Так что, ответ на вторую часть вопроса — нет, не гарантируется.

    10. Роль equals и hashCode в HashMap?

    Ответ на этот вопрос следует из ответа на вопрос 7, хотя явно там и не прописан. hashCode позволяет определить корзину для поиска элемента, а equals используется для сравнения ключей элементов в списке внутри корзины и искомого ключа.

    11. Максимальное число значений hashCode()?

    Здесь все довольно просто, достаточно вспомнить сигнатуру метода: int hashCode(). То есть число значений равно диапазону типа int — 2^32 (точного диапазона никогда не спрашивали, хватало такого ответа).

    12. Как и когда происходит увеличение количества корзин в HashMap?

    Вот это довольно тонкий вопрос. Как показал мой мини-опрос, если суть устройства HashMap себе представляют многие более-менее ясно, то этот вопрос часто ставил собеседника в тупик.

    Помимо capacity в HashMap есть еще параметр loadFactor, на основании которого, вычисляется предельное количество занятых корзин (capacity*loadFactor). По умолчанию loadFactor = 0,75. По достижению предельного значения, число корзин увеличивается в 2 раза. Для всех хранимых элементов вычисляется новое «местоположение» с учетом нового числа корзин.

    13. В каком случае может быть потерян элемент в HashMap?

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

    14. Почему нельзя использовать byte[] в качестве ключа в HashMap?

    Еще один вопрос от LeoCcoder. Как обычно, все оказалось довольно просто — хеш-код массива не зависит от хранимых в нем элементов, а присваивается при создании массива (метод вычисления хеш-кода массива не переопределен и вычисляется по стандартному Object.hashCode() на основании адреса массива). Так же у массивов не переопределен equals и выполняет сравнение указателей. Это приводит к тому, что обратиться к сохраненному с ключом-массивом элементу не получится при использовании другого массива такого же размера и с такими же элементами, доступ можно осуществить лишь в одном случае — при использовании той же самой ссылки на массив, что использовалась для сохранения элемента. За ответ на этот вопрос отдельная благодарность уходит пользователю @dark_dimius.

    15. В чем отличия TreeSet и HashSet?

    Начнем с того, что Set — это множество (так же называют «набором»). 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 разработчика в компанию с современным подходом к разработке и интересными задачами или просто может порекомендовать присмотреться к какой-либо подходящей вакансии — я буду благодарен, прошу в личку.
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 306
    • +7
      В вопросе ArrayList vs LinkedList очень важно ещё и понимать что элементы ArrayList`а хранятся массивом, т.е. линейно в памяти, и можно довольно удачно загрузить кусок массива в кэш процессора, что очень круто скажется на производительности.
      советую почитать: kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/
      • 0
        Спасибо за замечание и статью, отметил себе на вечернее прочтение, судя по всему статья будет интересной.
        • +4
          Ага. Кстати, с ArrayList ещё интересна постановка вопроса о вставке в середину или удалении из середины. Да, с математической точки зрения это O(N-k), где k — позиция вставки/удаления. Но в действительности это делается за одну операцию System.arraycopy, которая реализована нативно и сводится к ассемблерным инструкциям копирования блока памяти, которые даже для незакэшированного массива отработают довольно быстро. У меня (CoreDuo E7300 @2.66GHz) вставка в начало ArrayList из миллиона элементов занимает около одной миллисекунды, то есть по сути дела сдвиг одного элемента в массиве занимает наносекунду. Поэтому здесь линейная сложность не так уж страшна для большинства задач.
          • 0
            Понятие сложность (с прилагательными линейная, квадратичная и т.д.) в принципе асимптотическое, т.е." для достаточно больших N". Никакие инструкции процессора не заменяют понимания алгоритмической сложности
            • 0
              Ну разумеется. Главное, углубляясь в теорию, не оторваться от практики и не забыть о константе. Почему, к примеру, не используют пирамидальную сортировку с её гарантированным O(n*ln(n)) и O(1) дополнительной памяти? Почему предпочитают quickSort с O(n^2) в худшем случае? Всё дело как раз в константе.
              • +3
                В std::sort используется quick sort только если он достаточно близко к n*log(n), в противном случае он достаточно быстро фоллбэкается до heap sort'а
            • +2
              Сложность != скорость.
            • 0
              Ну, если заниматься уже такими подробностями работы процессора, то стоит сказать что на маленьких списках\в хвосте большого списка в случае ArrayList есть возможность что постоянные изменения одних и техже элементов в процессоре проинтерферируют в очереди записи и в память будет отображено только конечно состояние. В случае LinkedList на каждый чих будет выделятся новый обьект-контейнер, потому память будет использоваться разная а значит подобная оптимизация не сработает.
            • +1
              Почему нельзя использовать byte[] в качестве ключа в HashMap?

              Очень удивился, прочитав название. Прочитал весь пункт целиком и хочу сказать, что я бы задал этот вопрос, например, так: «почему важно знать как работает equals для массивов?». Потому что в общем и целом разницы с другими типами нет, объекты действительно разные.

              Ну, я конечно, не джавист, но все же считаю что такие вещи, как передача поссылке, должны быть очевидны любому специалисту.
              • 0
                equals и сравнение ссылок это разные вещи. Обычно классы переопределяют equals так, что сравнение идет логическое. Например для ArrayList equals работает как ожидается — сравнивает содержимое поэлементно. Класс массива в Java по какой-то причине очень бедный, в нем функционала практически нет. Объяснения этому я лично не знаю.
                • +1
                  > Класс массива в Java по какой-то причине очень бедный, в нем функционала практически нет. Объяснения этому я лично не знаю.

                  Есть Arrays.hashcode() и Arrays.equals() для особых ценителей, а так — меньше лишних телодвижений и додумок за программиста. Меньше магии в core API.
                  • 0
                    Сами разработчики из оракла высказывают на докладах иное мнение.
                    Project Lambda — больше магии в core API!
                    • 0
                      По мне, так это уже не магия, а попытка смены колес у стремительно мчащегося вперед поезда — проблема другого уровня.
                      • 0
                        Не все так плохо. Совместимость сохраняется, быстродействие не ухудшится, а смены парадигмы по сути не произойдет — уже и так есть библиотеки коллекций в функциональном стиле — вспомним хотя бы гуаву.

                        Да, реализации по умолчанию — это очень интересный ход для столь консервативного ЯП, но уже опробованный во многих языках.
                        • 0
                          От реализации по-умолчанию плюсы, ИМХО, будут ) особенно для случаев overload'а, чтобы автоматически выполнить контракт для нескольких сигнатур, для которых предполагается одна реализация.
                          • +2
                            На докладе Сергея Куксенко и Алексея Шипилёва (TheShade) про лямбды в Java 8. По залу носились очень громкие мысли в духе «trait!», «монады!», но зал вежливо молчал.

                            Кстати, очень рекомендую посмотреть видеозапись — рассказ просто великолепен.
              • +2
                С недавнего времени у меня появилась настойчивая мысль, что профессиональное развитие сильно замедлилось и это хочется как-то исправить.
                Пробовали смотреть в сторону многопоточности ;)
                • +2
                  Да, начал копать в этом направлении, к сожалению по работе не сталкиваюсь с этим, хотелось бы попасть на высконагржуенный проект с использованием многопоточности — ищу.)
                  • +1
                    Попробуйте на тестовом примере реализовать модель распределенных вычислений с перераспределением нагрузки между узлами и с правильным перехватыванием при «умирании» посредника.
                    Хорошая такая задачка :-)
                    • 0
                      Проверить можно на чем угодно, например, классические крестики-нолики (5 в ряд) на бесконечном поле :-)
                      • 0
                        Интересно, возьму на заметку, сейчас правда даже не представляю откуда начинать копать с таким)
                        • +1
                          С книги «Java Concurrency in Practice».
                        • 0
                          А использование Akka — чит?
                          • 0
                            Использование Akka — это не чит, это очень и очень хорошо, но профит от решения такой задачи про помощи готового фреймвока уже не тот.

                    • +4
                      У меня на собеседовании был вопрос про удаление элементов в arrayliste, где порядок элементов был неважен. Очень похож на пятый вопрос, только там можно было сделать ход конем: если порядок элементов неважен, то можно поменять удаляемый элемент с последним и удалить уже последний — работает за O(1) не учитывая trimtosize.
                      • –2
                        Я, если честно, думал, что он так и работает, удивился, когда прочитал, что происходит сдвиг.
                        • +1
                          Значит, Вы не понимаете контракт List'а.
                        • +2
                          Если порядок элементов не важен, нет смысла использовать List, основное свойство которого, сохранение порядка элементов.
                          • –1
                            свойство arraylistа не в сохранении порядка, а к быстрому обращению по индексу. При прямых руках и правильном использовании — самое то.
                            • 0
                              Какой смысл в индексе, если порядок элементов по определению неизвестен? Для таких случаев существуют другие коллекции с безындексными итераторами.
                              • +2
                                Порядок не важен != порядок не известен
                                • 0
                                  Эм… вообще-то как раз таки "==" в данном контексте. Структурой либо гарантируется порядок, либо нет. Если он не гарантируется, то как он может быть известным, поясните или пример структуры приведите?
                                  • 0
                                    Порядок элементов может использоваться с одной стороны в алгоритмах работающих по принципу divide and conquer, а также в различных системах с паралелльным выполнением операций и объединением полученных результатов (map-reduce).
                                    Возьмем пример с быстрой сортировкой (quick sort). После определения пивот-элемента нам нужно переставить его в конец текущего интервала, потом менять местами элементы что меньше и больше пивота. Все эти операции осуществляются за константное время при наличии индекса.
                        • +3
                          Почему нельзя использовать byte[] в качестве ключа в HashMap?


                          Не понял вопроса. Можно и все будет работать правильно. А то, что автор придумал с динамическим хэшкодом для byte[] как раз работать не будет. Никогда не вставляйте в hashMap объекты, у которых может поменяться hashCode.

                          В 95% случаев моего использования HashMap достаю именно те объекты, которые туда положил (то есть не делаю hasMap.get(new Integer(oldInteger)); )
                          • +1
                            Согласно контракту hashCode меняться не должен. Если он меняется, значит, объест сконструирован неверно.
                            • +1
                              Не совсем так.
                              Согласно контракту при изменении hashCode с точки зрения HashMap мы имеем другой объект ключа.
                              Со всеми вытекающими.
                              • +1
                                Это в каком смысде не совсем!!?!

                                The general contract of hashCode is:

                                Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application…

                                • 0
                                  Стоит обратить внимание на выделенный фрагмент:
                                  "...the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified..."
                                  "… метод hashCode должен стабильно возвращать одно и то же число при условии, что данные, используемые для сравнения объектов методом equals, не изменились..."
                              • +2
                                hashCode полезен для immutable-объектов. Для mutable — просто опасен.
                                • 0
                                  Народ, вы документацию читали? Значение hashCode после первого вызова меняться не может! Класс object, базовый как бы.
                                  • 0
                                    А что, где-то написано обратное?
                                    • 0
                                      А какая разница — mutable объект или нет?
                                      • 0
                                        Типичный случай — люди делают классы, в которых хэшкод является функцией от состояния экземпляра. Если состояние единственное (=immutable), то такая реализация корректна, ибо не нарушает контракт hashCode, о котором вы говорите. Если состояние может меняться — то контракт может нарушаться, поэтому делать так не стоит.
                                        • 0
                                          ну так это не имеет никакого отношения к типу объекта, а к кривости рук его создателя.
                                          • 0
                                            тип объекта имеет самое прямое отношение к рукам его создателя.
                                          • 0
                                            Выход из этой ситуации или не делать mutable объект, либо завязывать хеш-код на поля, которые не меняются в процессе жизни объекта? Есть ли еще варианты?
                                            • 0
                                              При этом надо, чтобы неравенство неменяющихся полей означало неравенство объектов? Для использования объекта в качестве ключа, может быть, подойдет. Но поиск «такого же» объекта с другим происхождением… может и не сработать.
                                              Возможно, для таких классов (mutable, но которые хотят быть ключами) создавать парные immutable классы — «моментальные снимки»?
                                              • 0
                                                > Возможно, для таких классов (mutable, но которые хотят быть ключами) создавать парные immutable классы — «моментальные снимки»?

                                                я не понял, если честно, зачем это делать.
                                                • 0
                                                  Чтобы можно было строить-строить объект, а когда построите — сравнивать его с другими по хэшу. Примерно как StringBuilder и string.
                                • 0
                                  Часто ключами являются строки, которые совсем не идентичные. К примеру, полученные из разных строк SQL-запроса, или вычитанные из разных строк файла, или пришедшие по сети из разных соединений. Когда я задумался над этим, оказалось, что далеко не так часто используются идентичные объекты.
                                  • 0
                                    Что подразумеваете под идентичностью? По указателям из всех приведенных вам примеров, это все будут разные строки, но как раз реализация hashCode() и equals() на основе содержимого строки и позволяет их использовать в хеш-кодах. Просто не совсем понял, то что вы хотели сказать.
                                    • +1
                                      Идентичный — это один и тот же объект (две ссылки равны по ==). Я возражал vics001 на утверждение «В 95% случаев моего использования HashMap достаю именно те объекты, которые туда положил». Там речь не шла о равных по equals.
                                  • 0
                                    Ну и с интегерами тоже. Как вы написали, конечно, никто не делает. А вот, например, в таком коде ключи будут неидентичными
                                    hashMap.put(500, 1);
                                    int value = hashMap.get(500);
                                    

                                    Боксинг в ключах к стандартным коллекциям — не редкость (да-да, используйте Trove!)
                                    • 0
                                      Особенно круто, если так:
                                      long v = 500L;
                                      map.put(v, 1);
                                      //…
                                      map.get(500)
                                • +5
                                  Хм, я никоим образом не Java программист, пробовал этот язык еще в школе в последний раз, но ни один из этих вопросов не заставил меня даже задуматься — предположения абсолютно совпали с верными ответами.

                                  Может в таком случае вам стоит почитать классической литературы? Например в такой классической литературе, как «Алгоритмы. Построение и анализ» Кормена, на фундаментальном уровне разобрана большая часть вопросов, касательная сложности алгоритмов, а эти знания, в свою очередь, можно будет уже экстраполировать на контейнеры/стандартные алгоритмы любого языка.

                                  7. Как устроена HashMap?
                                  Добавление, поиск и удаление элементов выполняется за константное время.

                                  Это неправда же. Математическое ожидание времени выполнения этих функций — O(1), а в общем случае их сложность O(n).

                                  В остальных случаях достаточно помнить, что сравнение в Java происходит по указателю, а не по значению, из чего можно делать уже соответствующие вывода.
                                  • 0
                                    Поправьте меня если я где-то ошибся:
                                    Добавление — берём бакет по хэшкоду, добавление в список — везде константа
                                    Поиск — берём бакет по хэшкоду, поиск в бакете фиксированного размера (в общем, не зависит от N) — опять O(1)
                                    Удаление — аналогично поиску
                                    • +1
                                      В корзине в худшем случае будет O(n) элементов в связном списке (если не повезло немного с хеш-функцией, либо данными). Для добавления/поиска/удаления нужно пройтись по всему списку, сложность прохождения по списку длины O(n) — O(n), поэтому сложность каждой из операций — O(n).
                                      • –2
                                        Добавление в любом случае это O(1).
                                        а для получения n элементов в бакете — это же нужно целенаправленно стрелять себе в ногу :)
                                        Именно в общем случае будет всё ок, в худшем — да, грубо говоря O(N) — но на то это и худший случай.
                                        • 0
                                          При добавлении надо еще проверить наличие такого же, так что сложность поиска.
                                          • 0
                                            Если бакет не пуст — да, согласен.
                                          • +2
                                            При добавлении нужно убедиться, что не возникнет дублирования по ключу, для этого надо пройтись по всему списку. И если найдется элемент с таким-же ключом, то он будет заменен. А обход списка — это O(n).

                                            И не путайте терминологию, O всегда обозначает худший из всех возможных случаев. (О-символика объясняется в Кормене в первой главе).

                                            это же нужно целенаправленно стрелять себе в ногу :)

                                            Нет, достаточно, чтобы вам кто-то попытался ее отстрелить) Программист всегда должен считать окружающий мир враждебным и писать код исходя из этого.
                                            • –1
                                              Если мы подходим со строго формальной точки зрения — да O всегда описывает худший вариант.
                                              Однако в реальной жизни нас более интересует не худшее время, а среднее. Кормен указывал что его больше интересуют худшие случаи — скорее для строгости дальнейшего повествования — худший случай нам даёт гарантию времени работы алгоритма.
                                              В 90% случаев достаточно оперировать средним случаем, и большинство оценок делается именно для этого среднего случая.
                                              Однако, если нам супер важно теоретически обосновать сложность алгоритма, или область работы такова, что худшие случаи часты — вы правы, HashMap это O(n) а quicksort это O(n^2) :)
                                              • +2
                                                Это элементарная грамотность, а не «строго формальная точка зрения». Собственно именно она позволяет понять, что далеко не всегда уместно использование hash table (в ряде случаев rb-tree/treap дают куда лучшие по скорости результаты), а quick sort (в его обычном виде) использовать вообще никогда не стоит.
                                                • 0
                                                  Ок, ваш подход понятен.
                                                  Я придерживаюсь немного другой точки зрения:
                                                  в 95% случаев — средняя оценка реально отражает суть процессов. оставшиеся 5% — отдельный случай (и данные случаи часто хорошо видны) — тут надо анализировать отдельно. Иначе нам грозит оверинжениринг.
                                                  • 0
                                                    А поясните, пожалуйста, про QuickSort.
                                                    • +1
                                                      При неудачных данных quick sort вырождается в квадратичный алгоритм. Поэтому зачастую используются разные «хаки», а именно:
                                                      • random shuffle
                                                      • переход к O(n*log(n)) сортировкам, если операций стало больше критического максимума
                                                      • и т.д.
                                                      • –2
                                                        При неудачных данных quick sort вырождается в квадратичный алгоритм.

                                                        То есть Вы имеете в виду worst case, Но, на мой взгляд, попытка учитывать этот worst case оправдана только при довольно большом n, когда разница между O(n2) и O(n log n) умноженная на вероятность этого worstcase будет заметна.
                                                • +2
                                                  При таком подходе, все совсем печально. При выборе структуры данных по вашей логике надо всегда брать список: и у него и у HashMap сложность O(N), зато список экономичней по памяти. :) Вы фактически не оставили HashMap шансов на жизнь, однако в жизни эта структура активно используется и скорость показывает вполне себе.

                                                  Чтобы у HashMap попасть на O(N), надо серьезно извращаться, это не «слегка» неповезло с функцией и данными, это капитально не повезло. Как правильно вспомнили выше quicksort тоже формально имеет временную сложность O(n^2), но все скорее держат это в голове как некий тонкий момент, нежели случай из практики, потому что вероятность его очень мала, даже если с данными так не повезет, все ориентируются на N lg N. Формально вы правы, но общепринятый вариант о константном времени выполнения операций, а O(N) практикуют как некий тонкий момент на собеседованиях, вероятность очень мала.
                                                  • 0
                                                    Почему список, а не красно-черное дерево, отсортированное по hash-коду? Там будет O(log N) в худшем случае.
                                                    • 0
                                                      В какой момент комментируете? Про выбор между Map и списком? Если да, то выше прочитайте ветвь, это просто пример с потолка для сравнения, а не практическая задача.
                                                      • +1
                                                        «При выборе структуры данных по вашей логике надо всегда брать список:».
                                                        Я не нашел, в каком месте дискуссии выбор мог оказаться ограничен только двумя вариантами (HashMap и список).
                                                    • +1
                                                      Бывали случаи, когда из-за непонимания возможности вырождения операций хеш-таблицы в линию не проходили задачи на олимпиадах. И именно это причина появления perfect hash table, которая гарантируют сложность операций поиска за O(1).
                                                      • 0
                                                        perfect hash table — это которая требует предподсчета, занимающего время, пропорциональное мощности множества всех возможных значений ключей? Или она не имеет отношения к perfect hash function?
                                                        • 0
                                                          perfect hash table — это хеш таблица с фиксированными элементами, мат. ожидание сложности ее построения O(n), где n — количество элементов, поддерживает только операции поиска и удаления за O(1) (операция вставки новых элементов — не поддерживается)
                                                          • 0
                                                            Построение идёт после того, как все элементы известны? И оно гарантированно за O(n), или только в среднем?
                                                            • 0
                                                              После того как все известны. В среднем, но вероятность построения больше 50%, поэтому очень сомнительно, что потребуется больше 2 перестроений.
                                                              • 0
                                                                Тогда такой вопрос — «больше 50%» это в среднем по всем множествам, или для любого множества — в среднем по всем построениям? Иными словами, существуют ли «плохие» множества, вероятность успеха для которых заметно ниже?
                                                                В любом случае, спасибо за наводку. Я этого приёма раньше не замечал. Пригодится.
                                                                • 0
                                                                  В любом случае, доказывается математическим аппаратом. При условии, конечно, что используется универсальная функция хеширования.
                                                    • +1
                                                      Специально отыскал Кормена, и не нашел там утверждения что под О понимается ТОЛЬКО сложность в «худшем» случае. Возможно перевод плохой.

                                                      ИМХО, чаще всего используется понятие асимптотической сложности алгоритма. И для HashMap она равна константе. Это же указано и в javadoc.
                                                      • 0
                                                        O — нотация это обозначение принадлежности к множеству.
                                                        Под записью O(g(x)) = f(x) имеется ввиду что f(x) принадлежит множеству функций асимптотически ограниченных сверху функцией g(x) умноженной на некую константу.

                                                        Никто не мешает на место f(x) засунуть более сложную функцию, например содержащую мат-ожидание.
                                                        И действительно для Хеш-таблицы с цепочковой индексацией матожидание(в пространстве таблиц с одинаковым размером и равновероятными ключами ) времени поиска будет O(1+loadFactor)
                                              • +2
                                                Также добавлю, что из-за подобного непонимания принципов работы хеш-таблиц (или отсутствия должного внимания к ним) вообще становятся возможными такие вещи как hash collision DoS в каждом втором веб-сервисе. Например, статья на хабре, и более подробная статья.

                                                А вообще, вопросы в статье — чисто джуниорские, для ответа на которые человеку достаточно один раз взять в руки книгу, или, хотя бы, прочитать документацию на Java.
                                              • –10
                                                Статья интересная, мне понравилась, как раз недавно начал писать приложение под андройд, и столкнулся с большим количеством списков.
                                                • +1
                                                  Ваш бы пост, да днем ранее…
                                                  • +2
                                                    А откуда взялась логарифмическая оценка для HashMap в 7 и 9 ответах? Там вроде O(n) должно быть.
                                                    • 0
                                                      Мне тоже интересно :-)
                                                      • 0
                                                        А чуть выше как раз дискуссия на эту тему, а логарифмическая оценка по Р.Седжевику, эта оценка исходит из хеш-функции с нормальным распределением.
                                                        • 0
                                                          Да, чуть выше обсуждали сложность какая все таки будет сложность O(1) и O(n) у различных операций. Мне хотелось бы узнать у автора а откуда вообще взялся логарифм.
                                                          По Р.Седжевику? Я не смог найти у него такого (возможно не там искал), но мне кажется мы все таки о разных вещах говорим.
                                                          У автора указано:
                                                          … хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время…
                                                          Что значит не ниже lg N, а в среднем случае как раз константное время? Если не ниже lg N, то это O(lg n) будет.
                                                          и еще одно:
                                                          … если вы будете использовать хеш-функцию с равномерным распределением, в предельном случае гарантироваться будет только временная сложность lg N.
                                                          В предельном случае будет гарантирован сложность только O(n) — полный перебор всех элементов.

                                                          Возможно Седжевик что то другое доказал с логарифмической оценкой?

                                                          P.S.: А возможно я не правильно в чем то понял автора. Буду благодарен если разъясните.
                                                          • +1
                                                            На самом деле Роберт Седжевик доказал совершенно другое:
                                                            при использовании SUHA — предположении о равновероятном и независимом от исходов уже проведенных эксперементов присвоении метки(это не просто «на одинаковые части», это намного больше) будет image.

                                                            Факт связанный с логарифмами доказанный недавно Седжвиком совершенно другой:
                                                            он в 2008 году придумал более простую конструкцию родственную красно-черным древьям, называется Left-leaning red–black tree. У них оценка операций вставки\удаления log(n). Но они удобнее в реализации и константа меньше

                                                            Другой вариант из «логарифмы и Седжевик» — он доказал что, при испрользовании Cockoo hashing(это опять не то что в HashMap) в предположении SUHA, оценка сверху для для loadFactor будет image
                                                            • 0
                                                              Возможно я не так выразился… полазил по слайдам его лекций собственно вот:
                                                              www.cs.princeton.edu/courses/archive/spr10/cos226/lectures/10-34HashTables-2x2.pdf

                                                              На предпоследнем слайде, сводная табличка по структурам данных.
                                                              • +1
                                                                Честно говоря так и не понял как он доказал гарантированную логарифмическую сложность. По-моему все же это вероятностный подход, т. е. если у Вас точно будет равномерное распределение элементов, что на практике недостижимо. Да и способ реализации хеш-таблицы там немного другой — с открытой индексацией (хотя не думаю что это важно).
                                                                • 0
                                                                  В моем понимании, распределение не строго равномерное, а близкое к тому (в каком то списке чуть меньше чем lg n элементов, в каком то чуть больше), если в таком случае пытаться рассчитать точную зависимость, то будет lg n с каким-нибудь коэффициентов и/или дополнительным слагаемым, но в целом все вращается вокруг lg n. В общем, мне кажется интуитивно, что для подавляющего большинства практических случаев худшая оценка будет как раз такая, но здесь я принимаю на веру слова авторитетного ученого, поэтому мысли могу подгонять «под ответ». Не задавался вопросом поиска доказательств данного положения и как показывают обсуждения выше оценка сложности вещь довольно многогранная и сложная, мнений много как правильно считать.
                                                                  • 0
                                                                    Подавляющее большинство практических случаев это O(1) (у него там кстати так и указанно — 3-5).

                                                                    Если данные заранее неизвестны, то для любой хеш-функции можно подобрать случай, приводящий к коллизиям и таким способом добиться O(n). А вот это точно будет худший случай.

                                                                    Логарифмическая оценка у него описывает худший случай для данных которые распределяются равномерно (и как я уже сказал выше, на практике этого нельзя гарантировать). Так что на мой взгляд это лишь вносит путаницу.
                                                                    • 0
                                                                      Подавляющее большинство практических случаев это O(1) (у него там кстати так и указанно — 3-5).


                                                                      Согласен, я писал про худший случай (а О(1) это в среднем) на практике: в большинстве случаев до O(n) не дойдет, а вот до O(lg n) вполне вероятно. Но я согласен с вами, вносит некую путаницу.
                                                        • –2
                                                          Куда мир катиться, я всю жизнь думал что это даже для Джуниора слишком простые вопросы.
                                                          • +2
                                                            а что же вы спрашиваете у своих джуниоров?
                                                            • +3
                                                              Зы: вопросы которые я задаю Junior не сильно отличаются от тех что Senior. Просто ожидаю разный уровень ответов.

                                                              Теория — пару вопросов из этого списка, чуть под настроение(вычеты, сортировки, перестановки, графы, древья: чтото базовое что можно вывести на месте) и разные вопросы на многопоточность:
                                                              как устроен CopyOnWriteArrayList. Зачем он так устроен?
                                                              Когда имеет смысл паралелить алгортм(хорошо если знает закон Амдала)?
                                                              Прошу написать принципы реализации многопоточных списков и кольцевого буфера. а неблокирующие?
                                                              Прошу придумать как бы он реализовывал многопоточный HashMap в случае разных паттернов работы с ним.
                                                              Как бы он реализовал кеш для приложения? а персистентный?
                                                              Как можно остановить поток выполняющий код который не находится под нашим контролем?
                                                              Из чего состоит переключение контекста процессора между потоками и процессами? сколько оно стоит?

                                                              Когда не знает ответа на вопрос(или даже не понимает формулировки) поясняю ему вопрос, я хочу увидеть как он мыслит.
                                                              После прошу написать реалию минимального приложения, тоже под настроение и в зависимости от диалога: последние варианты были написать сервис быстро возвращающий среднее в массиве(то есть к нему по сети приходят запросы «добавить елемент a» и «верни среднее»). На задачку даю часа 3-4. Для этого даю ему некий костяк — интерфейс который он должен реализовать и интерфейсы которыми он может пользоваться. Сам быстренько реализую последние.
                                                              Тут смотрю как они пишет тесты и mock-реализации(и пишет ли), пишет ли комментарии, как структурирует код. Обычно я наблюдаю что это спрашивают устно, но ИМХО в таких вопросах устный ответ часто в корни разнится от реальности.
                                                              • 0
                                                                забыл: пару вопросов о GC, о загрузке классов, было просил написать свою реализацию gc: представим что GC у JVM нет, человек должен был сделать некий super-class для всех обьектов, и должен был быть «личным» gc для них.
                                                                Потом попросил его сделать анализ работы этого GC с профайлером и пояснить почему он так работает.
                                                                ЗЫ: это был очень сильный соискатель и было очень приятно с ним говорить, потому и писали такую интересную вещь.

                                                                Задаю вопросы о production-мониторинге. Что и как нужно отслеживать в продакшене. Разок когда дал кусок кода написанного в моей команде и попросил в течении 3 часов разобраться как он работает и там где считает нужным расставить мониторинговые вызовы(дал в руки библиотеку metrics)
                                                                • –1
                                                                  Рядом с вопросом о GC и cache задаю вопросы о отличиях WeakRefferece, PhantomRefference и SoftReference.
                                                                  • +5
                                                                    Вопросы хорошие. А что в Яндексе теперь студенты собеседуют сеньёров?
                                                                    • 0
                                                                      в Яндексе теперь

                                                                      Я не работаю в Яндексе.
                                                                      Я там доучиваюсь, и у меня научрук из Яндекса.
                                                                      студенты собеседуют сеньёров

                                                                      Также мне тяжело себя отнести к junior\senior. У меня мало лет опыта, но учитывая что мне интересны алгоритмы и методологии разработки+организации людей, то претендую я обычно именно на позиции начиная с Senior.
                                                                      • +2
                                                                        Как бы там не было, вопросы очень сильно впечатляют, и мое ЧСВ падает over -9000.:)
                                                                    • 0
                                                                      На задачку даю часа 3-4.

                                                                      И что ж это за компания такая, в которой вы работаете, что люди готовы на собеседованиях по 3-4 часа сидеть и писать что-то?
                                                                      • 0
                                                                        Обычно если доходит до этого этапа то я вижу что мне интересно с этим человеком и ему со мной.
                                                                        Потому вопрос не встает.
                                                                        Если же нам вместе не интересно — я не вижу смысла его нанимать, во всяком случае в мою команду. Атмосфера работы — тоже крайне важный фактор который проверяет такое собеседование.
                                                                        • 0
                                                                          А что за компания, если не секрет? Мне кажется, не так уж и много в нашей стране компаний, требующих от соискателей умения отвечать на обозначенные выше вопросы.
                                                                          • +1
                                                                            Компанию ответил в личку. Я не хочу чтоб люди гугля название компании приходили «подготовленные». Очень неприятно видеть человека, который чтото заучил но не понимает что это такое. Несколько раз попадались люди которые на вопросы про HashMap отвечали сумбурными рассуждениями про «бакеты», но что такое эти бакеты ответить не могли.

                                                                            Как я уже говорил я ни в коем случае не «требую» умения отвечать на эти вопросы. Это просто вопросы которые мне самому интересно обсудить и которые мне кажется должны вызвать интерес у достойного соискателя. Я не ожидаю правильного ответа и на половину из них, но чаще всего двух-трех подобных вопросов достаточно чтобы у меня сложилось понимание, хочу ли я с этим человеком работать или нет.
                                                                        • +1
                                                                          Нормальная компания. У нас бывает что устное собеседование длится 3-4 часа, и то не все успеваем спросить. Бывает и 2-3 минуты всего.
                                                                          • +1
                                                                            Свою схему собеседования я сделал как результат анализа тех которые проходил я. Прошлой зимой-весной зная что мне предстоит вскоре набирать сотрудников я 2-3 раза в неделю ходил на собеседования.

                                                                            Основным недостатком большинства считаю как раз нерациональное использование времени: задают вопросы ответ на которые прост и однострочен и далее ходят вокруг да около простой темы, задают вопросы которые не отображают реальное состояние вещей, вроде теоретических «какие части кода нужно документировать».

                                                                            Доходило до идиотизма когда спрашивали StyleGuide java в течении получаса. Лучше бы попросили написать код на любую задачу(да блин хоть сортировку пузырьком). Потратили бы меньше моего времени и больше узнали бы обо мне.

                                                                            Еще большим идиотизмом было когда собеседующий начинал описывать проект и тратил на это более часа. Либо неся чтото невнятное либо вдаваясь в сугубо технические подробности их реализации элементарных вещей.
                                                                        • 0
                                                                          Можно поинтересоваться, чем вы занимаетесь, что спрашиваете такое на собеседованиях? Просто тематика вопросов совпадает с нашей, но за достаточно долгое время поисков разработчика я не видел ни одного, который смог бы ответить даже на половину вопросов.
                                                                          • +1
                                                                            Чем занимаюсь отписал в личку.

                                                                            Как я уже говорил я не ожидаю получить правильный ответ на собеседовании. Каждый из этих вопросов требует отдельного исследования, или же гиканутости чтобы знать на них ответ. У меня нет цели набрать команду гиков и есть сомнения что команда гиков вообще может выполнять поставленные задачи в нужных объемах и в нужные строки.

                                                                            Эти вопросы я использую как те, которые считаю что должны быть интересны людям в моей команде. Обсуждая с ним эти вопросы я узнаю как мыслит соискатель и будет ли ему интересно со мной и мне с ним.
                                                                            • +3
                                                                              Я, кстати говоря, уже давно не задаю на собеседовании сложны, алгоритмических, либо практических вопросов, например напишите пожалуйста самый простой неблокирующий стек. Мы примерно час общаемся на интересные, в первую очередь для нас, темы, такие как: многопоточность и сихронизация, память и сборка мусора. Иногда разбираем какие-либо интересные, опять же для нас, проблемы с которыми сталкивались мы или соискатель. Такой разговор по большей части дает понять что из себя представляет человек, что знает, чем умеет пользоваться а о чем слышит впервые.

                                                                              И опять же, если я задаю вопрос, то стараюсь формулировать его так, что бы соискатель не пытался вспомнить какую-нибудь конкретную вещь, а рассказал то, что знает. Например вопрос «какие три вида синхронизации применяются при использовании synchronized», я сформулирую примерно так: «что вы можете рассказать о ключевом слове synchronized», и при необходимости задать некоторые уточняющие вопросы, например «а чем он отличается от локов, кстати, каких именно, из пакета juc»
                                                                              • +1
                                                                                Спасибо за пищу для размышлений. Очень интересные темы вы обсуждаете при приёме на работу.
                                                                      • +1
                                                                        А может кто-нибудь подсказать, где почитать подобный материал, но применительно к C#? Кардинальных отличий при работе с коллекциями по сравнению с Java вроде бы нет, но может есть какие-то нюансы, которые стоит знать?
                                                                        • +2
                                                                          Есть очень хорошая книга, CLR via C#, покрывает многие аспекты языка и исполняющей среды.
                                                                          • 0
                                                                            Кстати, недавно вышло четвёртое издание, если будете покупать, обратите внимание.
                                                                        • 0
                                                                          LeoCcoder молодец, интересные вопросы придумал. К вопросу 14 добавлю, что использовать можно, иногда именно этого и добивается программист: используются только ключи идентичные (а не просто равные) тем, что уже помещены в Map. Например, у вас фиксированный набор объектов, с которыми вы хотите ассоциировать какую-то статистику и потом быстро её достать. Впрочем, для этих целей лучше использовать IdentityHashMap.
                                                                          • +1
                                                                            за 14й вопрос спасибо yandex'у, он у них в тесте есть на вакансию андроид девелопер, там в примере кеш релизован с ключами на byte[], которые пересоздавались и должны были сравниваться по содержимому… кеш в примере потяное дело не работал. использовать конечно же можно, но в большистве случаев результат будет не тем, который ожидают новички…
                                                                          • +3
                                                                            Вот вам задачка на коллекции.
                                                                            Нужно придумать реализацию структуру данных со следующим интерфейсом:
                                                                            Object get(int index);
                                                                            void put(int index, Object value);
                                                                            void clearAll();
                                                                            

                                                                            Эта структура данных является массивом. Размер (максимальное количество элементов) фиксирован и задается при создании. Метод get может возвращать как Object так и null, в случае, если по данному индексу не было put c момента создания или с момента вызова clearAll().
                                                                            И теперь самое важное. Методы get put и clearAll должны гарантированно работать за O(1).
                                                                            • +1
                                                                              Вести счетчик вызовов clearAll. По put рядом со значением положить текущее значение счетчика. По get сравнить сохраненное значение с текущим значеним счетчика, вернуть null, если меньше. Простовато для собеседования то.
                                                                              • +1
                                                                                По-моему для собеседования как раз и ничего. Если ещё и попросить код написать, то вполне. Посмотреть заодно как будет реализована структура.
                                                                                • 0
                                                                                  Задачка не сложная, не спорю. Хотя 90% junior-to-middle java developers из тех, кого я собеседовал, не могли написать работающую реализаци задачки на merge двух отсортированных массивов, не говоря уже о красивом коде.
                                                                                  • +1
                                                                                    «Да 90% разработчиков не смогут и список односвязный развернуть!» — байка откуда-то.
                                                                                    • 0
                                                                                      Вы не согласны?
                                                                                      • 0
                                                                                        Отчего же, согласен, но дело ведь в том, что подобного от этих 90% и не требуется — для решаемых ими проблем в подобных знаниях и умениях необходимости нет.

                                                                                        Но если уж вопрос заходит о том, что от соискателя требуются хотя бы знания базовых алгоритмов, структур данных, минимальные навыки проектирования, да и просто голова на плечах — стоит придумать более сложные и разносторонние задачи.
                                                                                      • 0
                                                                                        Это из RSDN: Задача на собеседовании — обращение списка
                                                                                        Там развернулась бурная дискуссия на тему должен ли программист уметь написать простой алгоритм, который не требует каких-то особых знаний кроме умения оперировать тремя ссылками.
                                                                                        • 0
                                                                                          Интересная дискуссия. Правда, целиком не осилил. Кто там победил?
                                                                                          • 0
                                                                                            Никогда такого не спрашивали, ради интереса попробовал на листке набросать, за пару минут рисования родилось 5 строчек кода. Вот сижу и не пойму, то ли я вхожу в 10% тех, кто может это написать, то ли я не понимаю сложности задачи.
                                                                                            • 0
                                                                                              А эти 5 строчек — через собственную реализацию или через стандартную? Насколько я понял, основная сложность там в том, что соискатели не могут поверить, что в наше время им вообще могут предложить написать самодельные структуры данных (вместо того, чтобы воспользоваться библиотечными). Тех, кто пытался в этой дискуссии предложить свои реализации, тут же закидывали тапками по самую шею.
                                                                                              Интересна задача про «выбрать K случайных элементов из массива за O(K)». Я так и не понял, там было только авторское решение, или кто-то предложил своё.
                                                                                              • 0
                                                                                                Эти 5 строчек, основаны на классической «своей» реализации списка, есть поле под значение и есть ссылка на следующий элемент. То есть никаких коллекций и ничего подобного. А по дискуссии имелась в виду реализация через что-то стандартное? я не дочитал, много букв.

                                                                                                Выбрать К элементов, то же не дошел. Я так понимаю сложность задачи чтобы выбрать К неповторяющихся элементов?
                                                                                                • 0
                                                                                                  Да, неповторяющихся. И любое подмножество должно быть выдано с равной вероятностью. Число элементов исходного массива известно.
                                                                                                  (А есть еще задача — выбрать K случайных элементов из последовательности неизвестной заранее длины. За один проход, с памятью O(K). Но это уже на смекалку...)
                                                                                                  • 0
                                                                                                    Похоже, что задача про массив решается за O(K) только если массив можно модифицировать (и выдать K значений). Выдать K случайных различных индексов от 1 до N за это время пока не получается.
                                                                                                  • +1
                                                                                                    В цикле, k раз: выбрать рандомный индекс (от 0 до n), вернуть по нему значение из массива, обменять этот элемент с последним, уменьшить n на единицу, повторить. Время — O(k), память — O(1). Профит.
                                                                                                    • 0
                                                                                                      Я правильно понимаю, что модификация массива не особо то и нужна, нужно просто O(k) памяти? (портить входные данные — нехорошо)
                                                                                                      • 0
                                                                                                        Без модификации будет очень сложно избежать выдачи одинаковых элементов. За O(k^2) выдать k случайных различных индексов легко, за O(k*log(k)), вероятно, тоже возможно. Но как это сделать за O(k)?
                                                                                                        • 0
                                                                                                          Упс, действительно O(k^2). Извините
                                                                                                          • 0
                                                                                                            O(k*log(k)) — например, рекурсией и очень хитрым слиянием. Примерно как в задаче о рыцарском турнире. Вот только выданное множество индексов получится отсортированным.
                                                                                                        • 0
                                                                                                          Если преобразовать это же решение (т.е. запоминать «обмены» в отдельном месте, типа хеш-таблицы), то да — O(k) памяти, но время работы будет больше O(k) — необходимо находить индекс элемента в массиве по его новому (после «обмена») индексу.
                                                                                                    • +1
                                                                                                      Решение там примерно такое:

                                                                                                      Список:
                                                                                                      public class Node<T>
                                                                                                      {
                                                                                                          public T Value { get; set; }
                                                                                                          public Node<T> Next { get; set; }
                                                                                                      }


                                                                                                      Разворот:
                                                                                                      public static Node<T> ReverseInPlace<T>(Node<T> root)
                                                                                                      {
                                                                                                          Node<T> prev = null;
                                                                                                          Node<T> curr = root;
                                                                                                          while (curr != null)
                                                                                                          {
                                                                                                              var next = curr.Next;
                                                                                                              curr.Next = prev;
                                                                                                              prev = curr;
                                                                                                              curr = next;
                                                                                                          }
                                                                                                      
                                                                                                          return prev;
                                                                                                      }
                                                                                                      


                                                                                                      Так что «самодельная структура данных» это громко сказано, класс с двумя полями — значение и ссылка на следующий узел.
                                                                                                      • 0
                                                                                                        Такие структуры там и предлагались. И их в ответ называли «велосипедами с треугольными колёсами». И обсуждали, через какие списки надо решать эту задачу — через ArrayList или какие-то ещё…
                                                                                                        • +1
                                                                                                          Ну слово «самодельная» я применил, чтобы однозначно определить, что имею в виду. Мой код переписываю с листика буква в букву:

                                                                                                          while(list != null) {
                                                                                                          next = list.next;
                                                                                                          list.next = prev;
                                                                                                          prev = list;
                                                                                                          list = next;
                                                                                                          }
                                                                                                          


                                                                                                          Собственно даже имена переменных совпали почти полностью.
                                                                                                        • 0
                                                                                                          Мне кажется, что с К случайных решение примерно такое:

                                                                                                          int K = 3; //количество необходимых чисел
                                                                                                          int N = 15; //количество элементов в массиве.
                                                                                                          var random = new Random();
                                                                                                          var randomIndexes = new int[K]; // случайные индексы элементов, которые мы должны вытащить из массива
                                                                                                          				
                                                                                                          for (int i = 0; i < K; i++)
                                                                                                          {
                                                                                                          	var prev = i > 0 ? (randomIndexes[i - 1] + 1) : 0;
                                                                                                          	randomIndexes[i] = random.Next(prev, N - (K - i - 1));
                                                                                                          }
                                                                                                          var shift = random.Next(0, N);
                                                                                                          for (int i = 0; i < K; i++)
                                                                                                          {	
                                                                                                          	randomIndexes[i] = (randomIndexes[i] + shift) % N;
                                                                                                          }
                                                                                                          
                                                                                                          ... // тут возвращаем все элементы с найденными индексами
                                                                                                          


                                                                                                          Сложность O(K), память O(K)
                                                                                                          • 0
                                                                                                            К сожалению, не подойдет. Если взять K=3, N=5, то вероятность подряд идущих индексов (012,123,234,034,014) будет по 65/540, а остальных наборов (013,124,023,134,024) — по 43/540, в полтора раза ниже. Надеюсь, что не ошибся.
                                                                                                        • 0
                                                                                                          то ли я вхожу в 10% тех, кто может это написать

                                                                                                          Видимо, да. По моему опыту — мало кто может написать этот весьма простой алгоритм (пример ответа написал выше)
                                                                                                          • 0
                                                                                                            Я недавно обнаружил, что не могу сходу написать быструю сортировку. Вроде бы всё работает, но на массиве, в котором много одинаковых элементов, скорость падает до O(N^2)… Очень неприятно было.
                                                                                                            • 0
                                                                                                              Ну так вы вроде и правильно написали — если работает, но на плохих случаях до квадратичной сложности спускается. А pivot как выбирали?
                                                                                                              • 0
                                                                                                                Неправильно. Правильный алгоритм на любом массиве работает в среднем за N*log(N). А у меня на массиве, в котором всего 2 значения, почти всегда получалось N^2: когда разделяющее число оказывалось минимальным, отщеплялся 1 элемент, даже если почти все элементы массива были равны этому минимальному. Ни разу не увидел в описании алгоритма этой тонкости (или не обратил на неё внимания), вот и попался.
                                                                                                                Как выбирал, не помню. Скорее всего — медиана из первого, центрального и последнего — как подглядел когда-то в стандартной библиотеке ещё на TurboC.
                                                                                                                • 0
                                                                                                                  Посмотрите на 3-way QuickSort, это улучшенная быстрая сортировка, которая как раз и решает проблему с одинаковыми элементами в массиве.
                                                                                                                  • 0
                                                                                                                    Скорее всего, в каком-нибудь индексе была ошибка +-1. Работать будет корректно, но скорость сильно упадет.
                                                                                                                    • 0
                                                                                                                      Там в качестве «оптимизации» было что-то вроде:
                                                                                                                        for(;;){
                                                                                                                          while(left<right && cmp(A[left],A[0])<=0) left++;
                                                                                                                          while(left<right && cmp(A[right],A[0])>=0) right--;
                                                                                                                          if(left>=right) break;
                                                                                                                          swap(A[left++],A[right--]);
                                                                                                                        }
                                                                                                                      

                                                                                                                      (в A[0] лежал разделяющий элемент).
                                                                                                                      Понятно, к чему оно приводило :)
                                                                                                                      • 0
                                                                                                                        Непонятно только, как я его вообще потом заставил работать. Какой-нибудь затычкой, наверное.