Как стать автором
Обновить

Комментарии 275

Кандидат: Можно использовать HashMap и считать каждый элемент массива. Как только попадётся элемент, который встречается больше одного раза, это и будет наш ответ.

О, уже лучше. Мы нашли решение O(N), но всё равно слишком тривиальное. В идеале кандидат должен с него и начать.

Можно поподробней, например в С расписать, чтобы сложность оценить.

Оно же без разницы на каком языке оценивать, итого в машинных кодах

Для таких вещей есть псевдокод. Если писать на определенном языке, будет сложно тем, кто на нём постоянно не работает

Простое решение на C++ с памятью и временем O(N).

unsigned f(const vector<unsigned>& vi) {
    vector<bool> vb(vi.size(), false);
    for(unsigned i = 0; i < vi.size(); ++i) {
        if(vb[vi[i] - 1] == true)
            return vi[i];
        vb[vi[i] - 1] = true;
    }
    return 0;
}

Кажется HashMap там в тексте лишний.

Вот Вы тоже без него обошлись. Ну или можно считать, что тут вырожденный случай и HashMap от n равно n , но он есть.

Зачем в последнем случае так сложно? У нас есть арифметическая прогрессия и одно дополнительное повторяющееся число. Считаем сумму прогрессии по формуле, отнимаем её от суммы всех элементов, решение в одну строчку

А если не одно?

Это условие задачи в последнем варианте, я говорю только про него

Да, я не прав, три раза - это тоже "повторяется"
Первое моё сообщение уже не могу редактировать

Меня тоже это немного спутало.

Сначала Аня пишет: "элементы в диапазоне [1,N]", а потом: "уникальных элементов в нем только N".

Посмотрел источник, про уникальность там ничего нет.

Короче, корявый перевод - причина всех недопониманий.

Если одно число в массиве A повторяется один раз, то можно решить так

X=1^2^3^...^N^A[0]^A[1]^...^A[N]

x=a[0]+a[1]+...+a[N]-(N+1)/2*N
так не проще?

так не проще?

У вас в одной строчке аж две ошибки:


  1. Это не будет работать для чётных N. Потому что приоритет операций. Правильно: (N+1) * N / 2.


  2. Это в общем случае не будет работать из-за переполнения типов при умножении.



Видимо, не проще.

  1. математически это одно и тоже. Я писал формулу в более наглядном виде, когда становится очевидно что мы ищем среднее значение элемента и умножаем на количество элементов. в ваей записи смысл найти не так просто. и см. п2.

  2. Чтобы говорить о переполнении типов эти типы должны быть. Я так понимаю речь же про псевдокод?

Эту задачу люди взяли с литкода я так подумал. Пошел искать её там, и она действительно там есть. Пришёл к такому же решению как и вы, через разницу суммы всех элементов от арифм. прогрессии. Только вот в условиях задачи явно не обозначили (либо я невнимательный такой), но элемент может повторяться не один раз. Моё решение завалилось на кейсе [2,2,2,2,2].

Чем эта задача "лучшая"? И что значит лучшая? Что она проверяет? Где корреляция между хорошим и плохим кандидатом и умением ее решать?

Добавлю, раз кандидаты задают уточняющие вопросы, задача поставлена не верно.

Но это же хорошо! Когда это программистам доставались "верно поставленные задачи"?

На собеседованиях?

В реальной жизни. Так что проверить навык уточнения задач – дело полезное. А то порой приходится наблюдать две крайности: человек либо додумывает неполное условие каким-то своим непредсказуемым образом, либо начинает задавать огромное количество вопросов по несущественным деталям.

А кому нужны кандидаты которые только с "верно поставленными задачами" работать способны?

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

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

В реальности же тоже хорошо если программист решает именно поставленную задачу, или нет? Плохо если он сделал меньше (т.е. не выполнил ТЗ). И плохо если он сделал больше. Больше значит дольше, а дольше значит дороже.

Конечно же это не хорошо. Если он решает поставленную задачу не уточняя ничего и потом споря о том, что он сделал как написано, а не так как надо, то ничего хорошего в этом нет.

Хорошие экзаменаторы спокойно относятся к уточняющим вопросам. Их ответ всегда неизменен - в условиях задачи это не указано.

Молодой человек, видимо не проводящий сам собеседования. В этих вопросах и есть самая соль. Я часто задаю что-то что человек ЗАВЕДОМО не знает из серии "у нас была такая-то проблема и мы умудрились ее решить, проломав всем коллективом голову месяц, можете сейчас за 10 минут каким-то образом предложить решение?" и смотрю только на вопросы и на направление мыслей. Умение в таких ситуациях отбрасывать из головы лишнее, сосредотачиваться на проблемах и ограничениях, умение задать точный и действительно что-то значащий для выводов вопрос и при этом не терять присутствия духа - это и есть тот кандидат, который мне предпочтительней того, у кого этих качеств нет, даже если он более хард-скилловый в данный момент времени. Потому что хардскиллы нарабатываются со временем, а вот эта общая способность размышлять, коммуницировать и справляться со стрессом - нет

Готов ответит на вопрос "что она проверяет?". Она проверяет способность кандидата быть внимательным и знание о том, что такое целые числа.

В дано было ясно сказано, что даны "целые числа" (слово "положительные" не использовалось) и диапазон [1, N]. Возьмём пример, N = -100, диапазон [1, -100]. Соответственно, на середине собеседования вариант с заменой знака числа отваливаются.

А ещё указан размер массива, равный N+1, который исключает возможность N < -1. Причём при N < 2 ситуация вырожденная (пустой массив, массив из одного элемента и массив [1, 1] соответственно) - следовательно, при решении общего случая их можно не рассматривать.

На выходе получаем специалиста, который отлично сортирует массивы, понимает в сложности и т.д. А потом ему приходится с 9 до 18 перегонять XML-ки...

Зато он гоняет их со знанием алгоритмов

НЛО прилетело и опубликовало эту надпись здесь

Зато он гоняет их со знанием алгоритмов

И пониманием этих самых O(N log N)!

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

Ну наверное на собеседовании не один такой вопрос используется. К тому же опять какие-то "оба знают алгоритмы, как выбрать". А я Вам скажу как - HR спросит у тимлида - кто тебе в целом больше понравился, с кем работать готов? - а тут не может уже быть совсем двух равных кандидатов

Ну раз у вас такие сложные задачи, стоит пересмотреть мои требования к ЗП. Особенно стоит - если "вы уменьшились и находитесь в миксере". За риск на рабочем месте.

всего до 18? некоторым приходится это делать до 22, иногда даже с JSON по середине.

>>Кандидат: А там точно будут повторяющиеся числа?

>>Это плохой уточняющий вопрос, ведь мы уже знаем, что размер массива N+1, а уникальных элементов в нем только N

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

это значит, что человек идет уточнять постановку задачи даже не потратив 1 минуту на ее осмысление

Если в в одном месте требований говорится что в кластере 5 серверов, а на другой странице указывается что данные обрабатываются в 6 потоков, то опытный инженер должен:


  • Начать прикидывать какому серверу попадётся двойная нагрузка, ибо Дирихле и всё такое прочее
  • Переспросить заказчика, потому как техзадание нередко пишется по частям, разными людьми и в разное время?

зачем прикидывать? надо реализовывать начинать - всякие нюансы на этапе сдачи проекта выяснятся

А что делать, если просят за 2 взвешивания найти фальшивую монету из 9?

Уточните, чем фальшивая монета отличается от других? Вдруг цветом.
А известно сколько там фальшивых, или достаточно найти любую из фальшивых?
А на чём можно взвешивать?

А неважно чем отличается. Главное, что информации недостаточно, Log2(9) > 2, потому решить не удастся.

Нужен еще хотя бы 1 бит информации, например, знание, что фальшивых ровно 1 штука

Если знать, легче ли фальшивая монета, то как раз все хватает, ведь вариантов исхода одного взвешивания три: левая часть легче, правая часть легче, части равны по весу. 3*3 = 9 — теоретически достаточно информации от двух взвешиваний для нахождения одной из 9 монет.

Знание, легче ли она всех остальных, это и есть недостающий бит информации.

Обычно в формулировке это всё сказано.

Кстати, если неизвестно, легче или тяжелее фальшивая монета, то за n взвешиваний можно найти фальшивую среди (3^n - 1)/2 монет, но нужна вспомогательная настоящая. При условии, что фальшивая только одна, конечно.

Я как раз привел пример, когда человек, не понимающий задачу, дает неправильное условие

Log2(9) > 2, потому решить не удастся

Нужен еще хотя бы 1 бит информации

О, да вы математик! А скажите ещё что-то по математически ;) А можно немного более развернуто? Log2(9) , няп, потому что при взвешивании на чашечных весах выборка делится на 2. Но решается задача только если мы знаем что фальшивая монета легче и она ровно одна - тогда можно делить на 3. Многовато для 1 битаинформации.

Количество микросостояний, реализующих данное макросостояние, иначе говоря, энтропия в битах

