Готовиться к собеседованию можно по‑разному: смотреть ролики на YouTube, читать документацию, положиться на судьбу и тд. В большинстве случаев кандидатам предложат решить одну или несколько задач. В этой статье вас ждет подробный разбор реальной задачки, рекомендации к ее решению и объяснение ожиданий интервьюера от кандидатов.
Найдите любое повторяющееся число
Дано:
массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N].
Найти:
любое повторяющееся число.
Вопрос очевидный, но кандидаты часто задают уточняющие вопросы, и это хорошо.
Вот что они обычно спрашивают:
Кандидат: Можно пример?
Интервьюер: [4, 3, 1, 1, 2].
Кандидат: Только одно число повторяется?
Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].
Кандидат: А там точно будут повторяющиеся числа?
Это плохой уточняющий вопрос, ведь мы уже знаем, что размер массива N+1, а уникальных элементов в нем только N, так что по принципу Дирихле каким‑то кроликам придётся сидеть в одном домике.
Интервьюер: А разве может быть массив длиной N+1 с элементами в диапазоне [1, N], в котором числа не повторяются?
Кандидат понимает условия, начинает обдумывать решение и предполагает, что это довольно лёгкая задача.
Продолжаем диалог.
Кандидат: Если решать в лоб, то можно проверить, встречается ли это число ещё раз в массиве.
С этого начинает каждый кандидат. Я считаю, что главное начать с какого‑то более‑менее оптимального решения.
Интервьюер: А есть более эффективные решения? (Можно ещё намекнуть на временную сложность)
Кандидат: Можно использовать HashMap и считать каждый элемент массива. Как только попадётся элемент, который встречается больше одного раза, это и будет наш ответ.
О, уже лучше. Мы нашли решение O(N), но всё равно слишком тривиальное. В идеале кандидат должен с него и начать.
Интервьюер: Посчитайте временную и пространственную сложность этого решения.
Кандидат: Временная сложность O(N), пространственная сложность O(N).
Пока всё хорошо, спрашиваем дальше.
Интервьюер: Можно решить эту задачу, не используя лишнее пространство?
Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.
Интервьюер: Тогда временная сложность вырастет до O(NLogN). Что ещё можно сделать?
На этом этапе кандидаты иногда думают, что это математическая задача и, например, пытаются посчитать сумму N*(N+1)/2 и т. д. В итоге запутываются и начинают решать другую задачу, в которой нужно найти недостающий и повторяющийся элемент, если в массиве только одно число повторяется дважды и элементы находятся в диапазоне [1, N], причём остальные элементы встречаются только один раз.
Сумма элементов в диапазоне нам никак не поможет, потому что мы не знаем, сколько элементов повторятся и сколько раз они повторяются. На этом этапе большинство кандидатов подвисает.
Подсказка: А если как с HashMap, только обозначать элементы индексами массива?
Кандидат: Аааааа, понятно! Если элементы находятся в диапазоне [1, N], а размер массива N+1, можно использовать индекс массива, чтобы помечать, присутствует элемент или нет. Берём число как индекс и меняем знак у числа по этому индексу на минус. Написать код? Или привести пример?
Интервьюер: Приведите пример.
Кандидат:
— Массив = [4, 1, 3, 2, 5, 4, 5, 5]
— Берём 4, переходим на 4-й индекс и меняем знак на минус
— Массив = [4, 1, 3, 2, -5, 4, 5, 5]
— Нужно взять абсолютное значение.
— Обрабатываем 1, массив = [4, -1, 3, 2, -5, 4, 5, 5]
— Обрабатываем 3, массив = [4, -1, 3, -2, -5, 4, 5, 5]
— Обрабатываем -2, массив = [4, -1, -3, -2, -5, 4, 5, 5]
— Обрабатываем -5, массив = [4, -1, -3, -2, -5, -4, 5, 5]
— Обрабатываем -4, массив = [4, -1, -3, -2, -5, -4, 5, 5], abs(-4) = 4, а число на четвёртом индексе уже отрицательное, значит число 4 встречается второй раз, это и есть наш ответ.
Интервьюер: Можете написать код?
Кандидат: Да.
Вот код:
int findAnyRepeatedNumber(int[] arr) {
for(int i = 0; i < arr.length; i++) {
int index = Math.abs(arr[i]);
if(arr[index] < 0) return index;
arr[index] = -arr[index];
}
throw new IllegalArgumentException("Invalid input array it should have elements in range [1, arr.length-1]");
}Кандидату может показаться, что он решил задачу. Но интервьюер ещё не закончил.
Интервьюер: Что если массив неизменяемый?
Кандидат: Нельзя менять входящий массив?
Интервьюер: Да.
Кандидат: А если мы изменим массив, а потом отменим изменения? Так можно?
Интервьюер: Нет. Сам по себе массив неизменяемый и нельзя использовать дополнительное пространство.
На этом этапе большинство кандидатов сдаётся. Но некоторые задают дополнительные вопросы.
Кандидат: Нам нужно решение O(N)?
Интервьюер: Сейчас у нас есть неизменяемый массив и нужно решение лучше O(N²). Как решить задачу с временной сложностью O(NLogN)?
Кандидат: Это задачка на поиск. Сложность LogN бывает у бинарного поиска или алгоритма «разделяй и властвуй». Но массив‑то не отсортирован.
Подсказка: А если всё‑таки применить бинарный поиск? Массив не отсортирован, но пространство поиска [1, N] отсортировано. Если сложность должна быть O(NLogN), можно выполнять операции O(N) с массивом LogN раз.
Эту подсказку кандидаты понимают редко.
Кандидат: Понимаю. Пожалуй, можно выполнить бинарный поиск повторяющегося числа. Например, можно пройтись по списку и посчитать число целых чисел от 1 до N/2. Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне. В противном случае повторяется число из диапазона от N/2+1 до N. Когда мы поймём, в какой половине диапазона повторяющееся число, можно снова разделить диапазон пополам, и так пока не найдём само число. Временная сложность получается O(NLogN), а пространственная — O(1).
Реализация:
int findAnyRepeatedNumber(int[] arr) {
// Range [1, N]
int low = 1, high = arr.length - 1;
int duplicate = -1;
while (low <= high) {
int cur = (low + high) / 2;
int count = countLessThatOrEqual(cur, arr);
if (count > cur) {
duplicate = cur;
high = cur - 1;
} else {
low = cur + 1;
}
}
if(duplicate == -1) {
throw new IllegalArgumentException("Invalid input array it should have elements in range [1, arr.length-1]");
}
return duplicate;
}
int countLessThatOrEqual(int num, int[] arr) {
int count = 0;
for (int x : arr) {
if (x <= num)
count++;
}
return count;
}Временная сложность O(NLogN), пространственная сложность O(1)
Интервьюер: Отлично!
Интервьюер: Ещё один вопрос.
Кандидат: (про себя: Ну что ещё?!) Да?
Интервьюер: Если повторяется только одно число, можно решить задачу с временной сложностью O(N)?
Кандидат: (про себя: Вряд ли.) Дайте подумать.
На этом этапе большинство кандидатов отчаивается. А ведь поначалу задачка показалась им лёгкой! Почти всем нужна подсказка.
Курс «Алгоритмы: roadmap для работы и собеседований»
Подсказка: Про зайца и черепаху слышали?
Кандидат: Да, это алгоритм, который определяет цикл в связном списке и помогает найти начальную точку цикла.
Интервьюер: Так. В нашей задачке тоже можно увидеть цикл.
Кандидат: Где?
Интервьюер: Давайте представим, что наш массив — это связный список, в котором число по каждому индексу указывает на индекс, равный этому числу.
Кандидат: Можно пример?
Возьмём массив [2, 6, 4, 1, 3, 1, 5].
Нулевой индекс указывает на второй, второй указывает на четвёртый и так далее.
Кандидат: Понятно.
Интервьюер: Можете написать код?
Кандидат: Вот код.
int findAnyRepeatedNumber(int[] arr) {
int slow = arr[0];
int fast = arr[0];
do {
slow = arr[slow];
fast = arr[arr[fast]];
} while(slow != fast);
slow = arr[0];
while (slow != fast) {
slow = arr[slow];
fast = arr[fast];
}
return fast;
}Временная сложность O(N), пространственная сложность O(1), массив неизменяемый.
Это решение не сработает, если повторяться может несколько чисел.
Интервьюер: Ещё один вопрос.
Кандидат: (злится) С меня хватит.
Интервьюер: Да я же просто хотел спросить... когда вы сможете приступить к работе?
Это умный вопрос, потому что:
Кандидат разбирается в алгоритмах, пространственной и временной сложности и т. д.
Кандидат адаптируется к разным ограничениям и находит компромисс. Инженерам постоянно приходится работать в таких условиях, так что это важный навык.
Кандидат проявил креативность. Каждое ограничение заставляет начинать с нуля и придумывать совершенно новый подход.
Кандидат правильно смотрит на сложность. Некоторые кандидаты застревают, пытаясь найти решение с временной сложностью O(NlogN) и пространственной сложностью O(1). Им кажется, что использовать хеш или сравнивать все элементы списка с остальными элементами было бы слишком просто, поэтому они не предлагают эти банальные решения — но и более сложные придумать не могут. Это указывает на то, что кандидат склонен чрезмерно всё усложнять. Обычно я прошу следующих интервьюеров обращать внимание на эту склонность.
Кандидат готов учиться и решать сложные задачи. Некоторые люди оживляются, когда условия задачи становятся сложнее, а другие опускают руки или ленятся прилагать усилия.
Как решать задачи, которые не могут решить другие программисты
Подготовка к собеседованию и само собеседование – то еще испытание для тех, кто только делает первые шаги в IT. В текущих реалиях не всегда достаточно знать теорию и уметь кодить. Чтобы получить долгожданный оффер и выделиться среди других соискателей, вам понадобится знание алгоритмов. В этом вам поможет наш экспресс-курс «Алгоритмы: roadmap для работы и собеседований».
Вы научитесь
???? решать задачи, которые не могут решить другие программисты
???? узнаете, как знание алгоритмов и структур данных помогает устроиться в топовые компании FAANG: Apple, Amazon, Netflix, Google
Эти навыки помогут вам участвовать в сложных высокооплачиваемых проектах, а также успешно подготовиться к алгоритмическим задачам на собеседованиях в топовые компании.
В экспресс-курсе нет детального разбора существующих алгоритмов — здесь то, что используется на практике чаще всего. Знание алгоритмов и структур данных — не достаточное, но необходимое условие успешного прохождения собеседований.
Курс «Алгоритмы: roadmap для работы и собеседований» доступен в любое время. Вас ждут ёмкие лекции, практические задачи, приближенные к реальным, полезная литература по теме и доступ к материалам курса на 2 года.
Сомневаетесь? Посмотрите первые две темы экспресс-курса бесплатно.
Комментарии (275)
holodoz
00.00.0000 00:00+25Зачем в последнем случае так сложно? У нас есть арифметическая прогрессия и одно дополнительное повторяющееся число. Считаем сумму прогрессии по формуле, отнимаем её от суммы всех элементов, решение в одну строчку
SomeAnonimCoder
00.00.0000 00:00+1А если не одно?
holodoz
00.00.0000 00:00+8Это условие задачи в последнем варианте, я говорю только про него
tyomitch
00.00.0000 00:00+12[1, 1, 1, 3, 4] -- это тоже "повторяется только одно число"
holodoz
00.00.0000 00:00Да, я не прав, три раза - это тоже "повторяется"
Первое моё сообщение уже не могу редактировать
BadHandycap
00.00.0000 00:00+11Меня тоже это немного спутало.
Сначала Аня пишет: "элементы в диапазоне [1,N]", а потом: "уникальных элементов в нем только N".
Посмотрел источник, про уникальность там ничего нет.
Короче, корявый перевод - причина всех недопониманий.
sgrebenkin
00.00.0000 00:00+5Если одно число в массиве A повторяется один раз, то можно решить так
X=1^2^3^...^N^A[0]^A[1]^...^A[N]
Tarakanator
00.00.0000 00:00x=a[0]+a[1]+...+a[N]-(N+1)/2*N
так не проще?
DistortNeo
00.00.0000 00:00+2так не проще?
У вас в одной строчке аж две ошибки:
-
Это не будет работать для чётных N. Потому что приоритет операций. Правильно: (N+1) * N / 2.
-
Это в общем случае не будет работать из-за переполнения типов при умножении.
Видимо, не проще.
Tarakanator
00.00.0000 00:00математически это одно и тоже. Я писал формулу в более наглядном виде, когда становится очевидно что мы ищем среднее значение элемента и умножаем на количество элементов. в ваей записи смысл найти не так просто. и см. п2.
Чтобы говорить о переполнении типов эти типы должны быть. Я так понимаю речь же про псевдокод?
-
DollyPapper
00.00.0000 00:00Эту задачу люди взяли с литкода я так подумал. Пошел искать её там, и она действительно там есть. Пришёл к такому же решению как и вы, через разницу суммы всех элементов от арифм. прогрессии. Только вот в условиях задачи явно не обозначили (либо я невнимательный такой), но элемент может повторяться не один раз. Моё решение завалилось на кейсе [2,2,2,2,2].
igrishaev
00.00.0000 00:00+79Чем эта задача "лучшая"? И что значит лучшая? Что она проверяет? Где корреляция между хорошим и плохим кандидатом и умением ее решать?
xaosxaos2
00.00.0000 00:00-7Добавлю, раз кандидаты задают уточняющие вопросы, задача поставлена не верно.
aamonster
00.00.0000 00:00+9Но это же хорошо! Когда это программистам доставались "верно поставленные задачи"?
Didimus
00.00.0000 00:00На собеседованиях?
aamonster
00.00.0000 00:00В реальной жизни. Так что проверить навык уточнения задач – дело полезное. А то порой приходится наблюдать две крайности: человек либо додумывает неполное условие каким-то своим непредсказуемым образом, либо начинает задавать огромное количество вопросов по несущественным деталям.
bay73
00.00.0000 00:00+2А кому нужны кандидаты которые только с "верно поставленными задачами" работать способны?
xaosxaos2
00.00.0000 00:00-2Ну на кого-то же уже работают те кто неверно ставит задачи. Из своей практики скажу я так олимпиаду по информатике выиграл. Были задачи я их решил. Когда стали проверять, было очень больно, но на апелляции я отыграл все положенные баллы, когда просто указал, вот задания вот решения, которые выполняют все ваши указанные условия, про ваши случаи на которых вы меня завалили ничего в задании нет. Я сделал то, что просили не больше и не меньше.
bay73
00.00.0000 00:00+11А вот этим олимпиада от работы и отличатся. Вы можете бесконечно долго спорить с менеджером или заказчиком о том, что вы решали именно поставленную задачу, и, возможно, даже получите деньги за это, но на следующий заказ найдут другого исполнителя.
DollyPapper
00.00.0000 00:00В реальности же тоже хорошо если программист решает именно поставленную задачу, или нет? Плохо если он сделал меньше (т.е. не выполнил ТЗ). И плохо если он сделал больше. Больше значит дольше, а дольше значит дороже.
bay73
00.00.0000 00:00+1Конечно же это не хорошо. Если он решает поставленную задачу не уточняя ничего и потом споря о том, что он сделал как написано, а не так как надо, то ничего хорошего в этом нет.
Kyushu
00.00.0000 00:00+1Хорошие экзаменаторы спокойно относятся к уточняющим вопросам. Их ответ всегда неизменен - в условиях задачи это не указано.
comdivuz
00.00.0000 00:00Молодой человек, видимо не проводящий сам собеседования. В этих вопросах и есть самая соль. Я часто задаю что-то что человек ЗАВЕДОМО не знает из серии "у нас была такая-то проблема и мы умудрились ее решить, проломав всем коллективом голову месяц, можете сейчас за 10 минут каким-то образом предложить решение?" и смотрю только на вопросы и на направление мыслей. Умение в таких ситуациях отбрасывать из головы лишнее, сосредотачиваться на проблемах и ограничениях, умение задать точный и действительно что-то значащий для выводов вопрос и при этом не терять присутствия духа - это и есть тот кандидат, который мне предпочтительней того, у кого этих качеств нет, даже если он более хард-скилловый в данный момент времени. Потому что хардскиллы нарабатываются со временем, а вот эта общая способность размышлять, коммуницировать и справляться со стрессом - нет
sanapad
00.00.0000 00:00Готов ответит на вопрос "что она проверяет?". Она проверяет способность кандидата быть внимательным и знание о том, что такое целые числа.
В дано было ясно сказано, что даны "целые числа" (слово "положительные" не использовалось) и диапазон [1, N]. Возьмём пример, N = -100, диапазон [1, -100]. Соответственно, на середине собеседования вариант с заменой знака числа отваливаются.
Cerberuser
00.00.0000 00:00+2А ещё указан размер массива, равный N+1, который исключает возможность N < -1. Причём при N < 2 ситуация вырожденная (пустой массив, массив из одного элемента и массив [1, 1] соответственно) - следовательно, при решении общего случая их можно не рассматривать.
Hlad
00.00.0000 00:00+77На выходе получаем специалиста, который отлично сортирует массивы, понимает в сложности и т.д. А потом ему приходится с 9 до 18 перегонять XML-ки...
DmitryZlobec
00.00.0000 00:00+2А что им больше делать , если оба знают алгоритмы, но беда в том что оба программировать не умеют. Решение на дженериках и стримах было бы похоже на правду, а так это какой-то шарообразный конь в вакууме.
comdivuz
00.00.0000 00:00Ну наверное на собеседовании не один такой вопрос используется. К тому же опять какие-то "оба знают алгоритмы, как выбрать". А я Вам скажу как - HR спросит у тимлида - кто тебе в целом больше понравился, с кем работать готов? - а тут не может уже быть совсем двух равных кандидатов
shornikov
00.00.0000 00:00+6Ну раз у вас такие сложные задачи, стоит пересмотреть мои требования к ЗП. Особенно стоит - если "вы уменьшились и находитесь в миксере". За риск на рабочем месте.
atygaev
00.00.0000 00:00всего до 18? некоторым приходится это делать до 22, иногда даже с JSON по середине.
AlexXYZ
00.00.0000 00:00+1>>Кандидат: А там точно будут повторяющиеся числа?
>>Это плохой уточняющий вопрос, ведь мы уже знаем, что размер массива N+1, а уникальных элементов в нем только N
А почему это плохой вопрос? Всегда есть нюансы. Вот так убеждаешь себя, что должно работать так, а не иначе, а потом не можешь поверить, почему вдруг в этом месте обнаружилась ошибка. Например, N какого типа? И вот тут начинаются сюрпризы.
ftdgoodluck
00.00.0000 00:00+2это значит, что человек идет уточнять постановку задачи даже не потратив 1 минуту на ее осмысление
commanderxo
00.00.0000 00:00+21Если в в одном месте требований говорится что в кластере 5 серверов, а на другой странице указывается что данные обрабатываются в 6 потоков, то опытный инженер должен:
- Начать прикидывать какому серверу попадётся двойная нагрузка, ибо Дирихле и всё такое прочее
- Переспросить заказчика, потому как техзадание нередко пишется по частям, разными людьми и в разное время?
Spaceoddity
00.00.0000 00:00зачем прикидывать? надо реализовывать начинать - всякие нюансы на этапе сдачи проекта выяснятся
Didimus
00.00.0000 00:00А что делать, если просят за 2 взвешивания найти фальшивую монету из 9?
Survtur
00.00.0000 00:00+2Уточните, чем фальшивая монета отличается от других? Вдруг цветом.
А известно сколько там фальшивых, или достаточно найти любую из фальшивых?
А на чём можно взвешивать?Didimus
00.00.0000 00:00-2А неважно чем отличается. Главное, что информации недостаточно, Log2(9) > 2, потому решить не удастся.
Нужен еще хотя бы 1 бит информации, например, знание, что фальшивых ровно 1 штука
wataru
00.00.0000 00:00+1Если знать, легче ли фальшивая монета, то как раз все хватает, ведь вариантов исхода одного взвешивания три: левая часть легче, правая часть легче, части равны по весу. 3*3 = 9 — теоретически достаточно информации от двух взвешиваний для нахождения одной из 9 монет.
Didimus
00.00.0000 00:00+2Знание, легче ли она всех остальных, это и есть недостающий бит информации.
Alexandroppolus
00.00.0000 00:00Обычно в формулировке это всё сказано.
Кстати, если неизвестно, легче или тяжелее фальшивая монета, то за n взвешиваний можно найти фальшивую среди (3^n - 1)/2 монет, но нужна вспомогательная настоящая. При условии, что фальшивая только одна, конечно.
Didimus
00.00.0000 00:00+1Я как раз привел пример, когда человек, не понимающий задачу, дает неправильное условие
iig
00.00.0000 00:00+1Log2(9) > 2, потому решить не удастся
Нужен еще хотя бы 1 бит информации
О, да вы математик! А скажите ещё что-то по математически ;)А можно немного более развернуто? Log2(9) , няп, потому что при взвешивании на чашечных весах выборка делится на 2. Но решается задача только если мы знаем что фальшивая монета легче и она ровно одна - тогда можно делить на 3. Многовато для 1 битаинформации.Didimus
00.00.0000 00:00+1Количество микросостояний, реализующих данное макросостояние, иначе говоря, энтропия в битах
qw1
00.00.0000 00:00+1А неважно чем отличается. Главное, что информации недостаточно, Log2(9) > 2, потому решить не удастся.
В этой задаче каждое взвешивание даёт более 1 бита информации, т.к. возможно 3 исхода: левая чашка тяжелее, правая тяжелее, чашки равновесны. Так что задача решаема.Didimus
00.00.0000 00:00Так как мы не знаем, тяжелее она или легче, нам эта информация бесполезна
qw1
00.00.0000 00:00Замечание в том, что формула
Log2(9) > 2
составлена по каким-то домыслам, и вывод из неё ошибочен.Знание, легче ли она всех остальных, это и есть недостающий бит информации.
По формуле выходит, что для случая 27 монет, 4 взвешишаний недостаточно (log2(27) > 4), но якобы «добавляя 1 бит информации» о весе фальшивой монеты, уже достаточно?
DirectoriX
00.00.0000 00:00например, знание, что фальшивых ровно 1 штука
Если в задаче не сказано сколько монет фальшивые, и при этом не указано в какую сторону они отличаются, то в общем случае у задачи решения вообще нет. Вот вам дали n монет, из них от 1 до n-1 фальшивых (как-то отличаются по весу), найдите их. Вам недостаточно только взвешиваний, вы сможете лишь разделить монеты на две категории (или сказать, что все одинаковые, если фальшивых может быть от 0 до n), но всё равно не узнаете, где настоящие. Предельный пример: 2 монеты. Вы из условия знаете что ровно одна из них фальшивая (0<Ф<2), а дальше что?
iig
00.00.0000 00:00+1Задач на взвешивание не так и много. Просто запомнить ;)
Norgorn
00.00.0000 00:00+7Решение настоящего инженера! А чтобы не запоминать - посмотреть в Справочнике задач на взвешивание)
iig
00.00.0000 00:00+1А какие полезные свойства кандидата показывает умение решить подобные задачи? Какая реальная задача может свестись к задаче с 9 монетами? Дубликаты в массиве это хоть немного напоминает валидацию входных данных ;)
comdivuz
00.00.0000 00:00Вопрос не то чтобы плохой, скорее он симптоматичный. Но надо понять симптом "чего" - не понимания постановки? просто невнимательности? переусложнения?.
Я бы ответил на такой вопрос "поясните, не совсем понял, мне казалось в задаче все прозрачно, может я чего-то не замечаю?"
Далее варианты такие
1. человек вчитывается и говорит "а тут N+1, а числа тоже 1..N", ок тут точно хотя бы 1 повтор - это мелкий залет совсем, такой на тему "резиновой уточки"
2. человек говорит "тут может быть ловушка с типами данных, например равен ли float64(2.0) числу int32(2), потому что хотя с точки зрения математики - это все еще целые числа, для кода это все же нечто различное" - я бы понял, что этот вопрос результат некоторого избыточного усложнения, с другой стороны ничего некорректного в этом нет. Я бы сказал в ответ, что тип не имеет значения, важна только "чистая математическая сторона" int(2)==float64(2.0) - это я не буду считать залетом
3. человек просто перечитывает задачу и говорит - "ну тут вообще нет никакой информации - есть там повторы или нет" - залет - просто не умеет читать условия в абстрактном представлении с - N там, множествами и прочим - признак конкретного мышления или очень и очень неподвижного мышления
То есть меня устроит вариант - что он просто понял, что там есть повторы или вариант 2 с каким-то усложенением, меня не особо напряжет вариант 1 и очень напряжет вариант 3.
Если автор рассматривал этот вопрос только как вариант 3 - то кончено это очень плохой вопрос.
ammo
00.00.0000 00:00+101На этом этапе большинство кандидатов сдаётся
Это не сдаются, это понимают, что
1) интервьюер - самовлюбленный чудак на букву м, выучивший перед интервью 30 вариаций одной и той же задачи плюс решения к ней, и сейчас с наслаждением наблюдающий, что "глупенький кандидатишка" этих решений сходу не называет
2) в команде с таким человеком и в компании, ставящей таких людей проводить интервью, они работать не хотят
lgorSL
00.00.0000 00:00+17А самое весёлое, когда ждут какое-то одно решение, получают другое и потом не могут его понять. И вообще, вот это постоянное усложнение задачи раз за разом выглядит как издевательство. Ты решил, но сейчас усложним и так будет до тех пор, пока не сдашься. Причём последние вариации часто совсем синтетические и в реальной жизни вряд ли встретятся.
Например, мне как-то раз дали задачу с N+1 числом, и в нём хотя бы по одному есть каждое число от 1 до N. Я беру и говорю - сумма чисел от 1 до N - (N+1)*N / 2 можно просуммировать и легко найти "лишнее число". Но ревьюверу это решение не понравилось, он захотел поломать мой план и сказал, что в массиве N+2 элементов. Я в ответ предложил посчитать не только сумму чисел, а ещё сумму квадратов чисел. Тут поломался уже ревьювер, которому я потом кучу времени объяснял, как это работает, а он буквально в упор не мог понять очевидных вещей.
event1
00.00.0000 00:00+6По идее, если кандидат поставил интервьюера в тупик своим ответом и смог вывести его из тупика дальнейшим пояснением, то это хорошо и засчитывается кандидату в плюс. Если интервьюер не мудак и контора не мудацкая.
1110001111
00.00.0000 00:00+1Нужно делать как при сдаче на краповый берет: если претендент уложил краповика в спарринге, то у него отнимают берет. Так что если кандидат завалил тебя самого - иди в джуны)
StupidMouse
00.00.0000 00:00И вообще, вот это постоянное усложнение задачи раз за разом выглядит как издевательство.
при том, что действительно толковых усложнений или технически тонких крайних случаев не было рассмотрено.
к примеру, что если N = +Infinity? или N не менее 1е12, а сам массив размазан по M веб сервисам, с несуществующим апи, но заказчик готов выкатить любой, только сформулируйте требования ...
Kondrogar
00.00.0000 00:00+2Больше скажу. Выучил задачу и решение, а потом представил себя с этими знаниями, как он классно отвечает за кандидата
comdivuz
00.00.0000 00:00А мне лично только с такими и нравится работать действительно по-настоящему, кто видит глубину в работе и что есть всегда не один только какой-то очевидный вариант.
binque
00.00.0000 00:00+3Последнее решение не сработает, если массив не является связным списком. Простейший пример: [0, 1, 1]. Функция выдаст ответ 0, верный ответ — 1.
VladimirFarshatov
00.00.0000 00:00+2Вот тоже на этом споткнулся и не понял почему последнее решение стало решением.
aamonster
00.00.0000 00:00+14Я бы сказал, задачка интересная, но для собеседования подходит крайне плохо. Много этапов вида "додумается/не додумается", но при этом ни то, ни другое не даёт вам достаточно информации о кандидате. Лучше уж дать задачку, которую мало-мальски вменяемый кандидат точно решит приемлемым образом, и пообсуждать с ним всякие модификации задачи.
sairus777
00.00.0000 00:00+14Подход нормального экзаменатора: сделать задачник по каждой компетенции, и спрашивать по разным компетенциям из списка задач. Можно даже публиковать такой задачник.
Подход автора статьи: "а что это у меня в кармане?". Это такой тип задач, которые автор сам когда-то там упорно шлифовал, что оно у него отпечаталась в голове (или на другом каком месте тела). И теперь этот кто-то стал загадывать это другим...
Nalivai
00.00.0000 00:00+78Шел <current year>, конторы продолжают собеседовать будто они жюри в олимпиаде по программированию.
Толку от всех этих задач слегка больше чем попросить кандидата двойной тулуп станцевать или арию спеть. Тоже сложный навык, не все умеют.
ioncorpse
00.00.0000 00:00Я бы взял того, кто сказал бы: сделаю N проходов наивно, а если можно взять N памяти, то два прохода. А вот если это конкретная задача - давайте сядем, обсудим детали.
kazimir17
00.00.0000 00:00+18А если кандидат сразу нашел все решения просто потому, что решал эту задачу ранее, это все еще хорошая задача или нет? И какую полезную информацию это несет компании?
terraplane
00.00.0000 00:00+25Не хватает "Неплохо. Вы справились, мы готовы предложить вам позицию разработчика в нашей компании и оклад 60 тысяч рублей в месяц".
Ksoo
00.00.0000 00:00+11Обычная задача на проверку насколько кандидат напрактиковался в решении таких задач.
Для собеседования лучше вообще ее не использовать, либо остановится после hashMap.
Alexandroppolus
00.00.0000 00:00+4Задача красивая, но, имхо, не для собесов - слишком творческая, хороший кандидат может не догадаться (особенно в "напряженной" обстановке собеса, где кажется, что время улетает со сверхзвуковой скоростью).
И разумеется, ничто не ново на хабре: https://habr.com/ru/company/JetBrains-education/blog/235855/
acordell
00.00.0000 00:00Я бы добавил, что в подобных задачках есть еще одна важная составляющая - как кандидат объясняет как решил. Ну или что именно у него не получается. Все же, плохая коммуникация весьма неприятная вещь в команде.
vconst
00.00.0000 00:00+23Ожидал увидеть что-то на топологию - типа такого
видеть что 
Fedorkov
00.00.0000 00:00+7Меня на одном собеседовании попросили развернуть генеалогическое дерево по поколениям.
Я, незадолго до этого переиграв в Crusader Kings, решил задачу с учётом возможного "ромбовидного наследования"...
igrishaev
00.00.0000 00:00+2Все просто. Первый мужик надевает сразу два презерватива, имеет секс первой женщиной, снимает, затем со второй. Второй мужик надевает внешний презерватив от первого мужика, имеет секс с первой Ж, затем надевает сверху второй П и имеет секс со второй.
Мне перезвонят?
Cerberuser
00.00.0000 00:00+1Так ведь в задаче расклад 3М1Ж, а не 2М2Ж...
igrishaev
00.00.0000 00:00Плохо прочитал. Я решал эту задачу с 2М2Ж, над 3М1Ж нужно подумать. Но первый шаг однозначно такой.
Alexandroppolus
00.00.0000 00:00+3Там один презик надо будет вывернуть наизнанку. Итого, первый надевает А и поверх него В, второй надевает В, третий надевает вывернутый А и поверх него В.
commanderxo
00.00.0000 00:00+20Отличная задача, по ответу сразу видно кто перед нами:
- Олимпиадник — Задача решается элементарно, если помнить, что презервативы можно надевать по два и выворачивать наизнанку
- Cloud Architect — Ребят, чем трахаться с хитрыми алгоритмами, лучше добавить чуть денег и закупить больше ресурсов. Сразу планируем минимум по две проститутки в каждом датацентре, плюс резервные в других регионах — мне же потом спасибо скажете, когда вас в командировку пошлют.
- Поклонник GoF и прочих шаблонов — Держите меня семеро, сейчас я всем покажу, как правильно писать EnterpriseSolutionCondomProviderStrategyFactory!
- Питонист — pip install more_condoms
Cerberuser
00.00.0000 00:00+7Старый циничный сеньор: "Это вы так описали типичный расклад сил на проекте? Один разработчик, два менеджера, три заказчика?"
vconst
00.00.0000 00:00+3- Охранник на проходной ЦОД — один наденет презик и она сделает ему минет, а двум другим просто подрочит
gatoazul
00.00.0000 00:00+6А реалист сразу заметит, что на практике это работать не будет. Два надетых одновременно презерватива закончатся тем, что один соскочит, а выворачивание с биологическими жидкостями внутри совершенно не стерильно.
ilvlapol
00.00.0000 00:00+1Есть такая-же задача про трех хирургов, пациента и две пары перчаток.
Первый мужик надевает два презерватива. Второй надевает один, тот, который был «внешним» на первом мужике. Третий надевает опять два презерватива, при этом выворачивает тот, что был «внутренним» на первом мужике, наизнанку.
playermet
00.00.0000 00:00+3Все это конечно очень интересно, но у подобных задач при переходе к практике могут возникать конфузы. Решение в лоб может оказаться эффективней при реализации на конкретных языках, причем даже при достаточном для некоторых практических применений количестве данных. Например, алгоритм может иметь низкую энтропию условных переходов, компилятор может удачно подобрать SIMD инструкции, плюс расходы на работу с памятью, зависимость от реализации контейнеров стандартной библиотеки, и куча других факторов. Единственный способ узнать реальную эффективность - это написать код и прогнать по бенчмаркам, которые тоже нужно правильно уметь писать.
DirectoriX
00.00.0000 00:00+5Более того, вся эта О-нотация отвечает на вопрос «какой из алгоритмов будет работать быстрее в пределе», то есть если мы будем повышать N до бесконечности. То, что NlogN может иметь, например, константный множитель хоть в полмиллиарда (и тем самым быть медленнее условного 3 N^2 на подавляющем количестве реальных случаев) почему-то любят забывать.
wataru
00.00.0000 00:00Конечно, надо оценивать, какое там у вас будет N. Но за очень редким исключением, если у вас N хотя бы 100, O(n log n) будет на порядки быстрее O(n^2). Вот между O(n log n) и O(n) уже разница размывается, да.
playermet
00.00.0000 00:00Еще больше смазанности, когда параметров два или больше. Где один, например, количество данных, а другой - размер окна или алфавита, которые значительно меньше количества. И ты вроде пытаешься уменьшить часть, на которую умножается зависимость от количества, а она не уменьшается. При этом еще и дополнительные ограничения возникают.
taalo
00.00.0000 00:00Плюс, если размер массива больше кэша процессора (а оптимизировать по памяти имеет смысл для сильно больших массивов), конструкция:
fast = arr[arr[fast]];
приведет к постоянным промахам и гарантировано сделает производительности больно.qw1
00.00.0000 00:00Есть вариант, где нет этой проблемы?
Подсчёт «в лоб»counts[arr[i]]++
ещё хуже, потому что запись генерирует лишний трафик при вытеснении изменившейся линии из кеша.DistortNeo
00.00.0000 00:00Можно организовать массив в виде хэш-таблицы, где число бакетов равно числу кэш-линий минус одна. В итоге у нас получается одна очередь линейного чтения и N-1 очередей линейной записи. Дальше обрабатываем бакеты по очереди. Если бакет целиком влезает в кэш, то используем наивный алгоритм. Если не влазит, то дробим дальше. Правда, такой алгоритм будет плохо работать, если один и тот же элемент будет повторяться очень много раз.
qw1
00.00.0000 00:00Допустим, у нас M=4096 (N уже занято в условии задачи) бакетов, по числу кеш-линий. Как я понимаю, индекс бакета — хеш от очередного X=arr[i], и в каждом бакете надо организовать список пар (X,C), где C — количество найденных повторов числа X (либо только список иксов, если нужен только факт повтора, а количество не важно).
Размер бакета = размеру кеш-линии = 64 байта. То есть, в бакет поместится 4 (если со счётчиком C) или 8 значений. Бакеты будут очень часто переполнятся, что в этом случае надо делать? Надо мержить бакет из кеша с бакетом в основной RAM. А это или сортировка, или ещё какой алгоритм, который нам скушает кеш-линии, занятые другими бакетами. Ведь бакеты не будут наполнятся одновременно. Надо либо опустошать только переполненный (и использовать кеш-линии других бакетов, что ставит всю идею под вопрос), либо скидывать вообще все 4096, если заполнился хотя бы один, что может быть очень неэффективно.
Очень сомнительно, что будет выигрыш.DistortNeo
00.00.0000 00:00Сорри, накосячил в плане терминологии. Понятие "число кэш-линий" стоит читать как "cache associativity". Короче, моя идея сводится к тому, что благодаря ассоциативности кэша мы можем одновременно читать и писать несколько потоков данных. По каком принципу формировать эти потоки данных, значения не имеет. Важно, чтобы одинаковые числа попадали в один поток.
qw1
00.00.0000 00:00Я всё равно не понимаю решения целиком. Допустим, мы поделили данные на M потоков по какому-то хешу и выполнили запись. Дальше что делать с этими записанными линейками? Есть алгоритм, который тоже будет обрабатывать их линейно, а не скакать рандомно между ними? Вырисовывается некий mergesort, со сложностью N*logN и довольно большой константой, выполняющий многократные прохождения по отрезкам (сначала данные многократно режем на куски, потом сливаем, потом делаем финальный проход и определяем дубликат).
DistortNeo
00.00.0000 00:00Дальше что делать с этими записанными линейками?
Если они целиком влезают в кэш, то уже можно обрабатывать линейным алгоритмом, предусматривающим случайный доступ. Если не влезают в кэш, то дробить дальше.
Вырисовывается некий mergesort
Типа того, да. Вот только, во-первых, сливать данные не нужно. А во-вторых, всё зависит от объёма данных и технических характеристик железа.
Если константа у алгоритма O(N) из-за случайного доступа больше, чем у O(N log N), где log N — это совсем небольшое значение (2-3), то алгоритм с O(N log N) будет быстрее. А если массив ещё в память не влезает, то выбор однозначно становится в пользу последнего.
thevlad
00.00.0000 00:00То что хуже совсем не очевидно, надо мерить. У этого load-store нет прямых зависимостей поэтому может не плохо лечь на типичное OoO.
qw1
00.00.0000 00:00Как это нет зависимостей? Пока не закончено чтение arr[i], невозможно начать инкремент ячейки в counts.
thevlad
00.00.0000 00:00+1Для OoO это практически эквивалентное "нет зависимостей", самое паршивое это когда инструкции сцеплены друг за другом, когда результат одной является аргументом другой и так по всей цепочки. (проблема критического пути в графе исполнения инструкций) А вот такие относительно независимые куски, должны колбаситься на ура.
qw1
00.00.0000 00:00Так они и сцеплены
counts[arr[i]]++;mov rdx, QWORD PTR arr[rax*8] add QWORD PTR counts[rdx*8], 1thevlad
00.00.0000 00:00Они сцеплены но их две, а не 200. Собственно я об этом и говорил. Все эти небольшие сцепленные цепочки будут в OoO выполняться практически "параллельно", скрывая latency.
qw1
00.00.0000 00:00А, вот в чём идея — развернуть этот цикл. Кстати, от gcc не получилось добиться векторизации этого цикла. Наверное, он не может доказать, что массивы arr и counts не пересекаются.
thevlad
00.00.0000 00:00+1Не, я скорее про то, что оно само разворачивается "внутри процессора" за счет спекулятивности и OoO(out-of-order execution). Инструкции не исполняются последовательно уже со времен Pentium 2/3.
qw1
00.00.0000 00:00На размерах, где оптимизация реально нужна (N > 1e9), каждая итерация — гарантированный cache miss, +200 cycles, и там уже не до OoO.
thevlad
00.00.0000 00:00OoO как раз в таких случаях и помогает больше всего. Размер rename файла у современных процессоров в районе ~200, то есть это то сколько зависимостей может быть одновременно "в воздухе".
thevlad
00.00.0000 00:00+1Ради науки, провел эксперимент для 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.665800https://gist.github.com/xmvlad/f5b9a13fa56007d215343cb3ca2c104a
qw1
00.00.0000 00:00Необъяснимо. Допустим, в процессоре действительно параллельно работает до 200 итераций и каждая итерация ждёт свои данные. Но каналов доступа в RAM не 200 же.
thevlad
00.00.0000 00:00Каналы влияют на пропускную способность, которая как раз обьяснимая, где то в 5 раз меньше пиковой. А в load и store юнитах есть очередь, именно ее глубина и определяет количество возможных одновременных запросов "в полете", она тоже гдето в районе 40 на каждый юнит.
qw1
00.00.0000 00:00Допустим, 1 запрос к памяти 200 тактов, а каналов предположим 4, мы не сможем читать в среднем быстрее, чем 1 чтение за 50 тактов, независимо от глубины очереди.
thevlad
00.00.0000 00:00+2С чего бы? ) 200 это latency, а throughput то лучше, а количество одновременных запросов и количество каналов, вещь не взаимосвязанная, о чем я вам уже писал. Немного наврал в подсчетах максимальной производительности, тест прогонялся за 7 секунд, что дает в пике для DDR4-2600 147 ГБ на тест. Единичный burst для DDR4 насколько я понимаю это 64 байта, чтобы давать в пике 21GB/s, надо уметь колбасить 352M запросов в секунду. За время теста(7 секунд) максимум 2.4G запросов, при количестве элементов 1G. Так что все вполне сходится.
farafonoff
00.00.0000 00:00+2Требования к константности памяти на практике бывают или в микроконтроллере, или если данных очень много.
В случае с микроконтроллером разница между N и N^2 на практике не большая, а если данных действительно очень много - там и подход совершенно иной.
Xambey97
00.00.0000 00:00+10По-моему подобная алгоритмическая 'дичь' (и эта еще довольно простая) проверяет скорее нервы кандидата, чем его опыт. Имхо, я бы такое дал разьве что джуну решать или человеку идущему на должность, где он будет много таким заниматься или схожим (найм кандидатов, криптография и тп), но точно не рядовому сеньору, задача которого пилить фичи в срок и 'перекладывать json'ы' без рисков сломать всю систему… Это что-то на уровне «сделайте нам не оплачиваемое тестовое на 10 часов работы». Мне лично об уровне кандидата становится все понятно по его ответам на общие вопросы, кругозору по технологиям, профильным технологиям вглубь, его опыте, сложных решениях которые он делал, на эти вопросы книжечки «как пройти собеседование в гугл» ответов липовому разработчику не дадут. Через 30-40 минут, понимаешь точно каков опыт человека, потом еще обсуждаете профессиональные темы и решения которые кандидат может предложить для решения проблем, которые ему предлагают (возможно даже реальных проблем в компании). Это гораздо лучше и ближе к реальной работе, чем спрашивать то, что человек использует разьве что на собеседованиях… Ей богу… А то потом смотрим на «прекрасно» работающие сервисы от гугла, яндекса и тп «мега крутых компаний, состоящих из инженеров-алгоритмистов», и невольно возникают вопросы. Я лучше возьму на работу чудилу-самоучку, который может много рассказать о разных технологиях и понимает сильные и слабые стороны разных инструментов, чем любителя методичек по прохождению собеседований и нарешиванию 100500 заданий с литкода… Но это все конечно субъективно, так что на вкус и цвет, я вот так думаю
habraabr
00.00.0000 00:00+2Эта дичь стала своего рода этикетом. Который как ни странно не имеет никакого отношения к реальности. Почему? Мы бы не получили настолько тормозной веб если бы фреймворки писали реальные короли алгоритмов. Более того — те самые индусы (типа автора), которые лезут в менеджмент не прочь и дальше плодить штаты эффективных программистов, которые будут распускать в сложные времена.
engineering at Instagram Facebook
Тут я конечно проиграл вспомнив их тормозной React
Finesse
00.00.0000 00:00+4Это набор вопросов на вакансию «специалист по алгоритмам», а не просто «программист».
Интервьюер: Можно решить эту задачу, не используя лишнее пространство?
Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.
Интервьюер: Тогда временная сложность вырастет до O(NLogN). Что ещё можно сделать?
Разве есть алгоритмы сортировки, которые требуют
O(N*log(N))времени и меньшеO(log(N))памяти?
AlexKimen
00.00.0000 00:00+1Мне кажется, что интервьюер ошибается или намеренно вводит в заблуждение.
По условиям: "массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N]. "И тут же интервьюер говорит:
Кандидат: Только одно число повторяется?
Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].
Если даны элементы в диапазоне [1, N], то при размере массива N + 1, будет повторяться только 1 элемент. Так что пример [4, 3, 3, 1, 1, 2] некорректен, т.к. повторяются два элемента.
И уж если говорить об оптимальном по времени и затратам ресурсов поиске в большом массиве такого типа, то ключевой вопрос в том, насколько случайность распределения чисел в исследуемом массиве близка к нормальной.
Cerberuser
00.00.0000 00:00+6"Элементы в диапазоне [1, N]" - не обязательно значит "все элементы диапазона". В последнем примере, все элементы содержатся в диапазоне [1, 5], длина массива 6 - под условие подходит.
Aleshonne
00.00.0000 00:00-3В последнем примере все элементы содержатся в диапазоне [1, 4] (квадратные скобки — включающие). Корректным примером был бы массив [5, 3, 3, 1, 1, 2].
Ogra
00.00.0000 00:00+1А что, диапазон [1,4] не входит в диапазон [1,5] ?
Aleshonne
00.00.0000 00:00-4А ещё он входит в диапазон (-∞, +∞), как и все другие числовые отрезки. Давайте теперь только этим диапазоном пользоваться во всех случаях. Например, указывая вилку зарплат в вакансии или время варки макарон в инструкции.
Похоже, что на традиционную практику, когда, давая ограничения на какую-то величину, используют диапазон минимально возможного размера, интервьюер наплевал специально, чтобы сильнее запутать кандидата и показать своё превосходство в умении решать конкретную задачу.
PS Подойдите к любому человеку и попросите сказать, в каком диапазоне лежат элементы массива [4, 3, 3, 1, 1, 2]. Полагаю, что вероятность ответа «от 1 до 4» будет гораздо выше, чем «от 1 до 5».
WraithOW
00.00.0000 00:00+4Если на пачке носков написано "желтые" — это не означает, что в пачке есть носки всех цветов, классифицируемых как оттенки желтого. Если говорят, что в компании работают китайцы — это не значит, что в компании работает всё население КНР. Призыву на срочную службу подлежат граждане от 18 до 27 лет (или уже до 30?), но это не значит, что каждая партия новобранцев содержит как минимум одного человека на каждый возраст.
Подойдите к любому человеку и попросите сказать, в каком диапазоне лежат элементы массива [4, 3, 3, 1, 1, 2]
Подмена тезиса, минус социальный рейтинг. Любой человек не в курсе условий исходной задачи, а кандидат — в курсе. Если я покупаю мешок конфет, на котором написано "ассорти" — это значит, что комбинация внутри может быть разной. Ваш вопрос будет аналогом того, что я возьму из этого пакета "Мишку косолапого", покажу его прохожему и спрошу, пачку каких конфет я купил.
Aleshonne
00.00.0000 00:00-2Ваш вопрос будет аналогом того, что я возьму из этого пакета "Мишку косолапого", покажу его прохожему и спрошу, пачку каких конфет я купил.
Вы, собственно, мои слова и подтверждаете. У человека попросили пример. Он привёл неудачный пример. У кандидата на основе неудачного примера может сложиться ошибочное мнение об условиях задачи (особенно если они не записаны, а были озвучены устно), что в массиве числа идут без пропусков. Кстати, обратите внимание, что в статье вообще ни разу не встречается массив с пропущенными числами, а, например, последний метод (поиск циклов в списке) в этом случае работать не будет.
wataru
00.00.0000 00:00Почему же не будет-то?
Aleshonne
00.00.0000 00:00Да это, собственно, автор поста написал:
Это решение не сработает, если повторяться может несколько чисел.
Наличие пропусков означает либо повтор одного числа более 2 раз, либо повтор нескольких разных чисел.
wataru
00.00.0000 00:00У автора там скопипасшено откуда-то криво. Это решение отлично работает даже если повторяется несколько чисел (находит какое-то одно повторение, да, но в условии как раз надо найти любое).
Aleshonne
00.00.0000 00:00+1Прогнал полный перебор всех вариантов для массивов из 9 и 10 элементов, каких-либо проблем не произошло. Так что согласен, решение, судя по всему, работает без проблем для любого такого массива. Правда, мнение о статье у меня от этого не улучшилось.
wataru
00.00.0000 00:00+1Тут не надо полного перебора. Решение доказывается логически. В массиве числа от 1 до N. Мы начинаем с индекса 0 и сможем до бесконечности переходить к индексам, записанным на текущей позиции. Но различных положений всего N (кроме шага в начале, где мы на индексе 0). Значит рано или поздно мы зациклимся — придем в ранее посещенную позицию. Но мы в эту позицию первый раз пришли из 0. А потом ни разу 0 не посетив, поэтому мы второй раз прошли по другому пути. Пути детерминированны, а значит в эту позицию ведут 2 разных пути, т.е. в нее входят две стрелочки, т.е. это число записано в двух разных позициях в массиве — мы нашли повторение. Нигде тут не требуется, чтобы были все числа или чтобы повторялось только одно. Надо только, чтобы в массиве были числа не больше N и не меньше 1, чтобы переход можно было сделать всегда.
Aleshonne
00.00.0000 00:00Корректность алгоритма не гарантирует корректности кода, это алгоритм реализующего. Возможно, код, приведённый в статье, зацикливался на каком-то варианте массива с более чем одним повторяющимся числом, из чего автор и сделал вывод о невозможности его использования его для таких данных. Плюс, если у вас не все числа из диапазона, то в массиве есть элементы, в которые вы вообще не попадёте при обходе, это тоже могло ввести автора статьи в заблуждение.
wataru
00.00.0000 00:00Ну и код, по идее, надо также логически доказывать. Тут надо на бумажке чуть чуть порисовать, чтобы понять, почему если после первого совпадения начать одним указателем с начала, то они встретятся на первом элементе цикла, но в остальном код достаточно тривиальный, чтобы было очевидно, что он будет работать.
qw1
00.00.0000 00:00Похоже, что на традиционную практику, когда, давая ограничения на какую-то величину, используют диапазон минимально возможного размера, интервьюер наплевал специально, чтобы сильнее запутать кандидата и показать своё превосходство
Ну, например
Интервьювер: надо отсортировать массив из N чисел.
Кандидат: какие ограничения на N и на значения сортируемых чисел?
Интервьювер: N помещается в UInt16, числа помещаются в Int32.
Кандидат: дайте пример входа
… и теперь что, нужно давать пример из 65535 чисел, обязательно включающий 0x7FFFFFFF и -0x80000000? Или, вы считаете, задача так поставлена, что ей невозможно дать пример входных данных, помещающийся на одном листе бумаги?Aleshonne
00.00.0000 00:00+1Я считаю, что тип и диапазон — схожие, но всё же разные вещи. Я сомневаюсь, что кто-то может неправильно понять ваше утверждение, но не сомневаюсь, что приведённое в посте утверждение вкупе с приведёнными там же примерами можно понять неправильно. Даже тут, в комментариях, есть как минимум два человека, которые неверно поняли условия задачи. При этом задача была записана, а они, скорее всего, находились в спокойной обстановке, а не на интервью в условиях стресса (и возможно, усталости, если вопрос не первый).
Конкретно в вашем случае хорошим будет любой пример, не имеющий в себе явных закономерностей, из которых кандидат может сделать для себя неверные выводы об особенностях входных данных.
qw1
00.00.0000 00:00Я считаю, что тип и диапазон — схожие, но всё же разные вещи
Типичные формулировки задач, что в спортивном программировании, что в реальной жизни: 1 <= N <= 10000
Чем не диапазон? Тут решение о выборе подходящего типа остается за кандидатом.Aleshonne
00.00.0000 00:00В спортивном программировании, как раз, границы диапазона в тестовых данных часто попадаются. А в реальной жизни всё вообще сложно, там границы обычно берут с некоторым запасом, чтобы в случае чего всё продолжило работать нормально.
qw1
00.00.0000 00:00Так у вас претензии не полному тестовому набору, а к поясняющему примеру в условии задачи. Там обычно до границ не доходят.
Sild
00.00.0000 00:00+1Мне вот нравится просить спроектировать виджет скорости скачивания файла. Как-то задали такую задачку в варгейминге лет 5 назад
Тут тебе
и алгоритмы (временная сложность на вставку, временная сложность на чтение, сколько памяти будет кушать)
и оптимизации (можно сделать агрегацию)
и вопросы для обсуждения (что мы хотим показывать пользователю в самом начале? Как часто нужно отображать изменения? и вообще что такое скорость скачивания?)
и многопоточка, если время останется (данные пушатся из разных потоков)
еще и по сетям слегка пройтись можно
Эх, хорошо тогда пообщались
Teamer_ol
00.00.0000 00:00+1А можете немного подробнее рассказать, как стоит рассуждать при решении такой задачи? Как в принципе стоит декомпозировать эту задачу?
Временная сложность на вставку и чтение будет зависеть от структур данных, которые будем использовать для хранения данных о загрузке? Что за оптимизации через агрегацию вы предлагаете использовать?
Буду рад, если дадите ёмкое пояснение. Спасибо.
Sild
00.00.0000 00:00+3Для начала я обычно даю шаблон интерфейса, с оговоркой что его можно менять
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 секунде)
Ну и в конце просим перестать бесконечно аллоцировать память в векторе, реализовав циклический буффер, а заодно поговорив про модель памяти (почему постоянные аллокации - это плохо)
Как-то кандидат предложил хорошее решение и без циклического буфера (там не было лишних аллокаций, константа на вставку и чтение, константа по памяти). Не помню само решение, но мой вариант решения точно не единственно верный)
Alexandroppolus
00.00.0000 00:00хорошее решение и без циклического буфера
там был связный список с переиспользованием элементов?
Sild
00.00.0000 00:00Вполне возможно, по сложностям с ним получается то же самое - а реализовать куда проще
Но тогда нужно обсуждать + и - связанного списка относительно вектора
Teamer_ol
00.00.0000 00:00Большое спасибо, теперь стало намного яснее, что вы имели в виду в предыдущем комментарии.
mixsture
00.00.0000 00:00Ну и термины вы используете. Как будто специально шифруете все от кандидата.
Пространственная сложность = сложность по памяти.Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне.
«Если количество получилось больше»: не «количество» -> сумма. А «чисел в этом диапазоне» -> как раз это количество. По аналогии с подобными выражениями sql.qw1
00.00.0000 00:00+7«Space complexity» — англоязычный термин. Хорошо, хоть не перевели как «космическая сложность».
mixsture
00.00.0000 00:00Пожалуй, можно выполнить бинарный поиск повторяющегося числа. Например, можно пройтись по списку и посчитать число целых чисел от 1 до N/2. Если количество получилось больше, чем чисел в этом диапазоне, мы поймём, что повторяющееся число находится в этом диапазоне.
Откуда тут «число ЦЕЛЫХ чисел»? разве тут есть с дробные/с плавающей запятой? Может имелось ввиду «положительных»? Но и это неверно. В исходном списке все числа целые и положительные, вы ввели невозможность менять список и невозможность использовать доппространство => списка с отрицательными никогда не появится.
Имхо, на этой части интервьювер сломался.
mixsture
00.00.0000 00:00+5Вообще, беда всех таких задач — их малонужность в реальной жизни (т.е. наверно есть единичные компании, где такое надо часто и там оправдан отбор. Но вот остальным 99,99% это не надо). Поэтому я все больше склоняюсь предлагать работодателям любителям поиграть в решение таких задач:
давайте я ее решу, но впишем в договор, что если подобной задачи не будет каждый квартал, то компания платит штраф 1 млн за то, что не смогла обеспечить работой, о которой говорила на собеседовании.
Почему-то мне кажется, что на этом месте сразу выяснится, что эта задача не такая уж и нужная.
GospodinKolhoznik
00.00.0000 00:00+2Интервьюер: Хорошо, переформулируем условие. В джире висит N+1 таска. Задача за линейное время найти дублирующиеся таски.
Кандидат: (вздыхая) Окай.
cartonworld
00.00.0000 00:00+10select title, count(*) from issues group by title having count(*) > 1;
bay73
00.00.0000 00:00+1Беда большинства кандидатов в том, что они не понимают в чем смысл собеседования. Они почему-то думают, что решение алгоритмических задач проверяет только умение решать алгоритмические задачи.
gandjustas
00.00.0000 00:00+3А что ещё проверяет?
bay73
00.00.0000 00:00-1Я так понимаю, что статью вы до конца не дочитали. А там это как раз указано.
gandjustas
00.00.0000 00:00+4Перечитал, там в 5 пунктах описано что "кандидат умеет решать алгоритмические задачи"
CKA304HUK
00.00.0000 00:00+5Сначала, не комментируя выбор задачи - подход через "найдем что-нибудь простое и очень понятное, и вместе с кандидатом докопаемся до центра земли" мне лично очень импонирует. Если вы можете позволить себе не обращать внимание на знание фреймворков - с моей точки зрения, только так и надо.
Выбор конкретно алгоритмической задачи как подопытной, а не более близкой к реальности "оптмизируем апи" может вызвать у нежной публики неприятие. Но, в защиту этого подхода: копание вглубь земли на примитивном алгоритме имеет, перед ковырянием в апи, одно простое достоинство - вам не нужно тратить время на прогружение кандидата в предметную область, а можно сразу говорить за программирование, практики, оформление и так далее.
kazimir17
00.00.0000 00:00Лично я считаю главной проблемой современной ИТ индустрии это НЕ погружение в предметную область, компании нанимают просто сферических программистов, в то время как хорошее знание предметной области может увеличить производительность труда на десятичные порядки.
CKA304HUK
00.00.0000 00:00+1Погружение в предметную область - это месяцы. На уровне интервью ты не сможешь погрузить человека в предметную область и попросить применить свои навыки в ее рамке.
Проверка умения же погружаться в предметную область натыкается на то же нежное "в нормальном процессе этим занимаются бизнес-аналитики, я буду переводить из английского в джаву".
Sild
00.00.0000 00:00Это очень хороший индикатор того, что человек может и хочет делать. Трансляторы из английского в джаву ведь тоже востребованы, просто нужно иметь ввиду что человек планирует тупокодить
farafonoff
00.00.0000 00:00+7Быстрое решение этой задачи требует знания (бесполезных) шорткатов, вроде двоичного поиска по значению, или алгоритма зайца и черепахи для связного списка. Писал двоичный поиск в продакшне 1 раз, связный список 0 раз.
С другой стороны даже если вы знаете шорткаты по написанию правильного апи - это же замечательно, апи нужно проектировать каждый спринт.
CKA304HUK
00.00.0000 00:00+1Мне всегда казалось, что простые варианты решения это задачи, вроде разворота индекса, или сортировки - их даже знать не надо, просто выводятся из общих соображений. Эта задача вообще не про сложность алгоритма - это про способность писать минимально-функциональный код и работать над его улучшением. В виде шортката через математику, так как предполагается, что на базовом уровне структуры данных знают все.
Правильный апи же разрабатывается под предметную область, с учетом развития и количества команд. Надо очень много бэкграунда распросить, чтобы его правильно задизайнить. Это (упражнение по выяснению ограничений и требований) - тоже прекрасное упражнение на интервью, но это упражнение занимает весь час влегкую. Я где-то слышал, что этот этап называют "системный дизайн".
farafonoff
00.00.0000 00:00+5Улучшение кода - расставить const где положено, а придумывание алгоритма это что-то из области озарений. Я бы не стал планировать собеседование с расчетом на 5 озарений подряд.
CKA304HUK
00.00.0000 00:00Возможно, мы ищем разных людей под разные задачи. Обычно, в моей практике, следовать известному шаблону бест практик (тот самый хрестоматийный перевод из английского в джаву) - достаточно неинтересная часть работы, которая доступна, при должной усидчивости, примерно всем.
Решение же нефункцональных требований к системе в целом - несколько более креативная часть, в которой без навыка озарения будет непросто.
gandjustas
00.00.0000 00:00+7Даже минусанул, потому что больше рекламы, чем пользы.
Последнее решение вообще лишнее, так как не универсальное. Просто автор решил повыделываться своим знанием алгоритмов.
Интересно с чего автор взял что есть решение лучше прямого подсчета? Только вместо hashmap надо применять bitarray(N), который будет требовать N/8 байт. Решение на bitarray может найти не только первое повторяющееся число, но и все повторяющиеся числа.
Если говорить о реальности применения, то решение O(N) по времени и O(N) по памяти выгоднее O(NlogN) по времени и O(1) по памяти.
thevlad
00.00.0000 00:00inplace radix sort, по времени O(N) и памяти O(1), не накладывает никаких дополнительных ограничений. Как тебе такое Илон Маск? ) (как его реализовать я конечно на собеседовании вряд ли вспомнил, но так это наименее безумный вариант. который к тому же уже где то "в интернете" наверняка реализован)
gandjustas
00.00.0000 00:00+1ну это не совсем так. Radix Sort имеет сложность O(NM), где N количество элементов в массиве, а N - количество разрядов. Если в массиве числа от 1 до N, то количество разрядов M = logN.
thevlad
00.00.0000 00:00Это так не работает, есть базовые предпосылки об устройстве "абстрактной машины". Иначе у вас даже банальное умножение со сложением будет не O(1). А если количество разрядов фиксировано(64 бита) то M для конкретной машины будет константой.
gandjustas
00.00.0000 00:00+1Обычно сложность в алгоритме сортировки считается как количество операций сравнения. При поразрядной сортировке это будет O(NM), где M - количество разрядов. Обычно M не зависит от N и может быть принято за константу. Но в этой задаче зависит.
thevlad
00.00.0000 00:00Да вы правы, согласен.
PS: хотя все равно не очевидно, так как N по условию размера массива, ограничено адресуемой памятью, которая константа и 64 бита. (а фиксированность и конечность памяти, является тем самым базовым предположением)
qw1
00.00.0000 00:00+1С таким подходом, и квадратичный, и кубический алгоритм — O(1), ведь N у нас константа, обязанная помещаться в 64 бита ))
gandjustas
00.00.0000 00:00А вы представьте что на пайтоне пишите и у вас не ограниченного размера целых чисел.
thevlad
00.00.0000 00:00Какой бы размер самих чисел не был, по условию у нас массив размера N. Но я согласен, с комментарием выше, что так считать, не корректно.
Fortistello
00.00.0000 00:00-1А никого не смущает, что после слов
массив неизменяемый и нельзя использовать дополнительное пространство.
сразу же идет решение, которое начинается с:
int low = 1, high = arr.length - 1; int duplicate = -1;т.е. с использования дополнительного пространства?
Или я что-то не знаю про программирование?
thevlad
00.00.0000 00:00+3Это "дополнительное пространство" имеет константный размер как функция от размера входного массива, то есть O(1). (а то что речь идет про O(1) понятно из контекста задачи)
PNSpasskiy
00.00.0000 00:00Я не программист, может мне кто-то объяснить, чем должен заниматься программист умеющий щёлкать подобные задачки? Ну там фронтенд или бек писать? Софт для микро контроллеров или банковское ПО? Как умение решать такие задачи влияет на работу программиста?
bay73
00.00.0000 00:00А где вы увидели, что на собеседовании проверяется "умение решать такие задачи"? На этом собеседовании проверили общие знания об алгоритмах и их сложности, умение задавать уточняющие вопросы, осознавать требования и способность подстраиваться под изменение требований. Ну и заодно посмотрели на то, как человек код оформляет.
iig
00.00.0000 00:00+1В реальные задачи на новой работе новый человек вкатывается не меньше недели. А это синтетический тест, который можно пройти за полчаса.
wataru
00.00.0000 00:00Конечно, именно такая задача с ограничениями на дополнительное место и неизменность входных данных — весьма искуственная. Такое может только в каких-то микроконтроллерах и вылезет. Но подобные алгоритмические задачки регулярно вылезают, например, при разработке webrtc и браузера хрома.
WraithOW
00.00.0000 00:00Но подобные алгоритмические задачки регулярно вылезают, например, при разработке webrtc и браузера хрома.
Даже проще бывает. Вот буквально вчера на ревью принесли — есть UI на клиенте, в нем список временных интервалов (начало + старт), нужно сделать валидацию — интервалы не должны пересекаться, пересекающиеся нужно подкрасить и добавить ошибку в результаты. Алсо это UI, поэтому надо чтоб быстро было, иначе FPS просядет. И с памятью надо поаккуратней, чтоб GC не стриггерить.
Busla
00.00.0000 00:00+3В типичной реализации адресной книги (например, gmail) есть функция поиска и объединения одинаковых контактов. В типичном фотоальбоме есть функция удаления одинаковых фотографий. Сколько-нибудь вменяемое ПО для организации логистики (посылки, курьеры) умеет находить и объединять доставки по близким маршрутам . Масса данных поступает по ненадёжным каналам и/или из ненадёжных источников, и может не только потеряться, но и задвоиться.
Тут скорее вопрос обратный: чем таким узконаправленным должен заниматься программист, чтобы не столкнуться на практике с поиском дубликатов?
Raimon
00.00.0000 00:00Хаха. Была похожая задача на районном туре олимпиады по программированию, лет эдак 20 назад. Там было условие, что все числа до N присутствуют. Решалась через простую сумму и сравнение с арифметическую прогрессию.
Я бы конечно не назвал это лучшей задачей, если только вы не нанимаете на работу пилить алгоритмы. Правда в этом случае задача слабовата. Не понимаю зачем делать жёлтый заголовок.
Классно писать алгоритмы в обычной жизни бекенд разработчика это 5% работы?
staskudashev
00.00.0000 00:00Есть однонаправленный список из структур. В нём random указывает на какой-то еще элемент этого же списка. Требуется написать функцию, которая копирует этот список с сохранением структуры (т.е. если в старом списке random первой ноды указывал на 4-ю, в новом списке должно быть то же самое – рандом первой ноды указывает на 4-ю ноду нового списка). O(n), константная дополнительная память + память под элементы нового списка. Нельзя сразу выделить память под все данные одник куском т.е. список должен быть честным, разбросанным по частям, а не единым блоком, как массив.
Alexandroppolus
00.00.0000 00:00В этой задаче предполагается, что исходный список - не readonly, но по завершении должен вернуться в исходный вид. И надо как-то корректно (но при этом без подсказок) обозначить такой нюанс в условии. По умолчанию принято считать, что входные данные могут быть readonly.
GospodinKolhoznik
00.00.0000 00:00Ну это будет подсказка, которая снижает сложность задачи в разы. А задача и так не очень сложная.
wataru
00.00.0000 00:00+1Хм… интересно. Пока придумал так: "удваиваем" список, вставляя новые элементы после каждого изначального. Новые элементы потом образуют копию списка. У этих новых элементов можно random заполнить за один проход. Надо обрабатывать элементы парами (изначальный элемент, вставленный за ним). У первого элемента random ведет на первый элемент какой-то другой пары. Просто взяв там next можно получить элемент, на который должен указхвать random у второго элемента в паре. Что-то вроде
origin->next->random = origin->random->next;. А потом надо эти списки расцепить, что тоже просто за один проход делается.Вряд ли это можно сделать вообще не меняя изначально заданный список.
BoltHold
00.00.0000 00:00Эта задача на проверку знания кандидатом вычислительной сложности и некоторых алгоритмов сортировки не более
MDFA
00.00.0000 00:00+1А как отмечать знаком числа в массиве, если они изначально могут быть отрицательные, или по условию они целые положительные?
commanderxo
00.00.0000 00:00+2По условию, числа в массиве лежат в диапазоне [1, N], а значит строго положительные.
Но вы правы, первое решение в общем случае не коректно, потому как в условии задачи нигде не сказано, что:- Значения в массиве можно менять. Может он в ПЗУ лежит.
- В массиве можно сохранять значения выходящие за первоначальный диапазон. По сути, применяя отрицание, мы втискиваем в исходный массив дополнительный бит информации, и не факт, что для него есть место. В массиве двубайтных ячеек можно без проблем хранить числа [1,65535], но нет места для их отрицательных пар.
fiksii
00.00.0000 00:00-1Ничего не понял....
массив из N+1 целых чисел, который содержит элементы в диапазоне [1, N].
Кандидат: Только одно число повторяется?
Интервьюер: Нет, не обязательно: [4, 3, 3, 1, 1, 2].
Уже здесь нарушено условие задачи.
Такое ощущение, что подобные статьи - это просто тупая реклама, которую делают малограмотные специалисты.
UltimateOrb
00.00.0000 00:00+1Сначала они просят тебя решать подобные задачки. А потом сливают их кодовую базы и ты понимаешь что там костыль на костыле...
WebSerega
00.00.0000 00:00-1Не прочитал все комменты, если что поправьте мое решение:
Я бы сделал тестовой массив и прогнал цикл по всем числам основного массива - и 1) удалял индекс массива с числом, которого нет в тестовом массиве (проверяя значение по индексу тестового массива) 2) после удаления текущего числа, записывал бы его в этот тестовой массив по индексу = числу. На выходе основной массив остается с числами, которые повторяются. P.s. это javascript решение упрощенное, если в начальном условии задачи не указано, что массив нельзя менять.
qw1
00.00.0000 00:00В статье подобное прошли, и задали следующий вопрос: а как обойтись без дополнительных массивов.
poterin
00.00.0000 00:00Если вы не ищете кандидата на очень специфический скоуп задач, то это очень похоже на рекомендацию как правильно проводить собес, если у вас нет желания найти сотрудника в разумные сроки. В большинстве случаев, я бы не рекомендовал подобный подход - времени на интервью съедает много, а представлений о кандидате дает мало.
svartberg
00.00.0000 00:00А что компания готова предложить в награду за такое интервью? будут ли такие же интересные условия, интересная зарплата, интересные задачи? или будет очередная система по перекладыванию json'ок с токсичными менеджерами и за унылую зарплату?
Получается, что все стремятся сделать хитрое интервью в стиле google, но только забывают предоставить аналогичные условия работы.
SpiderEkb
00.00.0000 00:00Тут возникает сразу вопрос - в предполагаемой для кандидата области деятельности как часто будут встречаться такие задачи?
Я лично предпочту спрашивать то, с чем кандидату придется столкнуться в реальной работе. И пусть это будет без кода, просто на словах - "как вы реализовали бы вот такое? а почему именно так, а не этак?"
Просто чтобы понять в какую сторону он будет думать, какой подход выберет и насколько глубоко понимает те подводные камни, которые неизбежно содержатся в том или ином подходе.
iig
00.00.0000 00:00+2как вы реализовали бы вот такое?
Действительно нужные задачи из реальной работы новому человеку вы будете обьяснять пару часов. Это уже называется тестовое задание.
SpiderEkb
00.00.0000 00:00Зачем пару часов? Вот простейшая задача - нужно сделать выборку некоторого (достаточно большого) объема данных и организовать его параллельную обработку. И просто на словах - как это будет реализовываться, какие там могут быть проблемы и т.п. Это общие паттерны
Если человек уже знаком с той платформой, на которой работаем, то там могут быть другие вопросы на понимание тонкостей и особенностей платформы и ее эффективного использования. И опять же без кода, все на словах.
В любом случае, это не олимпиадные задачи на базовые алгоритмы, которые в подавляющем большинстве случаев уже реализованы, а на то, как человек будет подходить к решению реальных задач.
Я не утверждаю что это "единственно правильный" или "самый правильный" подход. Но тут ведь каждый сам волен выбирать принципы по которым он отбирает людей, с которыми ему потом работать.
iig
00.00.0000 00:00Вот простейшая задача
Одно из первых собеседований напомнило ;) Меня спросили про веб-сервер и базу данных, я начал рассказывать про IIS и ASP (я эти слова знал), а от меня ожидали, возможно, php и apache (а этих слов я не знал ;) ).. Хотя позиция была без уклона в веб-программирование.. Крч, мы друг друга не поняли ;).
каждый сам волен выбирать принципы по которым он отбирает людей
Абсолютно верно.
tyomitch
00.00.0000 00:00Меня спросили про веб-сервер и базу данных, я начал рассказывать про IIS и ASP (я эти слова знал), а от меня ожидали, возможно, php и apache (а этих слов я не знал ;)
Что из всего этого база данных? о_О
iig
00.00.0000 00:00где ASP там и ODBC где-то рядом ;) (так же как php и mysql ;) )
Сорян, за давностью лет я не могу вспомнить всех подробностей того собеседования ;) Просто как иллюстрация, что в требованиях бывает одно, спрашивают совсем другое, а чего хотят на самом деле - ?
SpiderEkb
00.00.0000 00:00от меня ожидали, возможно, php и apache
Я не ожидаю "единственно правильного решения" т.к. его нет. Есть много способов, у каждого свои плюсы и минусы. Мне интересно насколько глубоко человек думает, чем обосновывает свой выбор конкретного подхода в конкретном случае.
Lexicon
00.00.0000 00:00Никогда не задавал и не буду задавать задачек, они абсолютно никакой полезной информации о кандидате мне не дают и тратят ценнейшее время диалога.
Кандидаты часто не видят ценности/умений в приобретенном ими опыте и не рассказывают самое важное, и интересное.
Зачем мне копаться в дерьме, которое способен осилить школьник с литкода, когда среди "решателей алгоритмов", которых видит рынок, я могу найти того, с кем будет шикарно работать.
Busla
00.00.0000 00:00Кандидат: Если решать в лоб, то можно проверить, встречается ли это число ещё раз в массиве.
Интервьюер: А есть более эффективные решения? (Можно ещё намекнуть на временную сложность)
Кандидат: так оно уже максимально эффективно по памяти (Можно намекнуть Интервьюеру на пространственную сложность)
Кандидат: Можно использовать HashMap и считать каждый элемент массива. Как только попадётся элемент, который встречается больше одного раза, это и будет наш ответ.
Интервьюер: О, уже лучше. Мы нашли решение O(N)
Это с обычным массивом было бы гарантированно O(N). HashMap эффективно заменяет разреженный массив, а для плотно упакованных данных у него цена записи возрастает до O(N) из-за коллизий хэш-функции. Поэтому здесь нашли решение скорее O(N²).
ainoneko
00.00.0000 00:00Лучше сразу взять битовый массив длины N и не морочить голову :)
(Он уже один раз упоминался в комментариях.)
(И это практически он же в варианте со сменой знаков.)
faiwer
00.00.0000 00:00а для плотно упакованных данных у него цена записи возрастает до O(N) из-за коллизий хэш-функции
А что такое "плотно упакованные данные"? И разве выбор хеш-функции под задачу не решает подобные проблемы? Кому нужен HashMap под N^2?
Andy_U
00.00.0000 00:00так что по принципу Дирихле каким‑то кроликам придётся сидеть в одном домике.
Как странно устроена память. Сразу вспомнилось, что подобная задача встречалась на школьных математических олимпиадах, кгхм, 50 лет назад, и что решение - суммированием.
zergon321
00.00.0000 00:00+3Насчёт того решения с индексами и минусами - оно работает по той причине, что элементы все в диапазоне от 1 до N, т.е. натуральные числа, но для хранения их, я так понимаю, используется тип со знаком. Это значит, что у нас есть лишний бит, который в общем случае используется для хранения знака, а в задаче его можно задействовать как флаг посещённости. А что если тип числа в массиве беззнаковый? Ведь тогда все биты относятся к модулю числа. Тут уже хочешь или нет, а придётся выделять дополнительную память, разве я не прав?
DirectoriX
00.00.0000 00:00Не всегда: если N хотя бы вдвое меньше максимального значения типа (например,
uint16_t arr[30000]), то можно использовать старший бит как индикатор — по сути то же самое, что с отрицательными числами, только код немного страшнее.zergon321
00.00.0000 00:00Ну это уже какое-то совсем надуманное допущение
DirectoriX
00.00.0000 00:00Это всего лишь ответ на ваш вопрос: нет, выделять дополнительную память придётся не всегда :)
А насчёт надуманности… ну не знаю, полагаться на то, что массив с положительными числами будет использовать знаковый тип — делать точно такое же допущение, что и в моём контрпримере: что (минимум) половина всех допустимых значений типа не используется.
nivorbud
00.00.0000 00:00На кого рассчитаны такие задачки? На кандидата, который с такой задачей уже знаком? Но тогда какой смысл?
На кандидата, который незнаком с такой задачей? Но... ситуация несколько стрессовая, а такой поиск решений задач основывается либо на глубоком спокойном анализе, либо на интуиции (а это вещь непредсказуемая). Т.е. нужна спокойная обстановка и достаточное количество времени, а не стояние над душой...
А так на месте интервьюера можно пойти еще дальше (а зачем останавливаться?)... Например, предложил бы кандидату провести интегрирование оцифрованного сигнала на вычислительных ресурсах, которых заведомо не хватит. Ожидая от кандидата, что он предложит вынести операцию интегрирования с цифровой части на аналоговую - например, поставить на вход перед оцифровкой операционный усилитель с конденсатором в цепи обратной связи...
Или в пределе... ждать от кандидата решения из серии баек о секретных советских кирпичах... Это было бы еще оригинальнее :)
Dasfex
00.00.0000 00:00Насколько она всё же хорошая? Сильный кандидат расскажет вам решение за 3 минуты и за 7 напишет.
Имхо красивая задача для собеса это когда к ней изначально можно подойти с нескольких сторон и прийти к разным решениям. Проблема в том, что это тогда не просто придумать алгоритм. Скорее решить какую-то практическую задачу. Вы и кандидата проверяете, и показываете ему, какие у вас есть задачи. Может предлагаете подумать про то, как она будет использоваться -> проверяете продуктовую думалку.
vvf1973
00.00.0000 00:00+1Решение алгоритмических проблем: Поиск повторяющихся элементов в массиве (nuancesprog.ru)
Интересно, как долго можно удерживать в голове все алгоритмы. И пройдёт ли испытание сам автор статьи, если какой-то кадр вытащит из Кнута или Кормена, Ахо с Ульманом что-нибудь эдакое или не очень эдакое. Разумеется, есть такие гении с хорошей памятью, но за всю жизнь их можно было сосчитать по пальцам одной руки. Имхо, конечно.
vasyakolobok77
00.00.0000 00:00+1Кликбейтовый заголовок, а внутри задачка на собеседовании, которая никак не отражает сути вакансии. Вы кого собеседуете такими задачками? Людей для участия в конкурсах по спортивному программированию?
comdivuz
00.00.0000 00:00Если для Вас ЭТА задача является "спортивным программированием", то задайтесь сами вопросом - Вы точно представляете себе чем занимаются компании которые набирают именно программистов для разработки софта, а не сопровождением легасных телеграм ботов и сайтов на ванильном PHP?
vasyakolobok77
00.00.0000 00:00+1Конечно же мой опыт не покрывает все области разработки софта, но я точно знаю, чем занимаются в компаниях, которые занимаются: разработкой сайтов, CMS/CMF систем, интернет-магазинов, личных кабинетов, CRM/OSS систем, BPM систем, разработкой мобильных приложений для вышеперечисленных видов приложений. Я в разработке с начала 00-х и по своему опыту и опыту коллег скажу, что в 99,999% случаев подобные алгоритмы не нужны, поскольку инструментарий (фреймворки, библиотеки, sdk) предоставляет все необходимое. Безусловно, бывают случаи, когда необходимо применить нестандартный подход, и такие случаи отдаются на реализацию знающим ребятам (условно сеньорам).
Я считаю, что пример из статьи определенно из рода спортивного программирования. Сможете ли вы придумать хоть один кейс, где будет нужна реализация алгоритма по заданным условиям?
comdivuz
00.00.0000 00:00+2Знаю, что наберу минусов. Но мне лично как-то без разницы.
Очередная отличная статья, написанная о собеседовании со стороны собеседующего, а не со стороны стоноты, который бегает собеседуются, а его ""мучают", "не берут" и вообще все вокруг идиоты, а он такой молодец".И опять человек в 100-й раз Вам пишет, как писали многие до этого, что вся соль на собеседовании в умении задавать вопросы и рассуждать, а не в Ваших хардскиллах, к тому же фальшивых, если под ними нет базы.
Когда на работу берут например строителя в бригаду прежде всего смотрят не то как он пользуется лопатой - этому научат.
На что смотрят:
1. кто по национальности и вере и где родился, чтобы не оказалось, что у тебя в бригаде потом на этой почве поножовщина с другими
2. что по пьянке
3. что набито на руках и спине
4. кто его знает, кому позвонить спросить кто такой
5. может наличие хоть какого-то документа
6. отсуствие признаков внешних каких-то явно нездоровых в части психики
Вот что будут смотреть. И программистов это касается в полной мере. Собеседование это не про "лопаты", а про "наколки"
Если вы идете программистом, то только тимлиды, не уважающие свой коллектив и работу и сами не имеющие квалификаций будут проводить интервью только по хардскиллам и только ровно по тем, что именно сейчас в работе. Вот кто тут жалуется в комментариях и негодует я скажу следующий чеклист в компаниях где действительно есть комманды разработчиков и они разрабатывают
1. если у вас стремные софты - это перевесит в итоге хорошие харды, хотя если софты хорошие это не значит, что они перевесят отсутствие хардов
2. умение мыслить - важнее гораздо готовых знаний
3. умение задать вовремя правильный вопрос - важнее чем готовые ответы
4. умение действительно справиться со стрессом - важнее чем показное веселье или напускное спокойствие
5. и да - такие простенькие задачи на алгоритмы (простые в плане что условия понятны, кода точно много не требуется и легко в голове прикидывать на числах типа 1,2,3) - надо решать до какого-то хотя бы уровня, хотя бы на хэшмапах - а ведь не все кандидаты даже это в состоянии предложить!
И только потом будет хоть какое-то разделение по уровням компаний и их требованиям. Я сам не знаю до какого алгоритма сам бы дошел если бы на собеседование попал, но когда сам собеседую - мне в принципе в большинство команд годятся люди там второго примерно уровня сложности (по автору задачи) ну то есть чутка оптимизированее чем хэшмапы. И я бы не стал слишком спрашивать сильно за расчет О. А может в какую-нибудь другую команду они хотят видеть тех, кто умеет это хорошо считать и глубже анализировать.
Если Вас это бесит - значит просто ВЫ не годитесь в эту команду, а команда и без ВАС спокойно проживет. Не хотите никаких требований на собесе? Идите работать на галеры - там Вас ни о чем кроме имени Вашего не спросят.
Sam777e
00.00.0000 00:00-2Кандидат: Можно отсортировать массив. Повторяющиеся элементы будут рядом, мы легко можем их найти.
Интервьюер: Тогда временная сложность вырастет до 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])
За нас уже подумали; и код лаконичный.wataru
00.00.0000 00:00+1Но теперь ещё надо пройти по всему массиву — итог n^2*ln(n).
Что?
Вы проходитесь по массиву на каждом шаге сортировки что ли? Действия последовательные, поэтому количество операций складывается O(n + n log n) = O(n log n).
Vlafy2
00.00.0000 00:00Все эти задачи с сортировками и поисками каких-то совпадений - ну такая голимая синтетика, в реальной жизни нужная чуть менее, чем никому. Больше похоже на попытку интервьюера самоутвердиться.
Denis42
00.00.0000 00:00Глупости. Лучшая задача для интервью - это как лучшая функция, которая решает все задачи.
Ни сама задача, ни наводящие вопросы ничего не говорят о кандидате. Абсолютно ничего.
sonepotam
00.00.0000 00:00Кандидат: сколько элементов в массиве?
Интервьюер: ну допустим 100.
Кандидат: тогда все ваши временные и прочие сложности никакого значения не имеют. Пакуем в мапу и всего делов.
Интервьер: мерзавец(про себя). Хорошо, допустим, 10 миллионов(вслух). Посмотрим как выкрутится(про себя)
Кандидат: на таких объёмах я бы использовал все же СУБД, делаем табличку с первичным ключом и вставляем в неё элементы. Как только будет dupval_on_index. Это вот оно и есть. Никогда не надо решать задачу неподходящими для неё методами.
wataru
00.00.0000 00:00+1Кандидат: на таких объёмах я бы использовал все же СУБД, делаем табличку с первичным ключом и вставляем в неё элементы. Как только будет dupval_on_index. Это вот оно и есть. Никогда не надо решать задачу неподходящими для неё методами.
Что работает на порядок медленнее той же мапы. И памяти жрет больше. Плюс тянется библиотека СУБД.
Никогда не надо решать задачу неподходящими для неё методами.
Вот уж точно.
sonepotam
00.00.0000 00:00Если развернуть СУБД на домашнем компе - безусловно. В промышленной среде - смешно даже сравнивать. Кое-какой производитель АБС решил посчитать отчетною форму и положил в мапу проводки за квартал:)) Ну что сказать. На чахлом объеме в 200.000 записей мапе этой настал каюк. Oracle на объеме 200 тысяч записей наконец-то перестает удерживать таблицу в памяти и вспоминает о свопировании. У него все еще только начинается.
wataru
00.00.0000 00:00Странная история. 200000 записий и мапа не справляется? Что там за записи-то такие? Там в каждой проводке ключи криптографические сохраняются или что? Даже если каждая запись занимает аж по 20кб, это все суммарно в 4 гб памяти влезет. Ну плюс сколько-то процентов на оверхед, но по сравнению с такими толстыми записями это будут копейки. 200 тысяч записей — это обычно ничтожный объем.
Понятно, если у вас данных так много, что оно в память не влезает, то надо что-то думать. В зависимости от задачи, опять же, СУБД скорее всего будет перебором. Ибо это универсальное средство оптимизированное под хранение данных а не их обработку. Что-то заточенное под вашу задачу может быть сильно быстрее и проще.
Единственный плюс СУБД — мозг у программиста не задет. Все дешево и быстро делается.Возвращаясь к началу ветки: если вам надо найти повторяющееся число, то мапа в память перестанет влезать только на миллиардах чисел. Но и тут тупой битовый массив будет работать до 32 миллиардов чисел спокойно. Приведенные выше 10 миллионов — это примерно на 3 с половиной порядка меньше.
sonepotam
00.00.0000 00:00Group by средство обработки информации. Если и немного более сложные средства которые позволяют не выкачивать на клиента весь датасет.
qw1
00.00.0000 00:00+1Так у вас задача сначала закачать в СУБД «весь датасет», затем его там обработать и выкачать агрегат. Вот вам и предлагают: может, вместо того, чтобы туда-сюда перекачивать, посчитать локально?
wataru
00.00.0000 00:00В описанном вами решении задачи через СУБД никаких group by и нет:
вставляем в неё элементы. Как только будет dupval_on_index
Все-равно, ручная обработка тут будет быстрее и лучше, пока она влезает в память (на 10 миллионах из вашего коммента — точно влезает)
sonepotam
00.00.0000 00:00Еще раз! Мне заявили, что СУБД якобы предназначена для хранения информации, а не для обработки . Это не так. В качестве примера обработки информации я и привел group by. Я уже не говорю про процедурное расширение языка, присутствующее практически в любой промышленной СУБД.
wataru
00.00.0000 00:00Мне заявили, что СУБД якобы предназначена
Я сказал "оптимизированное", а не "предназначенное".
И на этой конкретной задаче видно, что СУБД менее оптимально обрабатывает данные, чем простенькая структура данных.
DanielAlievsky
00.00.0000 00:00Задача, конечно, интересная... для олимпиады по информатике не слишком высокого ранга. Но при чем тут собеседование? Хороший сотрудник должен владеть существующими инструментами, например, разбираться в типичных алгоритмах и уметь их реализовывать. Вероятность столкнуться с подобной задачей в реальной практике, по моему опыту, весьма невелика, причем даже за десятки лет интенсивной работы в области алгоритмов. А если даже и возникнет подобная нестандартная ситуация (бывает всякое), то гораздо полезнее сотрудник, который сможет быстро найти готовое решение в интернете, в книгах (вроде Hackers Delight) или на форумах, чем тот, кто решит подобную задачу сам. Ибо почти наверняка готовое решение окажется профессиональнее и эффективнее.
Если же говорить о конкретно этой задаче, то, во-первых, надо отмести как неправдоподобное требование неизменяемости массива. Это может быть важным либо 1) при необходимости разработки очень фундаментальной стандартной библиотеки, которой будут пользоваться миллионы, например, базового API языка; 2) если размер массива сопоставим с объемом оперативной памяти, т.е. мы не можем позволить себе создать его копию. Первое, однако, явно мимо кассы - в этом случае над задачей будет работать команда профессиональных инженеров, а никак не новичок. Второе же, да, бывает, но очень маловероятно, что задача будет настолько простой. Большие массивы - это обычно изображения, карты, базы данных, а никак не наборы индексов. А самое главное, что в этом случае быстродействие O(N) становится важнее, чем неизменяемость - уж лучше сбросить исходный массив во внешнюю память, чтобы можно было изменять. Кстати, даже в первом случае нормальное решение, как минимум, должно проверить наличие свободной памяти и предпочесть копирование массива в случае, если памяти достаточно и если это повышает быстродействие.
Во-вторых, из реальных подходов к решению я бы выбрал либо сортировку, либо таблицу. В реальной ситуации там вряд ли будут такие удобные числа, как 1..N, но если это и правда целые числа и если их диапазон не слишком велик, то таблица, скорее всего, окажется оптимальным решением.
А вот если это не целые числа, а, к примеру, вещественные, то я бы очень оценил кандидата, который не "поведется" на стандартные библиотечные хеш-таблицы и предложит сортировку! Точнее, настоит на том, чтобы сравнить производительность обоих вариантов. Да, формально хеш-таблицы быстрее, но в реальности - при тех объемах, которые реально могут поместиться в ОЗУ - весьма вероятно, что N log N тщательно "вылизанной" библиотечной сортировки с легкостью обгонят поддержку структуру данных универсального хэша. Особенно если это язык вроде Java, где HashMap работает с объектами, размещаемыми в куче. Очень хорошо, если соискатель задумается о кэше процессора, о том, как именно будет происходить обращение к памяти - вразброс или последовательно, о том, поддается ли решение распараллеливанию на многоядерных процессорах и будет ли реальный прок от такого распараллеливания...Вот эти соображения, да, важны для профессионального сотрудника, они кое-что говорят о его опыте работы и умении создавать эффективные решения. А поиск супер-изящных алгоритмов при искусственных ограничениях, по-моему, лучше оставить олимпиадникам. Вроде тех, кто в свое время пользовались нестандартным форматом Intel-команды AAD, чтобы сэкономить лишний байт памяти, умножая число на множитель, отличный от 10 :)
RickC137
00.00.0000 00:00Мне сложно представить на собесе реального человека, который думал бы так быстро и так совершенно.
По моему, пора уже на литкоде, где-нибудь под катом прятать секретное стоп-слово, чтобы каждый знакомый с задачей разработчик мог предъявить его другому такому-же разработчику. А за одно можно было бы и остановить интервьюера, пока он не достиг экстаза от самолюбования.
Как то желчно вышло, но я бы и правда предпочел скорее тимейта с на 30% меньшим интеллектом и душностью, но на 20% большей честностью, сообразительностью и коммуникабельностью. Такой человек, как правило, всегда при работе и не станет специально готовится к собеседованию. Мой типовой вопрос попроще:
Есть 128-битный без знаковый инт на входе. При валидации этого числа надо проверить, влезет ли его факториал в такой-же 128-битный инт (т.е. сравнить с захардкоженым числом).
Как будешь считать это число?qw1
00.00.0000 00:00Зачтено, если спросить на WolframAlpha и получить ответ «34»?
Alexandroppolus
00.00.0000 00:00Наверно, требуется последовательно умножать 1*2*3*... до заданного числа, но так чтобы не вляпаться в переполнение. Например, очередное X! сравнивать с (pow(2, 128)-1)/(X+1)
qw1
00.00.0000 00:00Это слишком скучно.
Но у вас детект переполнения какой-то переусложнённый.
Хорошо бы спросить о документированном поведении системы при переполнении.
Если выставляется бит переноса или кидается исключение — можно это смотреть.
Если операция выполняется по модулю (2^128), достаточно проверить что произведение стало меньше максимального из сомножителей — значит, случилось переполнение.wataru
00.00.0000 00:00А вот не факт. Оно после переполнения может стать больше изначального числа, да и любого множителя тоже. Например (uint_max/2+1) при умножении на 3 будет uint_max/2+3.
Можно, результат потом на последний множитель или последнее значение делить и смотреть, что результат деления равен второму множителю.
Ну или надо, как Alexandroppolus описал — смотреть, что умнжаемое меньше max/множитель.
Без деления вы переполнение не отловите.
qw1
00.00.0000 00:00Я подозревал, что так и будет, но не смог найти пример )))
Хочется всё же без деления, например, вычислять бит переноса, поделив числа на 2 64-битные половинки (A*2^64+B)*C (второй множитель заведомо не вылезет за int64, он и за int32 не вылезет). Но не факт, что будет быстрее, чем деление в лоб.Alexandroppolus
00.00.0000 00:00Хочется всё же без деления
Можно сократить количество делений, например, факториалы на отрезке X! ... (X+k)! сравнивать с maxUint128/(X+k+1), взяв деление один раз на k шагов. Как только перевалили за max/(X+k+1), то можно уже с меньшим k, или вообще "поштучно".
Разумеется, в этом нет даже теоретического смысла на 128 битах, но если говорить о длинной-предлинной арифметике, то вполне.
qw1
00.00.0000 00:00Если я правильно понял идею, надо делить так:
max / ((x+1)*(x+2)*...*(x+k+1))
и сравнивать с текущим x!Alexandroppolus
00.00.0000 00:00Можно и так.
Моя идея в том, что берем некоторое P, вычисляем M = maxUint128/(P+1). Далее можно спокойно смотреть факториалы до P! и сравнивать с M. Если так и не превзошли М, то у нас (P+1)! < maxUint128, берем новое P = P + k, новое М, и идем дальше. Иначе переходим к пошаговому варианту, там до переполнения уже рукой подать.
RickC137
00.00.0000 00:00С моей точки зрения - любой корректно работающий вариант - правильный.
Я, к примеру пошел на https://umath.ru/calc/graph , построил y=x!/2^128 и посмотрел в какой точке кривая пересекает 1. Потом, чтобы убедиться, что логика сайта не забагована для таких случаев, пошел в убунтовский калькулятор, убедился, что 2^128−34! - положительное, а 2^128−35! отрицательное.
Конечно решение изяществом не блещет, но с точки зрения продакшена - корректный результат за разумное время - то что надо.
Соискатели (среди которых бывают и вчерашние студенты) демонстрируют, к примеру свой матан: "Надо вывести уравнение, так сейчас, сейчас... Минуточку, но у факториала же нет обратной функции!" иногда еще и с вопросительной интонацией в конце)
Дальше мы переходим к численным методам. В лоб перемножать числа с 2 почему-то всем очень не нравится, пытаются приплести метод половинного деления. Много разговоров об О-нотации, но это все - чтобы оценить на сколько инженер самостоятельный, будет ли он искать способ самому проверить свое творчество (не рассчитывая что другой инженер на код ревью все исправит), на сколько склонен к оверинжениренгу, достаточно ли у него фантазии, чтобы решать абстрактные задачи.
Это все я к тому, что над такой вот задачкой не надо 5 минут вчитываться, задавать уточняющие вопросы, потом 5 минут думать в неловкой тишине. А информации о том, как потом с человеком работать это даст не меньше. Но это субъективное мнение, конечно.
DanielAlievsky
00.00.0000 00:00А... зачем может пригодиться такой факториал? :)
Что действительно может понадобиться в реальной жизни, так это проверка переполнения при самых обыкновенных вычислениях - сумм, разностей, произведений. Вот, например, предложите задачу: написать функцию с целыми параметрами dimX, dimY, которая создает матрицу dimX x dimY в простом линейном массиве (не двумерном, даже если язык позволяет) и заполняет ее чем-нибудь полезным, ну хотя бы рисует там круг из единичек. И вот, тест на квалификацию: догадается ли кандидат перед отведением памяти проверить, что произведение dimX * dimY вычисляется без переполнения, и в противном случае выдать соответствующее исключение "слишком большой массив". Сколько я видел кода, который не задумывается о таких "мелочах жизни" - и, соответственно, при неудачных dimX и dimY ведет себе неадекватно (вплоть до порчи памяти в языках типа C++). Я уже не говорю о более тонких мометах, вроде того, что для знаковых x и y неравенство x - y < 0 вовсе обязательно означает, что x < y...
RickC137
00.00.0000 00:00А... зачем может пригодиться такой факториал? :)Мне это пригодилось для ленивого способа подсчета числа сочетаний для своего домашнего мини-бикини-пет-проекта. Рабочие задачи, к сожалению, более унылые. А те что не унылые требуют знания предметной области, которого от соискателя не ожидается.
произведение dimX * dimY вычисляется без переполненияМб я что-то не понял, но по моему самый простой вариант, если код будет работать на 64-разрядной машине, то произведение двух uint32_t не сможет превысить размер адресного пространства, Так можно наложить ограничения без накладных расходов на проверку. Правда проверка того, что сами аргументы не были вычислены с переполнением уже становится заботой клиентского кода). Кроме того у системы закончится память гораздо раньше и аллокатор выбросит bad_alloc исключение. Если же это код для 32-разрядной машины (или для контроллера), то всевозможные учеты аппаратных ограничений становятся самостоятельным видом искусства). В целом согласен - хорошая задача на внимание к деталям.
DanielAlievsky
00.00.0000 00:00+1Так для домашнего проекта нет ничего проще, чем воспользоваться стандартным классом длинных целых.
Что касается произведения, то я работаю в Java, где нужно использовать int и long. Но, вне зависимости от языка, суть в том, что нужно всегда помнить о возможности переполнения. Использовать правильное сочетание 32-битового и 64-битового типов - да, один из способов. (Если, конечно, оба беззнаковые либо оба знаковые.) При этом, правда, придется привести произведение к нужному более краткому типу. Но уже, например, для трехмерной матрицы этот способ не подойдет. Не подойдет и для изображения в формате RGBRGB... - там добавляется умножение на число каналов.
Наиболее простой и универсальный способ контроля - деление максимального допустимого размера на один из сомножителей. Правда, это медленно, но при отведении памяти это несущественно. Если нужна скорость (умножать надо не только для отведения памяти, но и, скажем, при вычислении индекса), то можно использовать прием из Hackers Delight. В последних версиях Java соответствующии функции добавлены в библиотеку Math: обычные арифметические операции, но гарантирующие исключение в случае переполнения.
qw1
00.00.0000 00:00Мб я что-то не понял, но по моему самый простой вариант, если код будет работать на 64-разрядной машине, то произведение двух uint32_t не сможет превысить размер адресного пространства
Но нужно это ещё правильно записать: compiler-explorer.com/z/caWKdW9qsRickC137
00.00.0000 00:00Согласен.
Такого рода ошибки можно отловить на код-ревью.
Таким тонкостям как раз можно научить, я думаю. А вот если человек плохо обучаем, или склонен безосновательно стоять на своем, то такого человека лучше сразу не брать в команду.qw1
00.00.0000 00:00Такого рода ошибки можно отловить на код-ревью.
А вот и нет. Когда на ревью поступает стена текста, глаз не зацепится за «обычную» строку
Это надо помнить в момент написания.auto buf = new char[dx*dy];
Ну, либо ревью потребует довольно большой концентрации и времени, чтобы на каждой строке возвращаться к типам переменных и обдумывать все сторонние эффекты.RickC137
00.00.0000 00:00Ну мы обычно первые комиты новичков очень придирчиво смотрим, а со временем становится понятно какие у каждого сильные и слабые стороны.
Конечно идеально было бы найти идеального кандидата, но мне пока так ни разу не везло)
sleepingonee
00.00.0000 00:00Это творческий пересказ решения задачи на leetcode https://leetcode.com/problems/find-the-duplicate-number/editorial/
ChePeter
Можно поподробней, например в С расписать, чтобы сложность оценить.
Оно же без разницы на каком языке оценивать, итого в машинных кодах
Didimus
Для таких вещей есть псевдокод. Если писать на определенном языке, будет сложно тем, кто на нём постоянно не работает
Ecleytt
Простое решение на C++ с памятью и временем O(N).
ChePeter
Кажется HashMap там в тексте лишний.
Вот Вы тоже без него обошлись. Ну или можно считать, что тут вырожденный случай и HashMap от n равно n , но он есть.