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

aa>Так я и говорю что твой вариант прикольнее....но до него ещё додуматься надо
aa>Зато, мой вариант будет работать если числа не уникальные (т.е. могут быть повторы)

Вы только не подумайте, что я рекламирую какой книжный магазин или издательство,
но вот недавно купил книжку:
"Джон Бентли. Жемчужины программирования."
Так там таких задач... С подсказками и решениями... Есть немного...

Вот например из второй главы (там 15 глав по 5-10 задачек):
1) Есть некий файл, содержащий не более четырех милиардов 32-битных чисел в случайном порядке. Нужно найти число, которое наверняка отсутствует в этом файле. Оптимальное решение должно выполняться за O(n) и может использовать жесткий диск для хранения временных файлов.
2)Осуществие циклический сдвиг одномерного массива из n элементов влево на i позиций. Требования к алгоритму — время выполенеия O(n), дополнительная память — O(1).
3) Дан словарь английского языка. Требуется найти все наборы анаграмм. Например слова pots, stop и tops — анаграммы, так как получаются друг из друга перестановкой букв. Требования к алгоритму — чтобы работал побыстрее.

Опечатки и усл. сокращения мои.

Здравствуйте, Sergey S., Вы писали:

SS>Кстати вопрос — сотрудники были местные или американцы? На каком языке проходило общение?

В соседнем посте дана ссылка на тред в www.privet.com. ТАм это так подробно было обсуждено... Американцы. На английском...

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

V>Вы только не подумайте, что я рекламирую какой книжный магазин или издательство,
V>но вот недавно купил книжку:
V>"Джон Бентли. Жемчужины программирования."
V>Так там таких задач... С подсказками и решениями... Есть немного...

хм...а какого года книга? Просто первые две задачки я решал на экзамене по С++ в институте

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

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


aa>а мне вот первое что пришло в голову (после тупой сортировки, есесно ) —
aa>при первом проходе строим 100-битовую карту (есть число — 1, нет — 0), при втором (уже по этой карте) смотрим какого бита не хватает...собственно можно не битовую карту, а любой массив из 100 элементов.

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

Потом я уже думал замутить так: сначала быстро отсортировать(Quick sort хотя бы), а потом двоичным поиском — максимум 7 сравнений.
Но тот способ всё равно быстрей.

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

V>Поиск ( ) очень быстрый (O(n)) и наверняка наибыстрейший (от просмотра всех чисел не уйти). Из недостатков — возможность переполнения на больших значениях n (хотя на пратике такого наверняка не случится).

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