Вам предоставляется файл, который содержит все возможные числа в 32-битной архитектуре. 4 числа отсутствуют в этом файле. Найдите 4 пропущенных номера

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

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

Для меня это означает сортировку чисел и сканирование на наличие пробелов. Но я работаю над бизнес-системами и веб-приложениями. Я не возиться с битами, и я не хочу, чтобы моя команда!

Если вы проводите собеседование на низкоуровневую работу, близкую к металлической, «сортировка», вероятно, будет встречаться с пустыми взглядами. Они хотят, чтобы вам было удобно думать о битах и ​​так далее. Ваш первый ответ должен быть: «О, я бы использовал растровое изображение». (Или битовый массив, или бит установлен.)

И затем, в любом случае - даже если вы дадите «неправильное» решение, если ваш собеседник (или начальник!) Настаивает на этом , вы можете предложить некоторые улучшения или альтернативы, сосредоточив внимание на конкретной проблемной области менеджера.

• Сильно ограниченная оперативная память? Меньше 512 МБ?
  Сортировка на месте, на диске. Вы можете использовать в основном произвольный объем ОЗУ для оптимизации и / или буферизации отсортированных блоков.
• Ограниченный срок?
  Используйте эту оперативную память! Сортировка уже есть O(n*log(n)). (Или O (n) для целочисленной сортировки!)
• Ремонтопригодность?
  Что может быть проще, чем сортировка ?!
• Не демонстрирует знание битовых флагов / полей? ( BitSet/ BitMap/ BitArray)
  Ну ладно ... иди и используй, BitArrayчтобы пометить «найденные числа». А затем отсканируйте для 0s.
• Предсказуемая сложность в реальном времени?
  Используйте растровое решение. Это один проход по файлу и еще один проход поBitArray/BitSet(чтобы найти0s). ЭтоO(n)я думаю!

Или что угодно.

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

Поскольку это файл, я предполагаю, что вам разрешено делать несколько проходов. Сначала создайте массив из 256 счетчиков, итерируйте по файлу и для каждого числа увеличивайте счетчик, индексированный как первый байт числа. Когда вы закончите, большинство счетчиков должно быть в 2 ^ 24, но от 1 до 4 счетчиков должны иметь более низкие значения. Каждый из этих индексов представляет первый байт одного из пропущенных чисел (если их меньше 4, это потому, что несколько пропущенных номеров имеют один и тот же первый байт).

Для каждого из этих индексов создайте другой массив из 256 счетчиков и сделайте второй проход по файлу. На этот раз, если первый байт является одним из значений предыдущего, увеличьте счетчик в его массиве на основе второго байта. Когда вы закончите, ищите счетчики ниже, чем 2 ^ 16, и у вас будет второй байт пропущенных чисел, каждый из которых соответствует своему первому байту.

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

Сложность времени - Сложность O(n * log n)
пространства - постоянная !

Редактировать:

На самом деле я считал n=2^32параметр параметром, но число пропущенных чисел k=4также является параметром. Предполагая, что k<<nэто означает, что сложность пространства равна O(k).

Обновить:

Просто для забавы (и потому что я сейчас пытаюсь изучать Rust) я реализовал это в Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Я выбрал текстовое представление, так как on-one будет запускать его с ~ 2 ^ 32 числами ...

Если бы это была Java, вы могли бы использовать BitSet. Ну, два из них, потому что они не могут вместить все 32-битные числа. Скелетный код, возможно, глючит:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Затем используйте, BitSet.nextClearBit()чтобы найти, кого не хватает.

Примечание добавлено намного позже:

Обратите внимание, что с помощью этого алгоритма довольно легко запустить трудоемкую часть параллельно . Скажем, исходный файл был разделен на четыре примерно равные части. Выделите 4 пары наборов битов (2 ГБ, по-прежнему управляемы).

1. Параллельно имейте четыре потока, каждый из которых обрабатывает один файл в своей собственной паре битов.
2. По завершении вернитесь к одному потоку или к наборам битов (тривиальное время), затем вызовите nextClearBit четыре раза (также довольно тривиальное время).

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

Этот вопрос может быть решен с использованием массива битов (true / false). Это должна быть наиболее эффективная структура для хранения ответов для всех чисел, использующая индекс массива для определения того, было ли найдено это конкретное число.

C #

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Затем просто переберите массив, и для тех значений, которые все еще имеют значение false, их нет в файле.

Вы можете разбить файл на более мелкие фрагменты, но я смог выделить полный массив максимального размера int32 (2147483647) на моем 16,0 ГБ ноутбуке под управлением Windows 7 (64 бит).

