Недавно я посетил интервью, на котором меня спросили "напишите программу, чтобы найти 100 самых больших чисел из массива из 1 миллиарда чисел".
Я мог только дать решение грубой силы, которое должно было сортировать массив в сложности времени O (nlogn) и принимать последние 100 чисел.
Arrays.sort(array);
Интервьюер искал более сложную временную сложность, я попробовал пару других решений, но не смог ответить на него. Есть ли лучшее решение по временной сложности?
Вы можете сохранить приоритетную очередь из 100 самых больших чисел, перебирать миллиардные числа, всякий раз, когда вы сталкиваетесь с числом, большим, чем наименьшее число в очереди (глава очереди), удалите головку очереди и добавьте новый номер в очередь.
EDIT:
как отметил Дев, с приоритетной очередью, реализованной с кучей, сложность вставки в очередь O(logN)
В худшем случае вы получите billionlog2(100), который лучше, чем billionlog2(billion)
В общем случае, если вам нужны самые большие K-номера из набора из N чисел, сложность O(NlogK), а не O(NlogN), это может быть очень значительным, когда K очень мало по сравнению с N.
EDIT2:
Ожидаемое время этого алгоритма довольно интересно, поскольку на каждой итерации может произойти или не произойти вставка. Вероятность того, что i-й номер будет вставлен в очередь, - это вероятность того, что случайная величина будет больше, чем по меньшей мере i-K случайных величин из одного и того же распределения (первые числа k автоматически добавляются в очередь). Мы можем использовать статистику заказа (см. ссылка) для расчета этой вероятности. Например, предположим, что числа были случайно выбраны равномерно из {0, 1}, ожидаемое значение (iK) -го числа (из я чисел) равно (i-k)/i, а вероятность того, что случайная величина будет больше этого значения, равна 1-[(i-k)/i] = k/i.
Таким образом, ожидаемое количество вставок:
И ожидаемое время работы может быть выражено как:
(k время для генерации очереди с помощью первых k элементов, а затем сравнения n-k и ожидаемого количества вставок, как описано выше, каждый занимает среднее время log(k)/2)
Обратите внимание, что когда N очень велико по сравнению с k, это выражение намного ближе к N, а не к NlogK. Это несколько интуитивно, как в случае вопроса, даже после 10000 итераций (что очень мало по сравнению с миллиардом) вероятность того, что число будет вставлено в очередь, очень мало.
Если это задано в интервью, я думаю, что интервьюер, вероятно, хочет увидеть ваш процесс решения проблем, а не только ваши знания алгоритмов.
Описание довольно общее, поэтому, возможно, вы можете задать ему диапазон или значение этих чисел, чтобы проблема была понятной. Это может повлиять на интервьюера. Если, например, эти числа означают возраст людей в стране (например, в Китае), то это гораздо более простая проблема. С разумным предположением, что никто из живых не старше 200, вы можете использовать массив int размером 200 (возможно, 201), чтобы подсчитать количество людей с одинаковым возрастом всего за одну итерацию. Здесь индекс означает возраст. После этого кусок пирога, чтобы найти 100 наибольшее количество. Кстати, этот алго называется подсчет сортировки.
В любом случае, вопрос становится более конкретным и понятным для вас в интервью.
Вы можете перебирать числа, которые принимают O (n)
Всякий раз, когда вы находите значение больше текущего минимума, добавьте новое значение в круговую очередь с размером 100.
Мин этой круглой очереди - это ваше новое значение сравнения. Продолжайте добавлять в эту очередь. Если полный, извлеките минимум из очереди.
Я понял, что это помечено как "алгоритм", но выкинет некоторые другие параметры, так как, вероятно, также следует пометить "интервью".
Каков источник 1 миллиарда чисел? Если это база данных, тогда "выбрать значение из таблицы порядка по значению desc limit 100" будет делать работу довольно красиво - могут быть различия в диалектах.
Является ли это разовым или что-то, что будет повторяться? Если повторяется, как часто? Если это одноразовый, а данные находятся в файле, тогда "cat srcfile | сортировать (параметры по мере необходимости) | head -100 'заставит вас быстро делать продуктивную работу, которую вам платят, пока компьютер справляется с этой тривиальной работой.
Если это повторяется, вы бы посоветовали подобрать подходящий подход, чтобы получить начальный ответ и сохранить/кэшировать результаты, чтобы вы могли постоянно сообщать о 100 лучших.
Наконец, это соображение. Вы ищете работу на начальном уровне и собеседование с опытным менеджером или будущим сотрудником? Если это так, то вы можете бросить всевозможные подходы, описывающие относительные технические плюсы и минусы. Если вы ищете более управленческую работу, то подходите к ней, как менеджер, который будет связан с расходами на разработку и обслуживание решения, и скажите "спасибо вам большое" и уходите, если это интервьюер хочет сосредоточиться на мелочах CS, У него и вас вряд ли будет много возможностей для продвижения.
Лучше удачи в следующем интервью.
Вы можете использовать алгоритм быстрого выбора, чтобы найти номер в индексе (по заказу) [миллиард-101] а затем перебирать числа и находить числа, которые больше этого числа.
array={...the billion numbers...}
result[100];
pivot=QuickSelect(array,billion-101);//O(N)
for(i=0;i<billion;i++)//O(N)
if(array[i]>=pivot)
result.add(array[i]);
Этот алгоритм Время: 2 X O (N) = O (N) (Средняя производительность)
Второй вариант, например Thomas Jungblut:
Используйте Heap, когда куча MAX будет принимать O (N), то верхние 100 максимальных чисел будут в верхней части куча, все, что вам нужно, это вытащить их из кучи (100 XO (Log (N)).
Этот алгоритм Время: O (N) + 100 X O (Log (N)) = O (N)
Моей непосредственной реакцией на это было бы использование кучи, но есть способ использовать QuickSelect, не сохраняя при этом все входные значения под рукой.
Создайте массив размером 200 и заполните его с помощью первых 200 входных значений. Запустите QuickSelect и отбросьте низкий 100, оставив вам 100 свободных мест. Читайте в следующих 100 входных значениях и снова запустите QuickSelect. Продолжайте движение до тех пор, пока вы не запустите весь вход в партии по 100.
В конце вы получите 100 лучших значений. Для значений N вы используете QuickSelect примерно N/100 раз. Каждый Quickselect стоит примерно в 200 раз больше константы, поэтому общая стоимость в 2 раза превышает некоторую константу. Это выглядит линейным по размеру ввода для меня, независимо от размера параметра, который я нахожу в этом объяснении 100.
Несмотря на то, что другое решение quickselect было приостановлено, факт остается фактом: quickselect быстрее найдет решение, чем использование очереди размером 100. Quickselect имеет ожидаемое время работы 2n + o (n) с точки зрения сравнений. Очень простая реализация была бы
array = input array of length n
r = Quickselect(array,n-100)
result = array of length 100
for(i = 1 to n)
if(array[i]>r)
add array[i] to result
В среднем это займет 3n + o (n). Более того, его можно сделать более эффективным, используя тот факт, что quickselect оставит самые большие 100 элементов в массиве в 100 самых правых местах. Таким образом, время работы можно улучшить до 2n + o (n).
Существует проблема, что это ожидаемое время работы, а не худший случай, но с использованием подходящей стратегии выбора стержня (например, выбирайте 21 элемент случайным образом и выберите медиану этих 21 как ось вращения), затем количество сравнения могут быть гарантированы с большой вероятностью не более (2 + c) n для сколь угодно малой константы c.
Фактически, используя оптимизированную стратегию выборки (например, произвольные выборки элементов sqrt (n) и выбор 99-го процентиля), время работы можно свести до (1 + c) n + o (n) для сколь угодно малым c (предполагая, что K, количество элементов, подлежащих выбору, равно o (n)).
С другой стороны, использование очереди размером 100 потребует сравнений O (log (100) n), а база 2 базы 100 равна приблизительно 6,6.
Если мы рассмотрим эту проблему в более абстрактном смысле выбора самых больших K-элементов из массива размера N, где K = o (N), но оба K и N переходят в бесконечность, тогда время выполнения quickselect версия будет O (N), а версия очереди будет O (N log K), поэтому в этом смысле quickselect также асимптотически превосходит.
В комментариях было упомянуто, что решение очереди будет выполняться в ожидаемое время N + K log N на случайном входе. Разумеется, случайное входное предположение никогда не действует, если в нем не говорится об этом. Решение очереди может быть выполнено для перемещения массива в случайном порядке, но это приведет к дополнительной стоимости N вызовов генератору случайных чисел, а также перестановке всего входного массива или выделению нового массива длины N, содержащего случайные индексы.
Если проблема не позволяет перемещаться по элементам в исходном массиве, а затраты на выделение памяти высоки, поэтому дублирование массива не является вариантом, это другое дело. Но строго с точки зрения времени работы это лучшее решение.
возьмите первые 100 номеров миллиарда и отсортируйте их. теперь просто перебираем миллиард, если исходный номер выше наименьшего из 100, вставьте в порядок сортировки. То, что вы в конечном итоге, намного ближе к O (n) по размеру набора.
Два варианта:
(1) Куча (priorityQueue)
Сохраняйте мини-кучу размером 100. Переместите массив. Как только элемент будет меньше первого элемента в куче, замените его.
InSERT ELEMENT INTO HEAP: O（log100）
compare the first element: O(1)
There are n elements in the array, so the total would be O(nlog100), which is O(n)
(2) Модель уменьшения карты.
Это очень похоже на пример подсчета слов в hadoop. Работа с карточкой: подсчитывать каждый элемент частоты или время. Уменьшить: получить верхний элемент K.
Обычно я давал вербовщику два ответа. Дайте им все, что захочет. Конечно, преобразование карты с уменьшением кодировки было бы трудоемким, потому что вы должны были знать все точные параметры. Нет вреда, чтобы практиковать это. Удачи.
Очень простым решением было бы итерацию через массив 100 раз. Это O(n).
Каждый раз, когда вы вытягиваете наибольшее число (и меняете его значение на минимальное значение, чтобы вы не видели его на следующей итерации или отслеживали индексы предыдущих ответов (путем отслеживания индексов оригинала массив может иметь несколько одинакового числа)). После 100 итераций у вас есть 100 самых больших чисел.
Простейшим решением является сканирование большого массива миллиардов чисел и сохранение 100 самых больших значений, найденных до сих пор в небольшом буфере массива без какой-либо сортировки и запоминание наименьшего значения этого буфера. Сначала я подумал, что этот метод был предложен fordprefect, но в комментарии он сказал, что он предположил, что структура данных 100 номеров реализована как куча. Всякий раз, когда будет найден новый номер, который больше, чем минимум в буфере, перезаписывается новым найденным значением, и буфер снова ищет текущий минимум. Если числа в миллиардном массиве чисел распределены случайным образом большую часть времени, значение из большого массива сравнивается с минимумом малого массива и отбрасывается. Только для очень маленькой доли числа значение должно быть вставлено в малый массив. Таким образом, различие манипулирования структурой данных, содержащей небольшие числа, можно пренебречь. Для небольшого числа элементов трудно определить, действительно ли использование очереди приоритетов происходит быстрее, чем использование моего наивного подхода.
Я хочу оценить количество вставок в буфере массива небольших 100 элементов, когда проверяется массив элементов 10 ^ 9. Программа сканирует первые 1000 элементов этого большого массива и должна вставить не более 1000 элементов в буфере. Буфер содержит 100 элементов из 1000 проверенных элементов, то есть 0,1 элемента, отсканированного. Поэтому мы предполагаем, что вероятность того, что значение из большого массива больше текущего минимума буфера, составляет около 0,1. Такой элемент должен быть вставлен в буфер. Теперь программа сканирует следующие 10 ^ 4 элементов из большого массива. Поскольку минимум буфера увеличивается каждый раз, когда вставлен новый элемент. Мы подсчитали, что отношение элементов, превышающих наш текущий минимум, составляет около 0,1, и поэтому вставляются 0,1 * 10 ^ 4 = 1000 элементов. Фактически ожидаемое количество элементов, вставленных в буфер, будет меньше. После сканирования этих 10 ^ 4 элементов доля чисел в буфере будет составлять около 0,01 элементов, отсканированных до сих пор. Поэтому при сканировании следующих 10 ^ 5 чисел мы предполагаем, что в буфер будет вставлено не более 0,01 * 10 ^ 5 = 1000. Продолжая эту аргументацию, мы вставили около 7000 значений после сканирования 1000 + 10 ^ 4 + 10 ^ 5 +... + 10 ^ 9 ~ 10 ^ 9 элементов большого массива. Поэтому при сканировании массива с 10 ^ 9 элементами случайного размера мы ожидаем не более 10 ^ 4 (= 7000 округленных) вставок в буфере. После каждой вставки в буфер должен быть найден новый минимум. Если буфер представляет собой простой массив, нам нужно 100 сравнения, чтобы найти новый минимум. Если буфер представляет собой еще одну структуру данных (например, кучу), нам нужно по крайней мере 1 сравнение, чтобы найти минимум. Для сравнения элементов большого массива нам нужны 10 ^ 9 сравнения. Таким образом, во всех случаях нам нужно примерно 10 ~ 9 + 100 * 10 ^ 4 = 1,001 * 10 ^ 9 сравнений при использовании массива в качестве буфера и сравнений по меньшей мере 1.000 * 10 ^ 9 при использовании другого типа структуры данных (например, кучи), Таким образом, использование кучи дает только прирост 0,1%, если производительность определяется количеством сравнений. Но какова разница во времени выполнения между вставкой элемента в кучу 100 элементов и заменой элемента в массиве 100 элементов и его новым минимумом?
На теоретическом уровне: сколько сравнений необходимо для вставки в кучу. Я знаю, что это O (log (n)), но насколько велик постоянный фактор? I
На уровне машины: каково влияние кеширования и предсказания ветвления на время выполнения вставки кучи и линейный поиск в массиве.
На уровне реализации: какие дополнительные затраты скрыты в структуре данных кучи, предоставленной библиотекой или компилятором?
Я думаю, что это некоторые из вопросов, на которые нужно ответить, прежде чем попытаться оценить реальную разницу между производительностью 100-элементной кучи или массивом из 100 элементов. Поэтому было бы целесообразно провести эксперимент и измерить реальную производительность.
Вдохновленный ответом @ron teller, вот программа на основе barebones C, чтобы делать то, что вы хотите.
#include <stdlib.h>
#include <stdio.h>
#define TOTAL_NUMBERS 1000000000
#define N_TOP_NUMBERS 100
int
compare_function(const void *first, const void *second)
{
int a = *((int *) first);
int b = *((int *) second);
if (a > b){
return 1;
}
if (a < b){
return -1;
}
return 0;
}
int
main(int argc, char ** argv)
{
if(argc != 2){
printf("please supply a path to a binary file containing 1000000000"
"integers of this machine wordlength and endianness\n");
exit(1);
}
FILE * f = fopen(argv[1], "r");
if(!f){
exit(1);
}
int top100[N_TOP_NUMBERS] = {0};
int sorts = 0;
for (int i = 0; i < TOTAL_NUMBERS; i++){
int number;
int ok;
ok = fread(&number, sizeof(int), 1, f);
if(!ok){
printf("not enough numbers!\n");
break;
}
if(number > top100[0]){
sorts++;
top100[0] = number;
qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function);
}
}
printf("%d sorts made\n"
"the top 100 integers in %s are:\n",
sorts, argv[1] );
for (int i = 0; i < N_TOP_NUMBERS; i++){
printf("%d\n", top100[i]);
}
fclose(f);
exit(0);
}
На моей машине (ядро i3 с быстрым SSD) требуется 25 секунд и 1724 сортировки.
Я создал двоичный файл с dd if=/dev/urandom/ count=1000000000 bs=1 для этого прогона.
Очевидно, что есть проблемы с производительностью при чтении всего 4 байта за раз - с диска, но это, к примеру, сакэ. С положительной стороны требуется очень мало памяти.
Although in this question we should search for top 100 numbers, I will
generalize things and write x. Still, I will treat x as constant value.
Алгоритм Самые большие х элементов из n:
Я выберу возвращаемое значение LIST. Это набор элементов x (на мой взгляд, должен быть связан список)
Итак, что такое худший вариант?
x log (x) + (n-x) (log (x) +1) = nlog (x) + n - x
Итак, это O (n) время для наихудшего случая. +1 - проверка, если число больше наименьшего в списке. Ожидаемое время для среднего случая будет зависеть от математического распределения этих n элементов.
Возможные улучшения
Этот алгоритм может быть немного улучшен для наихудшего сценария, но IMHO (я не могу доказать это утверждение), что ухудшит среднее поведение. Асимптотическое поведение будет одинаковым.
Улучшение этого алгоритма будет заключаться в том, что мы не будем проверять, больше ли элемент, чем самый маленький. Для каждого элемента мы попытаемся вставить его, и если он будет меньше самого маленького, мы его не будем игнорировать. Хотя это звучит нелепо, если мы рассмотрим только худший сценарий, мы будем иметь
x log (x) + (n-x) log (x) = nlog (x)
операции.
В этом случае я не вижу никаких дальнейших улучшений. Но вы должны спросить себя: что делать, если я должен сделать это больше, чем log (n) раз и для разных x-es? Очевидно, мы будем сортировать этот массив в O (n log (n)) и принимать наш элемент x, когда мы в них нуждаемся.
На этот вопрос будет отвечать сложность N log (100) (вместо N log N) с одной строкой кода С++.
std::vector<int> myvector = ...; // Define your 1 billion numbers.
// Assumed integer just for concreteness
std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end());
Конечным ответом будет вектор, в котором первые 100 элементов гарантированно будут 100 самыми большими числами вашего массива, в то время как остальные элементы будут неупорядочены
С++ STL (стандартная библиотека) весьма удобна для таких проблем.
Примечание. Я не говорю, что это оптимальное решение, но оно спасло ваше интервью.
Простым решением будет использование очереди приоритетов, добавление первых 100 номеров в очередь и отслеживание наименьшего числа в очереди, а затем повторение других миллиардов чисел, и каждый раз, когда мы находим тот, который больше, чем наибольшее число в очереди приоритетов, мы удаляем наименьшее число, добавляем новый номер и снова отслеживаем наименьшее число в очереди.
Если бы цифры были в случайном порядке, это было бы красиво, потому что, когда мы перебираем миллиард случайных чисел, было бы очень редко, если бы следующее число было одним из 100 крупнейших до сих пор. Но цифры могут быть не случайными. Если массив уже был отсортирован в порядке возрастания, мы всегда добавляем элемент в очередь приоритетов.
Итак, мы выбираем сначала 100 000 случайных чисел из массива. Чтобы избежать случайного доступа, который может быть медленным, добавим 400 случайных групп из 250 последовательных номеров. С этим случайным выбором мы можем быть абсолютно уверены, что очень немногие из оставшихся номеров находятся в первой соте, поэтому время выполнения будет очень близко к времени простого цикла, сравнивая миллиард чисел с некоторым максимальным значением.
Поиск лучших 100 из миллиарда чисел лучше всего сделать с помощью min-heap из 100 элементов.
Сначала запустите мини-кучу с первыми 100 встречающимися цифрами. min-heap будет хранить наименьшее из первых 100 номеров в корне (вверху).
Теперь, когда вы идете по остальным номерам, сравните их только с корнем (наименьшим из 100).
Если встреченное новое число больше, чем корень из min-heap, замените корень на это число, иначе проигнорируйте его.
Как часть вставки нового числа в мини-куче наименьшее число в куче придет к вершине (корень).
Как только мы пройдем все числа, у нас будет самое большое 100 чисел в мини-куче.
Я написал простое решение на Python в случае, если кто-то заинтересован. Он использует модуль bisect и временный список возврата, который он сортирует. Это похоже на реализацию очереди приоритетов.
import bisect
def kLargest(A, k):
'''returns list of k largest integers in A'''
ret = []
for i, a in enumerate(A):
# For first k elements, simply construct sorted temp list
# It is treated similarly to a priority queue
if i < k:
bisect.insort(ret, a) # properly inserts a into sorted list ret
# Iterate over rest of array
# Replace and update return array when more optimal element is found
else:
if a > ret[0]:
del ret[0] # pop min element off queue
bisect.insort(ret, a) # properly inserts a into sorted list ret
return ret
Использование 100 000 000 элементов и наихудший ввод данных, который является отсортированным списком:
>>> from so import kLargest
>>> kLargest(range(100000000), 100)
[99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907,
99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915,
99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923,
99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931,
99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939,
99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947,
99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955,
99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963,
99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971,
99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979,
99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987,
99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995,
99999996, 99999997, 99999998, 99999999]
Потребовалось около 40 секунд, чтобы рассчитать это для 100 000 000 элементов, поэтому я боюсь сделать это за 1 миллиард. Если честно, я кормил его наихудшим входом (по иронии судьбы, массив, который уже отсортирован).
Я вижу много обсуждений O (N), поэтому я предлагаю что-то другое для упражнений.
Есть ли какая-либо известная информация о характере этих чисел? Если он случайный по своей природе, тогда не идти дальше и смотреть на другие ответы. Вы не получите лучших результатов, чем они.
Однако! Посмотрите, заполнил ли какой-либо список в списке список в определенном порядке. Являются ли они в четко определенной схеме, где вы можете с уверенностью узнать, что наибольшая величина чисел будет найдена в определенной области списка или на определенном интервале? Там может быть шаблон. Если это так, например, если они гарантированно находятся в каком-то нормальном распределении с характерным горбом посередине, всегда повторяют восходящие тенденции среди определенных подмножеств, имеют длительный всплеск в течение некоторого времени T в середине данных как, например, частота инсайдерской торговли или отказ оборудования, или, может быть, просто "всплеск" каждого N-го числа, как при анализе сил после катастрофы, вы можете уменьшить количество записей, которые вы должны проверить значительно.
Там есть еда для размышлений. Возможно, это поможет вам дать будущим интервьюерам продуманный ответ. Я знаю, что я был бы впечатлен, если бы кто-то задал мне такой вопрос в ответ на такую проблему - это скажет мне, что они думают об оптимизации. Просто признайте, что не всегда можно оптимизировать.
Time ~ O(100 * N)
Space ~ O(100 + N)
Создайте пустой список из 100 пустых слотов
Для каждого номера в списке ввода:
Если число меньше первого, пропустите
В противном случае замените его на это число
Затем нажимаем номер через смежный своп; пока он не станет меньше следующего
Вернуть список
Примечание:, если log(input-list.size) + c < 100, то оптимальным способом является сортировка списка ввода, а затем разделение первых 100 элементов.
Сложность - O (N)
Сначала создайте массив из 100 ints, инициализируя первый элемент этого массива как первый элемент из N значений, отслеживать индекс текущего элемента с другой переменной, называть его CurrentBig
Итерации, хотя значения N
if N[i] > M[CurrentBig] {
M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number)
CurrentBig++; ( go to the next position in the M array)
CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.)
M[CurrentBig]=N[i]; ( pick up the current value again to use it for the next Iteration of the N array)
}
когда закончите, напечатайте массив M из CurrentBig 100 раз по модулю 100:-) Для ученика: убедитесь, что последняя строка кода не превзошла действительные данные до того, как код выходит из
Другой алгоритм O (n) -
Алгоритм находит наибольшие 100 путем исключения
рассмотрим все миллионы чисел в их двоичном представлении. Начните с самого значительного бита. Поиск, если MSB равен 1, может быть выполнен с помощью умножения булевой операции с соответствующим числом. Если в этих миллионах насчитывается более 100 единиц, то остальные числа уничтожаются нулями. Теперь оставшиеся числа идут со следующим самым значительным битом. сохраняйте счетчик количества оставшихся номеров после устранения и продолжайте, пока это число больше 100.
Основная логическая операция может выполняться параллельно на графических процессорах
Я бы узнал, у кого было время положить миллиард чисел в массив и уволить его. Должен работать для правительства. По крайней мере, если у вас есть связанный список, вы можете вставить число в середину, не перемещая полмиллиарда, чтобы освободить место. Еще лучше Btree допускает двоичный поиск. Каждое сравнение устраняет половину вашего общего количества. Алгоритм хэширования позволит вам заполнить структуру данных, как шахматная доска, но не так хороша для разреженных данных. Поскольку лучше всего иметь массив решений из 100 целых чисел и отслеживать наименьшее количество в вашем массиве решений, чтобы вы могли его заменить, когда встретите большее количество в исходном массиве. Вам нужно будет посмотреть на каждый элемент исходного массива, предполагая, что он не сортируется для начала.
Вы можете сделать это в O(n) времени. Просто перебирайте список и отслеживайте 100 самых больших чисел, которые вы видели в любой момент, и минимальное значение в этой группе. Когда вы найдете новое число больше самого маленького из десяти, а затем замените его и обновите новое значение min 100 (может потребоваться постоянное время 100, чтобы определить это каждый раз, когда вы это делаете, но это не влияет на общий анализ).
Обратите внимание на esp. второй шаг может быть легко вычисляться параллельно! И это также будет эффективно, когда вам понадобится миллион самых больших элементов.
Это вопрос от Google или других гигантов индустрии. Может быть, следующий код - правильный ответ, ожидаемый вашим интервьюером. Стоимость времени и стоимость пространства зависят от максимального числа во входном массиве. Для ввода 32-битного ввода массива максимальная космическая стоимость составляет 4 * 125 Мбайт, стоимость времени - 5 * млрд.
public class TopNumber {
public static void main(String[] args) {
final int input[] = {2389,8922,3382,6982,5231,8934
,4322,7922,6892,5224,4829,3829
,6892,6872,4682,6723,8923,3492};
//One int(4 bytes) hold 32 = 2^5 value,
//About 4 * 125M Bytes
//int sort[] = new int[1 << (32 - 5)];
//Allocate small array for local test
int sort[] = new int[1000];
//Set all bit to 0
for(int index = 0; index < sort.length; index++){
sort[index] = 0;
}
for(int number : input){
sort[number >>> 5] |= (1 << (number % 32));
}
int topNum = 0;
outer:
for(int index = sort.length - 1; index >= 0; index--){
if(0 != sort[index]){
for(int bit = 31; bit >= 0; bit--){
if(0 != (sort[index] & (1 << bit))){
System.out.println((index << 5) + bit);
topNum++;
if(topNum >= 3){
break outer;
}
}
}
}
}
}
}
Я сделал свой собственный код, не уверен, что его "интервьюер" он смотрит
private static final int MAX=100;
PriorityQueue<Integer> queue = new PriorityQueue<>(MAX);
queue.add(array[0]);
for (int i=1;i<array.length;i++)
{
if(queue.peek()<array[i])
{
if(queue.size() >=MAX)
{
queue.poll();
}
queue.add(array[i]);
}
}
Возможные улучшения.
Если файл содержит 1 миллиард номеров, чтение его может быть очень длинным...
Чтобы улучшить эту работу, вы можете:
Я знаю, что это может быть похоронено, но вот моя идея изменения на radix MSD.
pseudo-code:
//billion is the array of 1 billion numbers
int[] billion = getMyBillionNumbers();
//this assumes these are 32-bit integers and we are using hex digits
int[][] mynums = int[8][16];
for number in billion
putInTop100Array(number)
function putInTop100Array(number){
//basically if we got past all the digits successfully
if(number == null)
return true;
msdIdx = getMsdIdx(number);
msd = getMsd(number);
//check if the idx above where we are is already full
if(mynums[msdIdx][msd+1] > 99) {
return false;
} else if(putInTop100Array(removeMSD(number)){
mynums[msdIdx][msd]++;
//we've found 100 digits here, no need to keep looking below where we are
if(mynums[msdIdx][msd] > 99){
for(int i = 0; i < mds; i++){
//making it 101 just so we can tell the difference
//between numbers where we actually found 101, and
//where we just set it
mynums[msdIdx][i] = 101;
}
}
return true;
}
return false;
}
Функция getMsdIdx(int num) вернет индекс самой значащей цифры (отличной от нуля). Функция getMsd(int num) вернет самую значительную цифру. Функция removeMSD(int num) удалит самую значимую цифру из числа и вернет номер (или вернет null, если после удаления самой значащей цифры ничего не осталось).
Как только это будет сделано, все, что осталось, пересекает mynums, чтобы захватить 100 лучших цифр. Это будет примерно так:
int[] nums = int[100];
int idx = 0;
for(int i = 7; i >= 0; i--){
int timesAdded = 0;
for(int j = 16; j >=0 && timesAdded < 100; j--){
for(int k = mynums[i][j]; k > 0; k--){
nums[idx] += j;
timesAdded++;
idx++;
}
}
}
Я должен отметить, что, хотя вышесказанное выглядит так, что оно имеет высокую временную сложность, оно будет действительно только около O(7*100).
Краткое объяснение того, что это делается: По существу, эта система пытается использовать каждую цифру в 2d-массиве на основе индекса цифры в номере и значения цифры. Он использует их в качестве индексов, чтобы отслеживать, сколько чисел этого значения было вставлено в массив. Когда 100 достигнуто, он закрывает все "нижние ветки".
Время этого алгоритма - это что-то вроде O(billion*log(16)*7)+O(100). Я мог ошибаться. Также очень вероятно, что это требует отладки, поскольку это довольно сложно, и я просто написал это с головы.
РЕДАКТИРОВАТЬ: Даунвиты без объяснения причин не помогают. Если вы считаете, что этот ответ неверен, пожалуйста, оставьте комментарий. Довольно уверен, что StackOverflow даже говорит вам об этом, когда вы делаете downvote.
Этот код предназначен для нахождения наибольших чисел N в Unsorted array.
#include <iostream>
using namespace std;
#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000
void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);
int main() {
int array[BILLION] // contains data
int i=0, temp;
int max[Array_Size];
findLargest(max,array);
cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";
for(i=0; i< Array_Size; i++)
cout<< max[i] << endl;
return 0;
}
void findLargest(int max[], int array[])
{
int i,temp,res;
for(int k=0; k< Array_Size; k++)
{
i=0;
while(i < BILLION)
{
for(int j=0; j< Array_Size ; j++)
{
temp = array[i];
res= checkDup(temp,max);
if(res == 0 && max[j] < temp)
max[j] = temp;
}
i++;
}
}
}
int checkDup(int temp, int max[])
{
for(int i=0; i<N_O_L_N_T_F; i++)
{
if(max[i] == temp)
return -1;
}
return 0;
}
Это может оказаться неэффективным, но выполнить эту работу.
Надеюсь, что это поможет
Управление отдельным списком - это дополнительная работа, и вам нужно перемещать вещи по всему списку каждый раз, когда вы находите другую замену. Просто выполните его и возьмите 100 лучших.