Напишите программу, чтобы найти 100 самых больших чисел из массива из 1 миллиарда чисел

Недавно я посетил интервью, на котором меня попросили «написать программу, чтобы найти 100 крупнейших номеров из массива в 1 миллиард номеров».

Я мог только дать решение грубой силы, которое должно было сортировать массив в сложности времени O (nlogn) и принимать последние 100 чисел.

Arrays.sort(array); 

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

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

EDIT: как отметил Dev, с очередью приоритетов, реализованной с кучей, сложность вставки в очередь равна O(logN)

В худшем случае вы получаете billion log 2 (100) что лучше billion log 2 (billion)

В общем случае, если вам нужны самые большие K-номера из набора из N чисел, сложность O(NlogK) а не O(NlogN) , это может быть очень значительным, когда K очень мало по сравнению с N.

EDIT2:

Ожидаемое время этого алгоритма довольно интересно, так как на каждой итерации может произойти или не произойти вставка. Вероятность того, что i-й номер будет вставлен в очередь, – вероятность того, что случайная величина будет больше, чем, по меньшей мере, случайные переменные iK из одного и того же распределения (первые числа k автоматически добавляются в очередь). Мы можем использовать статистику заказа (см. Ссылку ) для расчета этой вероятности. Например, допустим, что числа были случайным образом выбраны из {0, 1} , ожидаемое значение (iK) -го числа (из i чисел) равно (ik)/i , а вероятность случайной величины больше этой значение равно 1-[(ik)/i] = k/i .

Таким образом, ожидаемое количество вставок:

введите описание изображения здесь

И ожидаемое время работы может быть выражено как:

введите описание изображения здесь

( k время для генерации очереди с первыми k элементами, затем сравнения nk и ожидаемое количество вставок, как описано выше, каждый из них принимает среднее значение log(k)/2 )

Заметим, что когда N очень велико по сравнению с K , это выражение намного ближе к n , чем NlogK . Это несколько интуитивно, как в случае вопроса, даже после 10000 итераций (что очень мало по сравнению с миллиардом) вероятность того, что число будет вставлено в очередь, очень мало.

Если это задано в интервью, я думаю, что интервьюер, вероятно, хочет увидеть ваш процесс решения проблем, а не только ваши знания алгоритмов.

Описание довольно общее, поэтому, возможно, вы можете задать ему диапазон или значение этих чисел, чтобы устранить проблему. Это может повлиять на интервьюера. Если, например, эти цифры означают возраст людей в стране (например, в Китае), то это гораздо более простая проблема. С разумным предположением, что никто из живых не старше 200, вы можете использовать массив int размером 200 (возможно, 201), чтобы подсчитать количество людей с одинаковым возрастом всего за одну итерацию. Здесь индекс означает возраст. После этого это кусок пирога, чтобы найти 100 самых больших чисел. Кстати, этот алго называется счетной сортировкой .

Во всяком случае, вопрос становится более конкретным и понятным для вас в интервью.

Вы можете перебирать числа, которые принимают O (n)

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

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

Я понял, что это помечено «алгоритмом», но выкинет некоторые другие варианты, так как, вероятно, также следует пометить «интервью».

Каков источник 1 миллиарда чисел? Если это firebase database, то «выбрать значение из таблицы порядка по значению 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=pivot) result.add(array[i]); выбор array={...the billion numbers...} result[100]; pivot=QuickSelect(array,billion-101);//O(N) for(i=0;i=pivot) result.add(array[i]); 

Этот алгоритм Время: 2 XO (N) = O (N) (Средняя производительность)

Второй вариант, например, Thomas Jungblut , заключается в следующем:

Использование кучи, создающего кучу MAX, примет O (N), тогда верхние 100 максимальных чисел будут в верхней части кучи, все, что вам нужно, – это вытащить их из кучи (100 XO (Log (N)).

Этот алгоритм Время: O (N) + 100 XO (Log (N)) = O (N)

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

Создайте массив размером 200 и заполните его с помощью первых 200 входных значений. Запустите QuickSelect и отбросьте низкий 100, оставив вам 100 свободных мест. Читайте в следующих 100 входных значениях и снова запустите QuickSelect. Продолжайте движение до тех пор, пока вы не запустите весь вход в партии по 100 штук.

В конце вы получите 100 лучших значений. Для значений N вы используете QuickSelect примерно N / 100 раз. Каждый Quickselect стоит примерно в 200 раз больше константы, поэтому общая стоимость в 2 раза превышает некоторую константу. Это выглядит линейным по размеру ввода для меня, независимо от размера параметра, который я нахожу в этом объяснении.

Хотя другое решение 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).

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

