risposta-alla-domanda-sullo-sviluppo-web-bd.com

Trova un numero intero non tra quattro miliardi di quelli dati

È una domanda di intervista:

Dato un file di input con quattro miliardi di interi, fornire un algoritmo per generare un intero che non è contenuto nel file. Supponi di avere 1 GB di memoria. Segui cosa faresti se hai solo 10 MB di memoria.

La mia analisi:

La dimensione del file è 4 × 109× 4 byte = 16 GB.

Possiamo fare l'ordinamento esterno, quindi possiamo conoscere l'intervallo degli interi. La mia domanda è qual è il modo migliore per rilevare il numero intero mancante nei set di interi grandi ordinati?

La mia comprensione (dopo aver letto tutte le risposte):

Supponendo che stiamo parlando di numeri interi a 32 bit. Ci sono 2 ^ 32 = 4 * 109 interi distinti.

Caso 1: abbiamo 1 GB = 1 * 109 * 8 bit = 8 miliardi di bit di memoria.

Soluzione: se usiamo un bit che rappresenta un intero distinto, è sufficiente. non abbiamo bisogno di sorta. Implementazione:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Caso 2: 10 MB di memoria = 10 * 106 * 8 bit = 80 milioni di bit

Soluzione: per tutti i possibili prefissi a 16 bit, ci sono 2 ^ 16 numeri interi = 65536, abbiamo bisogno di 2 ^ 16 * 4 * 8 = 2 milioni di bit. Abbiamo bisogno di costruire ben 65536 secchi. Per ogni bucket, abbiamo bisogno di 4 byte che contengono tutte le possibilità perché il caso peggiore è che tutti i 4 miliardi di interi appartengono allo stesso bucket.

  1. Costruisci il contatore di ogni bucket attraverso il primo passaggio attraverso il file.
  2. Scansiona i bucket, trova il primo che ha meno di 65536 hit.
  3. Costruisci nuovi bucket i cui prefissi a 16 bit sono disponibili nella fase 2 fino al secondo passaggio del file
  4. Analizza i bucket creati nel passaggio 3, trova il primo bucket che non ha successo.

Il codice è molto simile a quello precedente.

Conclusione: riduciamo la memoria aumentando il pass di file.


Un chiarimento per chi arriva in ritardo: la domanda, come richiesto, non dice che esista esattamente un intero che non è contenuto nel file - almeno non è così che la maggior parte delle persone lo interpretano. Molti commenti nel thread del commento sono su quella variazione dell'attività, comunque. Sfortunatamente il commento che ha introdotto al thread del commento è stato successivamente eliminato dal suo autore, quindi ora sembra che le risposte orfane ad esso abbiano semplicemente frainteso tutto. È molto confuso. Scusate.

675
SecureFish

Supponendo che "numero intero" significhi 32 bit : avere 10 MB di spazio è più che sufficiente per contare quanti numeri ci sono nel file di input con qualsiasi dato prefisso a 16 bit, per tutti i possibili prefissi a 16 bit in un passaggio attraverso il file di input. Almeno uno dei bucket sarà colpito meno di 2 ^ 16 volte. Fai un secondo passaggio per trovare quali dei possibili numeri in quel bucket sono già usati.

Se significa più di 32 bit, ma ancora di dimensioni limitate : fai come sopra, ignorando tutti i numeri di input che non rientrano nel (firmati o non firmati ; la tua scelta) gamma a 32 bit.