А неважно чем отличается. Главное, что информации недостаточно, Log2(9) > 2, потому решить не удастся.
В этой задаче каждое взвешивание даёт более 1 бита информации, т.к. возможно 3 исхода: левая чашка тяжелее, правая тяжелее, чашки равновесны. Так что задача решаема.

Так как мы не знаем, тяжелее она или легче, нам эта информация бесполезна

Замечание в том, что формула
Log2(9) > 2
составлена по каким-то домыслам, и вывод из неё ошибочен.

Знание, легче ли она всех остальных, это и есть недостающий бит информации.
По формуле выходит, что для случая 27 монет, 4 взвешишаний недостаточно (log2(27) > 4), но якобы «добавляя 1 бит информации» о весе фальшивой монеты, уже достаточно?

Вы же информацию добавляете к каждому взвешиванию

Нет. Знание, что фальшивая монета легче — это 1 факт, а не столько фактов, сколько взвешиваний.
например, знание, что фальшивых ровно 1 штука
Если в задаче не сказано сколько монет фальшивые, и при этом не указано в какую сторону они отличаются, то в общем случае у задачи решения вообще нет. Вот вам дали n монет, из них от 1 до n-1 фальшивых (как-то отличаются по весу), найдите их. Вам недостаточно только взвешиваний, вы сможете лишь разделить монеты на две категории (или сказать, что все одинаковые, если фальшивых может быть от 0 до n), но всё равно не узнаете, где настоящие. Предельный пример: 2 монеты. Вы из условия знаете что ровно одна из них фальшивая (0<Ф<2), а дальше что?

Задач на взвешивание не так и много. Просто запомнить ;)

Решение настоящего инженера! А чтобы не запоминать - посмотреть в Справочнике задач на взвешивание)

А какие полезные свойства кандидата показывает умение решить подобные задачи? Какая реальная задача может свестись к задаче с 9 монетами? Дубликаты в массиве это хоть немного напоминает валидацию входных данных ;)

Тешит самолюбие интервьюера, прочитавшего эту задачку перед собеседованием

Вопрос не то чтобы плохой, скорее он симптоматичный. Но надо понять симптом "чего" - не понимания постановки? просто невнимательности? переусложнения?.

Я бы ответил на такой вопрос "поясните, не совсем понял, мне казалось в задаче все прозрачно, может я чего-то не замечаю?"

Далее варианты такие
1. человек вчитывается и говорит "а тут N+1, а числа тоже 1..N", ок тут точно хотя бы 1 повтор - это мелкий залет совсем, такой на тему "резиновой уточки"
2. человек говорит "тут может быть ловушка с типами данных, например равен ли float64(2.0) числу int32(2), потому что хотя с точки зрения математики - это все еще целые числа, для кода это все же нечто различное" - я бы понял, что этот вопрос результат некоторого избыточного усложнения, с другой стороны ничего некорректного в этом нет. Я бы сказал в ответ, что тип не имеет значения, важна только "чистая математическая сторона" int(2)==float64(2.0) - это я не буду считать залетом
3. человек просто перечитывает задачу и говорит - "ну тут вообще нет никакой информации - есть там повторы или нет" - залет - просто не умеет читать условия в абстрактном представлении с - N там, множествами и прочим - признак конкретного мышления или очень и очень неподвижного мышления

То есть меня устроит вариант - что он просто понял, что там есть повторы или вариант 2 с каким-то усложенением, меня не особо напряжет вариант 1 и очень напряжет вариант 3.

Если автор рассматривал этот вопрос только как вариант 3 - то кончено это очень плохой вопрос.

На этом этапе большинство кандидатов сдаётся

Это не сдаются, это понимают, что
1) интервьюер - самовлюбленный чудак на букву м, выучивший перед интервью 30 вариаций одной и той же задачи плюс решения к ней, и сейчас с наслаждением наблюдающий, что "глупенький кандидатишка" этих решений сходу не называет
2) в команде с таким человеком и в компании, ставящей таких людей проводить интервью, они работать не хотят

А самое весёлое, когда ждут какое-то одно решение, получают другое и потом не могут его понять. И вообще, вот это постоянное усложнение задачи раз за разом выглядит как издевательство. Ты решил, но сейчас усложним и так будет до тех пор, пока не сдашься. Причём последние вариации часто совсем синтетические и в реальной жизни вряд ли встретятся.

Например, мне как-то раз дали задачу с N+1 числом, и в нём хотя бы по одному есть каждое число от 1 до N. Я беру и говорю - сумма чисел от 1 до N - (N+1)*N / 2 можно просуммировать и легко найти "лишнее число". Но ревьюверу это решение не понравилось, он захотел поломать мой план и сказал, что в массиве N+2 элементов. Я в ответ предложил посчитать не только сумму чисел, а ещё сумму квадратов чисел. Тут поломался уже ревьювер, которому я потом кучу времени объяснял, как это работает, а он буквально в упор не мог понять очевидных вещей.

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

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

А какой ответ ожидал ревьювер?

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

при том, что действительно толковых усложнений или технически тонких крайних случаев не было рассмотрено.

к примеру, что если N = +Infinity? или N не менее 1е12, а сам массив размазан по M веб сервисам, с несуществующим апи, но заказчик готов выкатить любой, только сформулируйте требования ...

Больше скажу. Выучил задачу и решение, а потом представил себя с этими знаниями, как он классно отвечает за кандидата

А мне лично только с такими и нравится работать действительно по-настоящему, кто видит глубину в работе и что есть всегда не один только какой-то очевидный вариант.

Последнее решение не сработает, если массив не является связным списком. Простейший пример: [0, 1, 1]. Функция выдаст ответ 0, верный ответ — 1.

0 нельзя по условию задачи

Блин, точно.

Все еще [2,1,3,3] работает как контрпример

Вот тоже на этом споткнулся и не понял почему последнее решение стало решением.

Я бы сказал, задачка интересная, но для собеседования подходит крайне плохо. Много этапов вида "додумается/не додумается", но при этом ни то, ни другое не даёт вам достаточно информации о кандидате. Лучше уж дать задачку, которую мало-мальски вменяемый кандидат точно решит приемлемым образом, и пообсуждать с ним всякие модификации задачи.

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

Подход автора статьи: "а что это у меня в кармане?". Это такой тип задач, которые автор сам когда-то там упорно шлифовал, что оно у него отпечаталась в голове (или на другом каком месте тела). И теперь этот кто-то стал загадывать это другим...

Шел <current year>, конторы продолжают собеседовать будто они жюри в олимпиаде по программированию.

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

Я бы взял того, кто сказал бы: сделаю N проходов наивно, а если можно взять N памяти, то два прохода. А вот если это конкретная задача - давайте сядем, обсудим детали.

...для собеседования на должность сферического-программиста-в-вакууме. ))

А если кандидат сразу нашел все решения просто потому, что решал эту задачу ранее, это все еще хорошая задача или нет? И какую полезную информацию это несет компании?

НЛО прилетело и опубликовало эту надпись здесь

...веб-дизайнера...

Обычная задача на проверку насколько кандидат напрактиковался в решении таких задач.

Для собеседования лучше вообще ее не использовать, либо остановится после hashMap.

Задача красивая, но, имхо, не для собесов - слишком творческая, хороший кандидат может не догадаться (особенно в "напряженной" обстановке собеса, где кажется, что время улетает со сверхзвуковой скоростью).

И разумеется, ничто не ново на хабре: https://habr.com/ru/company/JetBrains-education/blog/235855/

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

Ожидал увидеть что-то на топологию - типа такого
видеть что
видеть что

Меня на одном собеседовании попросили развернуть генеалогическое дерево по поколениям.

Я, незадолго до этого переиграв в Crusader Kings, решил задачу с учётом возможного "ромбовидного наследования"...

А как обрабатывается ситуация, когда человек приходится сам себе дедушкой?

НЛО прилетело и опубликовало эту надпись здесь
Боюсь, что мужики и проститутка не переживут этой процедуры.
Презервативы — тоже…

Если задача на 2М2Ж, то да (см ниже).

Прикольно. Особенно решение.

Все просто. Первый мужик надевает сразу два презерватива, имеет секс первой женщиной, снимает, затем со второй. Второй мужик надевает внешний презерватив от первого мужика, имеет секс с первой Ж, затем надевает сверху второй П и имеет секс со второй.

Мне перезвонят?

Так ведь в задаче расклад 3М1Ж, а не 2М2Ж...

Плохо прочитал. Я решал эту задачу с 2М2Ж, над 3М1Ж нужно подумать. Но первый шаг однозначно такой.

Там один презик надо будет вывернуть наизнанку. Итого, первый надевает А и поверх него В, второй надевает В, третий надевает вывернутый А и поверх него В.

