Найти целое число не среди четырех миллиардов заданных

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

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

Мой анализ:

Размер файла составляет 4 × 10 9 × 4 байта = 16 ГБ.

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

Мое понимание (после прочтения всех ответов):

Предполагая, что речь идет о 32-разрядных целых числах , Есть 2 ^ 32 = 4 * 10 9 различных целых чисел.

Случай 1: у нас есть 1 ГБ = 1 * 10 9 * 8 бит = 8 миллиардов бит памяти.

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

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Случай 2: 10 МБ памяти = 10 * 10 6 * 8 бит = 80 миллионов бит

Решение: Для всех возможные 16-битные префиксы, есть 2 ^ 16, число целых = 65536, нам нужно 2 ^ 16 * 4 * 8 = 2 миллиона бит. Нам нужно построить 65536 ведер. Для каждого сегмента нам нужно 4 байта, содержащих все возможности, поскольку в худшем случае все 4 миллиарда целых чисел принадлежат одному и тому же сегменту.

  1. Построить счетчик каждого сегмента через первый проход по файлу.
  2. Просканируйте ведра, найдите первого, у которого попадание менее 65536.
  3. Создайте новые сегменты, чьи высокие 16-битные префиксы мы найдем в шаге 2 через второй проход файла
  4. Сканирование блоков, встроенных в шаге 3, найдите первый сегмент, который не имеет попадания.

Код очень похож на приведенный выше.

Вывод: мы уменьшаем память за счет увеличения скорости передачи файлов.


Уточнение для тех, кто опаздывает: в заданном вопросе не говорится, что в файле содержится только одно целое число - по крайней мере, большинство людей его не так интерпретируют. Тем не менее, многие комментарии в ветке комментариев относятся к об этой вариации задачи. К сожалению, комментарий, который представил его в ветке комментариев, был позже удален его автором, так что теперь он выглядит так, как будто осиротевшие ответы на него просто неправильно поняли все. Это очень запутанно. К сожалению.

675
задан 23 revs, 13 users 41% 29 June 2019 в 15:30
поделиться