Se "intero" significa numero intero matematico : leggi l'input una volta e tieni traccia del il maggior numero lunghezza del numero più lungo che tu abbia mai visto. Quando hai finito, uscita il massimo più uno un numero casuale che ha un'altra cifra. (Uno dei numeri nel file può essere un bignum che impiega più di 10 MB per rappresentare esattamente, ma se l'input è un file, allora puoi almeno rappresentare la lunghezza di tutto ciò che si adatta a esso).

521
Henning Makholm

Gli algoritmi statisticamente informati risolvono questo problema utilizzando meno passaggi rispetto agli approcci deterministici.

Se sono consentiti interi molto grandi , allora è possibile generare un numero che può essere univoco in O(1) volta. Un intero pseudo-casuale a 128 bit come un GUID si scontrerà solo con uno dei quattro miliardi interi esistenti nel set in meno di uno di ogni 64 miliardi di miliardi di casi.

Se gli interi sono limitati a 32 bit , è possibile generare un numero che può essere univoco in un singolo passaggio utilizzando molto meno di 10 MB. Le probabilità che un intero a 32 bit pseudo-casuale si scontrino con uno dei 4 miliardi di interi esistenti è di circa il 93% (4e9/2 ^ 32). Le probabilità che mille interi pseudo-casuali entrino in collisione sono inferiori a uno su 12.000 miliardi di miliardi di miliardi (odds-of-one-collision ^ 1000). Quindi, se un programma mantiene una struttura di dati contenente 1000 candidati pseudo-casuali e itera attraverso gli interi noti, eliminando le corrispondenze dai candidati, è quasi certo di trovare almeno un numero intero che non è nel file.

194
Ben Haley

Una discussione dettagliata su questo problema è stata discussa in Jon Bentley "Colonna 1. Cracking the Oyster" Programming Pearls Addison-Wesley pp.3-10

Bentley discute diversi approcci, incluso l'ordinamento esterno, Merge Sort usando diversi file esterni, ecc., Ma il metodo migliore suggerito da Bentley è un algoritmo a passaggio singolo che usa campi di bit , che definisce umoristicamente "Wonder Sort" :) Venendo al problema, 4 miliardi di numeri possono essere rappresentati in:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

Il codice per implementare il bitset è semplice: (tratto dalla pagina delle soluzioni )

#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }
void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int  test(int i){ return a[i>>SHIFT] &   (1<<(i & MASK)); }

L'algoritmo di Bentley esegue un singolo passaggio sul file, setting il bit appropriato nell'array e quindi esamina questo array utilizzando la macro test sopra per trovare il numero mancante.

Se la memoria disponibile è inferiore a 0,466 GB, Bentley suggerisce un algoritmo k-pass che divide l'input in intervalli in base alla memoria disponibile. Per fare un esempio molto semplice, se era disponibile solo 1 byte (cioè la memoria per gestire 8 numeri) e l'intervallo era compreso tra 0 e 31, lo dividiamo in intervalli da 0 a 7, 8-15, 16-22 e così via e gestisci questo intervallo in ognuno dei passaggi 32/8 = 4.

HTH.

141
vine'th

Poiché il problema non specifica che dobbiamo trovare il numero più piccolo possibile che non è nel file, potremmo semplicemente generare un numero che è più lungo del file di input stesso. :)

117
Andris

Per la variante 1 GB RAM puoi usare un vettore bit. È necessario allocare 4 miliardi di bit == 500 MB di array di byte. Per ogni numero letto dall'input, imposta il bit corrispondente su "1". Una volta fatto, scorrere i bit, trovare il primo che è ancora '0'. Il suo indice è la risposta.

56
Itay Maman

Se sono interi a 32 bit (probabilmente dalla scelta di ~ 4 miliardi di numeri vicini a 2 ^ 32), il tuo elenco di 4 miliardi di numeri occuperà al massimo il 93% dei possibili numeri interi (4 * 10 ^ 9/(2 ^ 32)). Quindi se crei un array di bit di 2 ^ 32 bit con ogni bit inizializzato a zero (che occuperà 2 ^ 29 byte ~ 500 MB di RAM, ricorda un byte = 2 ^ 3 bit = 8 bit), leggi il tuo lista intera e per ogni int setta l'elemento bit-array corrispondente da 0 a 1; e quindi leggi il tuo array di bit e restituisci il primo bit che è ancora 0.

Nel caso in cui tu abbia meno RAM (~ 10 MB), questa soluzione deve essere leggermente modificata. 10 MB ~ 83886080 bit sono ancora sufficienti per fare un array di bit per tutti i numeri compresi tra 0 e 83886079. Quindi è possibile leggere l'elenco di ints; e registra solo # che sono compresi tra 0 e 83886079 nel tuo array di bit. Se i numeri sono distribuiti casualmente; con una probabilità schiacciante (differisce del 100% di circa 10 ^ -2592069 ) troverai un int mancante. Infatti, se si scelgono solo i numeri da 1 a 2048 (con solo 256 byte di RAM), si troverà comunque un numero mancante una percentuale schiacciante (99,9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999).