Отличная задача, по ответу сразу видно кто перед нами:


  • Олимпиадник — Задача решается элементарно, если помнить, что презервативы можно надевать по два и выворачивать наизнанку
  • Cloud Architect — Ребят, чем трахаться с хитрыми алгоритмами, лучше добавить чуть денег и закупить больше ресурсов. Сразу планируем минимум по две проститутки в каждом датацентре, плюс резервные в других регионах — мне же потом спасибо скажете, когда вас в командировку пошлют.
  • Поклонник GoF и прочих шаблонов — Держите меня семеро, сейчас я всем покажу, как правильно писать EnterpriseSolutionCondomProviderStrategyFactory!
  • Питонист — pip install more_condoms

Старый циничный сеньор: "Это вы так описали типичный расклад сил на проекте? Один разработчик, два менеджера, три заказчика?"

  • Охранник на проходной ЦОД — один наденет презик и она сделает ему минет, а двум другим просто подрочит

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

Есть такая-же задача про трех хирургов, пациента и две пары перчаток.

Первый мужик надевает два презерватива. Второй надевает один, тот, который был «внешним» на первом мужике. Третий надевает опять два презерватива, при этом выворачивает тот, что был «внутренним» на первом мужике, наизнанку.

М1->Г1&Г2->П
М2->Г2->П
М3->! Г1->М1

Третий шаг - опечатка или характеристика участников?

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

Более того, вся эта О-нотация отвечает на вопрос «какой из алгоритмов будет работать быстрее в пределе», то есть если мы будем повышать N до бесконечности. То, что NlogN может иметь, например, константный множитель хоть в полмиллиарда (и тем самым быть медленнее условного 3 N^2 на подавляющем количестве реальных случаев) почему-то любят забывать.

Конечно, надо оценивать, какое там у вас будет N. Но за очень редким исключением, если у вас N хотя бы 100, O(n log n) будет на порядки быстрее O(n^2). Вот между O(n log n) и O(n) уже разница размывается, да.

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

Плюс, если размер массива больше кэша процессора (а оптимизировать по памяти имеет смысл для сильно больших массивов), конструкция:
fast = arr[arr[fast]];
приведет к постоянным промахам и гарантировано сделает производительности больно.

Есть вариант, где нет этой проблемы?
Подсчёт «в лоб»
counts[arr[i]]++
ещё хуже, потому что запись генерирует лишний трафик при вытеснении изменившейся линии из кеша.

Можно организовать массив в виде хэш-таблицы, где число бакетов равно числу кэш-линий минус одна. В итоге у нас получается одна очередь линейного чтения и N-1 очередей линейной записи. Дальше обрабатываем бакеты по очереди. Если бакет целиком влезает в кэш, то используем наивный алгоритм. Если не влазит, то дробим дальше. Правда, такой алгоритм будет плохо работать, если один и тот же элемент будет повторяться очень много раз.

Допустим, у нас M=4096 (N уже занято в условии задачи) бакетов, по числу кеш-линий. Как я понимаю, индекс бакета — хеш от очередного X=arr[i], и в каждом бакете надо организовать список пар (X,C), где C — количество найденных повторов числа X (либо только список иксов, если нужен только факт повтора, а количество не важно).

Размер бакета = размеру кеш-линии = 64 байта. То есть, в бакет поместится 4 (если со счётчиком C) или 8 значений. Бакеты будут очень часто переполнятся, что в этом случае надо делать? Надо мержить бакет из кеша с бакетом в основной RAM. А это или сортировка, или ещё какой алгоритм, который нам скушает кеш-линии, занятые другими бакетами. Ведь бакеты не будут наполнятся одновременно. Надо либо опустошать только переполненный (и использовать кеш-линии других бакетов, что ставит всю идею под вопрос), либо скидывать вообще все 4096, если заполнился хотя бы один, что может быть очень неэффективно.

Очень сомнительно, что будет выигрыш.

Сорри, накосячил в плане терминологии. Понятие "число кэш-линий" стоит читать как "cache associativity". Короче, моя идея сводится к тому, что благодаря ассоциативности кэша мы можем одновременно читать и писать несколько потоков данных. По каком принципу формировать эти потоки данных, значения не имеет. Важно, чтобы одинаковые числа попадали в один поток.

Я всё равно не понимаю решения целиком. Допустим, мы поделили данные на M потоков по какому-то хешу и выполнили запись. Дальше что делать с этими записанными линейками? Есть алгоритм, который тоже будет обрабатывать их линейно, а не скакать рандомно между ними? Вырисовывается некий mergesort, со сложностью N*logN и довольно большой константой, выполняющий многократные прохождения по отрезкам (сначала данные многократно режем на куски, потом сливаем, потом делаем финальный проход и определяем дубликат).
Дальше что делать с этими записанными линейками?

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


Вырисовывается некий mergesort

Типа того, да. Вот только, во-первых, сливать данные не нужно. А во-вторых, всё зависит от объёма данных и технических характеристик железа.


Если константа у алгоритма O(N) из-за случайного доступа больше, чем у O(N log N), где log N — это совсем небольшое значение (2-3), то алгоритм с O(N log N) будет быстрее. А если массив ещё в память не влезает, то выбор однозначно становится в пользу последнего.

То что хуже совсем не очевидно, надо мерить. У этого load-store нет прямых зависимостей поэтому может не плохо лечь на типичное OoO.

Как это нет зависимостей? Пока не закончено чтение arr[i], невозможно начать инкремент ячейки в counts.

Для OoO это практически эквивалентное "нет зависимостей", самое паршивое это когда инструкции сцеплены друг за другом, когда результат одной является аргументом другой и так по всей цепочки. (проблема критического пути в графе исполнения инструкций) А вот такие относительно независимые куски, должны колбаситься на ура.

Так они и сцеплены
counts[arr[i]]++;
        mov     rdx, QWORD PTR arr[rax*8]
        add     QWORD PTR counts[rdx*8], 1

Они сцеплены но их две, а не 200. Собственно я об этом и говорил. Все эти небольшие сцепленные цепочки будут в OoO выполняться практически "параллельно", скрывая latency.

А, вот в чём идея — развернуть этот цикл. Кстати, от gcc не получилось добиться векторизации этого цикла. Наверное, он не может доказать, что массивы arr и counts не пересекаются.

Не, я скорее про то, что оно само разворачивается "внутри процессора" за счет спекулятивности и OoO(out-of-order execution). Инструкции не исполняются последовательно уже со времен Pentium 2/3.

На размерах, где оптимизация реально нужна (N > 1e9), каждая итерация — гарантированный cache miss, +200 cycles, и там уже не до OoO.

OoO как раз в таких случаях и помогает больше всего. Размер rename файла у современных процессоров в районе ~200, то есть это то сколько зависимостей может быть одновременно "в воздухе".

Ради науки, провел эксперимент для 2^30 элементов, дает 22 такта на элемент массива(на zen 3, при ram latency в районе 200 тактов) :

g++ ./main.cpp -O3 -o main

./main 1073741824

Array size: 1073741824
Rand max: 2147483647
Processor cycles: 24337217340, per array element: 22.665800

https://gist.github.com/xmvlad/f5b9a13fa56007d215343cb3ca2c104a

Необъяснимо. Допустим, в процессоре действительно параллельно работает до 200 итераций и каждая итерация ждёт свои данные. Но каналов доступа в RAM не 200 же.

Каналы влияют на пропускную способность, которая как раз обьяснимая, где то в 5 раз меньше пиковой. А в load и store юнитах есть очередь, именно ее глубина и определяет количество возможных одновременных запросов "в полете", она тоже гдето в районе 40 на каждый юнит.

Допустим, 1 запрос к памяти 200 тактов, а каналов предположим 4, мы не сможем читать в среднем быстрее, чем 1 чтение за 50 тактов, независимо от глубины очереди.

С чего бы? ) 200 это latency, а throughput то лучше, а количество одновременных запросов и количество каналов, вещь не взаимосвязанная, о чем я вам уже писал. Немного наврал в подсчетах максимальной производительности, тест прогонялся за 7 секунд, что дает в пике для DDR4-2600 147 ГБ на тест. Единичный burst для DDR4 насколько я понимаю это 64 байта, чтобы давать в пике 21GB/s, надо уметь колбасить 352M запросов в секунду. За время теста(7 секунд) максимум 2.4G запросов, при количестве элементов 1G. Так что все вполне сходится.

Требования к константности памяти на практике бывают или в микроконтроллере, или если данных очень много.

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

По-моему подобная алгоритмическая 'дичь' (и эта еще довольно простая) проверяет скорее нервы кандидата, чем его опыт. Имхо, я бы такое дал разьве что джуну решать или человеку идущему на должность, где он будет много таким заниматься или схожим (найм кандидатов, криптография и тп), но точно не рядовому сеньору, задача которого пилить фичи в срок и 'перекладывать json'ы' без рисков сломать всю систему… Это что-то на уровне «сделайте нам не оплачиваемое тестовое на 10 часов работы». Мне лично об уровне кандидата становится все понятно по его ответам на общие вопросы, кругозору по технологиям, профильным технологиям вглубь, его опыте, сложных решениях которые он делал, на эти вопросы книжечки «как пройти собеседование в гугл» ответов липовому разработчику не дадут. Через 30-40 минут, понимаешь точно каков опыт человека, потом еще обсуждаете профессиональные темы и решения которые кандидат может предложить для решения проблем, которые ему предлагают (возможно даже реальных проблем в компании). Это гораздо лучше и ближе к реальной работе, чем спрашивать то, что человек использует разьве что на собеседованиях… Ей богу… А то потом смотрим на «прекрасно» работающие сервисы от гугла, яндекса и тп «мега крутых компаний, состоящих из инженеров-алгоритмистов», и невольно возникают вопросы. Я лучше возьму на работу чудилу-самоучку, который может много рассказать о разных технологиях и понимает сильные и слабые стороны разных инструментов, чем любителя методичек по прохождению собеседований и нарешиванию 100500 заданий с литкода… Но это все конечно субъективно, так что на вкус и цвет, я вот так думаю

