Re[8]: Какого рода вопросы задают на собеседовании в Microso
От: Vitaly  
Дата: 06.12.02 13:12
Оценка:
Здравствуйте, aa, Вы писали:

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

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

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

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

Опечатки и усл. сокращения мои.
Re[5]: Какого рода вопросы задают на собеседовании в Microso
От: Vitaly  
Дата: 06.12.02 13:15
Оценка:
Здравствуйте, Sergey S., Вы писали:

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


В соседнем посте дана ссылка на тред в www.privet.com. ТАм это так подробно было обсуждено... Американцы. На английском...
Re[9]: Какого рода вопросы задают на собеседовании в Microso
От: aa  
Дата: 06.12.02 13:23
Оценка:
Здравствуйте, Vitaly, Вы писали:

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

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

хм...а какого года книга? Просто первые две задачки я решал на экзамене по С++ в институте
Re[6]: Какого рода вопросы задают на собеседовании в Microso
От: Mcyri  
Дата: 07.12.02 08:03
Оценка:
Здравствуйте, aa, Вы писали:

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



aa>а мне вот первое что пришло в голову (после тупой сортировки, есесно ) —

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

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

Потом я уже думал замутить так: сначала быстро отсортировать(Quick sort хотя бы), а потом двоичным поиском — максимум 7 сравнений.
Но тот способ всё равно быстрей.
... << RSDN@Home 1.0 beta 1 >>
Re[5]: Какого рода вопросы задают на собеседовании в Microso
От: Slamin США  
Дата: 07.12.02 15:48
Оценка: 15 (1)
Здравствуйте, vladsm, Вы писали:

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


Чтобы избежать переполнения можно использовать XOR, т.е. в начале вычисляется результат XOR для всех элементов, затем к полученному результату тот же XOR всех оставшихся элементов. На выходе удаленный элемент
There are 10 types of people in the world, those who don't understand binaries, those who do, and those who understand not only binaries.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.