Ma diciamo invece di avere circa 4 miliardi di numeri; avevi qualcosa come 2 ^ 32 - 1 numeri e meno di 10 MB di RAM; quindi qualsiasi piccola gamma di int è solo una piccola possibilità di non contenere il numero.

Se ti è stato garantito che ogni int presente nell'elenco fosse univoco, potresti sommare i numeri e sottrarre la somma con una # mancante alla somma totale (1/2) (2 ^ 32) (2 ^ 32 - 1) = 9223372034707292160 per trovare l'int mancante. Tuttavia, se un int si verifica due volte questo metodo fallirà.

Tuttavia, puoi sempre dividere e conquistare. Un metodo ingenuo, sarebbe quello di leggere l'array e contare il numero di numeri che sono nel primo tempo (da 0 a 2 ^ 31-1) e nella seconda metà (2 ^ 31, 2 ^ 32). Quindi seleziona l'intervallo con meno numeri e ripeti la divisione dell'intervallo a metà. (Diciamo se ci fossero due meno numeri in (2 ^ 31, 2 ^ 32), quindi la tua prossima ricerca conterebbe i numeri nell'intervallo (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32). Continua a ripetere finché non trovi un intervallo con numeri zero e hai la tua risposta. Dovresti prendere O (lg N) ~ 32 letture attraverso l'array.

Quel metodo era inefficiente. Stiamo utilizzando solo due numeri interi in ogni passo (o circa 8 byte di RAM con un numero intero a 4 byte (32 bit)). Un metodo migliore sarebbe quello di dividere in sqrt (2 ^ 32) = 2 ^ 16 = 65536 bin, ognuno con 65536 numeri in un raccoglitore. Ogni bin richiede 4 byte per memorizzare il suo conteggio, quindi è necessario 2 ^ 18 byte = 256 kB. Quindi bin 0 è (da 0 a 65535 = 2 ^ 16-1), bin 1 è (2 ^ 16 = 65536 a 2 * 2 ^ 16-1 = 131071), bin 2 è (2 * 2 ^ 16 = 131072 a 3 * 2 ^ 16-1 = 196607). In Python avresti qualcosa di simile:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Leggi la lista dei ~ 4 miliardi interi; e conta quanti introi cadono in ciascuno dei bidoni 2 ^ 16 e trovi un incomplete_bin che non ha tutti i 65536 numeri. Poi leggi di nuovo la lista dei 4 miliardi interi; ma questa volta si noti solo quando gli interi si trovano in quell'intervallo; girando un po 'quando li trovi.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break
45
dr jimbob

Perché renderlo così complicato? Chiedi un numero intero non presente nel file?

In base alle regole specificate, l'unica cosa che devi memorizzare è il numero intero più grande che hai incontrato finora nel file. Una volta che l'intero file è stato letto, restituire un numero 1 maggiore di quello.

Non c'è il rischio di colpire maxint o altro, perché secondo le regole, non vi è alcuna restrizione alla dimensione del numero intero o al numero restituito dall'algoritmo.

37
Pete

Questo può essere risolto in pochissimo spazio usando una variante della ricerca binaria.

  1. Inizia con l'intervallo consentito di numeri, da 0 a 4294967295.

  2. Calcola il punto medio.

  3. Passare in rassegna il file, contando quanti numeri erano uguali, inferiori o superiori al valore del punto medio.

  4. Se nessun numero era uguale, hai finito. Il numero del punto centrale è la risposta.

  5. Altrimenti, scegli l'intervallo con il numero minore e ripeti dal passaggio 2 con questa nuova gamma.

Ciò richiederà fino a 32 scansioni lineari attraverso il file, ma userà solo pochi byte di memoria per la memorizzazione dell'intervallo e dei conteggi.

Questo è essenzialmente lo stesso di la soluzione di Henning , tranne che usa due bin anziché 16k.

31
hammar

