Пользователь
0,0
рейтинг
11 декабря 2012 в 16:34

Разработка → 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 разработчика в компанию с современным подходом к разработке и интересными задачами или просто может порекомендовать присмотреться к какой-либо подходящей вакансии — я буду благодарен, прошу в личку.
@sphinks
карма
32,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (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)
        • 0
          Троллим? :-)
  • +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
                              Непонятно только, как я его вообще потом заставил работать. Какой-нибудь затычкой, наверное.
                  • 0
                    Странно, я пока не увидел ваше решение думал, что-то не так понял.
              • 0
                Да никто не победил, все остались при своем мнении :)
                Но мой ИМХО — программист должен уметь на компе в IDE за полчаса-час написать разворот списка. Там на самом деле идея тривиальная, проблемы могут быть только на граничных значениях, неправильная последовательность переброски элементов и пр. — но это должно решаться за 5-10 минут дебага.
                Даже с учетом стресса на интервью
                • 0
                  А у вас на интервью компьютер с IDE дают и 30 минут на такую задачу?
                  • 0
                    Кто как — я даю ноут с IDE.
                    На бумажке не люблю ни писать, ни проверять код. Чтобы кандидат не мучился вспоминая название методов и пр, и мне проще — запустил и проверил, заодно посмотрел стиль написания.
                    • 0
                      Вы очень либерально относитесь к данному факту, я такого не встречал, плюс наоборот хотят видеть как пишут на пустом листке.
                      • 0
                        Мне важнее как человек пишет в IDE
      • 0
        Можно добавить методы «вернуть какой-нибудь элемент» и «очистить элемент». Тоже за O(1).
        Кстати, то, что после MAXINT очисток класс сломается, это ничего?
        • 0
          Обычно, предполагается, что 2^31 раз вы хеш-таблицу очищать не будете :) В противном случае ключик можно сделать и uint64_t, тогда это точно будет недостижимая оценка
          • 0
            В противном случае ключик можно сделать и uint64_t, тогда это точно будет недостижимая оценка

            Ну, тогда я сделаю очистку циклом, и скажу, что он работает за O(1) (с константой порядка 2^64).
        • 0
          Есть же get и put, который можно вызвать с null.
          По поводу MAXINT — никто не заставляет использовать int для хранения версии.
          • 0
            put(null) — да. А get не поможет: под «вернуть какой-нибудь элемент» имелся в виду аналог First в итераторе или какие там средства есть чтобы найти хоть какой-нибудь элемент в множестве (не зная индексов, в которых элементы уже лежат).
          • 0
            По поводу MAXINT — никто не заставляет использовать int для хранения версии

            А что же использовать? Существует ли решение, когда размер массива ограничен (чтобы арифметика с индексами работала за константное время), а число обращений к нему — неограничено (вообще), и мы всё равно хотим решить задачу за O(1)?
            • 0
              Ага, есть решение для неограниченного числа очисток. Смешное такое :)
            • 0
              Софистика по поводу константы 264 и утверждение, что элементарные операции над long нельзя считать O(1) выглядит занудством.

              По поводу head() — тут поможет связывать элементы двусвязным списком и хранить ссылку на голову. Да, хорошее дополнение.
              • 0
                Занудство и есть. Но предложение заменить int на int64, чтобы не переполнился счетчик очисток — тоже как-то не очень. Чистота задачи разрушается. Можно не выходя за int, подправить решение так, что ограничения на число очисток не будет совсем.
              • 0
                С другой стороны, не зря же сложность быстрого умножения оценивают как O(N*log(N)*log(log(N)))? Если log(N)=32 кажется достаточно большой константой, то log(log(N)) только-только перешагнул значение 5… Но его всё равно пишут.
            • 0
              Да пожалуйста. Храните размер и номер версии в разных переменных одного типа (т.е. либо оба int, либо оба uint). Заведите дополнительную переменную, указатель, какой элемент коллекции мы обновили в плане номера версии. После обнуления массива, обнуляем этот указатель. На каждой операции get\put дополнительно ставим переменной null, а её версии — версию коллекции, после увеличиваем Все, у нас никогда не получится такого, чтобы после ряда операций put(index), clearAll(), put ( rand() != index) * manytimes у нас в get(index) выдавал не null. Все операции до сих пор O(1). Но это конечно, если ваш язык после инкремента int_max не кидает эксепшен (но и это можно предотвратить). Единственное — нужно тщательно подобрать код и доказать, что для последнего (или последних) элемента массива размера int_max не будет проблем.

              UPD: О да, прочитал нижнюю ветку и сказал, что таким образом мы чуть-чуть избавляемся от утечек.
              • 0
                Это у меня было первой идеей. Потом придумал, что достаточно хранить только номер версии (по модулю N), и перед его увеличением прописывать его элементам с индексами Vold и Vnew, где Vnew=(Vold+1)%N (только на этапе очистки). Тогда после каждой очистки у нас гарантированно не окажется ни одного элемента с версией Vnew:

                  void Clear(){
                      int Vnew=(CurVersion+1)%N;
                      Versions[CurVersion]=Versions[Vnew]=CurVersion;
                     CurVersion=Vnew;
                }
                
                • 0
                  Или я не понял ваше решение, или оно не верное. В приведенном куске кода что хранится в массиве Versions? А еще лучше, пожалуйста, приведите код решения целиком (clear, put и get).
                  • 0
                    Мое решение требует еще O(n) дополнительной памяти.
                  • 0
                    Ничего, если на C#? Получается примерно так (не проверял):

                    class FastSet{
                      int N;  // size of array
                      int CurVersion; // current version of data, clearings counter
                      object[] Values;  // values
                      int[] Versions;   // versions of elements
                    
                      public FastSet(int _N){
                         N=_N;
                         Values=new object[N];
                         CurVersion=1%N;     // or N==1 ? 0 : 1
                         Versions=new int[N];  // versions of all elements are 0, just out of date
                      }
                      public void Clear(){
                         int NewVer=(CurVersion+1)%N;
                        Versions[CurVersion]=Versions[NewVer]=CurVersion;
                        Values[CurVersion]=null;   // for case N=1
                        CurVersion=NewVer;
                      }
                      public void Put(int ind,object val){
                        if(ind<0 || ind>=N) return;
                        Values[ind]=val;
                        Versions[ind]=CurVersion;
                      }
                      public object Get(int ind){
                        if(ind<0 || ind>=N || Versions[ind]!=CurVersion) return null;
                        return Values[ind];
                      }
                    }
                    

                    Предполагается, что N>0.
                    Я пока не смог придумать, как его обмануть.
                    • 0
                      Ха, хитрó. Спасибо.
      • 0
        Только если озвучено данное решение, надо выяснить у человека, видит ли он здесь утечки памяти.
        • 0
          Если хочется его завалить — то да. Потому что если он не видит утечек, показать ему, что ссылка на элемент всё ещё болтается в массиве, и поэтому объект не удалится, а если видит — то объяснить, что это никакая не утечка, потому что ссылка нам легко доступна, и при необходимости мы всегда можем её очистить. В обоих случаях — до свидания.
          Но если с массивом идёт активная работа, то таких утечек легко можно избежать.
          • 0
            Причем тут завалить?
            У каждого решения есть слабые и сильные стороны, и если человек не видит слабых сторон, велик риск использовать решение не эффективно. (и далее можно перейти на тему работы с памятью, дабы выяснить — он просто не заметил эту проблему или есть провал в знаниях)
            • 0
              А какой правильный ответ? Утечка это или не утечка?
              • 0
                В общем случае — да, утечка.
                В некоторых частных случаях — формально тоже утечка, но с которой можно мериться (малое время до следующей перезаписи — объекты не успеют попасть в old gen, малые объекты/малое количество объектов)
                Конкретное решение очень зависит от задачи. В случае задачи на тех интервью — достаточно указать на данную особенность коллекции и сказать для финального решения по выбору (или не выбору данной структуры) не достаточно информации о том как коллекция будет использоваться.
    • 0
      один из способов:
      clearAll() {
      array = new Object[initSize];
      }
      

      в отличии от способа со счетчиками, мы не держим референсы на «удалённые» объекты.
      • 0
        Инициализация массива (null'ами) — O(n), да еще плюс накладные расходы на сборку мусора.
      • 0
        вы считаете, что это O(1)?
        • 0
          Спасибо! Ваш вопрос заставил меня задуматься глубже :)
          array = new Object[initSize]
          

          компилируется в команду jvm «anewarray» c указанием размера. инициализация массива null'ами — тоже внутри этой операции.
          И, честно говоря, я не знаю как оценить данный вызов.
          Буду премного благодарен, если кто-нить подскажет куда посмотреть дабы узнать что реально делает эта команда.
          • 0
            Реально оно сильно зависит от платформы и имеет право меняться даже между версиями и запусками одной и тойже JVM.
            В свое время когда интересовался проверял: если срабатывает Escape Analysis то аллоцирует на стеке и обнуляет процессорной инструкцией,
            иначе оно выделяет в эдеме обьект, и вызывает процессорную инструкцию обнуления.
            В моем случае для обнуления вызывалась оптимизированная реализация из SSE.
            • +1
              Все равно я не могу придумать, как обнулить кусок пямяти длиной n (n → ∞) быстрее, чем за O(n).
              • 0
                Когда вы занимаетесь теоретической разработкой алгоритма нужно говорить, в чем вы исчисляете операции. Говоря O(n) вы подразумеваете что элементарная операция это и есть обнуление одной ячейки. Если считать элементарной операцией такт процессора — думаю вы все еще правы, сложность имеет линейный рост. Но если считать byteCode инструкцию, то очевидно будет O(1). Это как договорится)

                Когда вы занимаетесь не теоретической разработкой а практической становятся важны константы.
                Например: есть реализации Map для целых чисел со сложностью log log M(при некоторых предположениях но упустим, не суть). Однако на практике константа у них больше и они становятся осмысленны когда количество данных сравнимо с числом атомов в наблюдаемой вселенной.

                В данном конкретном случае это сродни System.arrayCopy, но еще быстрее.

                офтопик: мне кажется что с использованием программной эмуляции версионирования памяти с помощью Y-fast tries можно добиться сложности log(количество инструкций УЖЕ выполненых програмой). В предположении что время работы вашей программы в целом суб-экспоненциально то это асимптотически быстрее.
                • +1
                  Все, что вы написали — верно. Но к исходному вопросу отношение имеет слабое.
                  Я думаю, вы сами понимаете, насколько нецелесообразно выбирать в качестве скалярной операции byteCode инструкцию.
                  Теоретизирование на тему гипотетических архитектур, специально заточенных на оптимизацию отдельных операций, также считаю не относящимся к исходной задаче.
                  Константы, конечно, имеют огромное практическое значение, но на ассимптотическую оценку не влияют.
  • +1
    Кстати: вопрос вдогонку на тему Generic+колекции:
    у Map<K,V>
    put(K key, V value)
    но V get(Object key).
    Почему в одном случае тип ключа V а в другом Object.
    • 0
      я когда первый раз увидел подумал, что это баг и пошел читать, зачем же так сделали… вот тут написано хорошо: smallwig.blogspot.ru/2007/12/why-does-setcontains-take-object-not-e.html
      • 0
        Хороший вопрос, прочитал по инфу по ссылке, суть ясна, но ввело в ступор следующее:
        But the compiler doesn't know the type — it could be a Foo, or SubFoo, or SubSubFoo, or who knows what? Thus the compiler would have to forbid everything — the only safe parameter to a method like this is null.

        This is the behavior you want for a method like Set.add() — if you can't make damn sure of the type, don't allow it.


        То есть в первом случае компилятор запретит любой тип, разрешен будет только null, а в методе add применяется тот же самый подход и разрешен не только null, но и тип E. По логике или и там и там, должно быть все запрещено или работать корректно в обоих случаях. Или я что-то все же не понял.
        • 0
          Оттуда же:
          Uniformly, methods of the Java Collections Framework (and the Google Collections Library too) never restrict the types of their parameters except when it's necessary to prevent the collection from getting broken.
  • 0
    Какая оценка временной сложности выборки элемента из HashMap? Гарантирует ли HashMap указанную сложность выборки элемента?
    Как я уже тут сказал вопрос очень странный, если рассматривать именно теорию сложностей, то гарантирует константную, да.

    з.ы Как раз эти вопросы подойдут именно для отсеивания приличных джуниоров от непойми кого, по определению просто. Или теперь джуниором называется тот, кто не понимает элементарных вещей, типа устройства классических структур данных? Т.е. начал с обратной стороны обучаться? Оригианльноу.
    • +1
      Учитывая что на хабре люди всерьез обсуждают нужно ли высшее образование, то у многих кто выбрал не тратить на него время обучение начинается со случайной точки. И может происходить в хаотическом порядке.

      ps:
      Я согласен что даже современные курсы алгоритмов в вузах устарели.
      Но они являются фундаментом для уже современных курсов, потому я не жалею что выбрал идти в вуз.
    • +1
      Вещи эти не совсем элементарные, но, я соглашусь, простые при должном background`е. Теперь про него, этот самый background. К сожалению, в «уездных» городах, где нет академ городков, или исследовательских центров связанных с IT, образование в ВУЗах по IT специальностям, как правило, очень слабая. В итоге на выходе получаем непойми кого, как вы говорите, с навыкам кодинга, если человек сам не будет дальше развиваться, то все, вот его уровень теоретических знаний. Это очень здорово, если повезло учиться в ВУЗе с сильным обучением, но таких вузов мало в стране, так что жизнь и рынок диктуют свои условия. К тому же джуниор очень сильно отличает от компании к компании, где-то возьмут вчерашнего студента из уездного вуза с базовым пониманием программирования на джуниора, а где то может после пары лет опыта работы и хорошего вуза не потянет на джуниора (само собой если и тот и тот хорошо учились в своих вузах). Как я в самом начале написал, на некоторые из этих вопросов не смогли ответить знакомые разработчики (middle, junior). У них хороший опыт, они серьезно разбираются в своих узких сферах деятельности, они хорошо делают свою работу и я думаю вполне смогут пройти собеседование на аналогичную деятельность в другие, в том числе и крупные компании, но вот здесь у них пробелы из-за вуза, из-за отсуствия увлеченности в этом направлении, из-за отсуствия необходимости разбираться в этом по работе. И у меня язык не поворачивается назвать их «не пойми кто». Реалии жизни не всегда укладываются в представление о правильном образовании: сначала серьезный фундамент базовых вещей, потом более узкие предметы и т.д.
  • –1
    7. Как устроена HashMap?

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

    Вкратце, HashMap состоит из «корзин» (bucket`ов).

    basket это корзина
    bucket это translate.google.com/#en/ru/bucket
    Большой совет — не переводите термины вроде этого, особенно на собеседовании. Если бы я Вас собеседовал, то кашлянул бы, лучше поверьте мне
    • 0
      Спасибо за замечание, про различие этих двух слов я знаю, и перевод (точнее не перевод, а адаптация термина на русский) принадлежит не мне. Я сейчас не вспомню откуда именно так пошло, но употребление именно этого термина не раз встречал. Может это конечно неверно закрепившийся термин, в каком-то ограниченном сообщество программистов. В любом случае учту ваше замечание.
      • 0
        то есть как, Вы читаете не оригиналы? Возможно этот термин и закрепился, я уже полгода не пишу на джава регулярно… но я его встречаю в первый раз. Наверное потому что не особо приходилось читать переводы, я вот как-то нормальных не находил никогда. Вообще лучше не читать авторов… брать спеку, и чехлить. Авторы вносят много выводов, лишая Вас удовольствия сделать их самому :)
        • 0
          Стараюсь читать оригиналы, но что греха таить бывает и в переводе читаю что-то, кроме того много информации в сети именно на русском (форумы, статьи), а там тоже бывает с переводом не все гладко.
          • 0
            послушайте The Java Posse, они, конечно, технические вопросы обсуждают вскользь (не сказать что вообще мимо :) ), но все-же это джава подкаст :) и не забивайте себе мозг Eckel-ем (thinking in java), хотя если у Вас есть киндл и Вы тратите больше часа в день на транспорт (метро) — эта книга будет интересным чтивом. для джуниора. трушные синьеры читают спеки :)
            • 0
              Попробую начать слушать, спасибо за совет.
              • +1
                без вопросов :)
    • +2
      В русском ACM'е фигурирует именно «корзина» в большинстве случаев. Мне кажется неверным всегда прямо экстраполировать английские термины в русские, например здесь «корзина» больше подходит по смыслу, чем «ведро».

      К тому же в университетах зачастую обучение алгоритмам происходит не по книгам, а передачей из уст в уста, в том же Кормене нет большей части используемого на олимпиадах — алгоритмы банально появились позже выхода книги, и многие из них пришли из России.
  • 0
    Чтобы сэкономить время, на собеседовании задаю вопрос, подсмотренный когда-то у Яндекса:
    в каких из указанных наборов данных время поиска элемента составляет O(ln n):
    Object[]
    ArrayList
    LinkedList
    Vector
    HashMap
    LinkedHashMap
    TreeMap
    отсортированный Object[]
    отсортированный ArrayList
    отсортированный LinkedList

    Еще хорошие вопросы про контракт equals-hashCode и обход коллекции итератором, в которую вносятся изменения не через итератор. Неизменяемые наборы данных тоже хорошая тема.

    А про выбор между ArrayList или LinkedList меня бы устроил ответ, что в 90% случаев разницы нет (как правило, список формируется один раз из небольшого количества элементов и более не изменяется, обходится полностью).
    • 0
      Object[]
      ArrayList
      LinkedList
      Vector
      здесь у нас полный перебор

      HashMap
      LinkedHashMap
      здесь меньше, чем ln n, хотя опять же как смотреть, выше идут споры про HashMap и Big O.

      TreeMap
      отсортированный Object[]
      отсортированный ArrayList
      вот это, подходит

      отсортированный LinkedList
      а здесь не получится lg N, нет возможности быстрого доступа к по индексу элемента
  • 0
    Коллекции — это только первая часть вопросов. Дальше интереснее: nio/atomic/concurrent/locks/threads, дальше специализация под проект /sockets/javaee/gwt/sql/…
  • –2
    а с каких пор у вас HashMap стал коллекцией?
    • +1
      А почему минусуют? По мне так забавный вопрос на знание Collections Framework джавы. Совсем не очевидно, что Map не реализует интерфейс Collection.
      • +1
        Не реализует, но относится к Collection Framework, поэтому думаю и минусуют.
      • 0
        Какая разница что оно там реализует. Hash, очевидно, всё равно является коллекцией по определению.
  • +3
    Вряд ли можно найти оправдание использованию LinkedList в качестве реализации списка. В качестве реализации Deque, ещё куда ни шло, но и здесь есть ArrayDeque.

    На самом деле, вопрос, какую реализацию выбрать не так актуален, если не знаешь какой интерфейс тебе нужен. Программистов как-то уже научили, что в качестве параметра или при объявлении переменной не стоит использовать конкретную реализацию, т.к. это приводит к усложнению дальнейшей разработки. Все согласились, хорошо, не будет использовать конкретную реализацию, будем писать везде List. Но не все поняли основную мысль, надо не лепить List куда ни попадя, надо максимально абстрагироваться. Почему-то все всегда и везде используют List, а ведь есть множество других интерфейсов. При объявлении параметра метода или переменной, или поля в классе нужно использовать именно тот интерфейс, свойства которого вам нужны.

    Iterable — говорит о том, что реализация может создавать итератор, в большинстве случаев от параметров метода большего и не нужно
    Collection — обеспечивает методы добавления и удаления данных
    List — гарантирует сохранение порядок
    Set — гарантирует уникальность элементов
    SortedSet — предоставляет элементы в естественном (ну можно с компаратором поиграть) порядке
    Queue — часто забывают про очередь, в один конец очереди элементы добавляются, а из другого достаются
    Deque — двунаправленная очередь, позволяет добавлять и удалять элементы с обоих концов, может быть использована в качестве стека
    Map — отображает одни элементы на другие
    SortedMap — опять же можно получить список кортежей, отсортированный по ключу

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

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

                С потокобезопасными коллекциями вообще отдельная песня — их или не используют вообще, тормозя поток на пустом месте блокировкой всего и вся, или используют неправильно, полагаясь на «раз написано Concurrent, значит сам все проблемы с потоками разрулит», и огребая гонки и прочие несогласованности.
      • +1
        А потом говорят, что на хабре сливают не по делу…

        Вы высказали абсолютно правильную мысль. Действительно всегда надо выбирать минимально необходимый контракт.
        И вполне можно подискутировать на тему того а так ли часто имеет смысл выбирать конкретную реализацию.

        Но заем вы все испортили высказыванием в столь странной форме?

        Штирлиц ворвался к Мюллеру, врезал ему в ухо, отобрал секретные документы и спросил:
        — А не найдется ли у вас канцелярских скрепок?
        Штирлиц знал, что в разговоре всегда запоминается последняя фраза, и если Мюллера спросят:
        — Зачем приходил Штирлиц? – тот наверняка ответит:
        — За скрепками.
      • –3
        А я совершенно согласен с вами. Тем более интересно слышать разговоры про различную производительность от апологетов языка со сборкой мусора. Если говорить про Android — не высшим приоритетом UI потока. Дальше, какие бы в гугле не работали инженеры, любое простейшее приложение не сделать реально быстрым, какие ты коллекции не используй.
  • 0
    А мне вот это [[В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.]]] совсем не понятно! У автора есть какие нить аргументы, подтверждающие это высказывание? Как может структура, где не надо вообще копировать хип, уступать в производительности другой, где каждый шаг может привети к реевалюэйту аллоцированной памяти??!!! поясните, пожалуйста?
    • 0
      Каждый шаг — не может. Это раз.

      А во-вторых, возьмите сами и попробуйте.

      В-третиьх, вот можете посмотреть у Страуструпа описана интересная задача, в которой по асимптотике выигрывает связный список, но на практике std::vector быстрее из-за константы.

      www.stroustrup.com/Software-for-infrastructure.pdf

      Depending on the machine architecture and the programming language, the answer will be that the vector is best for small to medium values of N. When I ran the experiment on my 8-Gbyte laptop, I found N to be much larger than 500,000.

    • 0
      По потребляемой памяти я дал ссылку на хорошую статью, можете почитать, а по скорости, вбейте в гугл, получите кучу тестов, ну и кроме того, здравый смысл подсказывает, что работа с массивом быстрее создания объектов на каждом шаге.
    • 0
      В LinkedList, полагаю, используется двусвязный список, поэтому на каждый элемент тратится дополнительная память на два указателя: на предыдущий и следующий элементы. Добавление каждого элемента — это создание нового объекта в хипе, что довольно дорого.
      В противовес этому ArrayList тратит память исключительно на массив указателей и его размер. Перевыделение памяти происходит довольно редко, можно доказать, что амортизированная сложность добавления нового элемента будет равна O(3), то есть O(1). Поэтому операция добавления элемента в конец ArrayList'а выполняется быстрее, чем для связного списка. Поиск нужного элемента так же может быть быстрее, т.к. мы идем последовательно по памяти, а в случае связного списка соседние элементы могут быть в противоположных кусках памяти. Обращение по индексу — без комментариев.

      Как-то так. LinkedList может быть быстрее только если нам нужно часто удалять/добавлять элементы в произвольные места.
      • 0
        Двусвязный список, все правильно. Сам всегда думал, что односвязный поэтому заглянул в сорцы.
        LinkedList.java (author Josh Bloch)
            private static class Node<E> {
                E item;
                Node<E> next;
                Node<E> prev;
        
                Node(Node<E> prev, E element, Node<E> next) {
                    this.item = element;
                    this.next = next;
                    this.prev = prev;
                }
            }
        
      • 0
        На самом деле, одна из больших проблем связных списков — это пробой кеша, с чем часто можно встречаться, если писать на C++. Для Java это в большинстве случаев не так актуально, т.к. там все равно ссылаемые объекты в другом месте лежат, но если писать что-то высокопроизводительное на примитивных типах, можно серьезно споткнуться об это.
  • 0
    > LinkedList наоборот, за постоянное время может выполнять вставку/удаление элементов в списке (именно вставку и удаление, поиск позиции вставки и удаления сюда не входит)

    Это очень странное предложение. Зачем рассматривать вставку в середину отдельно от поиска позиции?
    • +1
      А зачем смешивать две операции? Я согласен что в 90% случае они используются вместе, но все же бывают случаи, когда уже есть ссылка на нужный элемент (сохранили после вставки предыдущего элемента) + так удобнее, на мой взгляд все же сравнивать, операции не смешивая их и их сложности.
      • +1
        интересно, как Вы будете сохранять эту «ссылку на нужный элемент» в LinkedList'е? Откуда вы её возьмёте?
        • 0
          Да, согласен, как то интуитивно представил что создал объект, сделал add в список, а ссылка на объект у меня осталась. Отсюда и написал свой сценарий, но вы правы, дальше я что-то не додумал, с этой ссылкой в рамках списка уже ничего не сделать.
          • +1
            я просто пару раз на собеседованиях отвечал именно так на этот вопрос и «собеседователи» оба раза были сконфужены по той же причине)) С одной стороны — в исходном коде чётко видно, что список делится пополам и указатель начинает бежать до элемента либо с начала, либо с конца — в зависимости от того, что ближе.

            В то же время, это ещё ничего не значит. Реально может выполяться немного другой код — бывают всякие alt-rt.jar, JIT-компиляторы и много всяких других технологий, которые где-то в глубине души могут хранить подобную ссылку.

            В конце концов, имплементация от Оракла — не единственная. Любая другая имплементация может действительно кешировать имеющиеся промежуточные ссылки по какому-то алгоритму, и тогда описанное Вами будет работать. Но OracleJDK, судя по исходном коду, это не делает.
            • 0
              О, как! Спасибо поучительный подход к данному вопросу!:)
            • –1
              Ваши «собеседователи» не знали, что такое итератор. Странные какие-то собеседователи.
              • 0
                Ещё раз: я согласен, что за счёт использования listIterator операции можно разделить. Но с точки зрения сложности — это не панацея. До нужного места всё равно нужно сначала допрыгать.
    • 0
      Это очень правильное предложение. Рассматривать вставку/удаление элементов отдельно от поиска нужно именно потому, что эти операции имеют различную алгоритмическую сложность и характер этой сложности зависит от структуры данных. И не следует путать поиск с индексацией — получить доступ к элементу с уже известным индексом — не то же самое, что найти этот элемент. Вставить один элемент в связный список вы можете за константное время, в массив — за линейное. Тоже самое с удалением. Вставить одномоментно m последовательных элементов в список длины n вы сможете за константное время без копирования вставляемых элементов, за O(m) — с копированием. Проделать тоже самое с массивом вы сможете за O(n + m). Удалить m элементов из списка, если пренебречь работой сборщика мусора, вы можете за константное время. Из массива — за O(n — m + 1). Получить доступ к элементу по его индексу в списке вы можете за линейное время, в массиве — за константное. Выполнить поиск элемента в списке вы сможете за линейное время, в произвольном массиве — тоже за линейное, в отсортированном массиве — за логарифмическое, воспользовавшись бинарным поиском.
      • 0
        А как можно добавить m последовательных элементов в список за константное время? Или у вас уже эти m элементов «собраны» в другой список?
        • 0
          Я указал «без копирования». Без копирования это возможно, действительно, если элементы уже принадлежат другому списку. В STL C++ операция носит имя splice. Действительно, нужно было указать, что элементы принадлежат другому списку. Сорри.
      • –1
        Ах, простите, не все операции такого рода перечислил.
        Доступ к элементу по указателю (ссылке, итератору) осуществляется одинаково быстро в случае обеих структур данных — за константное время.
        Вы спросили, когда может понадобиться вставка/удаление элемента без его поиска. Отвечаю. На элемент коллекции некоторый иной объект может хранить указатель (ссылку, итератор), например с тем, чтобы иметь возможность его (этот элемент) удалить из коллекции в нужный момент. В этом случае, если предполагаемый размер коллекции достаточно велик, а необходима она только для того, чтобы была возможность периодически последовательно перебирать все элементы этой коллекции, лучшим выбором будет связный список, так как всего нам необходимы три вида операций — последовательный перебор элементов, доступ по указателю, удаление элемента. Первые две выполняются одинаково быстро и списком, и массивом, вторая значительно быстрее (O(1) против O(n)) выполняется связным списком. Условие на достаточно большой размер коллекции введено потому, что оценки сложности операций, выполняемых над списком, имеют большие константы по очевидным причинам.
      • 0
        В java.util.LinkedList нету метода «вставка/удаление элементов отдельно от поиска». Я рад, безусловно, что вы прочитали книжку Кормена, только вот топик не о том.
        • 0
          LinkedList реализует интерфейс Iterable, так что вы можете хранить итератор на произвольную позицию в списке (итераторы в Java указывают не на сами элементы, как в STL C++, а на «промежутки» между ними). Итератор позволит вам удалить нужный элемент за константое время. Для справки.
          • 0
            Но чтобы итератор указывал на «нужный» элемент придется, перебрать несколько элементов. По этим перебором 23derevo и понимает «поиск».
            • 0
              Именно. Несколько — это O(N).
            • 0
              Я постарался повыше описать модель задачи, в которой этот поиск будет не нужен. Вы добавляете новый элемент в список, скажем, всякий раз в голову. Берете после этого от списка итератор. И передаете его тому объекту, которому этот итератор интересен. Когда такому объекту-владельцу понадобиться удалить этот элемент из списка, он сможет это сделать без поиска, несмотря на то, что к тому времени указуемый элемент не будет первым, вероятно. А будет непонятно где.
              • 0
                нифига не сможет. Вызов методов add и remove у LinkedList'ового listIteartor'а начинается с вызова замечательного метода checkForComodification().

                В спеке это описано так:
                The list-iterator is fail-fast: if the list is structurally modified at any time after the Iterator is created, in any way except through the list-iterator's own remove or add methods, the list-iterator will throw a ConcurrentModificationException.


                Это именно — защита от того, что предлагаете Вы.

                • 0
                  Да, в моём конкретном примере вы правы. Он неудачен, приводить примеры мне трудно, учитывая, что я работаю на C++ и ни одним глазом не Java-программист. C++ свободы предоставляет больше и позволяет использовать преимущества структур данных, жаль, что это происходит в Java реже. Уверен, тому есть причины (возможно, ограничения накладывает GC, возможно, особые взгляды Java на многопоточное программирование — не могу сказать). Но эти проблемы касаются только стандартных реализаций коллекций в Java. У ntz конкретные примеры получаются лучше, хотя мы оба преследуем одну и ту же цель — показать, что поиск элемента в коллекции, доступ к элементу по индексу, по указателю (не важно, как называется указатель в вашем языке программирования), удаление или вставка элемента — разные и отделимые друг от друга вещи. Если ваша конкретная задача не позволяет вам этого увидеть, это не значит, что завтра вы не столкнетесь с задачей, которая окажется чувствительнее к этим особенностям.
                  • +2
                    поиск элемента в коллекции, доступ к элементу по индексу, по указателю (не важно, как называется указатель в вашем языке программирования), удаление или вставка элемента — разные и отделимые друг от друга вещи.


                    Спасибо, Кэп.
        • +2
          Вообще, в Java LinkedList очень даже можно вставлять и удалять элементы отдельно от их поиска.

          Метод listIterator() вернет ListIterator, который поддерживает вставки и удаления элементов (add(T element) и remove() соответственно) в текущей позиции итератора, за константное время, естественно. При этом поиск позиции вставки / удаления является, очевидно, отдельной операцией.

          Например, если мне надо вставить m элементов после элемента А в середине списка, я затрачу не O(mn) (если бы вставка была отделима от поиска), а O(n + m) (O(n) на поиск позиции для вставки, и O(m) на вставку всех m элементов).

          Такие дела.
          • 0
            Отвечаю по порядку:

            1. listItertor'ом нужно дойти сначала до нужного места. А это O(N). Так что без поиска — не выйдет. Некоторый выигрыш можно получить, если все Ваши операции локализованы в каком-то куске. Тогда итерироваться туда-сюда действительно быстрее. Но в общем случае — шило на мыло.

            2. Для вставки пачки элементов в середину списка есть addAll(int index, Collection<? extends E> c). Он тоже вполне себе за O(N+M) работает без всяких listIterator'ов.
            • 0
              Существует отдельно операция поиска элемента и отдельно операция его удаления / вставки нового. Эти операции разные, и в разных ситуациях общая асимптотика времени будет отличаться от подхода в лоб «найти и вставить, повторить».

              Пример, я согласен, привел не очень наглядный, вот лучше — проделать то же самое, но чередуя с элементами коллекции (т.е. вставить свой элемент, пропустить один существующий, вставить следующий свой элемент). Или другой пример — удалить m идущих подряд элементов, начиная с элемента A.
              • 0
                Да, операции разные. Да, в некоторых случаях listIterator быстрее. Например, когда позиции локализованы.

                удалить m идущих подряд элементов, начиная с элемента A

                Это тоже элементарно сделать за O(N):
                list.sublist(0, n).addAll(list.sublist(m+n, N))
                


              • 0
                проделать то же самое, но чередуя с элементами коллекции (т.е. вставить свой элемент, пропустить один существующий, вставить следующий свой элемент)


                не уверен, что понял Вас :) уточните, пожалуйста, этот сценарий.
                • +1
                  Исходная коллекция: 1 2 3 4 5 6 7 8 9 — n элементов;
                  Вставляемые элементы: 10 11 12 — m элементов;
                  Хочу получить: 1 2 3 4 5 10 6 11 7 12 8 9.

                  Как это сделать за O(n+m) по вашему?
                  Я конечно предположу ваш ответ — взять кусок списка с 5 по 7, слить его со вставляемыми элементами, склеить кусок списка до 5 + полученный кусок + кусок списка после 7. Но нахрена так жить?

                  И почему же вы так боитесь итераторов?
                  • 0
                    (меня тут жестоко минусуют, так что стану плюсовать людей, которые задают те же самые вопросы)
                  • 0
                    Итераторов никто не боится. Более того, в этом конкретном примере итератор очень даже подходит, потому что

                    1. позиции, в которые Вы хотите вставлять — локализованы (n, n+2, n+4, ...). Это подходящий юзкейс для итератора — я уже писал Вам об этом выше.

                    2. сама терминология, в которой Вы формулируете задачу («вставить свой элемент, пропустить один существующий, вставить следующий свой элемент») — это описание именно в терминах итератора (add, next, add, next). Так что ничего удивительного. Попробуйте ради интереса найти подобную задачу в реальной жизни.
                    • +1
                      То вы отрицаете всякую необходимость раздельных операций поиска и вставки, то отрицаете существование таких раздельных операций в Java, то вам задачи не те. Да, не всегда в ваших способах асимптотика выше, но остается множество совершенно лишних операций типа создания объектов, копирования списков и так далее.

                      Удалите все четные элементы in-place.
                      • –1
                        Удалите все четные элементы in-place.


                        Тут вполне хватит простого итератора, да :)

                        Только вот in-place непонятно зачем. Зачем такое требование? Портить данные, переданные неизвестно откуда. Есть риск что-то где-то поломать. А вот при копировании — риска нету. Поэтому обычный foreach с добавлением в конец каждого второго элемента в новый список выглядит безопаснее. А с учётом того, что длина известна заранее (N/2) то непонятно, почему не ArrayList.
                        • +2
                          Ну вы тут уже напридумывали условий, я тоже так могу — список на 100 млн элементов. Допустим, я собираю данные в реалтайме, и периодически их прореживаю.
                          • 0
                            ок, согласен :)
                          • 0
                            Массив лучше. Память не дёргается лишний раз.
  • –3
    О боже, тихий ужас. А каком джуниорстве вы говорите? Я бы забивал камнями любого осмелившегося назваться «программистом», но при этом оставившего без верного ответа более одного вопроса (его даже можно назвать — число корзин в хеш-таблице на момент ее создания — какая разница, для начала? Идиотский вопрос. Сегодня их там 16, в следующей версии Java станет 12 или 20 — это не имеет никакого значения абсолютно). Обратите внимание, я говорю — «программистом», а не «Java-программистом». Чтобы ответить на все вопросы не нужно даже знать о существовании Java — вся необходимая информация полностью раскрывается названиями классов. Есть такая замечательная книга: «Кормен Т., Лейзерсон Ч., Ривест Р. — Алгоритмы. Построение и анализ». Из вашей статьи только и можно сделать вывод, что открывали ее исключительно ребята с гордым именем «senior developer» и тремя годами опыта работы. Куда катится мир. Куда катится хабр. Только и прочесть теперь можно, что про бизнес, сделанный на адаптерах для сим-карт. Крайне увлекательно.
    • –1
      Нет, серьезно. Я крайне советую найти эту книгу и заставить себя изучить хотя бы избранные главы. Если кто-то заинтересуется, какие именно нужны для понимания работы коллекций — спрашивайте, потружусь перечислить. И да: лучше читать не самое современное издание, если вам нужен русский язык, а второе, в переводе замечательной организации МЦНМО
      • +3
        Я в свою очередь крайне рекомендую, скинуть спесь и пафос, выглядит плохо это все. Да приведенная книжка это классика, ее стоит изучить, но к чему закатывать глаза и артистично говорить «О, Боже, как темны все эти люди на хабре. Я еще читать не умел, но мог ответить на все эти вопросы». Утрирую конечно, но общий смысл Ваших комментариев таков. Сорри, что так эмоционально.
        • –2
          Я лишь искренне (и да, очень эмоционально, уж простите) расстроен, что подобные вопросы вызвали затруднение у «крепких середнячков» индустрии, а не у студентов первого семестра технического ВУЗа, что «лидеры рынка», интервьюируя человека с опытом работы, претендующего на должность а ля «Java разработчик» валят его на таких вопросах, до Java-то не успевая добраться. Понимаете, у человека, который хотя бы коснулся программ технического ВУЗа, очно ли, самостоятельно ли, не возникнет вопросов, в какой литературе подобную информацию искать, равно как не возникнет сомнений в том, что это надо знать. Так что такую статью все бы мы приняли разве что от школьника, который самостоятельно, без поддержки незаинтересованных в нем, как это почти всегда бывает, преподавателей пытается разобраться в чём-то для него безусловно непростом. А в таком формате это лишь вызывает изумление всё.
          • +1
            Ох, как вы тонко троллите меня, называя «школьником». Скажите, а что Вы заканчивали, что у Вас для «студентов первого семестра технического ВУЗа» сходу раскрывают довольно неплохо структуры данных?:) Мне, к сожалению, не повезло, я закончил самый обычный уездный технический ВУЗ, где на первом семестре преподавали Delphi с кучей общеобразовательных предметов до комплекта. Уж извините, реалии современной России таковы: в большинстве ВУЗов страны все так печально, что 100% выпускников по Вашей классификации ни на что не годятся, кроме как работать грузчиками.
            • 0
              Неплохо раскрывают структуры данных? Квадртатики, связанные стрелочками (связный список), и расчерченную на клеточки полосу (массив) на доске нам нарисовали на второй паре практики по информатике (практике по программированию), потому что на первой прошло что-то вроде тестирования — кто, откуда, чем раньше занимался. В группу я попал самую обычную, и впоследствии мы алгоритмам уделяли мало внимания. Даже очень мало. Больше преподаватель акцентировался на кратеньком введении в C++ (функции, модули), на стиле кодирования, Фредерика Брукса нам посоветовал прочесть (его «Мифический человеко-месяц»). Рассказал кратенько о водопадной модели разработки, agile-ах — и тому подобных вещах. В начале второго семестра — о системах контроля версий (мы дружно переехали со своими домашками на github), о модульном тестировании и прочем. А на теории, на лекциях, все это время шла низкосортная ерунда про синтаксис паскаля. Мало кто ходил на эти лекции. А, про обычную группу. Действительно хорошо структуры данных и алгоритмы раскрывали одной необычной группе, из которой потом подразумевалось набирать ACM-спорстменов. Вот эти ребята действительно разбираются в таких вопросах. И я не закончил учёбу. Я учусь на втором курсе. Мат-Мех СПбГУ. Кучи общеобразовательных у нас нет, у нас есть куча математик. Которые пытаются отнимать почти все время, на деле отнимают лишь большую часть. Все же стараемся заниматься побольше по специальности. Хоть и самостоятельно преимущественно.
              • +2
                Начнем с того, что все это происходит в вузах, которые можно конкретно пересчитать на пальцах одной руки — ВМК МГУ, МФТИ, СПбГУ, ИТМО, матмех УрФУ (который был УрГУ). Я мог что-то упустить, но во всех остальных даже и близко (т.е. хоть-сколько-нибудь-близко) ничего подобного нет. Ну вот нет и все. Грустно, да.
                • 0
                  Ну в моем вузе все-таки это было. Не скажу что в «полном» объеме, но все же Кнута почитывали. И кстате, не пойму почему Кормен стал таким популярным в ВУЗах теперь, а также начал считаться уже классикой. По-видимому из-за очень сжатого изложения.
                  • 0
                    Ого. Кнута нам только посоветовали. Не более того. Для первых курсов это слишком сложная литература по нашим меркам. Как называются ваши ВУЗ и факультет?
                    • 0
                      ВУЗ у меня довольно посредственный (не то что СПбГУ) — СГТУ. Факультет Электронной техники и приборостроения, специальность «Программирование вычислительных машин». Но в то время работали очень хорошие преподаватели. Сумели, кому надо было, научить и алгоритмам и промышленному программированию. Сейчас, насколько я знаю, старая школа почти развалилась, лучшие преподы уволились.
              • +5
                Впрочем, я уже остыл, за такую длительную беседу, и готов принести извинения за излишнюю резкость. При первом прочтении статья оставила очень сильные впечатления, потому я так и отреагировал.
                • +3
                  Вызывает уважение такое высказывание в конце спора.
                • +2
                  На самом деле, вы просто плохо осведомлены о рынке труда программистов вообще и в нашей стране в частности. Безусловно, знание лучше незнания, и где-то и кому-то даже ваши свежепрочитанные знания пригодятся, но не хочу вас расстраивать — это очень и очень узкий круг компаний. В 95% случаев подобное банально не нужно от сотрудника (а иногда даже и вредно для компании — возомнит себя спецом и начнет бабла требовать, а выгоды от этих знаний — никаких), так и живет индустрия.

                  И, опять же, разработка не на одних алгоритмах зиждется — очень часто важны умения грамотно проектировать систему и разрабатывать сложные архитектурные решения, потому не стоит так однобоко относиться к саморазвитию — можно неожиданно оказаться полным профаном в разработке реального софта.
                  • 0
                    Я знаю, что разработка не на одних алгоритмах зиждется. Это знает и мой преподаватель — я уже отметил, что мы почти не занимаемся алгоритмами. А пишем семестровые проекты (кто UML-диаграммы с рукописных рисунков распознает, кто обучает нейронные сети распознавать пол человека по фотографиям, кто ломает голову, как автоматизировать процесс проверки соблюдения правил code style'ов (styleguide'ов) в проектах на C++, мучая Clang), да зачёты по паттернам проектирования сдаём. Не сомневаюсь, что большинству работодателей нужна недорогая рабочая сила, хотя бы потому, что несложных, рутинных задач в индустрии больше, чем содержательных. Но самые первые строки статьи я понял так, что автор не мечтает оставаться такой вот рабочей силой. И кто вам сказал об однобокости? Если б я изложил что-то очень нетривильное из теории алгоритмов, можно было бы заподозрить однобокость. А я до сих пор говорил какие-то совершенно банальные вещи. Опыт работы у меня есть, я знаю, что технический директор компании, не первый месяц пытающейся побороть неудовлетворяющую клиента тормознутость своего продукта, выполняющего преимущественно поиск, может впервые от меня, стажёра — первокурсника, услышать, что такое бинарные деревья поиска вообще и красно-чёрные деревья в частности. И одновременно я знаю, что компания, позволяющая себе офис на пересечении канала Грибоедова и Невского проспекта, по-прежнему пользуется CVS, а то и вовсе хранит код в БД или даже на дисках в папочках. Это не значит, что всё так и должно оставаться, а вам не надо понимать, что это — не лучшее, что могло бы быть.
                • +1
                  Вообще говоря, ситуация с Computer Science в России очень плохая. Даже на матмехе приходится прикладывать сильные усилия, чтобы что-то узнать. Так что ваши расстройства понятны.
                  И, как уже отметили ниже, далеко не всегда на работе требуются подобные знания.
                  Обычно нужно уметь быстро написать что-то, что будет выглядеть как работающий код (и не важно, приложение это или сайт).

                  PS: Матмех лучше всех.
                  Рекомендую открытый ещё yurylifshits семинар в ПОМИ с названием Computer Science — он периодически мелькает в статьях на Хабре.
                  Когда я заканчивал ММ, его принял под руководство alexanderskulikov, но что с ним стало сейчас, я не в курсе.
                  • +1
                    Я не принимал. =)

                    Но мы всё же как-то пытаемся улучшать ситуацию с CS в Питере и России:
                    compscicenter.ru/
                    compsciclub.ru/
                    logic.pdmi.ras.ru/~csr/

                    • 0
                      Ну не знаю.
                      На моей первой почте именно от тебя приглашения на семинар висят :)

                      Спасибо за ссылки
                      • +1
                        Так это приглашение в клуб, наверное. После Юры семинаром заведовал Костя Первышев, кажется. Или это я уже всё забыл.
                        • 0
                          В общем, в любом случае спасибо за то, что держите идею на плаву.
                  • +1
                    CS-клуб при ПОМИ живет, здравствует, радует своими лекциями, материалами, гостями — спасибо ему за то, что он делает.
              • +2
                И тем не менее, даже самую обычную группу у вас пытаются держать более-менее в курсе текущих вещей, у меня про agile не было ни слова, про системы контроля версий тоже. Был синтаксис си, паскаля, java, немного о структурах данных, lisp и prolog, asm, а так же занимательная веселуха с БД FoxPro (просто препод его когда изучил и требовла от нас курсачи на нем). Это за 5 лет. Вы учитесь в ведущем ВУЗе страны, с богатой историй и группами для спортивного программирования. Цените то, что у Вас есть, но не зарывайтесь: многим остается только мечтать об учебе в подобном ВУЗе и эти многие не глупее, просто по тем или иным причинам не могут это осуществить. Опять же реалии нашей страны.
      • 0
        В МЦНМО издавали русский перевод первого издания, насколько я помню.
    • +2
      А что бы вы спросили на собеседовании на джуниора?
      • –1
        Минуточку. Автор говорит о том, что уже прошел этап джуниорства и претендовал на место у «лидера рынка» не джуниором. У джуниора такие вещи можно спрашивать и нужно. Так как наверняка у работодателя будут сущестовать определенные планы на кандидата, следует в довесок спросить что-нибудь специальное. Кандидату нужно будет работать с сетью? Спросите его что-нибудь из этой области. С графическими интерфейсами? Спросите оттуда. И так далее. Неплохие рекомендации по проведению собеседований можно найти у Джоуэла Спольски, «Джоуэл о программировании». Хорошая книга, много полезного в ней можно почерпнуть.
        • 0
          И сам себе я не противоречу. У джуниора можно все это спросить. У джуниора нельза на это все получить неверные или неполные ответы — иначе это не джуниор. Джуниор должен все это прекрасно знать — и знать еще чуть-чуть (см. выше). Он не знает чего-то более сложного, и, главный момент, имеет очень небольшой опыт работы в реальных коммерческих проектах — либо не имеет такого опыта вовсе.
          • +1
            Простите можно поинтересоваться. Утверждая так категорично, сколько сот раз вы проводили собеседования?
            • –3
              Я не провел ни одной сотни собеседований.
    • +2
      Интересно. Вероятно, меня нельзя назвать программистом — я не могу ответить даже на половину этих вопросов. В большинстве случаев ответ «а какая разница»?
      Я понятия не имею, как ArrayList устроен внутри. Судя по названию, это нечто с интерфейсом списка, как-то использующее в реализации массивы. Возможно, весь список помещен в один массив. Возможно, массив разрезан на кусочки, организованные в виде списка или дерева. Это слегка замедлит доступ, слегка ускорит удаление и расширение, уменьшит требования к памяти. И позволит не хранить куски, заполненные null-ами. Как поступили авторы, мне не известно. И пока в интерфейсе не появится метода вроде unsafe object* GetRawArray() (или IntPtr GetRawArray), я не вижу причины как-то закладываться на его структуру или изучать подробности — достаточно знать, что вставка или удаление могут занять какое-то время, а доступ по индексу — более-менее быстрые.
      HashMap? Наверное, сегодня и в этом языке эта структура называется так. В другое время и в других местах она называлась map, Hashtable, Dictionary<>, и т.д. Как устроена? А какая разница? Может быть, это вёдра со списками (внешнее разрешение коллизий). Может быть, один массив — с внутренним разрешением. Может быть, какой-то их гибрид. Из всего обсуждения важным мне показалось только, что нельзя менять элемент, который используется в качестве ключа (если это изменение повлияет на результаты сравнения).
      Что касается прямой работы с элеменами списков, вставкой элемента за единичное время и т.п. — опять же, здесь и сейчас это может быть такой интерфейс. Если для указателя внутрь списка решили использовать итераторы — пожму плечами: по-моему, модификация объекта — не из функционала итератора. Хотя использовать ListNode для этих целей еще хуже: он был бы слишком завязан на структуру списка. Но называть «указатель внутри списка» итератором… слегка запутывает.
      Но в любом случае, помнить, как бибиотечные стуктуры реализовано здесь и сейчас, по-моему, смысла нет — пять лет назад классы и функции были слегка другими, и через пять лет они тоже могут измениться. Главное, знать, что при необходимости можно найти то, что надо.
      Если зачем-то нужны детали реализации структуры, то лучше реализовать её самому. Потому что библиотечная реализация может измениться без предупреждения.
      С другой стороны, мне регулярно требуются такие структуры, как приоритетная очередь (в которой «добавить элемент» и «взять наименьший элемент» выполняются за log(N)) и динамический массив фиксированного типа. Я иногда вспоминаю, что изобретать велосипеды сейчас не модно, иду искать эти объекты в стандартной библиотеке, ругаюсь на в очередной раз потраченные 20 минут, и достаю какую-нибудь свою реализацию.
      • +2
        Если я вас правильно понял, вы говорили, стараясь не очень привязываться к Java. Буду дальше исходить из этого предположения.
        Да, библиотечные реализации могут измениться. Ничего не могу сказать про Java, но про C++ можно утверждать — могут измениться лишь тонкие детали реализации. Но алгоритмическую сложность всех или почти всех операций фиксирует стандарт языка, и создатели стандартных библиотек, по крайней мере тех, что поставляются вместе с распространенными компиляторами, их придерживаются. Фиксируется в достаточной мере стандартом и интерфейс классов библиотеки. Так случается, что зафиксировав интерфейс коллекции и алгоритмическую сложность её методов, вы почти всегда остаётесь один на один с одной какой-то реализацией без особых альтернатив — не придумать вам реализацию абстракции множества с требованием поиска элемента за константное время в среднем случае на бинарном дереве поиска. Ну вот никак.
        Посему довольно удобно поступить обратным способом. Не запоминать сложности методов существующих коллекций, а запоминать принципы их устройства — их, принципов, много меньше произведения «число методов» x «число коллекций». А из принципов устройства автоматически следуют все сложности. Да и такой подход более структурирован и позволяет легче и проще выбирать подходящую коллекцию. Делать это осмысленно.
        Зачем запоминать что-либо, когда всегда можно посмотреть в документации? А как мыслить в таком случае, как придумывать алгоритм? Вместо того, чтобы мгновенно понять, что вам больше всего подходит, пойти читать доки одну за другой? Да ради бога. Раз прочтете, два прочтете — да и выучите. А раз еще не выучили, значит, не читали, не интересовались, значит, неосознанно подходили к выбору коллекции. Никогда это еще не мешало? Значит, не сталкивались еще с задачами, когда скорость работы была важна. Конечному пользователю, не вам. Но ведь это не правда, ведь так? У вас есть свои реализации нетривильных вещей, вы сказали, что вам была необходима очередь с приоритетами с хорошей скоростью работы. Были такие задачи. Тогда я не совсем понимаю, почему вам без разницы, чем вы пользуетесь.
        В STL С++ вы можете сымитировать очередь с приоритетами на std::vector с помощью свободных функций std::make_heap, std::push_heap, std::pop_heap. Сложность O(n), O(log(n)), O(log(n)) соответственно.
        В том, что нет особой разницы, использует хеш-таблица HashMap открытое хеширование или закрытое, а TreeMap является красно-черным деревом или AVL-деревом, я с вами полностью соглашусь. Хотя не знать точно странно.
        • –1
          Начнем с того, что это Вы сказали — «я говорю — «программистом», а не «Java-программистом».». И Ваш пост я прочитал, как «тот, кто не знает подробностей реализации библиотеки Java образца 2012 года (о которых, собственно, шла речь в исходной статье), не может осмелиться назвать себя программистом».
          Каюсь, стандарта C++ я не читал. Да и не пользуюсь этим языком уже лет 10. Но неужели в нём в самом деле прописаны сложности операций коллекций, реализованных в библиотеках? Было бы очень странно. В стандарт могли бы войти реализации тех операций, без которых не будет компилироваться программа (вроде operator new), но включать туда какой-нибудь stl??? Не понимаю.
          Сложность операций понять и запомнить можно. С различными возможными вариантами реализаций и плюсами и минусами каждого из них. Но как это поможет определить стратегию роста размера HashMap или ArrayList? Во сколько раз увеличивается размер того же ArrayList — в два? в полтора? Или в 1.32 раза, что может дать заметные преимущества перед другими стратегиями?
          Как мыслить, придыувая алгоритм… Сначала понять задачу, подобрать нужные структуры (сложность и реализация которых вам известны). Потом, вероятно, полезть в документацию, посмотреть, реализованы ли нужные структуры в стандартных библиотеках. Если реализованы — типизированы ли они (создавать ArrayList из int-ов я буду только если меня совсем не волнует производительность). Если нет — подумать, доверяете ли вы (или ваш начальник) сторонним библиотекам, или предпочтете реализовывать самостоятельно. Если не верите, что можете хорошо реализовать — то нет ли чуть менее подходящей, но стандартной библиотеки… и далее, пока процесс не сойдется. И в критических случаях всё равно придётся проверить скорость стандартной реализации и сравнить её с самодельной.
          • +1
            Начнем с того, что это Вы сказали — «я говорю — «программистом», а не «Java-программистом».». И Ваш пост я прочитал, как «тот, кто не знает подробностей реализации библиотеки Java образца 2012 года (о которых, собственно, шла речь в исходной статье), не может осмелиться назвать себя программистом».


            Эмм… Извините, утверждая процитированное вами и «Чтобы ответить на все вопросы не нужно даже знать о существовании Java — вся необходимая информация полностью раскрывается названиями классов.» я стремился акценты расставить прямо противоположным образом. То есть, не только версия Java не важна в данном случае, не важно, что это Java. Хеш-таблица как структура данных всегда имеет определенное устройство, будь она в Java, C++, C#, Python etc. (захотите свой собственный язык создать и добавить в его стандартную библиотеку абстракцию «ассоциативный массив» — построите или самобалансирующееся бинарное дерево поиска, или хеш-таблицу и устроены он у вас будут каноническим образом, как в классической литературе описано. Иначе работать будут или медленее, или неправильно, или и то, и другое сразу)

            А мне наоборот очень удивительно, что вас изумляет существование строгого стандарта языка, на котором пишется крайне много вещей, в том числе таких, от скорости работы которых могут зависеть человеские жизни. Разумеется сложность операций ограничена сверху! Разработчик должен быть уверен, что та или иная операция не займет слишком много времени. Посмотрите у Мейерса («Эффективное использование c++»), какие сложности вызвал метод std::list<T>::splice, который позволяет перемещать отрезки списков за константное время (кстати, сама причина существования этого метода в том, что можно гарантировать выполнение такой операции («врезки» отрезка списка из источника, в котором этот отрезок исчезает, в список-назначение) за константное время). Сложность оказалась в реализации std::list<T>::size(). Все остальные контейнеры STL гарантируют константую сложность этого метода. Как такое сделать для списков со splice? Ведь такая гарантия вынуждает хранить текущий размер (вот пример однозначного отображения требований в детали реализации) в самом списке. А если в него осуществили врезку (splice) отрезка другого списка? Сколько прибавить к хранимому размеру? Столько, каков размер врезки? Ну это чудесно, вот только подсчитать этот размер можно только за линейное от размера врезки время. Зачем стандарту давать такие гарантии на ::size() вот вообще в принципе? Пусть вы написали

            for(size_t i = 0; i < something.size(); ++i) { /* blah-blah */ }

            Если ::size() работает за O(1), а в теле цикла происходит что-то, имеющее сложность O(1), то такой цикл имеет сложность O(n), где n — размер something. Если, скажем, ::size() работает за линейное время, то сложность этого цикла — O(n^2). Пусть вы считали, что верно первое. Написали такой код. Пустили в продакшн. Тут вдруг сменили авторы библиотек реализацию так, что изменилась сложность (ведь вы говорите, что ее не нужно стандартизировать), цикл стал квадратичным. Ваша программа замедлилась в n раз в общем случае. Положим, n = 100000000000. Ой.
            Более того. Почему до стандарта 2011 года в стандартной библиотеке сущестовала толко одна реализация абстракции «ассоциативный массив», это был std::map(), реализованный на красно-черном дереве, а не на в общем случае быстрее (O(log(n)) против O(1)) выполняющей поиск хеш-таблице? А всё потому же. Красно-черное дерево гарантирует, что операция поиска пройдет за O(log(n)), а хеш-таблица только обещает O(1), но предупреждает: может получиться O(n).

            Но как это поможет определить стратегию роста размера HashMap или ArrayList? Во сколько раз увеличивается размер того же ArrayList — в два? в полтора? Или в 1.32 раза


            Я вас не понимаю. То вам асимптотика не важна, то стала жутко важной константа в асимптотике. Странно.

            Потом, вероятно, полезть в документацию, посмотреть, реализованы ли нужные структуры в стандартных библиотеках


            Лезть в документацию выяснять, есть ли в стандартной библиотеке связный список или массив? Вы вчера вечером программиравать начали? Это знать надо.

            создавать ArrayList из int-ов я буду только если меня совсем не волнует производительность


            Снова вам стала важна константа в асимтотике. Так важна вам скорость работы используемых коллекций или не важна?

            Если нет — подумать, доверяете ли вы (или ваш начальник) сторонним библиотекам, или предпочтете реализовывать самостоятельно.


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

            И в критических случаях всё равно придётся проверить скорость стандартной реализации и сравнить её с самодельной.


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

            Пока в активную разработку эта задача не пошла, но когда пойдёт — придётся разбираться, что там со скоростью, и какими алгоритмами пользоваться.


            Хотите обогнать что? C#-шарповскую стандартную сортировку (на парах uint, ulong)? Офигеть. Удачи. Очень вас прошу, поделиться с общественностью результатом. Чем воспользуетесь? Самописный QuickSort? Самодельный TeamSort? Или попробуете сделать CountingSort (при ширине диапазона 2^96)? А как будете реализовывать? На самом шарпе, или на C/C++, а на шарпе только обёртку сделаете?
            • +1
              Я уж и не пытаюсь говорить, что используя стандартные реализации, вы упрощаете жизнь не только себе (а в конечном счете, своим пользователям, которые получат более надежный продукт), но и тем, кому ваш код впоследствии придется поддерживать и развивать. Ведь если человек не с гор спустился, он знает, как работают стандартные контейнеры, и увидев код, их использующий, поймет, что происходит. А быть уверенным в самописных контейнерах ему вряд ли удастся, придется заглядывать в их реализации — и объем кода, который нужно понимать и поддерживать, значительно увеличится. Люди поумнее нас с вами уж устали советовать, например, «используйте стандартные алгоритмы (типа std::copy), старайтесь по минимуму строить самописные циклы» (циклы!), а мы тут с вами всерьез обсуждаем, писать ли целые велосипеды, «доверять» ли стандартной библиотеке.

              В конечном счёте, кто что пытается доказать. Я — что надо знать, надо уметь. Остальная публика так или иначе — что знать не надо. Да ради бога. У меня на собеседованиях в нормальные фирмы конкурентов меньше будет.
            • 0
              То есть, не только версия Java не важна в данном случае, не важно, что это Java. Хеш-таблица как структура данных всегда имеет определенное устройство, будь она в Java, C++, C#, Python etc.


              Сами же пишете, что «В том, что нет особой разницы, использует хеш-таблица HashMap открытое хеширование или закрытое, а TreeMap является красно-черным деревом или AVL-деревом, я с вами полностью соглашусь». И хеш-таблица, и сбалансированное дерево имеют несколько возможных реализий. И когда человеку задают прямой вопрос «как устроен класс TreeSet», ему (если он не знает точного ответа для этой библиотеки) придётся говорить что-то вроде «ну… это какое-то сбалансированное упорядоченное дерево… Может быть, красно-черное, может быть, AVL. А могли и декартово туда вставить, хотя это вряд ли...» Вы это засчитаете за ответ? Или скажете «не смог ответить на второй вопрос — значит, не программист»? И засчитает ли этот ответ тот, кто проводит собеседование?
              То же и с другими вопросами. Это вопросы не на «какие бывают реализации», а «что есть в этой библиотеке».

              А мне наоборот очень удивительно, что вас изумляет существование строгого стандарта языка, на котором пишется крайне много вещей, в том числе таких, от скорости работы которых могут зависеть человеские жизни. Разумеется сложность операций ограничена сверху!


              Я понимаю, что существует строгий стандарт языка. Я понимаю, что существует документация по библиотеке, указывающая среднюю и максимальную сложность каждой операции над своими структурами данных. Но я не понимаю, почему второе должно входить в первое. Библиотека — не часть языка. Она от языка, конечно, иногда зависит, но язык от неё — нет.

              Я вас не понимаю. То вам асимптотика не важна, то стала жутко важной константа в асимптотике. Странно

              Мне-то всё равно (а когда будет не всё равно — разберусь). Но если на интервью спросят «как растёт ArrayList?» — опять придётся угадывать?

              Лезть в документацию выяснять, есть ли в стандартной библиотеке связный список или массив? Вы вчера вечером программиравать начали? Это знать надо.

              Библиотека имеет свойство развиваться. В 2003-м я не нашел в C# библиотеке метода Array.Resize — он там появился позже, с выходом .NET 2.0 А мне и в голову не пришло искать его снова и снова, приходилось удлиннять массивы вручную. Теперь буду знать, что он есть.
              Приоритетную очередь я снова не нашел (даже в .NET 4.5). Либо она называется так, что я не могу её опознать, либо в библиотеку её опять не включили. Так что в будущем снова придётся «лезть в документацию выяснять...»
              Односвязный список с возможностью указателя «внутрь», позволяющего модифицировать список. Или хотя бы эквивалент Java-ского ListIterator. Не знаю, есть ли в библиотеке. Тоже придётся лезть в документацию проверять.

              Снова вам стала важна константа в асимтотике. Так важна вам скорость работы используемых коллекций или не важна?

              Я же написал — «создавать не буду». Так что в данном случае коллекцию трудно назвать используемой. Но здесь меня больше волнует даже не скорость, а память. Впрочем, и в скорости я предполагаю, что ArrayList(int) дал бы потерю на порядок, а это может оказаться важным.

              Вы в себе уверены больше, чем в создателях стандартной библиотеки?

              Здесь речь шла не о стандартной библиотеке, а о библиотеках, написанных «третьими лицами». И я совсем не уверен, что они будут поддерживать и развивать библиотеку столько, сколько это нужно нам. За 13 лет существования проекта мы уже несколько раз обожглись на этом. И одной из таких библиотек (которую мы пока терпим), оказался микрософтовский DirectX, у которого в какой-то момент не обнаружилось 64-битной Managed версии. Говорят, позже она появилсь, придётся ещё с этм разбраться.

              Кто же вы?

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

              Хотите обогнать что? C#-шарповскую стандартную сортировку (на парах uint, ulong)? Офигеть. Удачи.

              Спасибо. После того, как моя самописная сортировка целых чисел (на C++) обогнала std::sort (немного — на 5-15%, подробности здесь), я, по крайней мере, надеюсь на успех. Чем буду пользоваться, пока не знаю, но алгоритм наверняка будетучитывать специфику данных и их происхождение. Скорее всего, на C#, но с использованием unsafe mode.

              • +1
                Вы это засчитаете за ответ? Или скажете «не смог ответить на второй вопрос — значит, не программист»? И засчитает ли этот ответ тот, кто проводит собеседование?


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

                Но если на интервью спросят «как растёт ArrayList?» — опять придётся угадывать?


                Я б не стал угадывать. Сказал бы что-нибудь в духе «Мультипликативно. Что обеспечивает константную амортизированную сложность операции добавления элемента в конец „списка“.» (бросаться это доказывать, разумеется, не стал бы. Не поймут. В смысле не оценят). Спросят, какой именно коэффициент используется (не спросят ведь), скажу, что это не имеет особого значения, но чаще всего выбирают ил