этюд или не этюд
От: мыщъх США http://nezumi-lab.org
Дата: 22.11.16 02:05
Оценка:
знакомую девушку юниора на 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.
Re: этюд или не этюд
От: wl. Россия  
Дата: 22.11.16 05:50
Оценка: :)))
Здравствуйте, мыщъх, Вы писали:

М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:


а кто твоя подруга, негритянка или кошка? вероятно от этого нужно отталкиваться
Re: этюд или не этюд
От: Kaifa Россия  
Дата: 22.11.16 07:45
Оценка: :))
Здравствуйте, мыщъх, Вы писали:

М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:


М>дано N целых чисел. пускай для определенности это будет массив A.

М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].

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


М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.


М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?


я бы понял на С++ собеседовалась ))) на джаве такое требовать сущий идиотизм
Re: этюд или не этюд
От: namespace  
Дата: 22.11.16 08:45
Оценка:
М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?
Всегда удивляло: откуда люди берут эти формулы?
Я не очень хорошо помню теорвер, но у меня получилось вот так:
n!
--------*(n-1)
2*(n-2)!
Re: этюд или не этюд
От: Khimik  
Дата: 22.11.16 09:05
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 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). Я подумал, что если как-то складывать или вычитать эти неравенства, можно уничтожить какой-то один член и сократить число операций до пяти. Но когда я пробовал всё это складывать/вычитать, у меня получилось деление на ноль
"Ты должен сделать добро из зла, потому что его больше не из чего сделать". АБ Стругацкие.
Re: этюд или не этюд
От: Voseldop  
Дата: 22.11.16 09:34
Оценка: +3
Здравствуйте, мыщъх, Вы писали:

М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:


М>дано N целых чисел. пускай для определенности это будет массив A.

М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].

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


М>знакомая решила задачу, но ответ не зачли. говорят, что должно быть не более 2*N — 1 операций.


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

М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?


Может что-то в условиях задачи пропущено?
Re: этюд или не этюд
От: Fantasist  
Дата: 22.11.16 18:49
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:


На юниора на java? Странная контора, математическа что ли?
Хотя задачка довольно студентчиская, в том смысле, что такие задачки как раз для упражнения студентам дают, но с другой стороны достаточно продвинутая — от большинства юниоров такие способности не требуются. Да и вообще несколько непонятно, что они хотят от этого — для юниорских девелоперских задач умение решать такие задачи вроде как и не нужно, а с другой стороны, продвинутый чел хорошо решивший эту задачу не обязательно обладает хорошими девелопескими навыками.
Re[2]: этюд или не этюд
От: мыщъх США http://nezumi-lab.org
Дата: 22.11.16 20:47
Оценка:
Здравствуйте, 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.
Re: этюд или не этюд
От: _ilya_  
Дата: 22.11.16 23:27
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>дано 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 — хрен за линейное число шагов проверить что не валидный.
Отредактировано 22.11.2016 23:33 _ilya_ . Предыдущая версия . Еще …
Отредактировано 22.11.2016 23:32 _ilya_ . Предыдущая версия .
Отредактировано 22.11.2016 23:30 _ilya_ . Предыдущая версия .
Отредактировано 22.11.2016 23:29 _ilya_ . Предыдущая версия .
Re[2]: этюд или не этюд
От: landerhigh Пират  
Дата: 22.11.16 23:34
Оценка:
Здравствуйте, _ilya_, Вы писали:

__>Задача по сортировке массива, но хитрого — каждое число в >1,5 раза больше предыдущего,


6 7 10 45
www.blinnov.com
Re: этюд или не этюд
От: jpr111a  
Дата: 23.11.16 02:17
Оценка: +1
Здравствуйте, мыщъх, Вы писали:

М>дано N целых чисел. пускай для определенности это будет массив A.

М>каждое число массива либо больше либо меньше суммы двух других чисел. то есть для любых X, Y и Z следующее условие ложно: A[X] == A[Y] + A[Z].

Может, имели в виду для каждых последовательных x, y, z? Тогда как раз можно джуниору дать, всё равно что foobar.
Re: этюд или не этюд
От: mgu  
Дата: 23.11.16 02:25
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>мне стало интересно. такое впечатление, что интервьр ошибся и правильный ответ N^2-1. или это я ошибаюсь?