Se manca un intero nell'intervallo [0, 2 ^ x - 1] quindi solo li guardiamo tutti insieme. Per esempio:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(So ​​che questo non risponde alla domanda esattamente , ma è una buona risposta a una domanda molto simile.)

24
rfrankel

Sulla base della formulazione attuale nella domanda originale, la soluzione più semplice è:

Trova il valore massimo nel file, quindi aggiungi 1 ad esso.

17
oosterwal

Potrebbero cercare di capire se avete sentito parlare di un filtro probabilistico che può determinare in modo molto efficiente assolutamente se un valore non fa parte di un grande insieme, (ma può determinare solo con alta probabilità che sia membro del set.)

16
Paul

Usa un BitSet. 4 miliardi di interi (supponendo fino a 2 ^ 32 numeri interi) impacchettati in un BitSet a 8 per byte è 2 ^ 32/2 ^ 3 = 2 ^ 29 = circa 0,5 Gb.

Per aggiungere ulteriori dettagli: ogni volta che si legge un numero, impostare il bit corrispondente in BitSet. Quindi, eseguire un passaggio su BitSet per trovare il primo numero che non è presente. In effetti, puoi farlo in modo altrettanto efficace selezionando ripetutamente un numero casuale e verificando se è presente.

In realtà BitSet.nextClearBit (0) ti dirà il primo bit non impostato.

Guardando l'API BitSet, sembra supportare solo 0..MAX_INT, quindi potresti aver bisogno di 2 BitSet - uno per i numeri + ve uno per -'ve numeri - ma i requisiti di memoria non cambiano.

14
dty

Se non ci sono limiti di dimensioni, il modo più rapido è prendere la lunghezza del file e generare la lunghezza del file + 1 numero di cifre casuali (o semplicemente "11111 ..." s). Vantaggio: non è nemmeno necessario leggere il file e si può ridurre a quasi zero l'uso della memoria. Svantaggio: stamperai miliardi di cifre.

Tuttavia, se l'unico fattore era ridurre al minimo l'utilizzo della memoria e nient'altro è importante, questa sarebbe la soluzione ottimale. Potrebbe anche darti un "peggior abuso delle regole".

12
vsz

Se assumiamo che l'intervallo di numeri sarà sempre 2 ^ n (una potenza pari a 2), quindi esclusivo o funzionerà (come mostrato da un altro poster). Per quanto riguarda il perché, proviamo:

La teoria

Dato qualsiasi intervallo di numeri interi basato su 0 che ha elementi 2^n con un elemento mancante, è possibile trovare quell'elemento mancante semplicemente xorizzando insieme i valori noti per ottenere il numero mancante.

La prova

Diamo un'occhiata a n = 2. Per n = 2, possiamo rappresentare 4 numeri interi univoci: 0, 1, 2, 3. Hanno un modello di bit di:

  • 0 - 00
  • 1 - 01
  • 2 - 10
  • 3 - 11

Ora, se guardiamo, ogni bit è impostato esattamente due volte. Pertanto, dal momento che è impostato un numero pari di volte, ed esclusivo - o dei numeri restituirà 0. Se manca un solo numero, l'esclusivo - o produrrà un numero che quando l'esclusivo numero con il numero mancante risulterà in 0. Di conseguenza, il numero mancante e il numero di derivazione esclusivo risultante sono esattamente gli stessi. Se rimuoviamo 2, il risultato xor sarà 10 (o 2).

Ora, diamo un'occhiata a n + 1. Chiamiamo il numero di volte in cui ogni bit è impostato in n, x e il numero di volte in cui ogni bit è impostato in n+1y. Il valore di y sarà uguale a y = x * 2 perché ci sono x elementi con n+1 bit impostato a 0 e x elementi con n+1 bit impostato a 1. E poiché 2x sarà sempre pari, n+1 avrà sempre ogni bit impostato su un valore pari numero di volte.

Pertanto, poiché n=2 funziona e n+1 funziona, il metodo xor funzionerà per tutti i valori di n>=2.

L'algoritmo per intervalli di base 0

Questo è abbastanza semplice. Utilizza 2 * n bit di memoria, quindi per qualsiasi intervallo <= 32, 2 numeri interi a 32 bit funzioneranno (ignorando qualsiasi memoria consumata dal descrittore di file). E rende un singolo passaggio del file.

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