Эта дичь стала своего рода этикетом. Который как ни странно не имеет никакого отношения к реальности. Почему? Мы бы не получили настолько тормозной веб если бы фреймворки писали реальные короли алгоритмов. Более того — те самые индусы (типа автора), которые лезут в менеджмент не прочь и дальше плодить штаты эффективных программистов, которые будут распускать в сложные времена.


engineering at Instagram Facebook

Тут я конечно проиграл вспомнив их тормозной React

Это набор вопросов на вакансию «специалист по алгоритмам», а не просто «программист».

Интервьюер: Можно решить эту задачу, не используя лишнее пространство?

Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.

Интервьюер: Тогда временная сложность вырастет до O(NLogN). Что ещё можно сделать?

Разве есть алгоритмы сортировки, которые требуют O(N*log(N)) времени и меньше O(log(N)) памяти?

Интервьюер: Ещё один вопрос.

Если у вас в команде будет 4 "эффективных менеджера" - как увеличится сложность?

где вот эта привязка к реальной жизни? :)

Если у вас в команде будет 4 «эффективных менеджера» — как увеличится сложность?

Экспоненциально?

Мне кажется, что интервьюер ошибается или намеренно вводит в заблуждение.
По условиям: "массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N]. "

И тут же интервьюер говорит:

Кандидат: Только одно число повторяется?

Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].

Если даны элементы в диапазоне [1, N], то при размере массива N + 1, будет повторяться только 1 элемент. Так что пример [4, 3, 3, 1, 1, 2] некорректен, т.к. повторяются два элемента.

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

"Элементы в диапазоне [1, N]" - не обязательно значит "все элементы диапазона". В последнем примере, все элементы содержатся в диапазоне [1, 5], длина массива 6 - под условие подходит.

В последнем примере все элементы содержатся в диапазоне [1, 4] (квадратные скобки — включающие). Корректным примером был бы массив [5, 3, 3, 1, 1, 2].

А что, диапазон [1,4] не входит в диапазон [1,5] ?

А ещё он входит в диапазон (-∞, +∞), как и все другие числовые отрезки. Давайте теперь только этим диапазоном пользоваться во всех случаях. Например, указывая вилку зарплат в вакансии или время варки макарон в инструкции.

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

PS Подойдите к любому человеку и попросите сказать, в каком диапазоне лежат элементы массива [4, 3, 3, 1, 1, 2]. Полагаю, что вероятность ответа «от 1 до 4» будет гораздо выше, чем «от 1 до 5».

Если на пачке носков написано "желтые" — это не означает, что в пачке есть носки всех цветов, классифицируемых как оттенки желтого. Если говорят, что в компании работают китайцы — это не значит, что в компании работает всё население КНР. Призыву на срочную службу подлежат граждане от 18 до 27 лет (или уже до 30?), но это не значит, что каждая партия новобранцев содержит как минимум одного человека на каждый возраст.


Подойдите к любому человеку и попросите сказать, в каком диапазоне лежат элементы массива [4, 3, 3, 1, 1, 2]

Подмена тезиса, минус социальный рейтинг. Любой человек не в курсе условий исходной задачи, а кандидат — в курсе. Если я покупаю мешок конфет, на котором написано "ассорти" — это значит, что комбинация внутри может быть разной. Ваш вопрос будет аналогом того, что я возьму из этого пакета "Мишку косолапого", покажу его прохожему и спрошу, пачку каких конфет я купил.

Ваш вопрос будет аналогом того, что я возьму из этого пакета "Мишку косолапого", покажу его прохожему и спрошу, пачку каких конфет я купил.

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

Почему же не будет-то?

Да это, собственно, автор поста написал:

Это решение не сработает, если повторяться может несколько чисел.

Наличие пропусков означает либо повтор одного числа более 2 раз, либо повтор нескольких разных чисел.

У автора там скопипасшено откуда-то криво. Это решение отлично работает даже если повторяется несколько чисел (находит какое-то одно повторение, да, но в условии как раз надо найти любое).

Прогнал полный перебор всех вариантов для массивов из 9 и 10 элементов, каких-либо проблем не произошло. Так что согласен, решение, судя по всему, работает без проблем для любого такого массива. Правда, мнение о статье у меня от этого не улучшилось.

Тут не надо полного перебора. Решение доказывается логически. В массиве числа от 1 до N. Мы начинаем с индекса 0 и сможем до бесконечности переходить к индексам, записанным на текущей позиции. Но различных положений всего N (кроме шага в начале, где мы на индексе 0). Значит рано или поздно мы зациклимся — придем в ранее посещенную позицию. Но мы в эту позицию первый раз пришли из 0. А потом ни разу 0 не посетив, поэтому мы второй раз прошли по другому пути. Пути детерминированны, а значит в эту позицию ведут 2 разных пути, т.е. в нее входят две стрелочки, т.е. это число записано в двух разных позициях в массиве — мы нашли повторение. Нигде тут не требуется, чтобы были все числа или чтобы повторялось только одно. Надо только, чтобы в массиве были числа не больше N и не меньше 1, чтобы переход можно было сделать всегда.

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

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

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

Интервьювер: надо отсортировать массив из N чисел.

Кандидат: какие ограничения на N и на значения сортируемых чисел?

Интервьювер: N помещается в UInt16, числа помещаются в Int32.

Кандидат: дайте пример входа

… и теперь что, нужно давать пример из 65535 чисел, обязательно включающий 0x7FFFFFFF и -0x80000000? Или, вы считаете, задача так поставлена, что ей невозможно дать пример входных данных, помещающийся на одном листе бумаги?

Я считаю, что тип и диапазон — схожие, но всё же разные вещи. Я сомневаюсь, что кто-то может неправильно понять ваше утверждение, но не сомневаюсь, что приведённое в посте утверждение вкупе с приведёнными там же примерами можно понять неправильно. Даже тут, в комментариях, есть как минимум два человека, которые неверно поняли условия задачи. При этом задача была записана, а они, скорее всего, находились в спокойной обстановке, а не на интервью в условиях стресса (и возможно, усталости, если вопрос не первый).

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

Я считаю, что тип и диапазон — схожие, но всё же разные вещи
Типичные формулировки задач, что в спортивном программировании, что в реальной жизни: 1 <= N <= 10000
Чем не диапазон? Тут решение о выборе подходящего типа остается за кандидатом.

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

Так у вас претензии не полному тестовому набору, а к поясняющему примеру в условии задачи. Там обычно до границ не доходят.

Не сразу смог понять что такое "пространственную сложность".

Мне вот нравится просить спроектировать виджет скорости скачивания файла. Как-то задали такую задачку в варгейминге лет 5 назад

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

еще и по сетям слегка пройтись можно

Эх, хорошо тогда пообщались

А можете немного подробнее рассказать, как стоит рассуждать при решении такой задачи? Как в принципе стоит декомпозировать эту задачу?

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

Буду рад, если дадите ёмкое пояснение. Спасибо.

Для начала я обычно даю шаблон интерфейса, с оговоркой что его можно менять

class CurDownloadSpeed {
    void addData();
    void getCurrentSpeed();
}

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

class CurDownloadSpeed {
public:
    void addData(size_t bytes);
    size_t getCurrentSpeed();
}

Далее мы обсуждаем контекст - сколько потоков скачивают данные, сколько отвечают за отображение, что для нас более критично - отображать правильные данные или скачивать быстрее
В ходе этого я объясняю что у нас несколько воркеров, которые скачивают файл в несколько потоков (ну, нравится нам так) и один поток который дергается из условного UI для отображения

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

class CurDownloadSpeed {
size_t startTimeMs;
size_t dowloaded;
 public:
    void addData(size_t bytes) {
        if (startTime == 0) startTime = getCurTimeMs();
        downloaded += bytes;
    }
    size_t getCurrentSpeed() {
       return downloaded / (getCurTimeMs() - startTimeMs);
    }
}

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

  • реализация getCurTimeMs() - написана она ручками или мы решили "замокать" эту функцию?

  • branch prediction - насколько хорошо ставить в if условие, которое выполнится единожды?

  • переполнение size_t

  • деление на 0

  • неинициализированные переменные

  • приведение типов

  • размерность startTimeMs