Фактически, используя оптимизированную страtagsю выборки (например, произвольные выборки элементов 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 самых больших чисел.

Вдохновленный ответом @ron teller, здесь есть программа на основе barebones C, чтобы делать то, что вы хотите.

 #include  #include  #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's 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); } 

На моей машине (kernel i3 с быстрым SSD) требуется 25 секунд и 1724 сортировки. Я сгенерировал двоичный файл с dd if=/dev/urandom/ count=1000000000 bs=1 для этого прогона.

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

Простейшим решением является сканирование большого массива миллиардов чисел и сохранение 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)), но насколько велик постоянный фактор? я

  • На уровне машины: каково влияние кэширования и outlookирования ветвления на время выполнения кучи вставки и линейный поиск в массиве.

  • На уровне реализации: Какие дополнительные затраты скрыты в структуре данных кучи, предоставленной библиотекой или компилятором?

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

  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 берутся из пула «по мере их поступления» и сортируются в LIST (это выполняется в постоянное время, так как x рассматривается как постоянное – время O (x log (x)))
  • Для каждого следующего элемента мы проверяем, является ли он больше, чем самый маленький элемент в LIST, и если мы вытаскиваем самый маленький и вставляем текущий элемент в LIST. Поскольку это упорядоченный список, каждый элемент должен найти свое место в логарифмическом времени (двоичный поиск), а так как это упорядоченная вставка списка, это не проблема. Каждый шаг также выполняется в постоянное время (время O (log (x))).

Итак, что такое худший вариант?

x log (x) + (nx) (log (x) +1) = nlog (x) + n – x

Таким образом, время O (n) для наихудшего случая. +1 – проверка, если число больше наименьшего в списке. Ожидаемое время для среднего случая будет зависеть от математического распределения этих n элементов.

Возможные улучшения

Этот алгоритм может быть немного улучшен для наихудшего сценария, но IMHO (я не могу доказать это утверждение), что ухудшит среднее поведение. Асимптотическое поведение будет одинаковым.

Улучшение этого алгоритма будет заключаться в том, что мы не будем проверять, больше ли элемент, чем самый маленький. Для каждого элемента мы попытаемся вставить его, и если он будет меньше самого маленького, мы его не будем игнорировать. Although that sounds preposterous if we regard only the worst case scenario we will have

x log(x) + (nx)log(x) = nlog(x)

operations.

For this use case I don’t see any further improvements. Yet you must ask yourself – what if I have to do this more than log(n) times and for different x-es? Obviously we would sort that array in O(n log(n)) and take our x element whenever we need them.

This question would be answered with N log(100) complexity (instead of N log N) with just one line of C++ code.

  std::vector myvector = ...; // Define your 1 billion numbers. // Assumed integer just for concreteness std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end()); 

The final answer would be a vector where the first 100 elements are guaranteed to be the 100 biggest numbers of you array while the remaining elements are unordered

C++ STL (standard library) is quite handy for this kind of problems.

Note: I am not saying that this is the optimal solution, but it would have saved your interview.

The simple solution would be using a priority queue, adding the first 100 numbers to the queue and keeping track of the smallest number in the queue, then iterating through the other billion numbers, and each time we find one that is larger than the largest number in the priority queue, we remove the smallest number, add the new number, and again keep track of the smallest number in the queue.

If the numbers were in random order, this would work beautiful because as we iterate through a billion random numbers, it would be very rare that the next number is among the 100 largest so far. But the numbers might not be random. If the array was already sorted in ascending order then we would always insert an element to the priority queue.

So we pick say 100,000 random numbers from the array first. To avoid random access which might be slow, we add say 400 random groups of 250 consecutive numbers. With that random selection, we can be quite sure that very few of the remaining numbers are in the top hundred, so the execution time will be very close to that of a simple loop comparing a billion numbers to some maximum value.

Finding the top 100 out of a billion numbers is best done using min-heap of 100 elements.

First prime the min-heap with the first 100 numbers encountered. min-heap will store the smallest of the first 100 numbers at the root (top).

Now as you go along the rest of the numbers only compare them with the root (smallest of the 100).

If the new number encountered is larger than root of min-heap replace the root with that number otherwise ignore it.

As part of the insertion of the new number in min-heap the smallest number in the heap will come to the top (root).

Once we have gone through all the numbers we will have the largest 100 numbers in the min-heap.

I have written up a simple solution in Python in case anyone is interested. It uses the bisect module and a temporary return list which it keeps sorted. This is similar to a priority queue implementation.

 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 

Usage with 100,000,000 elements and worst-case input which is a sorted list:

 >>> 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] 

It took about 40 seconds to calculate this for 100,000,000 elements so I’m scared to do it for 1 billion. To be fair though, I was feeding it the worst-case input (ironically an array that is already sorted).

I see a lot of O(N) discussions, so I propose something different just for the thought exercise.

Is there any known information about the nature of these numbers? If it’s random in nature, then go no further and look at the other answers. You won’t get any better results than they do.

However! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal distribution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a “spike” every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