L'algoritmo per intervalli arbitrari

Questo algoritmo funzionerà per intervalli di qualsiasi numero iniziale a qualsiasi numero finale, purché l'intervallo totale sia uguale a 2 ^ n ... Questo fondamentalmente ricalcola l'intervallo per avere il minimo a 0. Ma richiede 2 passaggi attraverso il file (il primo a prendere il minimo, il secondo a calcolare l'int mancante).

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

Gamme arbitrarie

Possiamo applicare questo metodo modificato a un insieme di intervalli arbitrari, poiché tutti gli intervalli supereranno una potenza di 2 ^ n almeno una volta. Funziona solo se c'è un singolo bit mancante. Richiede 2 passaggi di un file non ordinato, ma troverà il singolo numero mancante ogni volta:

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

Fondamentalmente, ricalcola l'intervallo intorno a 0. Quindi, conta il numero di valori non ordinati da aggiungere mentre calcola l'esclusivo-o. Quindi aggiunge 1 al conteggio dei valori non ordinati per occuparsi del valore mancante (conteggiare quello mancante). Quindi, mantieni il valore n per l'x, incrementato di 1 ogni volta finché n è una potenza di 2. Il risultato viene quindi ridistribuito alla base originale. Fatto.

Ecco l'algoritmo che ho provato in PHP (usando una matrice invece di un file, ma lo stesso concetto):

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

Alimentato in un array con qualsiasi intervallo di valori (ho provato anche i negativi) con uno all'interno di quell'intervallo che manca, ha trovato il valore corretto ogni volta.

Un altro approccio

Dal momento che possiamo usare l'ordinamento esterno, perché non limitarci a cercare una lacuna? Se supponiamo che il file sia stato ordinato prima dell'esecuzione di questo algoritmo:

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;
10
ircmaxell

Controlla la dimensione del file di input, quindi visualizza qualsiasi numero che è troppo grande per essere rappresentato da un file di tale dimensione. Questo può sembrare un trucco poco costoso, ma è una soluzione creativa per un problema di interviste, che elude in modo ordinato il problema della memoria, ed è tecnicamente O (n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Dovrebbe stampare 10 bitcount - 1 , che sarà sempre maggiore di bitcount. Tecnicamente, il numero che devi battere è bitcount - (4 * 109 - 1) , dato che sai che ci sono (4 miliardi - 1) altri numeri interi nel file, e anche con una compressione perfetta occuperanno almeno un bit ciascuno.

9
Justin Morgan
  • L'approccio più semplice è trovare il numero minimo nel file e restituire 1 in meno di quello. Questo utilizza O(1) memoria e O(n) tempo per un file di n numeri. Tuttavia, fallirà se l'intervallo di numeri è limitato, il che potrebbe rendere min-1 non-un-numero.

  • Il metodo semplice e diretto di usare una bitmap è già stato menzionato. Quel metodo usa O(n) tempo e spazio.

  • È stato anche menzionato un metodo a 2 passaggi con 2 ^ 16 contatori. Legge 2 * n numeri interi, quindi usa O(n) time e O(1) storage, ma non può gestire dataset con più di 2 ^ 16 numeri. Tuttavia, è facilmente estendibile a (ad esempio) 2 ^ 60 numeri interi a 64 bit eseguendo 4 pass invece di 2, e si adatta facilmente all'utilizzo di una memoria minuscola usando solo tanti contenitori adatti alla memoria e aumentando il numero di pass corrispondentemente, in quale caso il tempo di esecuzione non è più O(n) ma invece è O (n * log n).

  • Il metodo di XORing tutti i numeri insieme, menzionato finora da rfrankel e infine da ircmaxell risponde alla domanda posta in stackoverflow # 35185 , come ltn100 sottolineato. Utilizza il tempo di esecuzione O(1) e O(n). Se per il momento assumiamo numeri interi a 32 bit, XOR ha una probabilità del 7% di produrre un numero distinto. Motivazioni: dati i numeri distinti di ~ 4G insieme a XOR, e ca. 300M non nel file, il numero di bit impostati in ogni posizione di bit ha le stesse probabilità di essere pari o dispari. Quindi, i numeri 2 ^ 32 hanno la stessa probabilità di presentarsi come il risultato XOR, di cui il 93% è già in archivio. Nota che se i numeri nel file non sono tutti distinti, la probabilità di successo del metodo XOR aumenta.

8

Trick question, a meno che non sia stato citato in modo improprio. Basta leggere il file una volta per ottenere il numero intero massimo n e restituire n+1.

Naturalmente avresti bisogno di un piano di backup nel caso in cui n+1 causasse un overflow dei numeri interi.

8
Mark Ransom

Per qualche ragione, non appena ho letto questo problema ho pensato alla diagonalizzazione. Sto assumendo arbitrariamente grandi numeri interi.

Leggi il primo numero. Lasciala a sinistra con zero bit fino ad avere 4 miliardi di bit. Se il primo bit (di ordine elevato) è 0, output 1; else output 0. (Non è necessario il pad sinistro: si emette un 1 se non ci sono abbastanza bit nel numero.) Fate lo stesso con il secondo numero, tranne usare il secondo bit. Continua attraverso il file in questo modo. Emetterai un numero di 4 miliardi di bit un bit alla volta, e quel numero non sarà lo stesso di alcuno nel file. Dimostrazione: era uguale all'ennesimo numero, quindi sarebbero d'accordo sull'ennesimo bit, ma non per costruzione.

7

Solo per completezza, ecco un'altra soluzione molto semplice, che molto probabilmente impiegherà molto tempo per essere eseguita, ma utilizza pochissima memoria.

Lascia che tutti gli interi possibili siano l'intervallo da int_min a int_max e bool isNotInFile(integer) una funzione che restituisce true se il file non contiene un certo numero intero e falso altro (confrontando tale numero intero con ciascun numero intero nel file)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}
6
deg

È possibile utilizzare i bit di bit per contrassegnare se un numero intero è presente o meno.

Dopo aver attraversato l'intero file, eseguire la scansione di ciascun bit per determinare se il numero esiste o meno.

Supponendo che ogni numero intero sia a 32 bit, si adatteranno convenientemente a 1 GB di RAM se viene eseguita la segnalazione dei bit.

6
Shamim Hafiz

Striscia lo spazio bianco e i caratteri non numerici dal file e aggiungi 1. Il tuo file ora contiene un numero singolo non elencato nel file originale.

Da Reddit di Carbonetc.

6
Ashley

Per il vincolo di memoria da 10 MB:

  1. Converti il ​​numero nella sua rappresentazione binaria.
  2. Crea un albero binario dove left = 0 e right = 1.
  3. Inserisci ciascun numero nell'albero usando la sua rappresentazione binaria.
  4. Se un numero è già stato inserito, le foglie saranno già state create.

Al termine, basta prendere un percorso che non è stato creato prima per creare il numero richiesto.

4 miliardi di numeri = 2 ^ 32, ovvero 10 MB potrebbero non essere sufficienti.

EDIT

Un'ottimizzazione è possibile, se sono state create due estremità e hanno un genitore comune, allora possono essere rimosse e il genitore contrassegnato come non una soluzione. Questo taglia i rami e riduce la necessità di memoria.

EDIT II

Non è necessario costruire completamente l'albero. Hai solo bisogno di costruire rami profondi se i numeri sono simili. Se tagliamo anche i rami, allora questa soluzione potrebbe funzionare di fatto.

5

Risponderò alla versione da 1 GB:

Non ci sono abbastanza informazioni nella domanda, quindi dirò prima alcune ipotesi:

Il numero intero è 32 bit con intervallo -2.147.483.648 a 2.147.483.647.

Pseudo-codice:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}
5
BobTurbo

Finché stiamo facendo risposte creative, eccone un'altra.

Utilizzare il programma di ordinamento esterno per ordinare numericamente il file di input. Questo funzionerà per qualsiasi quantità di memoria che si può avere (utilizzerà la memorizzazione dei file, se necessario). Leggere il file ordinato e produrre il primo numero mancante.

4
Rhialto

Come ha detto in pratica Ryan, ordina il file e poi passa sopra i numeri interi e quando viene saltato un valore, ce l'hai :)

EDIT ai downvoters: l'OP ha detto che il file potrebbe essere ordinato in modo che questo sia un metodo valido.

3
ratchet freak

2128 * 1018 + 1 (che è (28)16 * 1018 + 1) - non può essere una risposta universale per oggi? Questo rappresenta un numero che non può essere tenuto in 16 file EB, che è la dimensione massima del file in qualsiasi file system corrente.

3

Bit Elimination

Un modo è quello di eliminare i bit, tuttavia questo potrebbe non produrre un risultato reale (è probabile che non lo farà). psuedocodarlo:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

Bit counts

Tieni traccia dei conteggi dei bit; e utilizzare i bit con le quantità minime per generare un valore. Ancora una volta questo non ha garanzia di generare un valore corretto.

Logica intervallo

Tieni traccia di un elenco di intervalli ordinati (ordinati per inizio). Un intervallo è definito dalla struttura:

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Passare attraverso ogni valore nel file e provare a rimuoverlo dall'intervallo corrente. Questo metodo non ha garanzie di memoria, ma dovrebbe fare abbastanza bene.

3

Penso che questo sia un problema risolto (vedi sopra), ma c'è un caso secondario interessante da tenere presente perché potrebbe essere chiesto:

Se ci sono esattamente 4.294.967.295 (2 ^ 32 - 1) numeri interi a 32 bit senza ripetizioni, e quindi ne manca solo uno, esiste una soluzione semplice.

Avvia un totale parziale a zero e per ogni numero intero nel file, aggiungi quel numero intero con overflow a 32 bit (in pratica, runningTotal = (runningTotal + nextInteger)% 4294967296). Una volta completato, aggiungi 4294967296/2 al totale parziale, sempre con overflow a 32 bit. Sottrai questo da 4294967296, e il risultato è il numero intero mancante.

Il problema "solo un numero intero mancante" è risolvibile con una sola esecuzione e solo 64 bit di RAM dedicati ai dati (32 per il totale parziale, 32 per leggere nel successivo intero).

Corollario: la specifica più generale è estremamente semplice da abbinare se non siamo interessati a quanti bit deve avere il risultato intero. Generiamo solo un numero abbastanza grande da non poter essere contenuto nel file che ci viene dato. Di nuovo, questo richiede RAM assolutamente minima. Vedi lo pseudocodice.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}
3
Syntaera