После того как обо всем поговорили, можно переходить от "средней скорости" к "текущей".
Худо-бедно соглашаемся о том, что "текущая скорость" - это скорость за последние, скажем, 10 секунд
Как это сделать?
Самый простой способ - при добавлении данных хранить их в паре (ts, value)
Если данные добавляются часто (с частотой в микросекунду) мы получим огромный массив, который можно будет очищать при вызове getCurrentSpeed

Линейная сложность на вставку, линейная на чтение - еще и с блокированием вставки. Не очень приятненько.

Обновляем код, делая линию на вставке и константу на чтение - при каждом добавлении обновляем curSpeed (вычитаем старые из результата, добавляем новые. Сами данные храним в векторе). Тут уже пора вспоминать о потокобезопасности (на самом деле и раньше было "пора", но не так интересно)

Теперь у нас все хорошо со временем работы, но линейная память в зависимости от количества вставок (чтобы правильно очищать старое при добавлении нового). А нужно ли нам хранить все данные? С точки зрения UI пользователю побоку в какую микросекунду произошло обновление, так что в качестве единицы измерения времени можно взять секунду, и все байты в рамках одной секунды класть в 1 корзинку. Получается константа по памяти (60 корзинок по 1 секунде)

Ну и в конце просим перестать бесконечно аллоцировать память в векторе, реализовав циклический буффер, а заодно поговорив про модель памяти (почему постоянные аллокации - это плохо)

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

хорошее решение и без циклического буфера

там был связный список с переиспользованием элементов?

Вполне возможно, по сложностям с ним получается то же самое - а реализовать куда проще

Но тогда нужно обсуждать + и - связанного списка относительно вектора

Большое спасибо, теперь стало намного яснее, что вы имели в виду в предыдущем комментарии.

Ну и термины вы используете. Как будто специально шифруете все от кандидата.
Пространственная сложность = сложность по памяти.
Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне.

«Если количество получилось больше»: не «количество» -> сумма. А «чисел в этом диапазоне» -> как раз это количество. По аналогии с подобными выражениями sql.
«Space complexity» — англоязычный термин. Хорошо, хоть не перевели как «космическая сложность».
Пожалуй, можно выполнить бинарный поиск повторяющегося числа. Например, можно пройтись по списку и посчитать число целых чисел от 1 до N/2. Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне.

Откуда тут «число ЦЕЛЫХ чисел»? разве тут есть с дробные/с плавающей запятой? Может имелось ввиду «положительных»? Но и это неверно. В исходном списке все числа целые и положительные, вы ввели невозможность менять список и невозможность использовать доппространство => списка с отрицательными никогда не появится.
Имхо, на этой части интервьювер сломался.
Вообще, беда всех таких задач — их малонужность в реальной жизни (т.е. наверно есть единичные компании, где такое надо часто и там оправдан отбор. Но вот остальным 99,99% это не надо). Поэтому я все больше склоняюсь предлагать работодателям любителям поиграть в решение таких задач:
давайте я ее решу, но впишем в договор, что если подобной задачи не будет каждый квартал, то компания платит штраф 1 млн за то, что не смогла обеспечить работой, о которой говорила на собеседовании.

Почему-то мне кажется, что на этом месте сразу выяснится, что эта задача не такая уж и нужная.

Интервьюер: Хорошо, переформулируем условие. В джире висит N+1 таска. Задача за линейное время найти дублирующиеся таски.

Кандидат: (вздыхая) Окай.

select title, count(*)
from issues
group by title
having count(*) > 1;

Беда большинства кандидатов в том, что они не понимают в чем смысл собеседования. Они почему-то думают, что решение алгоритмических задач проверяет только умение решать алгоритмические задачи.

А что ещё проверяет?

Я так понимаю, что статью вы до конца не дочитали. А там это как раз указано.

Перечитал, там в 5 пунктах описано что "кандидат умеет решать алгоритмические задачи"

Сначала, не комментируя выбор задачи - подход через "найдем что-нибудь простое и очень понятное, и вместе с кандидатом докопаемся до центра земли" мне лично очень импонирует. Если вы можете позволить себе не обращать внимание на знание фреймворков - с моей точки зрения, только так и надо.

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

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

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

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

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

Быстрое решение этой задачи требует знания (бесполезных) шорткатов, вроде двоичного поиска по значению, или алгоритма зайца и черепахи для связного списка. Писал двоичный поиск в продакшне 1 раз, связный список 0 раз.

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

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

Правильный апи же разрабатывается под предметную область, с учетом развития и количества команд. Надо очень много бэкграунда распросить, чтобы его правильно задизайнить. Это (упражнение по выяснению ограничений и требований) - тоже прекрасное упражнение на интервью, но это упражнение занимает весь час влегкую. Я где-то слышал, что этот этап называют "системный дизайн".

Улучшение кода - расставить const где положено, а придумывание алгоритма это что-то из области озарений. Я бы не стал планировать собеседование с расчетом на 5 озарений подряд.

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

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

Даже минусанул, потому что больше рекламы, чем пользы.

Последнее решение вообще лишнее, так как не универсальное. Просто автор решил повыделываться своим знанием алгоритмов.

Интересно с чего автор взял что есть решение лучше прямого подсчета? Только вместо hashmap надо применять bitarray(N), который будет требовать N/8 байт. Решение на bitarray может найти не только первое повторяющееся число, но и все повторяющиеся числа.

Если говорить о реальности применения, то решение O(N) по времени и O(N) по памяти выгоднее O(NlogN) по времени и O(1) по памяти.

inplace radix sort, по времени O(N) и памяти O(1), не накладывает никаких дополнительных ограничений. Как тебе такое Илон Маск? ) (как его реализовать я конечно на собеседовании вряд ли вспомнил, но так это наименее безумный вариант. который к тому же уже где то "в интернете" наверняка реализован)

ну это не совсем так. Radix Sort имеет сложность O(NM), где N количество элементов в массиве, а N - количество разрядов. Если в массиве числа от 1 до N, то количество разрядов M = logN.

Это так не работает, есть базовые предпосылки об устройстве "абстрактной машины". Иначе у вас даже банальное умножение со сложением будет не O(1). А если количество разрядов фиксировано(64 бита) то M для конкретной машины будет константой.

Обычно сложность в алгоритме сортировки считается как количество операций сравнения. При поразрядной сортировке это будет O(NM), где M - количество разрядов. Обычно M не зависит от N и может быть принято за константу. Но в этой задаче зависит.

Да вы правы, согласен.

PS: хотя все равно не очевидно, так как N по условию размера массива, ограничено адресуемой памятью, которая константа и 64 бита. (а фиксированность и конечность памяти, является тем самым базовым предположением)

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

А вы представьте что на пайтоне пишите и у вас не ограниченного размера целых чисел.

Какой бы размер самих чисел не был, по условию у нас массив размера N. Но я согласен, с комментарием выше, что так считать, не корректно.

А никого не смущает, что после слов

массив неизменяемый и нельзя использовать дополнительное пространство.

сразу же идет решение, которое начинается с:

int low = 1, high = arr.length - 1;
int duplicate = -1;

т.е. с использования дополнительного пространства?

Или я что-то не знаю про программирование?

Это "дополнительное пространство" имеет константный размер как функция от размера входного массива, то есть O(1). (а то что речь идет про O(1) понятно из контекста задачи)

Я не программист, может мне кто-то объяснить, чем должен заниматься программист умеющий щёлкать подобные задачки? Ну там фронтенд или бек писать? Софт для микро контроллеров или банковское ПО? Как умение решать такие задачи влияет на работу программиста?

Строить звездолёты, а по факту перекладывать json-ы. sad but true.

А где вы увидели, что на собеседовании проверяется "умение решать такие задачи"? На этом собеседовании проверили общие знания об алгоритмах и их сложности, умение задавать уточняющие вопросы, осознавать требования и способность подстраиваться под изменение требований. Ну и заодно посмотрели на то, как человек код оформляет.

В реальные задачи на новой работе новый человек вкатывается не меньше недели. А это синтетический тест, который можно пройти за полчаса.

Конечно, именно такая задача с ограничениями на дополнительное место и неизменность входных данных — весьма искуственная. Такое может только в каких-то микроконтроллерах и вылезет. Но подобные алгоритмические задачки регулярно вылезают, например, при разработке webrtc и браузера хрома.

Но подобные алгоритмические задачки регулярно вылезают, например, при разработке webrtc и браузера хрома.

Даже проще бывает. Вот буквально вчера на ревью принесли — есть UI на клиенте, в нем список временных интервалов (начало + старт), нужно сделать валидацию — интервалы не должны пересекаться, пересекающиеся нужно подкрасить и добавить ошибку в результаты. Алсо это UI, поэтому надо чтоб быстро было, иначе FPS просядет. И с памятью надо поаккуратней, чтоб GC не стриггерить.

В типичной реализации адресной книги (например, gmail) есть функция поиска и объединения одинаковых контактов. В типичном фотоальбоме есть функция удаления одинаковых фотографий. Сколько-нибудь вменяемое ПО для организации логистики (посылки, курьеры) умеет находить и объединять доставки по близким маршрутам . Масса данных поступает по ненадёжным каналам и/или из ненадёжных источников, и может не только потеряться, но и задвоиться.