There’s some food for thought anyway. Maybe this will help you give future interviewers a thoughtful answer. I know I would be impressed if someone asked me such a question in response to a problem like this – it would tell me that they are thinking of optimization. Just recognize that there may not always be a possibility to optimize.

 Time ~ O(100 * N) Space ~ O(100 + N) 
  1. Create an empty list of 100 empty slot

  2. For every number in input-list:

    • If the number is smaller than the first one, skip

    • Otherwise replace it with this number

    • Then, push the number through adjacent swap; until it’s smaller than the next one

  3. Return the list


Note: if the log(input-list.size) + c < 100 , then the optimal way is to sort the input-list, then split first 100 items.

THe complexity is O(N)

First create an array of 100 ints initialiaze the first element of this array as the first element of the N values, keep track of the index of the current element with a another variable, call it CurrentBig

Iterate though the N values

 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) } 

when done , print the M array from CurrentBig 100 times modulo 100 🙂 For the student: make sure that the last line of the code does not trump valid data right before the code exits

Another O(n) algorithm –

The algorithm finds the largest 100 by elimination

consider all the million numbers in their binary representation. Start from the most significant bit. Finding if the MSB is 1 can be a done by a boolean operation multiplication with an appropriate number. If there are more than 100 1’s in these million eliminate the other numbers with zeros. Now of the remaining numbers proceed with the next most significant bit. keep a count of the number of remaining numbers after elimination and proceed as long as this number is greater than 100.

The major boolean operation can be an parallely done on GPUs

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.

You can do it in O(n) time. Just iterate through the list and keep track of the 100 biggest numbers you’ve seen at any given point and the minimum value in that group. When you find a new number bigger the smallest of your ten, then replace it and update your new min value of the 100 (may take a constant time of 100 to determine this each time you do it, but this does not affect the overall analysis).

  1. Use nth-element to get the 100’th element O(n)
  2. Iterate the second time but only once and output every element that is greater than this specific element.

Please note esp. the second step might be easy to compute in parallel! And it will also be efficiently when you need a million biggest elements.

It’s a question from Google or some else industry giants.Maybe the following code is the right answer expected by your interviewer. The time cost and space cost depend on the maximum number in the input array.For 32-Bit int array input, The maximum space cost is 4 * 125M Bytes, Time cost is 5 * Billion.

 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; } } } } } } } 

i did my own code,not sure if its what the “interviewer” it’s looking

 private static final int MAX=100; PriorityQueue queue = new PriorityQueue<>(MAX); queue.add(array[0]); for (int i=1;i=MAX) { queue.poll(); } queue.add(array[i]); } } 

Possible improvements.

If the file contains 1 billions number, reading it could be really long…

To improve this working you can :

  • Split the file into n parts, Create n threads, make n threads look each for the 100 biggest numbers in their part of the file (using the priority queue), and finally get the 100 biggest numbers of all threads output.
  • Use a cluster to do a such task, with a solution like hadoop. Here you can split the file even more and have the output quicker for a 1 billion (or a 10^12) numbers file.

This code is for finding N largest numbers in an Unsorted array .

 #include  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 

This might not be the efficient one but gets the job done.

Надеюсь это поможет

I know this might get buried, but here is my idea for a variation on a 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; } 

The function getMsdIdx(int num) would return the index of the most significant digit (non-zero). The function getMsd(int num) would return the most significant digit. The funciton removeMSD(int num) would remove the most significant digit from a number and return the number (or return null if there was nothing left after removing the most significant digit).

Once this is done, all that is left is traversing mynums to grab the top 100 digits. This would be something like:

 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++; } } } 

I should note that although the above looks like it has high time complexity, it will really only be around O(7*100) .

A quick explanation of what this is trying to do: Essentially this system is trying to use every digit in a 2d-array based upon the index of the digit in the number, and the digit's value. It uses these as indexes to keep track of how many numbers of that value have been inserted in the array. When 100 has been reached, it closes off all "lower branches".

The time of this algorithm is something like O(billion*log(16)*7)+O(100) . I could be wrong about that. Also it is very likely this needs debugging as it is kinda complex and I just wrote it off the top of my head.

EDIT: Downvotes without explanation are not helpful. If you think this answer is incorrect, please leave a comment why. Pretty sure that StackOverflow even tells you to do so when you downvote.

Managing a separate list is extra work and you have to move things around the whole list every time you find another replacement. Just qsort it and take the top 100.

  • Как сортировать список по свойству в объекте
  • Какова цель фаз перетасовки и сортировки в редукторе в Программе сокращения карты?
  • Пользовательский вид mysql
  • массив java Arrays.sort 2d
  • Перечислить сложную сортировку
  • Сортировка ArrayList объектов с использованием пользовательского порядка сортировки
  • MongoDB сортирует документы по элементам массива
  • Сортировка NSArray пользовательских объектов по их свойствам NSDate
  • Как сортировать по двум полям в Java?
  • Буквенно-цифровая сортировка с использованием LINQ
  • Существует ли алгоритм сортировки по целому числу O (n)?
  • Давайте будем гением компьютера.