Scrivi un programma per trovare 100 numeri più grandi su un array di 1 miliardo di numeri

Recentemente ho partecipato a un’intervista in cui mi è stato chiesto “scrivi un programma per trovare 100 numeri più grandi su una serie di 1 miliardo di numeri”.

Ero solo in grado di fornire una soluzione di forza bruta che doveva ordinare l’array in O (nlogn) complessità temporale e prendere gli ultimi 100 numeri.

Arrays.sort(array); 

L’intervistatore stava cercando una complessità temporale migliore, ho provato un paio di altre soluzioni ma non gli ho risposto. Esiste una soluzione di complessità temporale migliore?

È ansible mantenere una coda di priorità dei 100 numeri più grandi, scorrere tra i miliardi di numeri, ogni volta che si incontra un numero maggiore del numero più piccolo nella coda (il capo della coda), rimuovere il capo della coda e aggiungere il nuovo numero in coda

EDIT: come notato da Dev, con una coda di priorità implementata con un heap, la complessità dell’inserimento in coda è O(logN)

Nel peggiore dei casi ottieni billion log 2 (100) che è meglio di billion log 2 (billion)

In generale, se hai bisogno dei maggiori numeri K da un insieme di numeri N, la complessità è O(NlogK) piuttosto che O(NlogN) , questo può essere molto significativo quando K è molto piccolo rispetto a N.

EDIT2:

Il tempo previsto per questo algoritmo è piuttosto interessante, poiché in ogni iterazione può o non può verificarsi un inserimento. La probabilità che il numero esimo venga inserito nella coda è la probabilità che una variabile casuale sia maggiore di almeno le variabili casuali iK dalla stessa distribuzione (i primi k numeri vengono automaticamente aggiunti alla coda). Possiamo usare le statistiche degli ordini (vedi link ) per calcolare questa probabilità. Ad esempio, si supponga che i numeri siano stati selezionati casualmente uniformsmente da {0, 1} , il valore atteso di (iK) il numero (fuori dai numeri) sia (ik)/i , e la possibilità che una variabile casuale sia più grande di questa il valore è 1-[(ik)/i] = k/i .

Pertanto, il numero previsto di inserimenti è:

inserisci la descrizione dell'immagine qui

E il tempo di esecuzione previsto può essere express come:

inserisci la descrizione dell'immagine qui

( k tempo per generare la coda con i primi k elementi, quindi nk confronti, e il numero atteso di inserimenti come descritto sopra, ognuno prende un log(k)/2 medio log(k)/2 volte)

Notare che quando N è molto grande rispetto a K , questa espressione è molto più vicina a n piuttosto che a NlogK . Questo è piuttosto intuitivo, come nel caso della domanda, anche dopo 10000 iterazioni (che è molto piccolo rispetto a un miliardo), la possibilità di un numero da inserire in coda è molto piccola.

Se questo viene chiesto in un’intervista, penso che l’intervistatore probabilmente voglia vedere il tuo processo di risoluzione dei problemi, non solo la tua conoscenza degli algoritmi.

La descrizione è abbastanza generale, quindi forse puoi chiedergli la portata o il significato di questi numeri per chiarire il problema. Questo potrebbe impressionare un intervistatore. Se, per esempio, questi numeri rappresentano l’età delle persone all’interno di un paese (ad esempio la Cina), allora è un problema molto più facile. Con la ragionevole supposizione che nessuno vivo sia più vecchio di 200, è ansible utilizzare un array int di dimensione 200 (forse 201) per contare il numero di persone con la stessa età in una sola iterazione. Qui l’indice indica l’età. Dopo questo è un pezzo di torta per trovare il 100 più grande numero. Tra l’altro questo algo è chiamato contare il tipo .

In ogni caso, rendere la domanda più specifica e più chiara fa bene a te in un’intervista.

Puoi scorrere i numeri che richiedono O (n)

Ogni volta che trovi un valore superiore al minimo corrente, aggiungi il nuovo valore a una coda circolare con dimensione 100.

Il minimo di quella coda circolare è il tuo nuovo valore di confronto. Continuate ad aggiungere a quella coda. Se pieno, estrai il minimo dalla coda.

Mi sono reso conto che questo è etichettato con ‘algoritmo’, ma eliminerò alcune altre opzioni, poiché probabilmente dovrebbe anche essere taggato ‘intervista’.

Qual è la fonte dei 1 miliardo di numeri? Se si tratta di un database, allora ‘selezionare il valore dall’ordine di una tabella in base al valore limite di 100’ farebbe abbastanza bene il lavoro – potrebbero esserci differenze di dialetto.

