Алгоритм хранения вопрос - проверить последовательные данные с небольшим объемом памяти

Question

Я нашел это на сайте с вопросами об интервью и обдумывал это пару дней.Я буду продолжать набивать, но мне интересно, что вы, ребята, думаете

"10 Гбайт 32-битных чисел на магнитной ленте, все там от 0 до 10G в случайном порядке. У вас есть 64 32-битных слова памяти: разработайте алгоритм для проверки того, что каждое число от 0 до 10G встречается на ленте один и только один раз с минимальными проходами ленты считывающей головкой, подключенной к вашему алгоритму. "

Answer 1

32-разрядные числа могут принимать 4G = 2 ^ 32 различных значений. Всего на ленте 2,5 * 2 ^ 32 номера. Поэтому после 2 ^ 32 отсчета одно из чисел будет повторяться 100%. Если на ленте было <= 2 ^ 32 числа, тогда, возможно, есть два разных случая - когда все числа разные или когда хотя бы один повторяется.

Answer 2

Это вопрос с подвохом, как мы с Майклом Андерсоном выяснили. Вы не можете хранить номера 10G 32b на ленте 10G. Интервьюер (а) связывается с вами и (б) пытается выяснить, сколько вы думаете о проблеме, прежде чем начать ее решать.

Answer 3

Похоже, в этом вопросе есть подвох, о котором никто до сих пор не говорил; интервьюер только попросил интервьюируемого написать программу, которая ПРОВЕРЯЕТ

(i) если каждое число, составляющее 10G, присутствует один раз и только один раз - что должен делать собеседник, если числа в данном списке присутствуют несколько раз? должен ли он предположить, что ему следует прекратить использовать программу и выдать исключение, или он должен предположить, что ему следует исправить ошибку, удалив повторяющийся номер, и заменить его другим (это может быть дорогостоящим упражнением, поскольку это предполагает полную перестановку набора номеров). )? исправление этого необходимо для выполнения второго шага в вопросе, т. е. чтобы убедиться, что данные хранятся наилучшим образом, что требует наименьших возможных проходов.

(ii) Когда собеседнику было предложено проверить, хранится ли набор данных веса 10G таким образом, чтобы ему требовалось наименьшее количество пауз для доступа к любому из этих номеров; что должен делать собеседник? должен ли он остановиться и выбросить исключение в тот момент, когда он обнаружит проблему в алгоритме, в котором они были сохранены, или исправить ошибку и продолжить до тех пор, пока все элементы не будут отсортированы в порядке наименьших возможных проходов?

Если интервьюер намерен попросить интервьюируемого написать алгоритм, который находит наилучшую комбинацию чисел, которые могут быть сохранены в 10 ГБ, с учетом 64 32-битных регистров; а также написать алгоритм для сохранения этих выбранных наборов чисел наилучшим из возможных способов, которые требуют наименьшего количества проходов для доступа к каждому; он должен был спросить об этом прямо, не так ли?

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

С уважением, Samba

Answer 4

Do 2 reduce s на числах, сумме и побитовом XOR.

Сумма должна быть (10G + 1) * 10G / 2
XOR должен быть ... чем-то

Answer 5

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

Это требует одного слова памяти, чтобы отслеживать, где вы находитесь - вы можете сократить количество проходов в 64 раза, используя все 64 слова, чтобы отслеживать, где вы находитесь, в нескольких разных местах в пространство поиска - проверка всех ваших текущих на каждом проходе. Все еще O (n) проходит, конечно.

Возможно, вы могли бы сократить его еще больше, используя части слов - учитывая, что ваше пространство поиска для каждого сегмента меньше, вам не нужно будет отслеживать полный 32-битный диапазон.

Answer 6

Выполнить сортировку на месте или быструю сортировку, используя ленту для хранения? Затем выполните итерацию по числам в последовательности, отслеживая, чтобы увидеть, что каждое число = предыдущий + 1.

Требуется умно реализованная сортировка, и она довольно медленная, но достигает цели, которой я верю.

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

Вот второй подход: сканировать, пытаясь построить до 30-ти интервалов непрерывных чисел. IE 1,2,3,4,5 будет одним диапазоном, 8,9,10,11,12 будет другим и т. Д. Если диапазоны перекрываются с существующими, то они объединяются. Я думаю, вам нужно всего лишь сделать ограниченное количество проходов, чтобы либо получить полный диапазон, либо доказать, что есть пропуски ... гораздо меньше, чем просто сканирование в блоках по несколько тысяч, чтобы увидеть, присутствуют ли все цифры.

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