Se non si assume il vincolo a 32 bit, è sufficiente restituire un numero a 64 bit generato a caso (o 128 bit se si è pessimisti). La possibilità di collisione è 1 in 2^64/(4*10^9) = 4611686018.4 (circa 1 su 4 miliardi). Avresti ragione la maggior parte del tempo!

(Scherzando ... un po '.)

2
Peter Gibson

Non è necessario ordinarli, solo ripetutamente partizionare sottoinsiemi di essi.

Il primo passo è come il primo passaggio di un quicksort. Scegli uno degli interi, x, e usalo per fare un passaggio attraverso l'array per mettere tutti i valori inferiori a x alla sua sinistra e valori maggiori di x alla sua destra. Trova quale lato di x ha il maggior numero di slot disponibili (numeri interi non nella lista). Questo è facilmente calcolabile confrontando il valore di x con la sua posizione. Quindi ripeti la partizione nella sotto-lista su quel lato di x. Quindi ripetere la partizione nell'elenco sub-sub con il maggior numero di numeri interi disponibili, ecc. Il numero totale di confronti per scendere a un intervallo vuoto dovrebbe essere di circa 4 miliardi, dare o avere.

1
Lucas Membrane

Forse mi manca completamente il punto di questa domanda, ma vuoi trovare un intero mancante da un file ordinato di interi?

Uhh ... davvero? Pensiamo a come sarebbe un file di questo tipo:

1 2 3 4 5 6 ... primo numero mancante ... ecc.

La soluzione a questo problema sembra banale.

1
hacksoncode

È possibile velocizzare la ricerca degli interi mancanti dopo aver letto quelli esistenti memorizzando intervalli di numeri interi non visitati in una struttura ad albero.

Si inizia memorizzando [0..4294967295] e ogni volta che si legge un numero intero si giunge all'intervallo in cui si trova, eliminando un intervallo quando diventa vuoto. Alla fine hai l'esatto insieme di numeri interi che mancano negli intervalli. Quindi se vedi 5 come primo numero, avresti [0..4] e [6..4294967295].

Questo è molto più lento della marcatura dei bit, quindi sarebbe solo una soluzione per il caso da 10 MB a condizione di poter archiviare i livelli inferiori dell'albero nei file.

Un modo per memorizzare un albero di questo tipo sarebbe un albero B con l'inizio dell'intervallo come chiave e la fine dell'intervallo come valore. Il peggior caso di utilizzo sarebbe quando si ottengono tutti gli interi dispari o pari che significherebbe memorizzare 2 ^ 31 valori o decine di GB per l'albero ... Ahi. Il caso migliore è un file ordinato in cui si utilizzano solo alcuni numeri interi per l'intero albero.

Quindi non proprio la risposta corretta ma ho pensato di menzionare questo modo di farlo. Suppongo che fallirei l'intervista ;-)

1
w00t

Dato un file di input con quattro miliardi di interi, fornire un algoritmo per generare un intero che non è contenuto nel file. Supponi di avere 1 GiB memoria. Segui cosa faresti se hai solo 10 MiB di memoria.

La dimensione del file è 4 * 109 * 4 byte = 16 GiB

In caso di numero intero senza segno a 32 bit

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

La mia soluzione proposta: C++ senza controllo degli errori

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

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

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

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

    unsigned int num = 0;

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

    infile.close();

    // print missing numbers

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

    return 0;
}

