Проверьте 1 миллиард номеров сотовых телефонов для дубликатов

Это вопрос интервью:

Есть 1 миллиард номеров сотовых телефонов, которые имеют 11 цифр, они хранятся случайным образом в файле, для пример 12345678910, первая цифра должна быть 1. Пройдите через эти цифры, чтобы увидеть, есть ли один с дубликатом, просто посмотрите, существует ли дубликат, если дубликат найден, return True или return False. Разрешено использовать только 10 МБ памяти.

Вот мое решение:

Хэш всех этих чисел в 1000 файлов с помощью hash(num)%1000, тогда дубликаты должны попадать в один и тот же файл.

После хэширования я получил 1000 маленьких файлов, каждый из которых содержит 1 million numbers at most, правильно? Я не уверен в этом, я просто делаю это 1 billion / 1000 = 1 million.

Затем для каждого файла создайте хеш-таблицу для хранения каждого числа и flag, представляющих ее появление.

Полагаю, для представления числа 5 B будет 4 B для нижнего 8 digits и 1 B для верхнего 3 digits; и на самом деле 1 bit хватит flag, потому что мне просто нужно выяснить, существует ли дубликат, только сколько раз. Но как я могу применить флаг 1 bit к каждому номеру? Я споткнулся, поэтому я выбираю bool как флаг, 1 B. Итак, каждый номер в хэш-таблице будет принимать 5B<for number> + 1B<for flag> + 4B<for the next-pointer> = 10B, тогда каждый файл примет 10M для хеш-таблицы.

Это мое глупое решение, пожалуйста, дайте мне лучшее.

Спасибо.

ПОСЛЕДУЮЩИЙ:

Если в этих 1 миллиардах телефонных номеров есть no duplicates, данный один номер телефона, как узнать данный is or is not in эти 1 миллиард номеров? Используйте как можно меньше памяти.

Я придумал 2 решения,

Номер телефона может быть представлен с использованием 5B, как я сказал выше, просмотром файла, чтением одного номера за раз и xor the given number with the one read from the file, если результат 0, тогда указанный номер находится в файла, это займет время O(n), правильно?
Partition эти числа в 2 small files в соответствии с leading bit, что означает, что числа с a leading 1-bit идут в файл, leading 0-bit идут в другой файл, тем временем подсчитывают, сколько чисел в каждом файле, если указанное число попадает в 1-битный файл, а 1-битный файл count - not full, затем again partition 1-битный файл в соответствии с secondary leading-bit и проверьте заданный номер рекурсивно; если 1-битный файл is full, то данное число должно быть в файле, это займет O(logn) время, правильно?

Ответ 1

Самое быстрое решение (также с точки зрения накладных расходов программиста):

# Generate some 'phones'
yes 1 | perl -wne 'chomp; ++$a; print $_."$a\n";' > phones.txt

# Split phones.txt in 10MB chunks
split -C 10000000 phones.txt

# Sort each 10MB chunk with 10MB of memory
for i in x??; do sort -S 10M $i > $i.srt; echo -ne "$i.srt\0" >> merge.txt; done

# Merge the shorted chunks with 10MB of memory
sort -S 10M --files0-from=merge.txt -m > sorted.txt

# See if there is any duplicates
test -z $(uniq -d merge.txt)

Проверьте, что ограничение использования памяти встречается с pmap $(сортировка pidof), например:

Ответ 2

После хэширования я получил 1000 маленьких файлов, каждый из которых содержит 1 миллион чисел в лучшем случае, справа

Не верно, в крайнем случае возможно, что один файл содержит все числа.

Создайте файлы на основе первых или последних x цифр чисел (игнорируйте стартовый 1). При создании этих файлов вы можете нарезать эти цифры, потому что они равны внутри файла. Это намного лучше, чем хеширование, потому что, хотя все числа могут быть в конечном итоге в одном файле, теперь диапазон этих чисел ограничен, поэтому вы можете поместить его в 10 МБ.

Каждый номер может быть представлен простым битом, потому что единственная информация, в которой вы нуждаетесь, - это число, которое было ранее. Вам не нужно сохранять фактические цифры, адрес бита - это номер. В 10 Мб вы можете хранить 80 М бит, поэтому вам понадобятся файлы 1G/80M = 12,5, но помните, что эти цифры должны отличаться, поэтому на самом деле вам понадобится 100 файлов (x = 2).

Наконец, вам не нужно создавать эти файлы, вы также можете сканировать весь файл несколько раз. В этом случае вы можете иметь несколько бит-карт в памяти, так как каждый не занимает 10 МБ.

Я настоятельно рекомендую прочитать эту книгу, она начинается с почти идентичного примера: http://www.amazon.co.uk/Programming-Pearls-ACM-Press-Bentley/дп/0201657880

Ответ 3

Не нужно использовать хэш, 10M = 83886080 бит, поместить каждое число в [0, 83886080), [83886080, 83886080 * 2)... [xx, 9999999999) (не считайте первую цифру), около 999999999/83886080 = 120 файлов, затем постройте bit set, он полностью принимает O (n).

Ответ 4

Вы можете следовать технике биттетов. Обратитесь к этому вопросу и ответам: Найдите целое число не из четырех миллиардов данных

Ответ 5

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

таким образом, разумно реализовать этот вопрос следующим образом:

take the first number
compare it to all numbers following it
take the second number
compare it to all numbers following it
...

это занимает огромное количество времени для обработки миллиардов чисел (O (n ^ 2)), но не занимает более 10 МБ пространства памяти.

Ответ 6

Вы можете использовать Bloom Filters, который содержит m бит-массив и использует k хэш-функции. Хотя я не уверен, сколько хэш-функций вам может понадобиться.