Я в таких задачах не Копенгаген, но приходит в голову, что правильный ответ (N^2-1)/2 -- циклично проверяем сумму пар на равенство элементу, а т. к. а + b == b + a, то количество проходов к концу массива сходит на нет, как при пузырьковой сортировке.
Re[2]: этюд или не этюд
От: Pyromancer  
Дата: 23.11.16 15:36
Оценка:
Здравствуйте, 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 неравенств. Там мыщъх сам в показаниях путается, вначале пишет двух других, потом любых.
По-моему, каких-то условий в задаче явно не хватает, чтобы порядок был линейным а не квадратичным.
Отредактировано 23.11.2016 15:47 Pyromancer . Предыдущая версия . Еще …
Отредактировано 23.11.2016 15:38 Pyromancer . Предыдущая версия .
Re[3]: этюд или не этюд
От: Fantasist  
Дата: 23.11.16 16:21
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>Здравствуйте, Fantasist, Вы писали:


F>>Здравствуйте, мыщъх, Вы писали:


М>>>знакомую девушку юниора на java завалили на собеседовании следующей задачкой:

F>> На юниора на java? Странная контора, математическа что ли?
М>контора пилит навигационный софт и там действительно много математики.

F>> Хотя задачка довольно студентчиская, в том смысле, что такие задачки как раз для упражнения студентам дают,

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

"Решение не зачли" — это другой вопрос. То есть решение начальной задачи есть, но им не понравилась его сложность вычисления. Но тут мы уже точно не знаем этого требования. Если решение с линейной зависимостью и существует, то достаточно сложное, чтобы ожидать его нахождения на интревью.
Re: этюд или не этюд
От: antonio_banderas Россия  
Дата: 28.11.16 14:00
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>дано 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) решаем на отсортированном массиве, точное кол-во операций не считал.
Решение как и еще один товарищ
Автор: Voseldop
Дата: 22.11.16
писал.
Re: этюд или не этюд
От: Кодт Россия  
Дата: 29.11.16 16:17
Оценка:
Здравствуйте, мыщъх, Вы писали:

М>знакомую девушку юниора на 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). Это случай наихудший, но и наиредчайший.
Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.
Перекуём баги на фичи!
Re[2]: этюд или не этюд
От: Кодт Россия  
Дата: 29.11.16 16:37
Оценка:
К>Допустим, что массив уникальных чисел отсортирован по возрастанию.

Если уточнить, что в массиве только положительные числа, то моё решение будет работать как есть.
Если же там могут встречаться отрицательные, — то 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. (Если только последовательность не похожа на супервозрастающую).
Перекуём баги на фичи!
Re[2]: этюд или не этюд
От: antonio_banderas Россия  
Дата: 30.11.16 10:08
Оценка:
Здравствуйте, Кодт, Вы писали:

К>И вот тут уже асимптотика становится гораздо симпатичнее. Потому что, чем дальше от левого края (а точнее, — чем дальше от нулевого значения), тем бодрее мы начнём скакать по массиву.

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

Гораздо симпатичнее — это сколько?
Кстати, что значит субквадратичное время? На википедии это есть, но очень непонятно написано.

К>Но тут вот ещё какой интересный момент.

К>Если содержимое массива — супервозрастающая последовательность, то по-любому отхватим самую первую ~ n*n*log(n). Это случай наихудший, но и наиредчайший.
К>Чтобы найти не верхнюю, а среднюю оценку, придётся теорверить со страшной силой.

А как так получилось, что у меня за квадратичное время O(N^2) решается при любом случае? То есть моё решение более эффективное, чем твоё? Или где-то ошибка?

UPD: а, прочитал твоё еще одно сообщение, у тебя тоже в результате квадратичная. Ок.
Отредактировано 30.11.2016 10:10 antonio_v_krasnom . Предыдущая версия .
Re[3]: этюд или не этюд
От: Кодт Россия  
Дата: 01.12.16 12:59
Оценка:
Здравствуйте, 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
Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.