È una cosa unica o qualcosa che verrà ripetuto? Se ripetuto, con quale frequenza? Se è una tantum e i dati sono in un file, allora ‘cat srcfile | ordina (opzioni se necessario) | head -100 ‘ti farà fare rapidamente un lavoro produttivo che ti viene pagato mentre il computer gestisce questo banale lavoro.

Se si ripete, si consiglia di scegliere un approccio decente per ottenere la risposta iniziale e memorizzare / memorizzare i risultati in modo da poter continuamente riportare i primi 100.

Infine, c’è questa considerazione. Stai cercando un lavoro entry level e intervista con un geeky manager o futuro collaboratore? Se è così, allora puoi scartare tutti i tipi di approcci che descrivono i pro e i contro tecnici relativi. Se stai cercando un lavoro più manageriale, allora affrontalo come farebbe un manager, preoccupato dei costi di sviluppo e manutenzione della soluzione, e dì “grazie mille” e vattene se questo è l’intervistatore che vuole concentrarsi su CS . Lui e voi probabilmente non avreste molto potenziale di avanzamento lì.

Meglio fortuna per la prossima intervista.

È ansible utilizzare l’ algoritmo di selezione rapida per trovare il numero all’indice (dell’ordine) [miliardi-101] e quindi scorrere i numeri e trovare i numeri più grandi da quel numero.

 array={...the billion numbers...} result[100]; pivot=QuickSelect(array,billion-101);//O(N) for(i=0;i=pivot) result.add(array[i]); 

Questo algoritmo Tempo è: 2 XO (N) = O (N) (Prestazioni del caso medio)

La seconda opzione come suggerisce Thomas Jungblut è:

Usa la costruzione di heap che l’heap di MAX impiegherà O (N), quindi i primi 100 numeri massimi saranno nella parte superiore dell’Heap, tutto ciò che serve è estrarli dall’heap (100 XO (Log (N)).

Questo algoritmo Tempo è: O (N) + 100 XO (Log (N)) = O (N)

La mia reazione immediata per questo sarebbe utilizzare un heap, ma c’è modo di usare QuickSelect senza tenere a portata di mano tutti i valori di input in qualsiasi momento.

Creare un array di dimensioni 200 e riempirlo con i primi 200 valori di input. Esegui QuickSelect e scarta i 100 bassi, lasciandoti con 100 posti liberi. Leggere i successivi 100 valori di input ed eseguire nuovamente QuickSelect. Continua finché non hai eseguito l’intero input in gruppi di 100.

Alla fine hai i primi 100 valori. Per i valori N hai eseguito QuickSelect all’incirca N / 100 volte. Ogni Quickselect costa circa 200 volte una costante, quindi il costo totale è 2 N volte più costante. Questo mi sembra lineare nella dimensione dell’input, a prescindere dalla dimensione del parametro che sto cablando con 100 in questa spiegazione.

Sebbene l’altra soluzione quickselect sia stata downvoted, resta il fatto che quickselect troverà la soluzione più veloce rispetto all’utilizzo di una coda di dimensione 100. Quickselect ha un tempo di esecuzione previsto di 2n + o (n), in termini di confronti. Un’implementazione molto semplice sarebbe

 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 

Ciò richiederà in media 3n + o (n) confronti. Inoltre, può essere reso più efficiente utilizzando il fatto che quickselect lascerà i 100 elementi più grandi nell’array nelle 100 posizioni più a destra. Quindi, in effetti, il tempo di esecuzione può essere migliorato a 2n + o (n).

C’è il problema che questo è previsto per il tempo di esecuzione, e non il caso peggiore, ma usando una strategia di selezione pivot decente (ad esempio, scegliere 21 elementi a caso e scegliere la mediana di quelli 21 come pivot), quindi il numero di confronti può essere garantito con alta probabilità di essere al massimo (2 + c) n per una costante arbitrariamente piccola c.

Infatti, utilizzando una strategia di campionamento ottimizzata (ad esempio, campionando gli elementi sqrt (n) a caso e scegliendo il 99 ° percentile), il tempo di esecuzione può essere ridotto a (1 + c) n + o (n) per un numero arbitrariamente piccolo c (assumendo che K, il numero di elementi da selezionare è o (n)).

D’altra parte, l’uso di una coda di dimensione 100 richiede confronti O (log (100) n) e la base di log 2 di 100 è approssimativamente uguale a 6.6.

Se pensiamo a questo problema nel senso più astratto di scegliere i maggiori elementi K da una matrice di dimensione N, dove K = o (N) ma entrambi K e N vanno all’infinito, allora il tempo di esecuzione della versione di Quickselect sarà O (N) e la versione della coda sarà O (N log K), quindi in questo senso quickselect è anche asintoticamente superiore.

Nei commenti, è stato detto che la soluzione di coda verrà eseguita nel tempo previsto N + K log N su un input casuale. Ovviamente, l’ipotesi di input casuale non è mai valida a meno che la domanda non lo specifichi esplicitamente. La soluzione di coda può essere fatta per attraversare la matrice in un ordine casuale, ma ciò comporterà il costo aggiuntivo di N chiamate a un generatore di numeri casuali così come la permutazione dell’intero array di input o l’assegnazione di una nuova matrice di lunghezza N contenente il indici casuali.

Se il problema non ti consente di spostarti tra gli elementi dell’array originale e il costo dell’allocazione della memoria è elevato, quindi duplicare l’array non è un’opzione, è un’altra questione. Ma rigorosamente in termini di tempo di esecuzione, questa è la soluzione migliore.

prendi i primi 100 numeri del miliardo e ordinali. ora basta scorrere il miliardo, se il numero sorgente è superiore al più piccolo di 100, inserire in ordine. Ciò che si finisce è qualcosa di molto più vicino a O (n) rispetto alla dimensione del set.

Due opzioni:

(1) Heap (priorityQueue)

Mantenere un heap minimo con dimensione di 100. Attraversare l’array. Una volta che l’elemento è più piccolo del primo elemento nell’heap, sostituirlo.

 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) Modello di riduzione della mappa.

