Всем привет,


Недавно на собеседовании задали такой вопрос - 

Есть массив целых чисел.. из него убрали 1, как узнать какое? Если убрали 2 числа?

В случае с одним понятно.. сумма элементов одного, минус сумма элементов другого.. 

А как быть если убрали больше 1 числа.. перебором?

http://habrahabr.ru/post/154765/

там в комментах есть эта задача.
ps. а для суммы вам перебор не нужен?

Ну, тут скорей вопрос не в переборе я так понимаю, а в операциях участвующих в процессе.

Т.е. либо выбрал - сравнил, либо выбрал и сложил.
Думаю сравнение будет медленней.

gambit, 
Благодарю за линк.. Никак не могу допетрить в случае с бинарным поиском.. когда обрывать процесс???

Массивы:
изначальный
1  4  3  7  10  15  3  2
после того как из него убрали 2 числа
1  4  7  10  3  2

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

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

Агрох, 
Ты не знаешь каков изначальный массив.. 

есть только массив 1..n

в нем нехватает 2 чисел. нужно их найти.

Edit:

Хотя нет вру.. знаешь. Т.е. известно что это последовательность.

Но ИМХО суммирование и сравнение это еще медленнее чем просто сравнение отсортированного.

Это сообщение отредактировал(а) Wanderer2019 - 5.9.2013, 16:12

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

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

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

Мне вот на собеседовании дали задачку написать функцию вычисления факториала.  3 строки кода за 20 секунд. И главное, на что думаю наниматели обратили внимание, я спросил: "А что такое факториал?" - вылетело из головы, т.к. вуз 6 лет назад закончил и факториалами по жизни и на работе не пользовался.

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

вот набросал:


Не могу сообразить откуда воторое число брать (или после поиска первого добавлять недостающее и искать снова?)...

Еще из вариантов почерпнутых в инете... для двух чисел.. посчитать не только сумму, но и скажем факториал - 1*2*3*4*5...



В конце получаем два уровнения - x1+x2=a и x1*x2=b, далее решаем квадратное..

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

Может я что то позабыл из математики.. 

Wanderer2019, бинарный же это поиск чего то конкретного в отсортированном массиве. А тебе надо сравнить два массива и найти то что есть в первом, но нет во втором.

попробовал с суммой квадратов.. то же самое..

т.е. x1+x2=a и x1^2+x2^2=b... 

решение не дает правильного результата

Все.. признаю себя идиотом.. все просто..

для двух

x1+x2=сумма членов полного - сумма членов урезанного
x1*x2=произведение членов полного/произведение членов урезанного

решение квадратного ур дает правильноый результат

Wanderer2019, у меня вопрос: тебе когда задавали задачу поставили какие-нибудь ограничения на способ ее выполнения? Есть же стандартный функционалВыводТо есть выводит все удаленные объекты, независимо от типа и количества. 

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

Исходя из постановки задачи, в принципе, такой вывод можно сделать: 
1. Указан конкретный тип данных.
2. Варианты с одним удаленным значением и с двумя представлены по сути как разные задачи.
3. Вопроса о произвольном количестве удаленных элементов не последовало. 

Тем не менее: 
1. Чтобы свести задачу к применению стандартного функционала, логика тоже вроде как нужна.
2. Для применения функционала надо как минимум знать о его существовании.
3. Нахождение более общего решения куда ценнее умения найти оригинальное, но слишком частное решение(если функция Except недоступна, то ее неплохо было бы написать самому).
4. То решение, на котором остановился ты, скорее показывает способность решать головоломки из книжек типа "Занимательные задачи по математике для школьников", нежели способности, каким-либо образом связанные с программированием.
5. У меня есть очень серьезное подозрение, что программист, давший такой ответ, либо знаком с задачей либо загуглил ее, а таких кому в голову пришел бы именно такой ответ - единицы.
6. О непрактичности такого решения ты сам сказал.


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