Тут скорее вопрос обратный: чем таким узконаправленным должен заниматься программист, чтобы не столкнуться на практике с поиском дубликатов?

Хаха. Была похожая задача на районном туре олимпиады по программированию, лет эдак 20 назад. Там было условие, что все числа до N присутствуют. Решалась через простую сумму и сравнение с арифметическую прогрессию.

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

Классно писать алгоритмы в обычной жизни бекенд разработчика это 5% работы?

Эта задача на проверку знания кандидатом вычислительной сложности и некоторых алгоритмов сортировки не более

А как отмечать знаком числа в массиве, если они изначально могут быть отрицательные, или по условию они целые положительные?

По условию, числа в массиве лежат в диапазоне [1, N], а значит строго положительные.
Но вы правы, первое решение в общем случае не коректно, потому как в условии задачи нигде не сказано, что:


  • Значения в массиве можно менять. Может он в ПЗУ лежит.
  • В массиве можно сохранять значения выходящие за первоначальный диапазон. По сути, применяя отрицание, мы втискиваем в исходный массив дополнительный бит информации, и не факт, что для него есть место. В массиве двубайтных ячеек можно без проблем хранить числа [1,65535], но нет места для их отрицательных пар.

А после оффера crudы ковыряем...

Ничего не понял....

массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N].

Кандидат: Только одно число повторяется?

Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].

Уже здесь нарушено условие задачи.

Такое ощущение, что подобные статьи - это просто тупая реклама, которую делают малограмотные специалисты.

А с помощью XOR это нельзя сделать?

Кандидат: Только одно число повторяется?
Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].

Сначала они просят тебя решать подобные задачки. А потом сливают их кодовую базы и ты понимаешь что там костыль на костыле...

Не прочитал все комменты, если что поправьте мое решение: 

Я бы сделал тестовой массив и прогнал цикл по всем числам основного массива - и 1) удалял индекс массива с числом, которого нет в тестовом массиве (проверяя значение по индексу тестового массива) 2) после удаления текущего числа, записывал бы его в этот тестовой массив по индексу = числу. На выходе основной массив остается с числами, которые повторяются. P.s. это javascript решение упрощенное, если в начальном условии задачи не указано, что массив нельзя менять.

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

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

А что компания готова предложить в награду за такое интервью? будут ли такие же интересные условия, интересная зарплата, интересные задачи? или будет очередная система по перекладыванию json'ок с токсичными менеджерами и за унылую зарплату?

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

Тут возникает сразу вопрос - в предполагаемой для кандидата области деятельности как часто будут встречаться такие задачи?

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

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

как вы реализовали бы вот такое?

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

Зачем пару часов? Вот простейшая задача - нужно сделать выборку некоторого (достаточно большого) объема данных и организовать его параллельную обработку. И просто на словах - как это будет реализовываться, какие там могут быть проблемы и т.п. Это общие паттерны

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

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

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

Вот простейшая задача

Одно из первых собеседований напомнило ;) Меня спросили про веб-сервер и базу данных, я начал рассказывать про IIS и ASP (я эти слова знал), а от меня ожидали, возможно, php и apache (а этих слов я не знал ;) ).. Хотя позиция была без уклона в веб-программирование.. Крч, мы друг друга не поняли ;).

каждый сам волен выбирать принципы по которым он отбирает людей

Абсолютно верно.

Меня спросили про веб-сервер и базу данных, я начал рассказывать про IIS и ASP (я эти слова знал), а от меня ожидали, возможно, php и apache (а этих слов я не знал ;)

Что из всего этого база данных? о_О

где ASP там и ODBC где-то рядом ;) (так же как php и mysql ;) )

Сорян, за давностью лет я не могу вспомнить всех подробностей того собеседования ;) Просто как иллюстрация, что в требованиях бывает одно, спрашивают совсем другое, а чего хотят на самом деле - ?

от меня ожидали, возможно, php и apache

Я не ожидаю "единственно правильного решения" т.к. его нет. Есть много способов, у каждого свои плюсы и минусы. Мне интересно насколько глубоко человек думает, чем обосновывает свой выбор конкретного подхода в конкретном случае.

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

Кандидаты часто не видят ценности/умений в приобретенном ими опыте и не рассказывают самое важное, и интересное.

Зачем мне копаться в дерьме, которое способен осилить школьник с литкода, когда среди "решателей алгоритмов", которых видит рынок, я могу найти того, с кем будет шикарно работать.

Кандидат: Если решать в лоб, то можно проверить, встречается ли это число ещё раз в массиве.

Интервьюер: А есть более эффективные решения? (Можно ещё намекнуть на временную сложность)

Кандидат: так оно уже максимально эффективно по памяти (Можно намекнуть Интервьюеру на пространственную сложность)

Кандидат: Можно использовать HashMap и считать каждый элемент массива. Как только попадётся элемент, который встречается больше одного раза, это и будет наш ответ.

Интервьюер: О, уже лучше. Мы нашли решение O(N)

Это с обычным массивом было бы гарантированно O(N). HashMap эффективно заменяет разреженный массив, а для плотно упакованных данных у него цена записи возрастает до O(N) из-за коллизий хэш-функции. Поэтому здесь нашли решение скорее O(N²).

Лучше сразу взять битовый массив длины N и не морочить голову :)
(Он уже один раз упоминался в комментариях.)
(И это практически он же в варианте со сменой знаков.)

а для плотно упакованных данных у него цена записи возрастает до O(N) из-за коллизий хэш-функции

А что такое "плотно упакованные данные"? И разве выбор хеш-функции под задачу не решает подобные проблемы? Кому нужен HashMap под N^2?

Если выбрать идеальную для этой задачи хэш-функцию f(x)=x, HashMap выродится в массив.

Если выбрать идеальную для этой задачи хэш-функцию f(x)=x, HashMap выродится в массив.

И ладно :)

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

Именно поэтому начинаем с индекса 0, который в массиве не может встречатся по условию (диапазон от 1 до N).

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

Как странно устроена память. Сразу вспомнилось, что подобная задача встречалась на школьных математических олимпиадах, кгхм, 50 лет назад, и что решение - суммированием.

Насчёт того решения с индексами и минусами - оно работает по той причине, что элементы все в диапазоне от 1 до N, т.е. натуральные числа, но для хранения их, я так понимаю, используется тип со знаком. Это значит, что у нас есть лишний бит, который в общем случае используется для хранения знака, а в задаче его можно задействовать как флаг посещённости. А что если тип числа в массиве беззнаковый? Ведь тогда все биты относятся к модулю числа. Тут уже хочешь или нет, а придётся выделять дополнительную память, разве я не прав?

Не всегда: если N хотя бы вдвое меньше максимального значения типа (например, uint16_t arr[30000]), то можно использовать старший бит как индикатор — по сути то же самое, что с отрицательными числами, только код немного страшнее.

Ну это уже какое-то совсем надуманное допущение

Это всего лишь ответ на ваш вопрос: нет, выделять дополнительную память придётся не всегда :)
А насчёт надуманности… ну не знаю, полагаться на то, что массив с положительными числами будет использовать знаковый тип — делать точно такое же допущение, что и в моём контрпримере: что (минимум) половина всех допустимых значений типа не используется.

На кого рассчитаны такие задачки? На кандидата, который с такой задачей уже знаком? Но тогда какой смысл?

На кандидата, который незнаком с такой задачей? Но... ситуация несколько стрессовая, а такой поиск решений задач основывается либо на глубоком спокойном анализе, либо на интуиции (а это вещь непредсказуемая). Т.е. нужна спокойная обстановка и достаточное количество времени, а не стояние над душой...

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

Или в пределе... ждать от кандидата решения из серии баек о секретных советских кирпичах... Это было бы еще оригинальнее :)

Насколько она всё же хорошая? Сильный кандидат расскажет вам решение за 3 минуты и за 7 напишет.

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

Решение алгоритмических проблем: Поиск повторяющихся элементов в массиве (nuancesprog.ru)

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

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

Если для Вас ЭТА задача является "спортивным программированием", то задайтесь сами вопросом - Вы точно представляете себе чем занимаются компании которые набирают именно программистов для разработки софта, а не сопровождением легасных телеграм ботов и сайтов на ванильном PHP?

Конечно же мой опыт не покрывает все области разработки софта, но я точно знаю, чем занимаются в компаниях, которые занимаются: разработкой сайтов, CMS/CMF систем, интернет-магазинов, личных кабинетов, CRM/OSS систем, BPM систем, разработкой мобильных приложений для вышеперечисленных видов приложений. Я в разработке с начала 00-х и по своему опыту и опыту коллег скажу, что в 99,999% случаев подобные алгоритмы не нужны, поскольку инструментарий (фреймворки, библиотеки, sdk) предоставляет все необходимое. Безусловно, бывают случаи, когда необходимо применить нестандартный подход, и такие случаи отдаются на реализацию знающим ребятам (условно сеньорам).

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