Даже если бы у меня не было 64-битной версии, я мог бы выделить меньшие битовые массивы. Я бы предварительно обработал файл, создав набор файлов меньшего размера, каждый из которых содержал бы диапазон [0-64000] [64001-128000] и т. Д., Которые подходили бы для доступных ресурсов окружающей среды. Пройдите через большой файл и запишите каждое число в соответствующий файл набора. Затем обработайте каждый файл меньшего размера. Это займет немного больше времени из-за этапа предварительной обработки, но это позволит обойти ограничения ресурсов, если ресурсы ограничены.

Так как это вопрос интервью, я бы показал интервьюеру некоторое понимание ограничений. Тогда, что означает «все возможные числа»? Действительно ли это 0 ... 2 <(32-1), как все догадываются? Обычные 32-битные архитектуры могут работать не только с 32-битными числами. Это просто вопрос представительства, очевидно.

Это должно быть решено в 32-битной системе, или это скорее часть ограничения на числа? Например, типичная 32-разрядная система не сможет сразу загрузить файл в оперативную память. Я бы также упомянул, что 32-битная система часто не может иметь файл, содержащий все числа, из-за ограничения размера файла. Ну, если только у него нет какой-нибудь умной кодировки, такой как «Все числа, кроме этих четырех», в этом случае проблема решается тривиально.

Но если вы действительно хотите понять вопрос как «Учитывая файл со всеми числами от 0 ... 2 ^ (32-1), кроме нескольких, дайте мне пропущенные» (а это большое, если !), Тогда Есть много способов ее решить.

Тривиально, но неосуществимо: для каждого возможного числа отсканируйте файл и посмотрите, есть ли он там.

С 512 МБ ОЗУ и однопроходным файлом: отметьте каждое число (= установите бит по этому индексу), прочитанное из файла, а затем один раз пропустите ОЗУ и увидите недостающие.

Один из подходов, который легко запомнить и легко сформулировать в интервью, состоит в том, чтобы использовать тот факт, что, если вы посмотрите на все числа в N битах, каждый бит будет установлен ровно в половине этих значений, а не в другой половине. ,

Если вы перебираете все значения в файле и сохраняете 32 значения в конце, вы получите 32 значения, которые точно (2 ^ 32/2) или немного меньше этого значения. Разница, что максимум (2 ^ 32/2) и сумма дает вам общее количество битов, установленных в каждой позиции пропущенных значений.

Когда у вас есть это, вы можете определить все возможные наборы из 4 значений, которые могут дать эти итоги. Принимая это во внимание, вы можете снова просмотреть значения в файле, проверив наличие значений, входящих в эти комбинации. Когда вы найдете один, комбинации, содержащие это значение, исключаются как возможности. Как только у вас останется только одна возможная комбинация, вы получите ответ.

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

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

Общее количество битов, установленных в каждой позиции:

7867

Вычитая их из 8 (4 ^ 2/2), получаем:

1021

Это означает, что существуют следующие возможные наборы из 4 значений:

1000
0000
0011
0010

1010
0001
0010
0000

(прости меня, если я что-то пропустил, я просто делаю это в лицо)

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

Предполагая, что файл отсортирован по возрастанию номеров:

Убедитесь, что он содержит (2³²-4) числа.
Теперь, если файл был готов (или если 4 пропущенных числа были последними 4), чтение любого слова в файле в позиции N вернет соответствующее значение N.

Используйте дихотомический поиск по позициям [0..2³²-4-1), чтобы найти первое неожиданное число X1.
Найдя это первое пропущенное число, снова выполните дихтотомический поиск по позициям [X1 .. (2³²-4-1)], чтобы найти второе пропущенное, X2: на этот раз чтение слова в позиции N должно вернуть соответствующее значение N-1. если не было пропущенных номеров (так как вы пропустили один пропущенный номер).
Повторите аналогично для двух оставшихся чисел. На третьей итерации чтение слова в позиции N должно возвращать N-2, а на четвертой - N-3.

Предостережение: я не проверял это. Но я думаю, что это должно работать. :)

Теперь в реальной жизни я согласен с другими ответами: первые вопросы будут об окружающей среде. Есть ли у нас оперативная память (сколько), это файл на устройстве хранения с прямым доступом, одноразовая операция (оптимизация не требуется) или критическая (количество циклов), есть ли у нас внешняя утилита сортировки? и т. д.
Затем найдите компромисс, приемлемый для контекста. По крайней мере, это показывает, что вы начинаете анализировать проблему, прежде чем искать алгоритм.

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

Этот вопрос и варианты имеют очень определенный «правильный» ответ, включающий XORing всех чисел. Это должно показать вам понимание индексов в базах данных или что-то. Так что ноль баллов за любой «может сработать, но не то, что написано на бумаге», ответьте им в ряду.

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

Редактировать. Ааа, кажется, для 4 есть другой подход, чем XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Редактировать. Downvoters: Это опубликованный учебник O (n) решение точной проблемы, указанной в OP.