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

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

675 голосов
/ 23 августа 2011

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

Учитывая входной файл с четырьмя миллиардами целых чисел, предоставьте алгоритм для генерации целого числа, которого нет в файле.Предположим, у вас есть 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, найдите первое, которое не имеет попадания.

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

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

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

Ответы [ 38 ]

1 голос
/ 25 августа 2011

Вам не нужно сортировать их, просто многократно разбивайте их подмножества.

Первый шаг похож на первый проход быстрой сортировки. Выберите одно из целых чисел, x, и, используя его, сделайте проход через массив, чтобы поместить все значения, меньшие x, в его левое и значения больше, чем x в его правое. Найти, какая сторона х имеет наибольшее количество доступных слотов (целых чисел нет в списке). Это легко вычислить, сравнивая значение x с его положением. Затем повторите раздел в подсписке с той стороны x. Затем повторите раздел в подсписке с наибольшим количеством доступных целых чисел и т. Д. Общее число сравнений, чтобы перейти к пустому диапазону, должно составлять около 4 миллиардов, давать или брать.

1 голос
/ 29 сентября 2011

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

Вы начнете с сохранения [0..4294967295] и каждый раз, когда читаетецелое число, в котором вы склеиваете диапазон, в который он попадает, удаляя диапазон, когда он становится пустым.В конце у вас есть точный набор целых чисел, которые отсутствуют в диапазонах.Поэтому, если вы видите 5 в качестве первого целого числа, вы получите [0..4] и [6..4294967295].

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

Одним из способов хранения такого дерева будет B-дерево с началом диапазона в качестве ключа и концом диапазонав качестве значения.В худшем случае, когда вы получите все нечетные или четные целые числа, это будет означать хранение 2 ^ 31 значений или десятков ГБ для дерева ... Ой.В лучшем случае это отсортированный файл, в котором вы бы использовали всего несколько целых чисел для всего дерева.

Так что не совсем правильный ответ, но я подумал, что упомяну этот способ сделать это.Я полагаю, что провалю интервью; -)

1 голос
/ 14 мая 2015

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

Размер файла составляет 4 * 109 * 4 байта = 16 ГиБ

Вслучай 32-разрядного целого числа без знака 

0 <= Number < 2^32
0 <= Number < 4,294,967,296

Мое предлагаемое решение: C ++ без проверки ошибок 

#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

int main ()
{
    const long SIZE = 1L << 32;

    std::vector<bool> checker(SIZE, false);

    std::ifstream infile("file.txt");  // TODO: error checking

    unsigned int num = 0;

    while (infile >> num)
    {
        checker[num] = true ;
    }

    infile.close();

    // print missing numbers

    for (long i = 0; i < SIZE; i++)
    {
        if (!checker[i])
            cout << i << endl ;
    }

    return 0;
}

сложность

  • пробел ~ 2 32 биты = 2 29 байтов = 2 19 КБ = 2 9 МБ = 1/2 ГБ
  • Время ~ Один проход
  • Полнота ~ Да
1 голос
/ 24 августа 2011

Возможно, я полностью упускаю смысл этого вопроса, но вы хотите найти целое число, отсутствующее в отсортированном файле целых чисел?

Э-э ... правда? Давайте подумаем, как будет выглядеть такой файл:

1 2 3 4 5 6 ... первое пропущенное число ... и т. Д.

Решение этой проблемы кажется тривиальным.

0 голосов
/ 15 декабря 2014

Конечно, и, говоря с ограниченным опытом (только начал изучать Java в Uni), вы можете запустить хотя бы один набор (бочку) из int, и, если число не найдено, избавьтесь от бочки. Это освободит место и проведет проверку каждой единицы данных. Если то, что вы ищете, найдено, добавьте его в переменную count. Это заняло бы много времени, но, если вы создали несколько переменных для каждого раздела и проверили количество проверок для каждой переменной и убедились, что они выходят / удаляются одновременно, хранилище переменных не должно увеличиваться? И ускорит процесс проверки. Просто мысль.

0 голосов
/ 24 августа 2011

Возможно, я читаю это слишком внимательно, но в вопросах говорится: "сгенерировать целое число, которое не содержится в файле".Я бы просто отсортировал список и добавил 1 к максимальной записи.Bam, целое число, которое не содержится в файле.

0 голосов
/ 06 октября 2013

Старый вопрос, но мне интересно про «нефункциональные» требования.По моему мнению, должна быть дана подсказка - если этот вопрос был задан где-то еще, чем в книге, которая затем обсуждает все возможности с плюсами и минусами.Довольно часто, кажется, это спрашивает на собеседованиях, оставляя меня озадаченным, так как не может быть определенного ответа, не зная мягких требований, то есть «должно быть очень быстро искать пропущенные числа, потому что он используется х раз за секунду".

Я думаю, что такой вопрос мог бы дать разумный ответ.

  • Я бы слил-отсортировал все числа в новый файл, используя 4 байта на целое число.Конечно, сначала это будет медленно.Но это может быть сделано с небольшим объемом памяти (вам не нужно обязательно хранить все в оперативной памяти)
  • Используйте бинарный поиск, чтобы проверить, существует ли число в предварительно отсортированном файле.Поскольку у нас остается 4 байта на значение, это не проблема

недостатки:

  • Размер файла
  • Медленная первая сортировка - но требуется только один раз

преимущества:

  • очень быстрый поиск

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

0 голосов
/ 07 февраля 2012

Я придумал следующий алгоритм.

Моя идея: просмотреть весь файл целых чисел один раз, и для каждой позиции бита считать 0 и 1.Количество 0 и 1 должно быть 2 ^ (numOfBits) / 2, поэтому, если сумма меньше ожидаемой, мы можем использовать ее из полученного числа.

Например, предположим, что целое число равно 32 бита, тогданам требуется 

int[] ones = new int[32];
int[] zeroes = new int[32];

Для каждого числа, которое мы должны повторить, хотя 32-битные и увеличить значение 0 или 1: 

for(int i = 0; i < 32; i++){
   ones[i] += (val>>i&0x1); 
   zeroes[i] += (val>>i&0x1)==1?0:1;
}

Наконец, после обработки файла: 

int res = 0;
for(int i = 0; i < 32; i++){
   if(ones[i] < (long)1<<31)res|=1<<i;
}
return res;

ПРИМЕЧАНИЕ: в некоторых языках (например, Java) 1 << 31 - отрицательное число, поэтому (long) 1 << 31 - правильный способ сделать это </p>

Страница:
...