Знаю, что наберу минусов. Но мне лично как-то без разницы.


Очередная отличная статья, написанная о собеседовании со стороны собеседующего, а не со стороны стоноты, который бегает собеседуются, а его ""мучают", "не берут" и вообще все вокруг идиоты, а он такой молодец".

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

Когда на работу берут например строителя в бригаду прежде всего смотрят не то как он пользуется лопатой - этому научат.
На что смотрят:
1. кто по национальности и вере и где родился, чтобы не оказалось, что у тебя в бригаде потом на этой почве поножовщина с другими
2. что по пьянке
3. что набито на руках и спине
4. кто его знает, кому позвонить спросить кто такой
5. может наличие хоть какого-то документа
6. отсуствие признаков внешних каких-то явно нездоровых в части психики

Вот что будут смотреть. И программистов это касается в полной мере. Собеседование это не про "лопаты", а про "наколки"

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

1. если у вас стремные софты - это перевесит в итоге хорошие харды, хотя если софты хорошие это не значит, что они перевесят отсутствие хардов
2. умение мыслить - важнее гораздо готовых знаний
3. умение задать вовремя правильный вопрос - важнее чем готовые ответы
4. умение действительно справиться со стрессом - важнее чем показное веселье или напускное спокойствие
5. и да - такие простенькие задачи на алгоритмы (простые в плане что условия понятны, кода точно много не требуется и легко в голове прикидывать на числах типа 1,2,3) - надо решать до какого-то хотя бы уровня, хотя бы на хэшмапах - а ведь не все кандидаты даже это в состоянии предложить!

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

Если Вас это бесит - значит просто ВЫ не годитесь в эту команду, а команда и без ВАС спокойно проживет. Не хотите никаких требований на собесе? Идите работать на галеры - там Вас ни о чем кроме имени Вашего не спросят.

Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.

Интервьюер: Тогда временная сложность вырастет до O(NLogN). Что ещё можно сделать?

А если массив A = 1,2,3,...,n,n?
И, сходу, быстрая сортировка — уже n^2.
Ладно, пусть отсортировали за n*ln(n)
Но теперь ещё надо пройти по всему массиву — итог n^2*ln(n).

from collections import Counter
print(list(Counter(A))[0])

За нас уже подумали; и код лаконичный.
Но теперь ещё надо пройти по всему массиву — итог n^2*ln(n).

Что?


Вы проходитесь по массиву на каждом шаге сортировки что ли? Действия последовательные, поэтому количество операций складывается O(n + n log n) = O(n log n).

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

Глупости. Лучшая задача для интервью - это как лучшая функция, которая решает все задачи.

Ни сама задача, ни наводящие вопросы ничего не говорят о кандидате. Абсолютно ничего.

Кандидат: сколько элементов в массиве?

Интервьюер: ну допустим 100.

Кандидат: тогда все ваши временные и прочие сложности никакого значения не имеют. Пакуем в мапу и всего делов.

Интервьер: мерзавец(про себя). Хорошо, допустим, 10 миллионов(вслух). Посмотрим как выкрутится(про себя)

Кандидат: на таких объёмах я бы использовал все же СУБД, делаем табличку с первичным ключом и вставляем в неё элементы. Как только будет dupval_on_index. Это вот оно и есть. Никогда не надо решать задачу неподходящими для неё методами.

Кандидат: на таких объёмах я бы использовал все же СУБД, делаем табличку с первичным ключом и вставляем в неё элементы. Как только будет dupval_on_index. Это вот оно и есть. Никогда не надо решать задачу неподходящими для неё методами.

Что работает на порядок медленнее той же мапы. И памяти жрет больше. Плюс тянется библиотека СУБД.


Никогда не надо решать задачу неподходящими для неё методами.

Вот уж точно.

Если развернуть СУБД на домашнем компе - безусловно. В промышленной среде - смешно даже сравнивать. Кое-какой производитель АБС решил посчитать отчетною форму и положил в мапу проводки за квартал:)) Ну что сказать. На чахлом объеме в 200.000 записей мапе этой настал каюк. Oracle на объеме 200 тысяч записей наконец-то перестает удерживать таблицу в памяти и вспоминает о свопировании. У него все еще только начинается.

Странная история. 200000 записий и мапа не справляется? Что там за записи-то такие? Там в каждой проводке ключи криптографические сохраняются или что? Даже если каждая запись занимает аж по 20кб, это все суммарно в 4 гб памяти влезет. Ну плюс сколько-то процентов на оверхед, но по сравнению с такими толстыми записями это будут копейки. 200 тысяч записей — это обычно ничтожный объем.


Понятно, если у вас данных так много, что оно в память не влезает, то надо что-то думать. В зависимости от задачи, опять же, СУБД скорее всего будет перебором. Ибо это универсальное средство оптимизированное под хранение данных а не их обработку. Что-то заточенное под вашу задачу может быть сильно быстрее и проще.
Единственный плюс СУБД — мозг у программиста не задет. Все дешево и быстро делается.


Возвращаясь к началу ветки: если вам надо найти повторяющееся число, то мапа в память перестанет влезать только на миллиардах чисел. Но и тут тупой битовый массив будет работать до 32 миллиардов чисел спокойно. Приведенные выше 10 миллионов — это примерно на 3 с половиной порядка меньше.

Group by средство обработки информации. Если и немного более сложные средства которые позволяют не выкачивать на клиента весь датасет.

Так у вас задача сначала закачать в СУБД «весь датасет», затем его там обработать и выкачать агрегат. Вот вам и предлагают: может, вместо того, чтобы туда-сюда перекачивать, посчитать локально?

В описанном вами решении задачи через СУБД никаких group by и нет:


вставляем в неё элементы. Как только будет dupval_on_index

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

Еще раз! Мне заявили, что СУБД якобы предназначена для хранения информации, а не для обработки . Это не так. В качестве примера обработки информации я и привел group by. Я уже не говорю про процедурное расширение языка, присутствующее практически в любой промышленной СУБД.

Мне заявили, что СУБД якобы предназначена

Я сказал "оптимизированное", а не "предназначенное".
И на этой конкретной задаче видно, что СУБД менее оптимально обрабатывает данные, чем простенькая структура данных.

Задача, конечно, интересная... для олимпиады по информатике не слишком высокого ранга. Но при чем тут собеседование? Хороший сотрудник должен владеть существующими инструментами, например, разбираться в типичных алгоритмах и уметь их реализовывать. Вероятность столкнуться с подобной задачей в реальной практике, по моему опыту, весьма невелика, причем даже за десятки лет интенсивной работы в области алгоритмов. А если даже и возникнет подобная нестандартная ситуация (бывает всякое), то гораздо полезнее сотрудник, который сможет быстро найти готовое решение в интернете, в книгах (вроде Hackers Delight) или на форумах, чем тот, кто решит подобную задачу сам. Ибо почти наверняка готовое решение окажется профессиональнее и эффективнее.

Если же говорить о конкретно этой задаче, то, во-первых, надо отмести как неправдоподобное требование неизменяемости массива. Это может быть важным либо 1) при необходимости разработки очень фундаментальной стандартной библиотеки, которой будут пользоваться миллионы, например, базового API языка; 2) если размер массива сопоставим с объемом оперативной памяти, т.е. мы не можем позволить себе создать его копию. Первое, однако, явно мимо кассы - в этом случае над задачей будет работать команда профессиональных инженеров, а никак не новичок. Второе же, да, бывает, но очень маловероятно, что задача будет настолько простой. Большие массивы - это обычно изображения, карты, базы данных, а никак не наборы индексов. А самое главное, что в этом случае быстродействие O(N) становится важнее, чем неизменяемость - уж лучше сбросить исходный массив во внешнюю память, чтобы можно было изменять. Кстати, даже в первом случае нормальное решение, как минимум, должно проверить наличие свободной памяти и предпочесть копирование массива в случае, если памяти достаточно и если это повышает быстродействие.

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

А вот если это не целые числа, а, к примеру, вещественные, то я бы очень оценил кандидата, который не "поведется" на стандартные библиотечные хеш-таблицы и предложит сортировку! Точнее, настоит на том, чтобы сравнить производительность обоих вариантов. Да, формально хеш-таблицы быстрее, но в реальности - при тех объемах, которые реально могут поместиться в ОЗУ - весьма вероятно, что N log N тщательно "вылизанной" библиотечной сортировки с легкостью обгонят поддержку структуру данных универсального хэша. Особенно если это язык вроде Java, где HashMap работает с объектами, размещаемыми в куче. Очень хорошо, если соискатель задумается о кэше процессора, о том, как именно будет происходить обращение к памяти - вразброс или последовательно, о том, поддается ли решение распараллеливанию на многоядерных процессорах и будет ли реальный прок от такого распараллеливания...