Questo è molto simile all’esempio di conteggio delle parole in hadoop. Lavoro mappa: conta la frequenza o l’ora di ogni elemento. Riduci: Ottieni il miglior elemento K.

Di solito, darei al reclutatore due risposte. Dai loro tutto ciò che vogliono. Ovviamente, la mappa riduce la codifica potrebbe essere laboriosa, perché è necessario conoscere ogni parametro esatto. Nessun danno per praticarlo. In bocca al lupo.

Una soluzione molto semplice sarebbe quella di scorrere l’array 100 volte. Che è O(n) .

Ogni volta che estrai il numero più grande (e ne cambi il valore al valore minimo, in modo da non vederlo nella successiva iterazione, o tieni traccia degli indici delle risposte precedenti (tenendo traccia degli indici che l’array originale può avere multiplo dello stesso numero)). Dopo 100 iterazioni, hai i 100 numeri più grandi.

Ispirato dalla risposta di @ron teller, ecco un programma C barebones per fare ciò che vuoi.

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

Sulla mia macchina (core i3 con un veloce SSD) ci vogliono 25 secondi e 1724 tipi. Ho generato un file binario con dd if=/dev/urandom/ count=1000000000 bs=1 per questa esecuzione.

Ovviamente, ci sono problemi di prestazioni con la lettura di soli 4 byte alla volta - dal disco, ma questo è ad esempio. Tra i lati positivi, è necessaria pochissima memoria.

La soluzione più semplice consiste nell’esplorare il grande numero di miliardi di array e contenere i 100 valori più grandi trovati finora in un piccolo buffer di array senza alcun ordinamento e ricordare il valore più piccolo di questo buffer. Per prima cosa ho pensato che questo metodo fosse proposto da fordprefect, ma in un commento ha affermato di aver ipotizzato che la struttura dei dati a 100 numeri fosse implementata come un heap. Ogni volta che viene rilevato un nuovo numero più grande, il minimo nel buffer viene sovrascritto dal nuovo valore trovato e il buffer viene nuovamente cercato per il minimo corrente. Se i numeri in miliardi di array di numeri vengono distribuiti casualmente il più delle volte il valore del grande array viene confrontato con il minimo dell’array piccolo e scartato. Solo per una piccolissima frazione di numero il valore deve essere inserito nel piccolo array. Quindi la differenza di manipolare la struttura dei dati tenendo i numeri piccoli può essere trascurata. Per un numero limitato di elementi è difficile determinare se l’utilizzo di una coda di priorità sia effettivamente più veloce rispetto all’utilizzo del mio approccio ingenuo.

