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

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

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

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

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

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

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

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

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

Спасибо.

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

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

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

1. Телефонный номер можно представить с помощью 5B, как я сказал выше, просканировать файл, прочитать одно число за раз и выполнить xor заданный номер с одним, прочитанным из файл , если результат 0 , то данный файл находится в файле, это займет O (n) времени, верно?

2. Partition эти числа в 2 небольших файла в соответствии с ведущим битом , что означает, что числа с ведущим 1 битом переходят в файл, ведущий 0-битный перейти в другой файл, тем временем подсчитать, сколько чисел в каждом файле, если данное число попадает в 1-битный файл, а счетчик 1-битного файла равен не заполнен , затем снова разделит 1-битовый файл в соответствии с вторичным ведущим битом и рекурсивно проверяет данное число; если 1-битный файл заполнен , тогда данное число должно быть в файле, это займет O (logn) времени, верно?