Вот эти соображения, да, важны для профессионального сотрудника, они кое-что говорят о его опыте работы и умении создавать эффективные решения. А поиск супер-изящных алгоритмов при искусственных ограничениях, по-моему, лучше оставить олимпиадникам. Вроде тех, кто в свое время пользовались нестандартным форматом Intel-команды AAD, чтобы сэкономить лишний байт памяти, умножая число на множитель, отличный от 10 :)

Мне сложно представить на собесе реального человека, который думал бы так быстро и так совершенно.
По моему, пора уже на литкоде, где-нибудь под катом прятать секретное стоп-слово, чтобы каждый знакомый с задачей разработчик мог предъявить его другому такому-же разработчику. А за одно можно было бы и остановить интервьюера, пока он не достиг экстаза от самолюбования.
Как то желчно вышло, но я бы и правда предпочел скорее тимейта с на 30% меньшим интеллектом и душностью, но на 20% большей честностью, сообразительностью и коммуникабельностью. Такой человек, как правило, всегда при работе и не станет специально готовится к собеседованию. Мой типовой вопрос попроще:
Есть 128-битный без знаковый инт на входе. При валидации этого числа надо проверить, влезет ли его факториал в такой-же 128-битный инт (т.е. сравнить с захардкоженым числом).
Как будешь считать это число?

Зачтено, если спросить на WolframAlpha и получить ответ «34»?

Наверно, требуется последовательно умножать 1*2*3*... до заданного числа, но так чтобы не вляпаться в переполнение. Например, очередное X! сравнивать с (pow(2, 128)-1)/(X+1)

Это слишком скучно.
Но у вас детект переполнения какой-то переусложнённый.
Хорошо бы спросить о документированном поведении системы при переполнении.
Если выставляется бит переноса или кидается исключение — можно это смотреть.
Если операция выполняется по модулю (2^128), достаточно проверить что произведение стало меньше максимального из сомножителей — значит, случилось переполнение.

А вот не факт. Оно после переполнения может стать больше изначального числа, да и любого множителя тоже. Например (uint_max/2+1) при умножении на 3 будет uint_max/2+3.


Можно, результат потом на последний множитель или последнее значение делить и смотреть, что результат деления равен второму множителю.


Ну или надо, как Alexandroppolus описал — смотреть, что умнжаемое меньше max/множитель.


Без деления вы переполнение не отловите.

Я подозревал, что так и будет, но не смог найти пример )))
Хочется всё же без деления, например, вычислять бит переноса, поделив числа на 2 64-битные половинки (A*2^64+B)*C (второй множитель заведомо не вылезет за int64, он и за int32 не вылезет). Но не факт, что будет быстрее, чем деление в лоб.

Хочется всё же без деления

Можно сократить количество делений, например, факториалы на отрезке X! ... (X+k)! сравнивать с maxUint128/(X+k+1), взяв деление один раз на k шагов. Как только перевалили за max/(X+k+1), то можно уже с меньшим k, или вообще "поштучно".

Разумеется, в этом нет даже теоретического смысла на 128 битах, но если говорить о длинной-предлинной арифметике, то вполне.

Если я правильно понял идею, надо делить так:
max / ((x+1)*(x+2)*...*(x+k+1))
и сравнивать с текущим x!

Можно и так.

Моя идея в том, что берем некоторое P, вычисляем M = maxUint128/(P+1). Далее можно спокойно смотреть факториалы до P! и сравнивать с M. Если так и не превзошли М, то у нас (P+1)! < maxUint128, берем новое P = P + k, новое М, и идем дальше. Иначе переходим к пошаговому варианту, там до переполнения уже рукой подать.

Понятно, ваш вариант оптимальнее.

С моей точки зрения - любой корректно работающий вариант - правильный.
Я, к примеру пошел на https://umath.ru/calc/graph , построил y=x!/2^128 и посмотрел в какой точке кривая пересекает 1. Потом, чтобы убедиться, что логика сайта не забагована для таких случаев, пошел в убунтовский калькулятор, убедился, что 2^128−34! - положительное, а 2^128−35! отрицательное.
Конечно решение изяществом не блещет, но с точки зрения продакшена - корректный результат за разумное время - то что надо.
Соискатели (среди которых бывают и вчерашние студенты) демонстрируют, к примеру свой матан: "Надо вывести уравнение, так сейчас, сейчас... Минуточку, но у факториала же нет обратной функции!" иногда еще и с вопросительной интонацией в конце)
Дальше мы переходим к численным методам. В лоб перемножать числа с 2 почему-то всем очень не нравится, пытаются приплести метод половинного деления. Много разговоров об О-нотации, но это все - чтобы оценить на сколько инженер самостоятельный, будет ли он искать способ самому проверить свое творчество (не рассчитывая что другой инженер на код ревью все исправит), на сколько склонен к оверинжениренгу, достаточно ли у него фантазии, чтобы решать абстрактные задачи.

Это все я к тому, что над такой вот задачкой не надо 5 минут вчитываться, задавать уточняющие вопросы, потом 5 минут думать в неловкой тишине. А информации о том, как потом с человеком работать это даст не меньше. Но это субъективное мнение, конечно.

Вполне.
спросить на WolframAlpha
Про такой сервис не знал, спасибо.

А... зачем может пригодиться такой факториал? :)

Что действительно может понадобиться в реальной жизни, так это проверка переполнения при самых обыкновенных вычислениях - сумм, разностей, произведений. Вот, например, предложите задачу: написать функцию с целыми параметрами dimX, dimY, которая создает матрицу dimX x dimY в простом линейном массиве (не двумерном, даже если язык позволяет) и заполняет ее чем-нибудь полезным, ну хотя бы рисует там круг из единичек. И вот, тест на квалификацию: догадается ли кандидат перед отведением памяти проверить, что произведение dimX * dimY вычисляется без переполнения, и в противном случае выдать соответствующее исключение "слишком большой массив". Сколько я видел кода, который не задумывается о таких "мелочах жизни" - и, соответственно, при неудачных dimX и dimY ведет себе неадекватно (вплоть до порчи памяти в языках типа C++). Я уже не говорю о более тонких мометах, вроде того, что для знаковых x и y неравенство x - y < 0 вовсе обязательно означает, что x < y...

А... зачем может пригодиться такой факториал? :)

Мне это пригодилось для ленивого способа подсчета числа сочетаний для своего домашнего мини-бикини-пет-проекта. Рабочие задачи, к сожалению, более унылые. А те что не унылые требуют знания предметной области, которого от соискателя не ожидается.

произведение dimX * dimY вычисляется без переполнения

Мб я что-то не понял, но по моему самый простой вариант, если код будет работать на 64-разрядной машине, то произведение двух uint32_t не сможет превысить размер адресного пространства, Так можно наложить ограничения без накладных расходов на проверку. Правда проверка того, что сами аргументы не были вычислены с переполнением уже становится заботой клиентского кода). Кроме того у системы закончится память гораздо раньше и аллокатор выбросит bad_alloc исключение. Если же это код для 32-разрядной машины (или для контроллера), то всевозможные учеты аппаратных ограничений становятся самостоятельным видом искусства). В целом согласен - хорошая задача на внимание к деталям.

Так для домашнего проекта нет ничего проще, чем воспользоваться стандартным классом длинных целых.

Что касается произведения, то я работаю в Java, где нужно использовать int и long. Но, вне зависимости от языка, суть в том, что нужно всегда помнить о возможности переполнения. Использовать правильное сочетание 32-битового и 64-битового типов - да, один из способов. (Если, конечно, оба беззнаковые либо оба знаковые.) При этом, правда, придется привести произведение к нужному более краткому типу. Но уже, например, для трехмерной матрицы этот способ не подойдет. Не подойдет и для изображения в формате RGBRGB... - там добавляется умножение на число каналов.

Наиболее простой и универсальный способ контроля - деление максимального допустимого размера на один из сомножителей. Правда, это медленно, но при отведении памяти это несущественно. Если нужна скорость (умножать надо не только для отведения памяти, но и, скажем, при вычислении индекса), то можно использовать прием из Hackers Delight. В последних версиях Java соответствующии функции добавлены в библиотеку Math: обычные арифметические операции, но гарантирующие исключение в случае переполнения.

Мб я что-то не понял, но по моему самый простой вариант, если код будет работать на 64-разрядной машине, то произведение двух uint32_t не сможет превысить размер адресного пространства
Но нужно это ещё правильно записать: compiler-explorer.com/z/caWKdW9qs

Согласен.
Такого рода ошибки можно отловить на код-ревью.
Таким тонкостям как раз можно научить, я думаю. А вот если человек плохо обучаем, или склонен безосновательно стоять на своем, то такого человека лучше сразу не брать в команду.

Такого рода ошибки можно отловить на код-ревью.
А вот и нет. Когда на ревью поступает стена текста, глаз не зацепится за «обычную» строку
auto buf = new char[dx*dy];
Это надо помнить в момент написания.

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

Ну мы обычно первые комиты новичков очень придирчиво смотрим, а со временем становится понятно какие у каждого сильные и слабые стороны.
Конечно идеально было бы найти идеального кандидата, но мне пока так ни разу не везло)

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