Complessità

Space ~ 2^32 bits = 2^29 Bytes = 2^19 KB = 2^9 MB = 1/2 GB

Time ~ Single Pass

Completeness ~ Yes
1
Khaled.K

Vecchia domanda, ma mi chiedo dei requisiti "non funzionali". Secondo me dovrebbe esserci un indizio dato - se questa domanda è stata posta in un altro posto che in un libro che poi passa a discutere tutte le possibilità con pro e contro. Abbastanza spesso sembra essere un problema nelle interviste di lavoro, lasciandomi perplesso perché non può esserci una risposta definitiva data senza conoscere i requisiti soft, cioè "deve essere molto veloce per cercare numeri mancanti, perché è usato x volte in un secondo ".

Penso che una simile domanda possa essere una risposta ragionevole.

  • Unirei tutti i numeri in un nuovo file, usando 4 byte per int. Ovviamente questo sarà lento da fare in un primo momento. Ma può essere fatto con una piccola quantità di memoria (non è necessario tenere tutto in RAM)
  • Utilizzare la ricerca binaria per verificare se il numero esiste nel file preordinato. Poiché restiamo 4 byte per valore, questo non è un problema

svantaggi:

  • Dimensione del file
  • Slow first sort - ma solo una volta

vantaggi:

  • molto veloce da cercare

Quindi, ancora una bella domanda per un libro. Ma penso che sia una domanda strana quando si chiede una soluzione migliore, quando il problema da risolvere non è completamente noto.

0
benjist

Potrei leggerlo troppo da vicino, ma le domande dicono "genera un numero intero che non è contenuto nel file". Vorrei solo ordinare la lista e aggiungere 1 alla voce massima. Bam, un numero intero che non è contenuto nel file.

0
Sib

Ho trovato il seguente algoritmo.

La mia idea: passare tutto il file di interi una volta e per ogni posizione di bit contare i suoi 0 e 1. La quantità di 0 e 1 deve essere 2 ^ (numOfBits)/2, quindi, se l'importo è inferiore al previsto, possiamo usarlo del nostro numero risultante.

Ad esempio, supponiamo che il numero intero sia 32 bit, quindi è necessario

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

Per ogni numero dobbiamo ripetere 32 bit e aumentare il valore di 0 o 1:

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

Infine, dopo che il file è stato elaborato:

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

NOTA: in alcune lingue (es. Java) 1 << 31 è un numero negativo, quindi, (lungo) 1 << 31 è il modo giusto per farlo

0
Timofey