знакомую девушку юниора на java завалили на собеседовании следующей задачкой:
дано N целых чисел. пускай для определенности это будет массив A.
каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
спрашивается: за какое кол-во операций мы можем установить что заданный массив чисел отвечает предъявленным требованиям? у нас есть операции сложения и сравнения. сложение это одна операция, сравнение это одна операция. память не выделять, но можно читать/писать в массив и операции чтения/записи считаются бесплатными. в коде должно быть не более трех целочисленных переменных и не более одной булевой переменной. массив на выходе может быть испорченным и возвращать его в исходное состояние не обязательно.
знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.
мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:
М>дано N целых чисел. пускай для определенности это будет массив A. М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
М>спрашивается: за какое кол-во операций мы можем установить что заданный массив чисел отвечает предъявленным требованиям? у нас есть операции сложения и сравнения. сложение это одна операция, сравнение это одна операция. память не выделять, но можно читать/писать в массив и операции чтения/записи считаются бесплатными. в коде должно быть не более трех целочисленных переменных и не более одной булевой переменной. массив на выходе может быть испорченным и возвращать его в исходное состояние не обязательно.
М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
я бы понял на С++ собеседовалась ))) на джаве такое требовать сущий идиотизм
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
Всегда удивляло: откуда люди берут эти формулы?
Я не очень хорошо помню теорвер, но у меня получилось вот так:
n!
--------*(n-1)
2*(n-2)!
Здравствуйте, мыщъх, Вы писали:
М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
Я думаю, вы ошибаетесь. Но
>на джаве такое требовать сущий идиотизм
Я пока не понял правильный алгоритм.
Предположим, есть только три числа: A1, A2, A3. Тогда имеем три неравенства:
1) A1==A2+A3
2) A2==A1+A3
3) A3==A1+A2
Получается шесть операций (а N^2-1 в данном случае 8). Я подумал, что если как-то складывать или вычитать эти неравенства, можно уничтожить какой-то один член и сократить число операций до пяти. Но когда я пробовал всё это складывать/вычитать, у меня получилось деление на ноль
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Здравствуйте, мыщъх, Вы писали:
М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:
М>дано N целых чисел. пускай для определенности это будет массив A. М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
М>спрашивается: за какое кол-во операций мы можем установить что заданный массив чисел отвечает предъявленным требованиям? у нас есть операции сложения и сравнения. сложение это одна операция, сравнение это одна операция. память не выделять, но можно читать/писать в массив и операции чтения/записи считаются бесплатными. в коде должно быть не более трех целочисленных переменных и не более одной булевой переменной. массив на выходе может быть испорченным и возвращать его в исходное состояние не обязательно.
М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.
Мне кажется , что за один проход задача решается только в случае отсортированного массива. Ссылка на пример решения задачи
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
Здравствуйте, мыщъх, Вы писали:
М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:
На юниора на java? Странная контора, математическа что ли?
Хотя задачка довольно студентчиская, в том смысле, что такие задачки как раз для упражнения студентам дают, но с другой стороны достаточно продвинутая — от большинства юниоров такие способности не требуются. Да и вообще несколько непонятно, что они хотят от этого — для юниорских девелоперских задач умение решать такие задачи вроде как и не нужно, а с другой стороны, продвинутый чел хорошо решивший эту задачу не обязательно обладает хорошими девелопескими навыками.
Здравствуйте, Fantasist, Вы писали:
F>Здравствуйте, мыщъх, Вы писали:
М>>знакомую девушку юниора на java завалили на собеседовании следующей задачкой: F> На юниора на java? Странная контора, математическа что ли?
контора пилит навигационный софт и там действительно много математики.
F> Хотя задачка довольно студентчиская, в том смысле, что такие задачки как раз для упражнения студентам дают,
если девушка ничего не перепутала, то я вообще не представляю возможных путей решения. выше по ветке предположили, что массив может быть отсортирован. но даже в этом случае найти в нем элемент равный сумме двух других элементов -- хз как. решение "в лоб" тривиально, но его не зачли.
F> с другой стороны, продвинутый чел хорошо решивший эту задачу не обязательно обладает хорошими девелопескими навыками
...по крайней мере от нее не просили написать echo-сервер. собеседующие сделали упор на решение, а не на реализацию. я охотно допускаю, что от кандидата требовалось доказать, что решения не существует. я жопой чувствую, что задачу не решить, но доказать не могу. кстати, в ее коде я обнаружил ошибку. по условию элемент не должен быть равен сумме двух _других_ элементов, а у нее в ходе проверки A[X] == A[Y] + A[Z] возникает ситуация когда X == Y == Z. следовательно, массив 1, 0 , 7 дает ложно-позитивный результат.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, мыщъх, Вы писали:
М>дано N целых чисел. пускай для определенности это будет массив A. М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Задача по сортировке массива, но хитрого — каждое число в >1,5 раза больше предыдущего, а если условие нарушается то задача решена — массив не валидный. Типа 1 2 4 7 12 20 33 это норм. Для отсортированного 2N операций норм, но не отсортированный — сомнительно что такая линейная сложность сортировки возможна, а без сортировки не выйдет проверить условие, разве что побитовые операции но про такие не сказано в задаче.
Для примера массив 32 20 4 7 12 2 1 — хрен за линейное число шагов проверить что не валидный.
Здравствуйте, мыщъх, Вы писали:
М>дано N целых чисел. пускай для определенности это будет массив A. М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
Может, имели в виду для каждых последовательных x, y, z? Тогда как раз можно джуниору дать, всё равно что foobar.
Здравствуйте, мыщъх, Вы писали:
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
Я в таких задачах не Копенгаген, но приходит в голову, что правильный ответ (N^2-1)/2 -- циклично проверяем сумму пар на равенство элементу, а т. к. а + b == b + a, то количество проходов к концу массива сходит на нет, как при пузырьковой сортировке.
Здравствуйте, Khimik, Вы писали:
K>Я пока не понял правильный алгоритм. K>Предположим, есть только три числа: A1, A2, A3. Тогда имеем три неравенства:
K>1) A1==A2+A3 K>2) A2==A1+A3 K>3) A3==A1+A2
K>Получается шесть операций (а N^2-1 в данном случае 8). Я подумал, что если как-то складывать или вычитать эти неравенства, можно уничтожить какой-то один член и сократить число операций до пяти. Но когда я пробовал всё это складывать/вычитать, у меня получилось деление на ноль
Если "для любых X, Y и Z" то надо проверять и случай, когда Y == Z, то есть ещё 6 неравенств. Там мыщъх сам в показаниях путается, вначале пишет двух других, потом любых.
По-моему, каких-то условий в задаче явно не хватает, чтобы порядок был линейным а не квадратичным.
Здравствуйте, мыщъх, Вы писали:
М>Здравствуйте, Fantasist, Вы писали:
F>>Здравствуйте, мыщъх, Вы писали:
М>>>знакомую девушку юниора на java завалили на собеседовании следующей задачкой: F>> На юниора на java? Странная контора, математическа что ли? М>контора пилит навигационный софт и там действительно много математики.
F>> Хотя задачка довольно студентчиская, в том смысле, что такие задачки как раз для упражнения студентам дают, М>если девушка ничего не перепутала, то я вообще не представляю возможных путей решения. выше по ветке предположили, что массив может быть отсортирован. но даже в этом случае найти в нем элемент равный сумме двух других элементов -- хз как. решение "в лоб" тривиально, но его не зачли.
"Решение не зачли" — это другой вопрос. То есть решение начальной задачи есть, но им не понравилась его сложность вычисления. Но тут мы уже точно не знаем этого требования. Если решение с линейной зависимостью и существует, то достаточно сложное, чтобы ожидать его нахождения на интревью.
Здравствуйте, мыщъх, Вы писали:
М>дано N целых чисел. пускай для определенности это будет массив A. М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].
М>спрашивается: за какое кол-во операций мы можем установить что заданный массив чисел отвечает предъявленным требованиям? у нас есть операции сложения и сравнения. сложение это одна операция, сравнение это одна операция. память не выделять, но можно читать/писать в массив и операции чтения/записи считаются бесплатными. в коде должно быть не более трех целочисленных переменных и не более одной булевой переменной. массив на выходе может быть испорченным и возвращать его в исходное состояние не обязательно.
М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
У меня пока получается так: за О(N*ln(N)) сортируем (или за O(N), если можно поразрядной сортировкой), и потом за O(N^2) решаем на отсортированном массиве, точное кол-во операций не считал.
Решение как и еще один товарищ
Здравствуйте, мыщъх, Вы писали:
М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:
Если именно завалили, то либо она как-то особенно проявила себя неудачно, либо интервьюер — этюд-наци.
Обычно такие задачи — на демонстрацию стиля мышления, а не только на извлечение готового ответа.
Ну да ладно.
Допустим, что массив уникальных чисел отсортирован по возрастанию.
for (int i = 0; i < n-2; ++i) // a[i] возрастаютfor (int j = 0; j < n-2; ++j) // a[j] возрастают, a[i]+a[j] тоже
{
int k = lower_bound(a+j+1, a+n, a[i]+a[j]); // a[k-1] < a[i]+a[j] <= a[k+1]if (k < n && a[i]+a[j] == a[k]) return false;
}
В таком виде получаем nlogn(n-2) + nlogn(n-1) + ... + nlogn(1) — это чуть меньше n*n*log(n). Точную асимптотику лень высчитывать.
Поскольку забег идёт по возрастающей, то есть смысл на каждой следующей итерации не от левого края искать, а от предыдущей точки
for (int i = 0; i < n-2; ++i)
{
int kj = i+2;
for (int j = 0; j < n-2; ++j)
{
int k = lower_bound(a+kj, a+n, a[i]+a[j]);
if (k == n) break;
if (a[i]+a[j] == a[k]) return false;
kj = k+1; // на следующем шаге будем искать с позиции, следующей за найденнойif (kj == n) break; // эта проверка автоматически выполнится на следующей итерации, в рамках lower_bound.
}
}
Для оптимизации внешнего цикла придётся чуть постараться
int ki = 2;
for (int i = 0; i < n-2; ++i) {
int kj = ki;
for (int j = i+1; j < n-2; ++j) {
int k = lower_bound(a+kj, a+n, a[i]+a[j]);
if (j == i+1) ki = k; // запомним, куда попали с первой попыткиif (k == n) break;
if (a[i]+a[j] == a[k]) return false;
kj = k+1;
}
if (ki == n) break;
ki ++;
}
И вот тут уже асимптотика становится гораздо симпатичнее. Потому что, чем дальше от левого края (а точнее, — чем дальше от нулевого значения), тем бодрее мы начнём скакать по массиву.
Вполне может быть, что получим субквадратичное время.
Но тут вот ещё какой интересный момент.
Если содержимое массива — супервозрастающая последовательность, то по-любому отхватим самую первую ~ n*n*log(n). Это случай наихудший, но и наиредчайший.
Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.
К>Допустим, что массив уникальных чисел отсортирован по возрастанию.
Если уточнить, что в массиве только положительные числа, то моё решение будет работать как есть.
Если же там могут встречаться отрицательные, — то ki должно начинаться не с 2, а с 0. И первые стрельбы будут в мысленную область отрицательных индексов (понятно, что lower_bound не допустит выбега из диапазона, но всё же).
В этом случае следует решить неравенство a[i_min]+a[j_min] <= a[0].
Сейчас не приходит в голову, как именно...
И кстати, двоичный поиск не особо нужен.
Если j линейно бежит от i+1 до n, и k линейно бежит от i+2 до n, без отскоков назад, — то время выполнения забега по j будет ровно n-i-1.
И мы получим (n-2)*(n-1)/2 шагов, т.е. O(n*n).
Двоичный поиск служит ускорением прыжков k вперёд, — мы быстрее допрыгаем до края массива и прервём цикл по j. (Если только последовательность не похожа на супервозрастающую).
Здравствуйте, Кодт, Вы писали:
К>И вот тут уже асимптотика становится гораздо симпатичнее. Потому что, чем дальше от левого края (а точнее, — чем дальше от нулевого значения), тем бодрее мы начнём скакать по массиву. К>Вполне может быть, что получим субквадратичное время.
Гораздо симпатичнее — это сколько?
Кстати, что значит субквадратичное время? На википедии это есть, но очень непонятно написано.
К>Но тут вот ещё какой интересный момент. К>Если содержимое массива — супервозрастающая последовательность, то по-любому отхватим самую первую ~ n*n*log(n). Это случай наихудший, но и наиредчайший. К>Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.
А как так получилось, что у меня за квадратичное время O(N^2) решается при любом случае? То есть моё решение более эффективное, чем твоё? Или где-то ошибка?
UPD: а, прочитал твоё еще одно сообщение, у тебя тоже в результате квадратичная. Ок.
Здравствуйте, antonio_banderas, Вы писали:
_>А как так получилось, что у меня за квадратичное время O(N^2) решается при любом случае? То есть моё решение более эффективное, чем твоё? Или где-то ошибка?
_>UPD: а, прочитал твоё еще одно сообщение, у тебя тоже в результате квадратичная. Ок.
Я могу предложить наборы данных, на которых, благодаря отсечкам, будет достигаться бОльшая скорость.
Ну самый простой: N=100, a[i]=100+i±eps. Понятно, что с первой же попытки мы обнаружим, что a[0]+a[1] > a[100], и на этом всё закончится.
Кроме того, мы ведь и границы циклов можем подбирать двоичным поиском:
i1 — текущее значение (начинаем с 0)
j1 = i1+1
k1 : a[i1]+a[j1] <= a[k1]
k2 = k1+1
j2 : a[j1] < a[j2] <= a[k2]-a[i1] — вместо того, чтобы просто j2 = j1+1
... — продолжаем итерировать по j таким же способом
i2 : a[i1] < a[i2] <= a[k2]-a[j1] — вместо того, чтобы i2 = i1+1