Voglio stimare il numero di inserimenti nel piccolo buffer di 100 elementi quando viene scansionato l’array di elementi 10 ^ 9. Il programma analizza i primi 1000 elementi di questo grande array e deve inserire al massimo 1000 elementi nel buffer. Il buffer contiene 100 elementi dei 1000 elementi scansionati, ovvero 0,1 dell’elemento scansionato. Quindi supponiamo che la probabilità che un valore dall’array grande sia maggiore del minimo corrente del buffer è circa 0.1 Un tale elemento deve essere inserito nel buffer. Ora il programma esegue la scansione dei successivi 10 ^ 4 elementi dal grande array. Perché il minimo del buffer aumenta ogni volta che viene inserito un nuovo elemento. Abbiamo stimato che il rapporto tra gli elementi più grandi del nostro minimo corrente è di circa 0,1 e quindi ci sono 0,1 * 10 ^ 4 = 1000 elementi da inserire. In realtà il numero previsto di elementi che vengono inseriti nel buffer sarà più piccolo. Dopo la scansione di questa frazione di 10 ^ 4 elementi dei numeri nel buffer sarà circa 0,01 degli elementi scansionati finora. Quindi, quando si scandiscono i successivi numeri 10 ^ 5, si assume che non saranno inseriti più di 0,01 * 10 ^ 5 = 1000 nel buffer. Continuando questa argomentazione abbiamo inserito circa 7000 valori dopo aver scansionato 1000 + 10 ^ 4 + 10 ^ 5 + … + 10 ^ 9 ~ 10 ^ 9 elementi del grande array. Pertanto, quando si esegue la scansione di un array con 10 ^ 9 elementi di dimensione casuale, non ci aspettiamo più di 10 ^ 4 (= 7000 arrotondamenti per eccesso) nel buffer. Dopo ogni inserimento nel buffer deve essere trovato il nuovo minimo. Se il buffer è un array semplice, abbiamo bisogno di 100 confronti per trovare il nuovo minimo. Se il buffer è un’altra struttura di dati (come un heap) abbiamo bisogno di almeno 1 confronto per trovare il minimo. Per confrontare gli elementi del grande array abbiamo bisogno di confronti 10 ^ 9. Quindi, tutto sumto, occorrono circa 10 ^ 9 + 100 * 10 ^ 4 = 1.001 * 10 ^ 9 confronti quando si utilizza un array come buffer e almeno 1.000 * 10 ^ 9 confronti quando si utilizza un altro tipo di struttura dati (come un heap) . Quindi usare un heap porta solo un guadagno dello 0,1% se la performance è determinata dal numero di confronto. Ma qual è la differenza nel tempo di esecuzione tra l’inserimento di un elemento in un heap di 100 elementi e la sostituzione di un elemento in un array di 100 elementi e la ricerca del nuovo minimo?

  • A livello teorico: quanti confronti sono necessari per l’inserimento in un heap. So che è O (log (n)) ma quanto è grande il fattore costante? io

  • A livello macchina: qual è l’impatto della previsione della cache e della branca sul tempo di esecuzione di un inserto heap e una ricerca lineare in una matrice.

  • A livello di implementazione: quali costi aggiuntivi sono nascosti in una struttura dati heap fornita da una libreria o da un compilatore?

Penso che queste siano alcune delle domande a cui è necessario rispondere prima di poter tentare di stimare la reale differenza tra le prestazioni di un heap di 100 elementi o un array di 100 elementi. Quindi avrebbe senso fare un esperimento e misurare le prestazioni reali.

  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. 

Algoritmo I più grandi x elementi da n:

Chiamerò il valore di ritorno ELENCO . È un insieme di elementi x (secondo me dovrebbe essere una lista collegata)

  • I primi x elementi sono presi dal pool “come vengono” e ordinati in LIST (questo viene eseguito in tempo costante poiché x viene trattato come costante – O (x log (x)) tempo)
  • Per ogni elemento successivo verifichiamo se è più grande dell’elemento più piccolo in ELENCO e se scoppiamo il più piccolo e inseriamo l’elemento corrente in ELENCO. Dal momento che questo è ordinato, ogni elemento dovrebbe trovare il suo posto in tempo logaritmico (ricerca binaria) e dal momento che è ordinato l’inserimento dell’elenco non è un problema. Ogni fase viene eseguita anche in tempo costante (tempo O (log (x))).

Quindi, qual è lo scenario peggiore?

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

Quindi questo è il tempo O (n) per il caso peggiore. Il +1 è il controllo se il numero è maggiore di quello più piccolo in ELENCO. Il tempo previsto per il caso medio dipenderà dalla distribuzione matematica di questi elementi.

Possibili miglioramenti

Questo algoritmo può essere leggermente migliorato per lo scenario peggiore, ma IMHO (non posso dimostrare questa affermazione) che peggiorerà il comportamento medio. Il comportamento asintotico sarà lo stesso.

Il miglioramento di questo algoritmo sarà che non controlleremo se l’elemento è maggiore del più piccolo. Per ogni elemento cercheremo di inserirlo e se è più piccolo del più piccolo lo ignoreremo. Anche se ciò sembra assurdo se consideriamo solo lo scenario peggiore che avremo

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

operazioni.

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.

Però! 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.

Spero che questo ti aiuti

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.